要解决的问题

当集合元素数量非常大时，如何判断一个元素是否存在一个集合中？

常规思路利用普通数据结构(数组、链表、树、哈希表)存储集合，再对每一个需要判断的元素进行比对。

对于元素数量非常大的集合，普通计算机无法提供如此大的内存进行存储。

布隆过滤器介绍

• 巴顿布隆于1970年提出。
• 一个很长的二进制位数组。
• 一系列哈希函数。
• 空间效率和查询效率很高。
• 有一定的误判率。

常规思路下，对于超大数据量，哈希表是空间复杂度比较好的数据结构，不需要存储元素值。可以利用哈希函数将一个元素映射到一个位数组中的一个位，如果该位不为1，则集合中肯定不存在该值。(如果该位为1，则集合中不一定存在该值)。

如何进一步降低空间占用率？使用多个哈希函数。

一个Bloom Filter是基于一个m位的位向量（b1,…bm），这些位向量的初始值为0。另外，还有一系列的hash函数（h1,…hk），这些hash函数的值域属于1~m。

对每个要查询的元素，都经过k个哈希函数映射到位向量，如果==有一个位置不为1，则该元素一定不在集合中。如果每个位置都为1，则该元素可能在集合中。==

举例

下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图：

上图中，m=18，k=3；插入x是，三个hash函数分别得到蓝线对应的三个值，并将对应的位向量改为1，插入y，z时，类似的，分别将红线，紫线对应的位向量改为1。查找时，当查找x时，三个hash值对应的位向量都为1，因此判断x在此数据集中。y，z也是如此。但是查找w时，w有个hash值对应的位向量为0，因此可以判断不在此集合中。但是，假如w的最后那个hash值比上图中的大1，这是就会认为w在此集合中，而事实上，w可能不在此集合中，因此可能出现误报。显然的，插入数据越多，1的位数越多，误报的概率越大。

删除

如果使用位数组，则只支持add和isExist操作。

要支持删除可以将位数组改为计数值，增加一个值就是对应索引槽的值加一，删除就是减一。但是删除前必须确保被删除的元素之前被加入过。

特点

因为布隆过滤器能够用较少的内存占用==过滤出绝对不存在的值==，适用于过滤查询中不存在的值，减少磁盘IO或网络请求。

本文地址：https://cheng-dp.github.io/2019/03/22/bloom-filter/