布隆过滤器

需求场景

1. 经常需要判断一个元素是否在一个集合中
2. 集合规模巨大，散列表存储效率低。
   2.1 散列表中，每条数据都需要对应一个信息指纹。当存储海量数据时，需要太多空间
   2.2 散列表存储效率不高，一般只有 50%。

布隆过滤器的优点

通过数学原理——两个完全随机的数字冲突的概率极小。使得布隆过滤器可以只使用散列表 1/8 或者 1/4 的大小解决同样的问题。

布隆过滤器的缺点

因为底层原理是两个完全随机的数字冲突的概率极小，但是不可避免仍可能存在冲突。此时的“冲突”，就会造成误判。使得不在集合中的元素，被误判为存在集合中，得到错误的结果。

弥补缺点

常见的解决办法是再开一个小的白名单，存储那些被误判的信息。

工作原理

布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。

• 构建布隆过滤器

1. 假定存储 i 个数据，先建立 16 * i 个比特位，全部置为 0 。
2. 对每个数据 x，用 8 个不同的随机数产生器 F1, F2, ...,F8 产生 8 个信息指纹 f1, f2,..., f8
3. 对每个信息指纹，用一个随机数产生器 G 映射成 16 * i 个比特位中的某一位，得到这八个映射后的比特位下标 g1, g2, ..., g8。
4. 把对应八个比特位置为 1。
5. 对 i 个数据重复 2 到 4 三个步骤。

• 使用布隆过滤器

1. 对要检测数据 y，重复构建阶段的 2 和 3 步骤，得到 y，对应的八个比特位下标 t1, t2, ..., t8。
2. 检查这八个比特位下标是否全为 1。若是，判定该元素已经存在集合中；否则，该元素不存在集合中。

为什么选择数字 16 和 8 作为构建的参数？

前面提到，布隆过滤器的一个不足之处就是它可以把可能不存在集合中的元素错判成集合中的元素，这在检验上被称为“假阳性”。

而使用这两个数字构建出来的布隆过滤器，，假阳性的概率是万分之五，在普通情况下配合白名单足够满足需求了。

关于这两个数字的不同取值，如何导致不同假阳性概率的分析，可以查看谷歌。