布隆过滤器 (Bloom Filter) 是一个空间高效的概率数据结构,它能够用来测试是否一个元素在一个集合中。布隆过滤器存在着 false positive (返回存在,其实不存在),但是不存在 false negative (返回不存在,其实存在)。集合中的元素越多,false positive 的概率就越高。

结构描述

布隆过滤器的结构非常简单,即一个长度为 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