布隆过滤器原理及其应用 | 小谷的编程随笔空间

解决成员查询问题的最简单且最知名的数据结构是 布隆过滤器（bloom filter）。1970 年由 Burton Howard Bloom 提出。

布隆过滤器只支持两种操作：

布隆过滤器不支持删除操作，如果需要删除操作，可以考虑使用改进的方法，例如：计数布隆过滤器

数据结构

实际应用中，常用 比特数组 来表示布隆过滤器。假定该数组长度为 $m$ ，包含不同的散列函数 $\{h_i\}_{i=1}^{k}$ 。假定 $m$ 正比于期望的元素数量 $n$ ，且 $k \ll m$ 。

插入元素 x 时，则需要对每个散列函数 $h_k$ 计算其值 $j=h_k(x)$ ，并将过滤器中的第 $j$ 位的比特置为 1。

如果遍历发现某个散列计算出来的位置对应的比特位不为 1，则为 False。

如果所有对应的比特都已经被置为1，那么元素 x 可能存在于过滤器中 。否则，元素 x 一定不可能在过滤器中。

布隆过滤器的不足之处就是它可能把不在集合中的元素错判成集合中的元素，这个概率很低。

假定布隆过滤器中有 $m$ 比特，里面有 $n$ 个元素，每个元素对应 $k$ 个信息指纹的散列函数。目前比特数组中有的是 1，有的 0。

向这个布隆过滤器中插入一个元素，它的第一个散列函数会把某个比特置为 1。因此，任何一个比特被置为 1 的概率是 $1/m$ ，该位依然是 0 的概率则是：

$1-\frac{1}{m}$

对于某个特定的位置， $k$ 个散列函数都没有把这个位置设置为 1 的概率：

$(1-\frac{1}{m})^k$

依此类推，插入 $n$ 个元素后，还没有把该位设置为 1（依然为 0），概率是：

$(1-\frac{1}{m})^{kn}$

反过来，某个比特位置，再被插入 $n$ 个元素后，被设置为 1 的概率：

$1-(1-\frac{1}{m})^{kn}$

现在假定 $n$ 个元素都在布隆过滤器中，新增一个不在该集合中的元素。一个不在集合中的元素被误识别为在集合中，需要所有的散列函数对应的比特值均为 1，其概率为：

$P_{fp}=(1-(1-\frac{1}{m})^{kn})^k \approx (1 - e^{-\frac{kn}{m}})^k$

这是下界的概率。在期望元素总数 n 固定的情况下，假阳性率取决于 k 和 m 的选择。很显然，这是在过滤器的大小、散列函数的数量与误报率之间做出权衡。

实际情况中，假阳性率 $P_{fp}$ 以及期望元素数量 n 确定的时候，过滤器长度 m 由公式决定：

$m=-\frac{n\ln{P_{fp}}}{(\ln{2})^2}$

因此为保持误报率不变，过滤器的大小与元素数量呈线性关系。

对于给定比例 m/n，其意义为每个元素所需要分配的平均存储位数，假阳性率可以通过改变散列函数的数量 k 进行调整。最优的 k 值可通过最小化公式 $P_{fp}$ 中的假阳性率来计算的：

$k=\frac{m}{n}\ln{2}$

换句话来说，散列函数的最优数量 k 约为每个元素平均比特数的 0.7 倍。因为 k 必须为一个整数，因此向下取整的k的次优值是更为常用的。