结构描述#

布隆过滤器的结构非常简单，即一个长度为 m 的比特数组，初始化都为 0。然后，布隆过滤器需要有 k 个不同的哈希函数，每一个都能将元素映射到 [0, m) 中的一个数字，也就是数组上的一个位置，并呈现均匀分布。

通常，k 是一个远小于 m 的常数，与将要被加入的元素成比例。精确的 k 和 m 的取值取决于期望的 false positive 率。

下图是一个布隆过滤器：

那么介绍下布隆过滤器上的两个操作：

• 添加一个元素：对每一个哈希函数，都计算出对应的数组上的位置，并将其置为 1
• 查询一个元素：对每一个哈希函数，计算出对应的数组上的位置，如果都是 1，则返回元素存在，否则元素不存在

显然，如果一个元素曾经被添加过，在查询的时候一定存在，但是查询返回存在却不一定表明元素被添加过。

在这种设计中，由于不允许 false negative，所以不可能进行元素删除。如果允许 false negative，可以通过计数数组来处理元素删除。如果是一次性的删除，可以通过新建一个记录被删除元素的布隆过滤器来实现，但是这个过滤器的 false positive 就会变成第一个过滤起的 false negative。

空间和时间#

布隆过滤器的空间效率非常高，比其他一些用于集合的数据结构高效的多，例如自平衡二叉树、字典树、哈希表等。期望 1% 以内误报率的布隆过滤器，在采用最优 k 的情况下，每个元素只需要 9.6 个比特存储，并且与元素本身无关。甚至，我们只需要为每个元素添加大约 4.8 个比特，就可以把误报率降低到 0.1%。但是，当集合中可能的元素非常少时，布隆过滤器显然要比比特数组差。

在插入和查询时，布隆过滤器的时间复杂度都取决于 k 个哈希函数，通常哈希函数效率较高，我们认为时间复杂度就是 O(k)。

误报率和最优选择#

我们来推导一下误报的概率，当一个元素插入时，数组中一个位置还没被设置为 1 的概率显然为：$(1 - \frac{1}{m})^{k}$，那么当已经插入了 n 个元素之后，这个位置仍然是 0 的概率为 $(1 - \frac{1}{m})^{kn}$。

所以当查询时，每个哈希函数的位置都为 1 的概率为: $(1 - \left[1 - \frac{1}{m}\right]^{kn})^k \approx (1 - e^{-kn/m})^k$。

这个概率的推导并不完全正确，因为它假设每个比特被设置的事件是相互独立的。事实上当去除假设时，仍然可以分析出相同的近似结果，有兴趣的同学可以阅读。那么我们有

• 误报率随着 m 的增大而减小，并随着 n 的增大而增大

那么我们将有最优的哈希函数数为: $k = \dfrac{m}{n}\ln 2$ 推导过程如下所示:

$p = (1 - e^{-kn/m})^k$

$\ln p = k\ln(1 - e^{-kn/m}) = -\dfrac{m}{n}\ln(e^{-kn/m}) \ln(1 - e^{-kn/m})$

令 $g = e^{-kn/m}$，即有 $\ln p = -\dfrac{m}{n}\ln(g) \ln(1 - g)$，由对称法可知 $g = \dfrac{1}{2}$ 时上式最小。

所以有 $g = e^{-kn/m} = \dfrac{1}{2}$, $k = \dfrac{m}{n}\ln 2$。

估计集合大小#

Swamidass & Baldi (2007) 给出了布隆过滤器中集合的大概大小：

$n^* = -\dfrac{m}{k}\ln\left[1 - \dfrac{X}{m}\right]$ ，

其中 X 是比特数组中 1 的个数。

布隆过滤器的应用#

• Google Bigtable、 Apache HBase、 Apache Cassandra 和 Postgresql 使用布隆过滤器来减少不必要的磁盘查询。
• Google Chrome 使用布隆过滤器来检测危险的 URL。
• …

参考文献#

[1] https://en.wikipedia.org/wiki/Bloom_filter#Approximating_the_number_of_items_in_a_Bloom_filter