Bloom Filter

形式陈述 ​

Bloom Filter 维护初始全零的 $m$ bit 数组，并从通用哈希公理库通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。或满足分析所需独立性的函数族中选择 $k$ 个映射到 $[m]$ 的哈希函数。插入键 $x$ 时，把 $h_1(x),\dots ,h_k(x)$ 对应 bit 全部置为 $1$；查询时，任一位置为 $0$ 就返回“确定不存在”，全部为 $1$ 则返回“可能存在”。在只插入、不损坏状态的模型中，已插入键对应的 bit 不会复零，因此没有假阴性；未插入键可能因其他键共享位置而产生假阳性。

在哈希近似独立均匀、插入 $n$ 个键的分析下，一位仍为零的概率约为 $e^{-kn/m}$，故

$$p_{\mathrm{fp}}\approx {(1-e^{-kn/m})}^k.$$

固定 $m,n$ 时，使该近似最小的哈希数为 $k\approx (m/n)\ln 2$，实际取相邻整数。公式描述指定随机模型下的概率，不是面对任意相关哈希和自适应攻击者的无条件保证。

直觉 ​

Bloom Filter 不保存“哪个键占了哪个 bit”，而让所有键共享一张位图。一个零位是强证据：查询键若曾插入，该位必已被置一；全为一却无法判断这些 bit 是否来自同一个键。它用放弃精确肯定换取远小于显式哈希表公理库哈希表Hash table用哈希函数把键映射到桶并处理冲突的字典结构。的空间。

最适合的用法是过滤昂贵负查询：返回“不存在”即可停止，返回“可能存在”再访问权威存储。过滤器本身不提供值，也不能枚举成员。

例子与边界 ​

缓存系统可先用 Bloom Filter 判断对象键是否可能在远端集合中。只要某个查询位置为零，就省去一次远端访问；若全部为一，仍必须查询真实字典确认。假阳性只增加一次无效后端访问，不会把不存在对象当作真实值返回。

普通 Bloom Filter 不能安全删除：把键 $x$ 的某个位置清零，可能同时抹掉另一个键 $y$ 共享的证据，使 $y$ 出现假阴性。Counting Bloom Filter 用小计数器替代 bit 才能在适当前提下递减，但空间和溢出问题也随之增加。

$k$ 并非越大越好。更多哈希最初增加查询约束，却也更快把位图填满；接近全一后，任何查询都会返回“可能存在”。若实际插入量超过设计的 $n$，原定假阳性率不再成立，应扩容、分层或重建。

推论与应用 ​

Bloom Filter 用于数据库查询过滤、网络缓存、存储系统 SSTable 索引和集合差异预筛。空间预算、预计元素数和容许假阳性率共同决定 $m,k$，不能只报告一个哈希数量。

它与完美哈希方向相反：完美哈希为已知静态集合消除查询冲突，Bloom Filter 则允许概率性误报以压缩成员表示。二者都依赖哈希，却解决不同正确性契约。

参考资料

• Burton H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM 13(7), 1970, pp. 422–426.
• Michael Mitzenmacher and Eli Upfal, Probability and Computing, 2nd ed., Cambridge University Press, 2017, §5.5.