目录
00.引入
上一篇博客介绍了位图这一数据结构，它可以在大量整数中快速查找某一数据是否存在，并且内存占用率很低（例如，查找40亿个整数只需0.5G空间）。博客链接跳转->
那么问题来了，如果我要查找的数据类型是字符串或其他类型，位图还能用吗？
分析：
位图本质上是一种哈希结构，哈希结构在存储元素时是根据元素的哈希值进行存储的，整数在位图中进行存储时，哈希值就是它本身，因此也不会产生哈希冲突；如果字符串想要用位图进行存储的话，需要计算出对应的哈希值，就要通过哈希函数来实现。
但是有一个问题，那就是哈希冲突：
最优秀的哈希函数也只能减少产生冲突的可能性，而不能完全避免冲突，那么在位图中，哈希冲突会造成什么后果呢？
例如：字符串“AaAaA”与“BBBBB”通过某哈希函数计算所得的哈希值都是5，事实上，“AaAaA”是存在的元素，而“BBBBB”并不存在，将所有元素存入位图后，bit位5的bool值为1（因为“AaAaA”的哈希值为5）此时就会对“BBBBB”产生误判，即“BBBBB”不存在但是通过位图会判断其存在。
当然了，为了应对哈希冲突，我们可以对位图进行扩容（通常是二倍扩容），并更新哈希函数重新计算哈希值来化解冲突，但是这种扩容的方式背离了位图的初衷：高效的内存利用。频繁的扩容必然导致内存的浪费，那么面对字符串的存储问题，该怎么解决呢？下面就要介绍布隆过滤器了。
01.布隆过滤器的概念
哈希冲突的产生原理就是，不同的元素有相同的哈希值，一般来说，一个元素对应一个哈希值，但是布隆（Burton Howard Bloom）告诉你，一个元素可以有多个哈希值：
一个元素经过多个不同哈希函数得到多个哈希值，将这些哈希值都作为该元素的映射，这样就大大减小了哈希冲突的可能性。两个不同的元素要想发生冲突，它们每个哈希值都得相同，并且可以通过增加哈希函数的办法，让这种可能性继续降低。
这是某位大佬总结出来的哈希函数的个数与误判率的关系：
说到底，布隆过滤器还是没办法完全解决哈希冲突的问题，还是会导致误判，但是布隆过滤器的以下特点使其具有重要意义：
特点1：极低的内存消耗
布隆过滤器拥有和位图一样的底层结构，使其使用极少的内存空间就可以支持大量数据的“存在性”查询。
特点2：快速查询
布隆过滤器通过简单的位运算就可以完成元素的“存在性”判断，速度非常之快，这种高效性在实时性要求高的场景（如网络请求过滤、黑名单检测）中尤为有用。
特点3：假阳性误判（禁止删除）
布隆过滤器虽然存在误判，但是可以将误判率控制在一个可以接受的范围内，并且布隆过滤器的误判是假阳性误判，不会存在假阴性误判，解释：
假阳性误判就是，将不存在的元素误判为存在，例如：由于A和B的哈希值全部相同，A存在就会导致B被误判
而假阴性误判就是，将存在的元素误判为不存在，查询某一元素是否存在，就要看它对应的比特位bool值是否都为1，只要该位置的bool值不被修改，就不会造成假阴性误判。元素的插入不会造成修改，但是元素的删除会造成修改。
A与B有一个哈希值7相同，B的删除会使7的bool值置0，这就会导致A被误判为不存在，即假阴性误判，为了避免这种情况发生，布隆过滤器不允许删除元素。
为什么布隆过滤器允许假阳性误判但不允许假阴性误判的产生呢，来看下面这一个场景：
为了方便用户之间的搜索，某应用不允许用户的id重复，现在用布隆过滤器存储着所有用户id的存储情况，用户注册时如果预输入id已存在，则要求更换id（可能预输入id并不存在，但是发生假阳性误判），由于假阴性误判的杜绝，用户的id一定不会相同（已存在的id肯定不会被误判为不存在，而被新用户注册）
02.布隆过滤器的底层实现
布隆过滤器的底层结构与位图相同，只不过前者用多个哈希值表示1个元素，而且后者只用1个哈希值对应1个元素
// 将which比特位置1
void set(size_t which)
{
if (which > _bitCount)
return;
size_t index = (which >> 5);
size_t pos = which % 32;
_bit[index] |= (1 << pos); // 将对应bit位改为1
}
// 将which比特位置0
void Set(const K& key)
{
size_t len = X*N;
size_t index1 = HashFunc1()(key) % len;
size_t index2 = HashFunc2()(key) % len;
size_t index3 = HashFunc3()(key) % len;
_bs.set(index1);
_bs.set(index2);
_bs.set(index3);
}
哈希函数参考：
struct BKDRHash
{
size_t operator()(const string& s)
{
// BKDR
size_t value = 0;
for (auto ch : s)
{
value *= 31;
value += ch;
}
return value;
}
};
struct APHash
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (long i = 0; i < s.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
以上就是对布隆过滤器的详细介绍与说明，欢迎指正~
码文不易，还请多多关注支持，这是我持续创作的最大动力！
标签：误判,元素,布隆,C++,哈希,过滤器,size From： https://blog.csdn.net/dhgiuyawhiudwqha/article/details/143449695