【C++】BloomFilter——布隆过滤器

一、布隆过滤器概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间 .

位图的优点是节省空间，快，缺点是要求范围相对集中，如果范围分散，空间消耗上升，同时只能针对整型，字符串通过哈希转化成整型，再去映射，对于整型没有冲突，因为整型是有限的，映射唯一的位置，但是对于字符串来说，是无限的，会发生冲突，会发生误判：此时的情况的是不在是正确的，在是不正确的，因为可能不来是不在的，但是位置跟别人发生冲突，发生误判

此时布隆过滤器就登场了，可以降低误判率：让一个值映射多个位置，但是并不是消除误判

可能还是会出现误判：

💘虽然布隆过滤器还是会出现误判，因为这个数据的比特位被其他数据所占，但是判断一个数据不存在是准确，不存在就是0！

---

布隆过滤器改进：映射多个位置，降低误判率（位置越多，消耗也越多）

如果布隆过滤器长度比较小，比特位很快会被占为1，误判率自然会上升，所以布隆过滤器的长度会影响误判率，理论上来说，如果一个值映射的位置越多，则误判的概率越小，但是并不是位置越多越好，空间也会消耗：大佬们自然也能够想得到，所以有公式：

我们可以来估算一下，假设用 3 个哈希函数，即K=3，ln2 的值我们取 0.7，那么 m 和 n 的关系大概是 m = n×k/ln2=4.2n ，也就是过滤器长度应该是插入元素个数的 4 -5倍

---

二、布隆过滤器应用

不需要一定准确的场景。比如游戏注册时候的昵称的判重：如果不在那就是不在，没被使用，在的话可能会被误判。

提高查找效率：客户端中查找一个用户的ID与服务器中的是否相同，在增加一层布隆过滤器提高查找效率：

---

三、布隆过滤器实现

布隆过滤器的插入元素可能是字符串，也可能是其他类型，只要提供对应的哈希函数将该类型的数据转换成整型就可以了。

一般情况下布隆过滤器都是用来处理字符串的，所以布隆过滤器可以实现为一个模板类，将模板参数 T 的缺省类型设置为 string：

template <size_t N,size_t X = 5,class K=string,class HashFunc1 = BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJBHash>
class BloomFilter{public:private:bitset<N * X> _bs;};

这里布隆过滤器提供三个哈希函数，由于布隆过滤器一般处理的是字符串类型的数据，所以我们默认提供几个将字符串转换成整型的哈希函数：选取综合评分最高的 BKDRHash、APHash 和 DJBHash这三种哈希算法：

   struct BKDRHash{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}};struct APHash{size_t operator()(const string& key){size_t hash = 0;int i = 0;for (auto ch : key){if ((i & 1) == 0){hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));}++i;}return hash;}};struct DJBHash{size_t operator()(const string& key){size_t hash = 5318;for (auto ch : key){hash += (hash << 5) + ch;}return hash;}};

1.插入

布隆过滤器复用bitset的 set 接口用于插入元素，插入元素时，我们通过上面的三个哈希函数分别计算出该元素对应的三个比特位，然后在位图中设置为1即可：

        void set(const K& key){size_t hash1 = HashFunc1()(key) % (N * X);size_t hash2 = HashFunc2()(key) % (N * X);size_t hash3 = HashFunc3()(key) % (N * X);_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);_bs.set(hash4);}

2.查找

通过三个哈希函数分别算出对应元素的三个哈希地址，得到对应的比特位，然后去判断这三个比特位是否都被设置成了1

如果出现一个比特位未被设置成1说明该元素一定不存在，也就是如果一个比特位为0就是false；而如果三个比特位全部都被设置，则return true表示该元素已经存在（注：可能会出现误判）

        bool test(const K& key){size_t hash1 = HashFunc1()(key) % (N * X);if (!_bs.test(hash1)){return false;}size_t hash2 = HashFunc2()(key) % (N * X);if (!_bs.test(hash2)){return false;}size_t hash3 = HashFunc3()(key) % (N * X);if (!_bs.test(hash3)){return false;}return true;}

3.删除

布隆过滤器一般没有删除，因为布隆过滤器判断一个元素是会存在误判，此时无法保证要删除的元素在布隆过滤器中，如果此时将位图中对应的比特位清0，就会影响到其他元素了：

这时候我们只需要在每个比特位加一个计数器，当存在插入操作时，在计数器里面进行 ++，删除后对该位置进行 -- 即可

但是布隆过滤器的本来目的就是为了提高效率和节省空间，在每个比特位增加额外的计数器，空间消耗那就更多了

---

四、布隆过滤器优缺

优

\1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关

\2. 哈希函数相互之间没有关系，方便硬件并行运算

\3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

\4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

\5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

\6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺

\1. 有误判率，不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)

\2. 不能获取元素本身

\3. 一般情况下不能从布隆过滤器中删除元素

五、结语

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法？

近似算法：利用布隆过滤器，交集的就一定会进去，但是可能会存在误判：不同的也会进去，这是近似

精准算法：query一般是查询指令，比如可能是网络请求，或者是一个数据库sql语句

100亿个query,假设平均每个query是50byte，则100亿个query那就是合计500GB

相同的query，是一定进入相同编号的小文件，再对这些文件放进内存的两个set中，编号相同的Ai和Bi小文件找交集即可

本篇结束…