Bloom FilterBloom filter

以多个哈希位判断一个键是否可能存在。

核心约束: 标准插入式过滤器允许误报，不产生算法性漏报。
适用问题: 避免访问不存在的键，减少无效存储 I/O。
边界与取舍: 不能代替精确索引；误报率依赖容量与哈希参数。

常见操作#

m 为比特数，n 为插入键数，k 为哈希位置数；以下为标准非计数 Bloom Filter。

操作	时间复杂度	条件与说明
插入	$O(k)$	计算 k 个位置并置位；键哈希还需读取键内容。
查询可能存在	$O(k)$	任一位置为零即可判定不存在；全为一只能表示可能存在。
删除单个键	不支持安全的直接清位	不同键会共享位；需计数 Bloom Filter 等变体。
构建	$O\left(nk+\frac{m}{w}\right)$	先清零，再插入 n 个键；w 为机器字位数。

时间与空间#

时间复杂度: 查询 / 插入 $O(k)$
存储空间: $O(m)$ 位

经典理想哈希模型误判率约为 (1 − e^(−kn/m))^k；没有删除、损坏或并发错误时不会出现假阴性。

工程中的应用#

1 个案例 · 附源码

RocksDB·SST 过滤器v9.7.3

先排除不含目标键的 SST

RocksDB 可为 SST 配置 Bloom filter，在读取数据块前排除不可能包含目标键的文件，减少无效查询工作。

Bloom Filter LSM-tree

附源码片段 · 检索与计算

基础原理参考资料

Bloom 1970 · Space/time trade-offs in hash coding允许误判以节约存储的原始设计。

Redis · Bloom filter成员查询语义、误判率和扩展型过滤器的工程行为。