来源：程序员 Aaron Zhu 

哈希表（又称作散列表）这种数据结构，通过计算元素在哈希表中的存储位置，可以快速判定该元素是否存在于该哈希表中，而无需遍历哈希表中全部元素一一进行比较。看上去哈希表这种数据结构是一个很好的工具，但是当数据量非常大达到亿级别，再加上为了解决哈希冲突的负载因子的缘故，使得哈希表的内存空间开销非常巨大，甚至会出现机器内存都无法支撑的情况。

这种超大规模数据的场景下，如何快速判定一个元素是否在指定元素集合中？本文将详细介绍一种概率模型的数据结构——布隆过滤器（Bloom Filter）

基本原理

在哈希表中存放的是元素本身，而 Bloom Filter 在内存中是一个足够大的位数组 (Bit Array)，其最小的内存使用单位是 Bit(仅这一点，内存开销就已经大大压缩了)。元素在插入 Bloom Filter 时，使用哈希函数 (Hash Function) 计算其哈希值确定其在位数组中的位置索引，然后将位数组中的指定 Bit 从 0 置 1 即可 (如该 Bit 已经被置 1，则无需再次置 1)。当使用 Bloom Filter 判定指定元素是否存在其中时，同样利用该 Hash Function 先计算哈希值，确定其在位数组的中位置索引，然后取出该位置的值， 若该 Bit 为 0，则说明该元素不存在于其中；若该 Bit 为 1，则说明该元素存在于其中

现已向一个 Bloom Filter 分别插入元素 "Hello"、"World" 为例，给出其插入过程的图解

当判断元素 "World" 是否在该 Bloom Filter 中时，先利用 Hash Function 计算其哈希值 (Hash Value = 3)，确定其在位数组的中位置索引，然后取出该位置的值 (即，BitArray[3])，其值为 1，即说明元素 "World" 存在于该 Bloom Filter 中；当判断元素 "Tony" 是否在该 Bloom Filter 中时，先利用 Hash Function 计算其哈希值 (Hash Value = 0)，确定其在位数组的中位置索引，然后取出该位置的值 (即，BitArray[0])，其值为 0，即说明元素 "Tony" 不存在于该 Bloom Filter 中

至此，Bloom Filter 模型的基本原理已经介绍完毕了。聪明的朋友可能已经发现了一个问题，即，发生哈希冲突可能会导致误判。假设我们现在对该 Bloom Filter 来判定元素 "Wow" 是否存在其中，其哈希值计算后，恰好为 3。，从上图可知 BitArray[3]=1，则那么根据上文介绍的判定规则，我们判定元素 "Wow" 存在于该 Bloom Filter，显然该判定结果与该 Bloom Filter 中仅存在 "Hello"、"World" 两个元素的真实情况不符

因此正如前文所述，其是一种概率模型的数据结构，发生哈希冲突的概率可以减少，但是无法完全避免。故判定一个元素是否存在于 Bloom Filter，如果判定结果是不存在 (False)，则一定不存在；但是如果判定结果是存在 (True)，则实际情况其实是可能存在，而不是一定存在，即假阳性。 所以，实际应用中，在 Bloom Filter 一般会使用多个 Hash Function，以减小发生哈希冲突的概率。即，减小误判率 P(true)。插入一个元素时，分别计算其在各个 Hash Function 的哈希值，然后将各个哈希值对应的 Bit 的值置 1；而判定元素是否存在于 Bloom Filter 时，则要求各个哈希值对应的 Bit 的值均为 1 才行

现依然是已向一个 Bloom Filter 分别插入元素 "Hello"、"World" 为例，给出其插入过程的图解。不同的是，这次我们使用了 2 个 Hash Function，并说明提高 Hash Function 个数如何降低误判率 P(true)

假设我们现在对该 Bloom Filter 依然判定元素 "Wow" 是否存在其中，其分别使用两个 Hash Function 计算哈希值，分别为 3、0。从上图可知虽然 BitArray[3]=1 但是 BitArray[0]=0，则那么根据上文介绍的判定规则，我们即可判定元素 "Wow" 不存在于该 Bloom Filter。从这里，我们看出，提高 Hash Function 的个数可以显著降低误判率 P(true)

细谈参数设计

相信大家对于 Bloom Filter 的工作原理都有了一个基本的了解，现在我们来看看在 Bloom Filter 中涉及到的一些参数指标：

• 欲插入 Bloom Filter 中的元素数目 : n

• Bloom Filter 误判率 : P(true)

• BitArray 数组的大小 : m

• Hash Function 的数目 : k

欲插入 Bloom Filter 中的元素数目 n 是我们在实际应用中可以提前获取或预估的；Bloom Filter 的误判率 P(true) 则是我们提前设定的可以接受的容错率。所以在设计 Bloom Filter 过程中，最关键的参数就是 BitArray 数组的大小 m 和 Hash Function 的数目 k，下面将给出这两个关键参数的设定依据、方法

误判率 P(true)

向 Bloom Filter 插入一个元素时，其一个 Hash Function 会将 BitArray 中的某 Bit 置为 1，故对于任一 Bit 而言，其被置为 1 的概率 ，那么其依然是 0 的概率；易知插入一个元素时，其 k 个 Hash Function 都未将该 Bit 置为 1 的概率。则向 Bloom Filter 插入全部 n 个元素后，该 Bit 依然为 0 的概率即为，反之，该 Bit 为 1 的概率则为

由前文可知，判定一个元素存在于 Bloom Filter，要求 k 个 Hash Function 的哈希值对应的 Bit 的值均为 1。据此，我们可以计算出其误判率 P(true)：

根据基本极限

可知：

从上式可以看出，当 BitArray 数组的大小 m 增大 或 欲插入 Bloom Filter 中的元素数目 n 减小时，均可以使得误判率 P(true) 下降

Hash Function 的数目 k

前文已经看到 Hash Function 数目 k 的增加可以减小误判率 P(true)，但是随着 Hash Function 数目 k 的继续增加，反而会使误判率 P(true) 上升，即误判率是一个关于 Hash Function 数目 k 的凸函数。所以当 k 在极值点时，此时误判率即为最小值

令 a = e^(n/m)，则有：

分别对上式两边，先取对数，再对 k 求一次导，可有：

易知，当 k 取极值点时，有，故将其带入上式即可求出 k

此时，我们即可以利用上式的结果，通过 m 和 n 来确定最优的 Hash Function 数目 k

BitArray 数组的大小 m

如何确定 BitArray 数组的大小 m 呢？这里，我们联立 P(true)、k 的公式，即可解出 m

联立后有：

对上式求解，可得：

此时，我们即可以利用上式的结果，通过 P(true) 和 n 来确定最优的 BitArray 数组的大小 m

应用场景

1. 爬虫

由于互联网中的网页数量巨大，如果使用哈希表保存爬虫工具访问过的 url 显然是不现实的，此时即可使用 Bloom Filter 来存储。当爬虫工具每次爬取一个网页，判定该网页是否已经被爬取过时，如果 Bloom Filter 给出的是结果是 False，则事实上一定没有被访问过，即可去爬虫；但如果 Bloom Filter 给出的是结果是 True，即，该网页已经被爬取过。虽然有一定概率出现误判，即该网页其实并未被访问过。但是鉴于互联网中网页数目浩如烟海，遗漏很小一部分网页未被爬取访问在工程上也是可以接受的

2. 缓存穿透

缓存穿透：外部发送请求去查询一个缓存中一定不存在的数据。由于未命中缓存，则外部请求将直接转发到 DB 中，当外部频繁请求、流量过大时，即可能会直接导致 DB 服务宕机

同样地，这里可以应用 Bloom Filter 来加在缓存前一级用于过滤查询请求，当判定查询数据不存在，即可直接返回请求而无需向缓存、DB 传递该请求

参考文献

1. 《数学之美》 吴军著