SP6 redis布隆过滤器
描述
请按照下列指示实现一个redis布隆过滤器:
① 首先构造n个哈希方法,每个哈希方法字符串到key值映射公式为:key = ( i * key + s) % mod,其中key从0开始,s为字符串中每个字符的ASCII值,i为这是第几个哈希方法(从1开始),mod为每个方法对应的随机数,取值在10000~20000之间。
② 实现add函数,向布隆过滤器中添加一个字符串:使用每个构造的哈希方法得到n个key值,相应key值标记。
③ 实现contains函数,检查给定字符串是否在布隆过滤器中:检查是否每个哈希方法的key值都有标记。
输入字符串数组s1表示先将这些字符串加入到布隆过滤器中,再检验字符串数组s2中的字符串是否在布隆过滤器中。
示例1
输入:
["NiuNiu"],["Niu", "NiuN", "NiuNiu", "niu"],3
返回值:
[0,0,1,0]
说明:
0表示不在布隆过滤器中,1表示在布隆过滤器中
题解
题目说的比较模糊,让人不知道如何入手。可以先看一下布隆过滤器的原理,然后再入手做题。
思路:
- 使用n个hash函数为每个string生成key,然后将key值对应的bit设置为1
- 遍历第二个输入数组,使用相同的hash函数为其生成对应的key,然后判断对应的bit是否为true,只要有一个不为true就说明该字符不存在
#include <bits/stdc++.h>
using namespace std;
long generate_key(int i, long mod, const std::string &str)
{
long key = 0;
for (auto s : str)
{
key = (i * key + s) % mod;
}
return key;
}
vector<int> BloomFilter(vector<string> &s1, vector<string> &s2, int n)
{
std::bitset<10000> bs;
long mod = 10000;
for (auto &s : s1)
{
for (int i = 1; i <= n; ++i)
{
long key = generate_key(i, mod, s);
bs.set(key);
}
}
std::vector<int> ans;
for (auto &s : s2)
{
int flag = 1;
for (int i = 1; i <= n; ++i)
{
long key = generate_key(i, mod, s);
if (!bs[key])
{
flag = 0;
break;
}
}
ans.push_back(flag);
}
return ans;
}