布隆过滤器

如何判断一个元素在亿级数据中是否存在？

程序员小灰——漫画：什么是布隆算法？

 

现在有一个非常庞大的数据，假设全是 int 类型。现在我给你一个数，你需要告诉我它是否存在其中(尽量高效)。

需求其实很清晰，只是要判断一个数据是否存在即可。

 

但这里有一个比较重要的前提：非常庞大的数据。

 

 

Bloom Filter

基于上面分析的条件，要实现这个需求最需要解决的是如何将庞大的数据 load 到内存中。

而我们是否可以换种思路，因为只是需要判断数据是否存在，也不是需要把数据查询出来，所以完全没有必要将真正的数据存放进去。

 

伟大的科学家们已经帮我们想到了这样的需求。

Burton Howard Bloom 在 1970 年提出了一个叫做 Bloom Filter（中文翻译：布隆过滤）的算法。

 

它主要就是用于解决判断一个元素是否在一个集合中，但它的优势是只需要占用很小的内存空间以及有着高效的查询效率。

所以在这个场景下在合适不过了。

 

 

Bloom Filter 原理

 

如图所示：

 

1、首先需要初始化一个二进制的数组，长度设为 L（图中为 8），同时初始值全为 0 。

2、当写入一个 A1=1000 的数据时，需要进行 H 次 hash 函数的运算（这里为 2 次）；与 HashMap 有点类似，通过算出的 HashCode 与 L 取模后定位到 0、2 处，将该处的值设为 1。

3、A2=2000 也是同理计算后将 4、7 位置设为 1。

4、当有一个 B1=1000 需要判断是否存在时，也是做两次 Hash 运算，定位到 0、2 处，此时他们的值都为 1 ，所以认为 B1=1000 存在于集合中。

5、当有一个 B2=3000 时，也是同理。第一次 Hash 定位到 index=4 时，数组中的值为 1，所以再进行第二次 Hash 运算，结果定位到 index=5 的值为 0，所以认为 B2=3000 不存在于集合中。

 

整个的写入、查询的流程就是这样，汇总起来就是：

 

对写入的数据做 H 次 hash 运算定位到数组中的位置，同时将数据改为 1 。当有数据查询时也是同样的方式定位到数组中。一旦其中的有一位为 0 则认为数据肯定不存在于集合，否则数据可能存在于集合中。

 

 

所以布隆过滤有以下几个特点：

 

只要返回数据不存在，则肯定不存在。

返回数据存在，但只能是大概率存在。

同时不能清除其中的数据。

 

第一点应该都能理解，重点解释下 2、3 点。

为什么返回存在的数据却是可能存在呢，这其实也和 HashMap 类似。

 

在有限的数组长度中存放大量的数据，即便是再完美的 Hash 算法也会有冲突，所以有可能两个完全不同的 A、B 两个数据最后定位到的位置是一模一样的。

这时拿 B 进行查询时那自然就是误报了。

 

删除数据也是同理，当我把 B 的数据删除时，其实也相当于是把 A 的数据删掉了，这样也会造成后续的误报。

基于以上的 Hash 冲突的前提，所以 Bloom Filter 有一定的误报率，这个误报率和 Hash 算法的次数 H，以及数组长度 L 都是有关的。