布隆过滤器

布隆过滤器（Bloom Filter）是1970年由伯顿·霍华德·布隆（Burton Howard Bloom）提出的高空间效率的概率数据结构。由一个通过一系列散列函数对样本元素映射而成的二进制位数组组成。布隆过滤器可用于检索一个元素是否在一个集合中，其空间效率和查询时间效率都远超一般算法。它不会产生假阴性（漏报），但有一定的假阳性（误报）率且难以删除元素。

## 基本概念

如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为$O(n),O(\log n),O(1)$。

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。所以布隆过滤器可能会产生假阳性，但不会产生假阴性。

## 算法描述

<image>

一个“空布隆过滤器”是一个由m位组成的位数组（bit array），所有位都被设置为0。它配备了k个不同的散列函数，这些函数将集合元素映射到m个可能的数组位置之一。为了达到最佳效果，散列函数应为均匀分布且独立。通常，k是一个小的常数，它取决于期望的假阳性（误报）率ε，而m与k和要添加的元素数量成正比。

要“添加”一个元素，将其分别输入到k个散列函数中，以获得k个数组位置。将所有获得的位置的位设置为1。

要“检验”一个元素是否在集合中，将其输入到每个k散列函数中，以获得k个数组位置。如果这些位置“存在”位为0的位置，则该元素一定不在集合中；如果它在集合中，那么当它被插入时，所有位都应该已经是1。如果所有位都已为1，说明该元素可能在集合中，又或许这些位是在插入其他元素时碰巧被设置为1，从而导致假阳性。就一个简单的布隆过滤器而言，并不能区分这两种情况，但更先进的技术可以解决这个问题。

设计k个不同的独立散列函数的要求对于大的k可能是难以实现的。对于一个具有宽输出的良好散列函数，这种散列的不同位域之间应该几乎没有相关性，因此这种散列类型可以用于通过将其输出切片成多个位域来生成多个“不同”的散列函数。或者，可以将k个不同的初始值（例如0, 1, ..., k − 1）传递给一个接受初始值的散列函数；或者将这些值加入（或追加）到键。对于较大的m和/或k，散列函数之间的独立性可以放宽，而假阳性率的增加可以忽略不计。（具体而言，展示了使用增强双重散列和三重散列（双散列的变体，实际上是用两个或三个散列值播种的简单随机数生成器）导出k个索引的有效性。）

这样简单的布隆过滤器无法移除元素，因为无法得知它映射到的k位中的哪些位应该被移除。虽然将这些k位中的任何一位设置为零足以移除该元素，但它也会移除任何恰好映射到该位的其他元素。由于简单的算法没有提供任何方法来确定是否已添加任何其他影响要移除元素的位的元素，因此清除任何位都会引入假阴性（漏报）的可能性。

若要模拟从布隆过滤器中一次性移除元素的操作，可以引入一个辅助布隆过滤器（“移除过滤器”），用于存储已移除的元素。然而，第二个过滤器中的假阳性会变成复合过滤器（“原过滤器”与“移除过滤器”的联合体）中的假阴性，这是不被希望遇到的。在这种方法中，却无法重新添加先前被移除的元素，因为还须将其从“移除过滤器”中移除，这又会回到最初的问题。

常见的情况是，所有键（待过滤的所有元素）都能够被获取（可用），但枚举它们的代价较高（例如，需要多次的硬盘读取）。当假阳性率变得太高时，可以重新生成过滤器；但此类事件应该是相对罕见的。

## 优劣分析

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（$O(k)$）。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

假阳性率是布隆过滤器的不足之一。随着存入的元素数量增加，假阳性率随之增加。但是如果元素数量太少，则使用散列表足矣。在降低假阳性率方面，有不少工作，使得出现了很多布隆过滤器的变种。

## 时间与空间优势

<image>

尽管存在假阳性风险，布隆过滤器在表示集合的数据结构中比其他数据结构（如自平衡二叉搜索树、字典树、哈希表或简单的数组或链表）具有显著的空间优势。这些数据结构中的大多数都需要存储至少数据项本身，这可能需要从少量位（对于小整数）到任意数量的位（例如对于字符串，字典树是例外，因为它们可以在具有相同前缀的元素之间共享存储）。然而，布隆过滤器完全不存储数据项，且须为过滤器的实际存储另行提供解决方案。链式结构会产生额外的线性空间开销用于指针。相比之下，具有1%误报率和最优k值的布隆过滤器，每个元素只需要大约9.6位，无论元素的大小如何。这一优势部分源于其紧凑性，继承自数组，部分源于其概率性质。通过为每个元素增加大约4.8位，可以将1%的误报率降低一个数量级。

然而，如果潜在值的数量较少且其中许多值可能存在于集合中，布隆过滤器很容易被确定性位数组超越，后者只需要为每个潜在元素使用一位。如果哈希表开始忽略冲突并仅存储每个桶是否包含条目的信息，它们将获得空间和时间优势；在这种情况下，它们实际上已成为$k=1$的布隆过滤器。

布隆过滤器还具有一个不寻常的特性，即添加项目或检查项目是否在集合中的时间都是固定常数，$O(k)$如前所述，$k$为散列函数数。完全独立于集合中已有的项目数量。没有其他常数空间集合数据结构具有这种特性，但稀疏哈希表的平均访问时间可能使其在实践中比某些布隆过滤器更快。然而，在硬件实现中，布隆过滤器表现出色，因为它的k次查找是独立的并且可以并行化。

要理解其空间效率，可以将通用布隆过滤器与其$k=1$的特殊情况进行比较。如果$k=1$，为了保持足够低的假阳性率，而只允许一小部分位被置位为1，这意味着数组必然非常大并包含很长的全零序列。相对于其大小，数组所包含的信息量较低。通常意义的布隆过滤器（k大于1）允许更多的位被置位为1，同时仍然保持较低的假阳性率；如果参数（k和m）选择得当，约有一半的位会被置位，并且这些位要明显随机，从而最小化冗余并最大化信息量。

## 假阳性率

<image>

假设哈希函数以相等概率选择数组中的每个位置。设m为数组的总位数，则某个位在元素插入过程中“未被”某个哈希函数置位为1的概率为

$$1 - \frac 1 m$$

设k为哈希函数的数量，并且每个哈希函数之间没有显著的相关性，那么该位未被任何哈希函数置位为1的概率是$(1-\frac1m)^k$。

通过关于$e^{-1}$的著名公式。

$$\lim_{m \to \infty}(1-\frac{1}m)^m=\frac{1}e$$

得出：对于较大的m。

$$(1-\frac1m)^k=((1-\frac1m)^m)^{k/m}\approx{e}^{-k/m}$$

假设过滤器已经被插入了n个元素，那么某个位仍为0的概率是

$$(1-\frac1m)^{kn}\approx{e}^{-kn/m}$$

于是，为1的概率是

$$1-(1-\frac1m)^{kn}\approx{1}-{e}^{-kn/m}$$

假设测试一个不在集合中的元素。基于上述的概率计算，由哈希函数计算的k位数组的每个位置都为1。所有这些位置都为1的概率，将导致算法错误地报告该元素在集合中（假阳性），通常给出概率为

$$\epsilon=(1-[1-\frac1m]^{kn})^k\approx{(1-e^{-kn/m})^k}$$

然此论未必完善，因其假设每位置位之概率互相独立。假设有较理想之近似，可得：假阳性率随m（数组总位数）的增加而降低，并随n（插入元素数）的增加而升高。

不考虑独立性，假阳性的真实概率是

$$\frac{1}{m^{k(n+1)}}\sum_{i=1}^m{i}^ki!\binom{m}{i}\begin{Bmatrix}kn\\i\end{Bmatrix}$$

其中{花括号}表示第二类斯特林数。

Mitzenmacher和Upfal曾提出一种无需独立性假设即可得到相同近似结果的分析。在过滤器中添加了所有n个项目后，设q为m位（数组总位数）中为0的比例。（即仍为0的位数是。）然后，在测试不在集合中的元素时，对于由任何k个哈希函数给出的数组位置，该位被置位为1的概率是$1-q$。因此，所有k个哈希函数都找到其位被置位为1的概率是$(1-q)^{k}$。此外，q的期望值，即为一个给定的数组位置在n个元素分别经过k个哈希函数处理后，依然保持纯洁（未被置位）的概率。其计算方式（同上）如下：

$$E[q]=(1-\frac1m)^{kn}$$

在不依赖独立性假设的前提下，可以证明q的取值高度集中在其期望值附近。具体而言，利用吾妻不等式，可证得：

$$Pr(|q-E[q]|\geq\frac\lambda{m})\leq2exp(-2\lambda^2/kn)$$

因此可得，假阳性（误报）的准确概率如前所述为：

$$\sum_{t}Pr(q={t})(1-t)^k\approx(1-E[q])^k=(1-[1-\frac1m]^{kn})^k\approx(1-e^{-kn/m})^k$$

## 参考

### 文献

- . Open source implementation available on github .
- . A preliminary version appeared at SIGCOMM '98.
- . Prototype implementation available on github .