我要评论
目录
一，布隆过滤器
1.布隆过滤器的概念
2.易错点
3.使用场景
二 ，布隆过滤器的实现
实现：
namespace bloomfilter {
//字符串hash函数
struct bkdrhash
{
size_t operator()(const string& str)
{
size_t hash = 0;
for (auto e : str)
{
hash = hash * 131 + e; // 也可以乘以31、131、1313、13131、131313..
}
return hash;
}
};
struct aphash
{
size_t operator()( const string& str)
{
size_t hash = 0;
size_t ch;
for (size_t i = 0; i < str.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ str[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ str[i] ^ (hash >> 5)));
}
}
return hash;
}
};
struct rshash
{
size_t operator() ( const string& str)
{
size_t hash = 0;
size_t magic = 63689;
for (auto e : str)
{
hash = hash * magic + e;
magic *= 378551;
}
return hash;
}
};
template <size_t n, class k = string, class funk1 = bkdrhash, class funk2 =aphash, class funk3 = rshash>
class bloomfilter
{
public:
void set( const k& key)//set函数
{
size_t hash1 = funk1()(key)%n;//计算出第一个位置
size_t hash2 = funk2()(key)%n;//计算出第二个位置
size_t hash3 = funk3()(key)%n;//计算出第三个位置
_bes.set(hash1);
_bes.set(hash2);
_bes.set(hash3);
}
bool test(const k& key)//test函数，返回true是不准确的。
{
size_t hash1 = funk1()(key)%n;//计算出第一个位置
size_t hash2 = funk2()(key)%n;//计算出第二个位置
size_t hash3 = funk3()(key)%n;//计算出第三个位置
if (_bes.test(hash1) == false)//检测是否出现过
{
return false;
}
if (_bes.test(hash2) == false)
{
return false;
}
if (_bes.test(hash3)==false )
{
return false;
}
return true;
}
private:
bitset::bitset<n>_bes;//自定义位图
};
void test()//测试用例
{
bloomfilter<100>blf;
blf.set("猪八戒");
blf.set("孙悟空");
blf.set("白龙马");
cout<<blf.test("猪八戒")<<" ";
cout<<blf.test("孙悟空")<<" ";
cout<<blf.test("白龙马")<<" ";
cout << blf.test("abc") << " ";
}
}
发表评论