Bloom Filter

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

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

设预计插入 $n=1000$ 个不同键，位图预算为 $m=10000$ bit。近似最优哈希数是 $10\ln 2\approx 6.93$，选整数 $k=7$ 后，预计置一比例为 $1-e^{-0.7}\approx 0.5034$，假阳性率为

在上述随机哈希近似下，一万个未插入键的查询约有 $82$ 次需要到后端核实。返回“可能存在”仍要查询权威字典，不能把它当成真实成员。若位图不变而实际插入量翻倍，近似误报率升到 $(1-e^{-1.4}{)}^7\approx 0.138$；这说明容量估计直接决定后端多付的查询成本，而非仅影响一个抽象百分比。

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

商过滤器理路商过滤器Quotient filter · 商余数过滤器用商确定逻辑桶、只存余数和三种状态位，在循环数组中恢复有序指纹多重集，并约束删除与误报语义。保存可解码的完整指纹多重集，用商、余数和三种状态位支持逐项改动；删除仍须由外部保证真实键存在，误报本身不能授权删除。Xor过滤器理路Xor 过滤器Xor filter · 异或过滤器把静态成员集写成三位置异或方程，度一剥离后逆序赋值，并把构建失败、查询误报与哈希独立性分别证明。则对静态集合剥离三位置方程并逆序赋值，查询只读三项，但一般集合变化需要重新构建。这两种成员结构分别给出动态位状态与静态构建证书，不能沿用普通Bloom的清位操作。

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

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

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