probabilistic set · bit array + k hashes

Bloom filter 的拆解

Bloom filter（布隆过滤器）是一个概率型集合，只回答「 $x$ 在不在」这一个问题。它用一排 bit 换来一个不对称的承诺：说「不在」就一定不在，说「在」则只是可能在，有小概率误报，但绝不漏报。它不存元素本身，只把每个元素用 $k$ 个哈希点亮几个 bit。

定义 0.1（单侧误差） Bloom filter 没有假阴性：真正加进去的元素，查询一定报「可能在」。但有假阳性：没加过的元素，偶尔也会被报成「可能在」。因此它适合做「说不在就真不在」的前置筛子。

1 · 用一排 bit 回答成员查询

motivation · membership ADT

很多场景只需要一个答案：这条 URL 爬过没、这个 key 在不在数据库。哈希表能精确回答，代价是把元素都存下来；当元素有几亿条且每条不短时，光存下来就要几十 GB。Bloom filter 换一条路：不存元素，只用一排 bit 记痕迹，容忍极小概率的误报，把空间压到零头。

图 1-1 · 一个 48 bit、3 个哈希的黑箱 Bloom filter。可加入若干词再查询，它只给「一定不在」与「可能在」两种答案。查一个没加过的词，多数回「一定不在」，偶尔撞上「可能在」即一次误报。

图 1-2 · 100 万条 URL、平均每条 40 字节时精确存储与 Bloom filter 的空间对照。

按误判率 1% 的参数（每元素约 9.6 bit）核算：100 万条 URL 精确存下来是 40 MB，Bloom filter 约 1.2 MB，相差约 33 倍。代价有两条，一是偶尔误报，二是存不回元素本身，它只记痕迹不记内容。所以它常做前置筛子，说「不在」就直接放行或拦截，说「可能在」再去查真正的、更慢的数据源确认。

2 · 从朴素方案到 Bloom filter

derivation · why this shape

Bloom filter 的结构是被约束推导出来的。给定同一个目标——用尽量少的空间回答成员查询、允许极小误报——从最直接的「存哈希」出发，每一步追问还能不能更省，最终会收敛到那个形状：一排 bit 加 $k$ 个重叠的哈希。

图 2-1 · 四种设计装同一批词、用同样 48 bit 预算时的结构对照。可逐个切换，观察内存的用法如何变化。

图 2-2 · 四种设计的实测误判率。以所有没加过的三字母组合逐个查询，统计被误判成「可能在」的比例，绿色为当前最低。

四步的改进各有来源。其一，直接存哈希：不存原词，只存它的一个 $b$ bit 短指纹，查询看指纹是否在已存集合中，误报来自指纹碰撞。元素少时它很省，但装得越多、分给每个的指纹位越少，碰撞随之上升。其二，一排 bit 加单哈希：开 $m$ 个 bit，add(x) 把第 $h(x)$ 位置 1，省去了记录「存了哪些指纹」的开销；但只有一个哈希时位很快填满，一个没加过的词只要撞上任意一个已置位的 bit 就误报。其三， $k$ 个独立的小数组：把内存切成 $k$ 份，各配一个独立哈希、各置一位，查询要求 $k$ 份全部命中。一次误报需同时撞中 $k$ 份，概率是单份的 $k$ 次方，误判率被压成幂次，这是关键一跃。其四，把 $k$ 份叠回同一排 bit：既然要 $k$ 个哈希，不必把内存切开，让 $k$ 个哈希共用整排 $m$ 个 bit。同样的预算下不切分反而让每个哈希都能用到全部 $m$ 位，误判率不差于切开的方案，实现还更简单。推到这一步正好是 Bloom filter。

警示 · 图 2-2 上有两件事值得动手验证。其一，元素少时「直接存哈希」的误判可能比重叠方案还低，多加几个词才会被反超，这正是「集合够大时 Bloom 才划算」的临界点。其二，同样内存下重叠方案总是不差于 $k$ 个独立数组，但两者差距在 $k$ 较小时并不明显，据此说「重叠一定明显更优」是过度断言。

3 · 位数组与 k 个哈希

core · bit array + k hashes

打开盒子，里面是一排长度 $m$ 的 bit（初始全 0）与 $k$ 个哈希函数。add(x) 把 $x$ 的 $k$ 个哈希位置全置 1；query(x) 看这 $k$ 位是否全为 1，有一个是 0 就一定不在，全是 1 就可能在。误报的来源很直观： $x$ 的那几个位恰好被别的元素点亮了。

图 3-1 · 位数组与

k

个哈希落点的对应。可逐个加入元素并查询，观察哪些位被点亮、一次误报是由哪几个元素的落点凑出来的。

每个 bit 都是共享的，位 7 可能同时是 cat 与 dog 的落点。当一个没加过的词的 $k$ 个位正好都被此前别的词点亮，就被误判成「可能在」。位填得越满，即装得越多、 $m$ 越小或 $k$ 越大，撞上的概率越高，§5 会把它量化。

警示 · Bloom filter 不能直接删除。若想删 cat 而把它的位清 0，那些位可能也是 dog 的落点，清了会让 dog 漏报，破坏单侧误差这一保证。要支持删除须改用计数型变体，见 §5。

4 · k 个下标的来源

hashing · double hashing

§3 说 $k$ 个哈希点亮 $k$ 个 bit，但哪来这么多哈希函数。实际只算两个基础哈希 $h_1$ 、 $h_2$ 就够，剩下的 $k$ 个下标全由它俩派生。

Kirsch 与 Mitzenmacher 证明，取 $g_i(x) = (h_1 + i \cdot h_2) \bmod m$ 派生出的 $k$ 个下标，其误判率与真的算 $k$ 个独立哈希在渐近意义上相同。本系列用的是它的增强版，Dillinger 与 Manolios 的 enhanced double hashing，多加一项二次修正：

g_i(x) = (h_1 + i \cdot h_2 + i^2) \bmod m, \qquad i = 0, 1, \dots, k-1

图 4-1 · 由

h_1

与

h_2

派生

k

个下标的过程。可输入任意词，逐步查看两个基础哈希以及由它俩推出的每一个位。

$h_2$ 要强制成奇数。 $m$ 常取 2 的幂，若 $h_2$ 与 $m$ 不互质， $i \cdot h_2 \bmod m$ 会反复落进同几个位而浪费空间；把 $h_2$ 按位或 1 置奇即保证它与 2 的幂互质， $k$ 个下标铺得更开。式中的 $i^2$ 则进一步打散，避免下标退化成等差数列。这样每次 add 与 query 只跑两次哈希，之后的 $k$ 个下标都是几条加法与取模，实现见本系列的 core/bloom.ts。

哈希函数本身只需两个性质：快，且输出足够均匀地铺满 $[0, m)$ 。它不需要抗碰撞与不可逆这些密码学性质，成员查询里没有攻击者要骗，撞了大不了多一次误报。所以非加密哈希正合适，用 SHA 不会更准，只会更慢。

图 4-2 · 几种哈希函数在同一批输入下的分布与速度对照。可切换 MurmurHash3、xxHash、FNV-1a 与加密哈希，观察分布均匀度与耗时。

5 · 误判率与参数选择

math · 误判率 / 参数 / 变体

位填得越满，误报越多。三个量决定一切：装进多少元素 $n$ 、多少 bit $m$ 、几个哈希 $k$ 。

图 5-1 · 误判率

p

随

n

、

m

、

k

的变化。可拖动三个滑块，注意

k

并非越大越好，把它拨到最优值附近时

p

最低。

误判率有一个干净的近似式，三步即可推出。插入一个元素时，某个特定 bit 没被它的 $k$ 个哈希点中的概率是 $(1 - 1/m)^k$ ，装完 $n$ 个后这个 bit 仍为 0 的概率是

(1 - 1/m)^{kn} \approx e^{-kn/m}

即 $m$ 较大时的标准近似。于是它为 1 的概率约 $1 - e^{-kn/m}$ 。一次误报即查一个没加过的词而它的 $k$ 位恰好都为 1，故

p \approx \left(1 - e^{-kn/m}\right)^{k}

这一步把 $k$ 个位当作独立事件处理，严格说并不成立，但在 $m \gg k$ 时是很好的近似。

工程上通常先定「要装 $n$ 个、误判率不超过 $p$ 」，再算需要多少 bit。

图 5-2 · 由

n

与目标

p

反推所需的

m

与最优

k

。可改变目标误判率，观察每元素所需位数的变化。

最优配置下每元素约需 $\log_2(1/p) / \ln 2 \approx 1.44 \log_2(1/p)$ bit。取几档核算： $p = 1\%$ 需约 9.6 bit， $0.1\%$ 需约 14.4 bit， $0.01\%$ 需约 19.2 bit。误判率每降一个数量级，空间只线性增长，这是它性价比的来源。

信息论给出的下界是：任何能以误判率 $p$ 回答成员查询的结构，每元素至少需要 $\log_2(1/p)$ bit。Bloom filter 用掉 $1/\ln 2 \approx 1.4427$ 倍于此，即只比下界多约 44%，换来的是不存元素与 $O(k)$ 查询，因此称得上近乎最优。

有一点反直觉：最优 $k$ 只与 $p$ 有关，与装多少元素无关。把最优的 $m/n$ 代回 $k = (m/n)\ln 2$ 即得 $k = \log_2(1/p)$ 。原因是最优配置下每个 bit 恰好有一半概率为 1，此时 $p = 2^{-k}$ ，反解即得。所以目标 $1\%$ 对应 $k \approx 7$ 、 $0.1\%$ 对应 $k \approx 10$ 是定死的，与打算装一万个还是十亿个无关。

普通 Bloom filter 删元素会清错别人的位而造成漏报。计数型 Bloom filter 把每格从 1 bit 换成一个小计数器，add 时加一、remove 时减一，查询看是否都大于 0，代价是每格约 4 bit、空间翻几倍。

图 5-3 · 计数型 Bloom filter 的加入与删除。可反复 add 与 remove 同一元素，观察计数器的增减以及它为何不会误清他人的位。

还有更省的删法。Deletable Bloom filter 把位数组切成 $r$ 个 region，另用一张很小的 collision bitmap 标记哪些 region 发生过多个元素的位重叠；删除时只有没卷入碰撞的位才允许清 0。于是一部分元素可删、一部分不可删，但永远不会误清而破坏单侧误差，代价远小于计数型，适合「能删一部分就够」的场景。

6 · 应用场景

场景	怎么用
缓存穿透防护	先问 Bloom 这个 key 可能存在吗，说「不在」直接返回，避免每次都打到数据库
爬虫 URL 去重	几十亿 URL 判断「这条爬过没」，说「没」就放心抓
数据库 LSM-tree	RocksDB、Cassandra、LevelDB、HBase 每个 SSTable 配一个 Bloom，跳过肯定不含此 key 的文件以省磁盘 IO；Cassandra 另可调 `bloom_filter_fp_chance` 在内存与命中率间权衡
PostgreSQL bloom index	`bloom` 扩展把多个列编码进每行一个小 Bloom，任意列组合查询都能先筛掉大部分行
Spark broadcast join	对小表建 Bloom 广播出去，先在 map 端滤掉大表里肯定 join 不上的行，省一轮 shuffle
CDN 缓存	过滤只被访问一次的对象，第二次见到才缓存，Bloom 记「这个 URL 见过没」
弱口令与黑名单	判断密码是否在泄露库里，不必下载整个库
推荐去重	判断「这条内容给该用户推过没」，省内存地过滤已读

以推荐去重估算量级：1000 万用户各记 5000 条已读，共 $5 \times 10^{10}$ 条。用哈希集合精确存，按每条 12 至 16 字节算是 600 至 800 GB；换成每用户一个误判率 1% 的 Bloom filter，每条约 9.6 bit，总量约 60 GB，节省九成上下。代价只是偶尔把一条没推过的当成推过，漏推一条影响有限。

这些场景的共同模式是把 Bloom 当一道便宜的前置筛子：说「不在」就真不在，可以直接走捷径；说「可能在」再去查那个又慢又准的真数据源。用一点空间和偶尔的误报，挡掉绝大多数昂贵查询。

注 · Bloom filter 由 Burton Howard Bloom 于 1970 年提出 [1]，最初用于内存吃紧时的拼写检查词典查找。与字符串查找系列对照：Trie 精确回答「这个词在不在字典」，BK-tree 做容错查询，而 Bloom filter 用概率把同一个问题压进一排 bit；它与 Rabin–Karp 一样，核心都是哈希。

7 · 参考文献

Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422–426.
Kirsch, A., & Mitzenmacher, M. (2008). Less hashing, same performance: Building a better Bloom filter. Random Structures & Algorithms, 33(2), 187–218.
Dillinger, P. C., & Manolios, P. (2004). Bloom filters in probabilistic verification. In Formal Methods in Computer-Aided Design (pp. 367–381). Springer.
Rothenberg, C. E., Macapuna, C. A. B., Verdi, F. L., & Magalhães, M. F. (2010). The deletable Bloom filter: A new member of the Bloom family. IEEE Communications Letters, 14(6), 557–559.