probabilistic set · bit array + k hashes

Bloom filter · 拆解一个「会撒小谎」的集合

Bloom filter（布隆过滤器）是个概率型的集合，只回答一个问题——「x 在不在？」。它用极小的空间（一排 bit）换来一个奇特的承诺：说**「不在」就一定不在**；说**「在」则可能在**（有小概率误报，但绝不漏报）。它不存元素本身，只把每个元素用 k 个哈希点亮几个 bit。本系列从「为什么要这样」讲到位数组机制、误判率公式与参数选择。五步依次是：为什么 → 设计演化 → 机制 → 哈希 → 误判率与参数。

核心承诺（记牢这条）：没有假阴性(no false negative)——真正加进去的，查询一定查得到；但有假阳性(false positive)——没加过的，偶尔也会被误判成「在」。所以 Bloom filter 适合做「先挡一道、说不在就真不在」的前置筛子。

1 · 为什么：用一排 bit 回答「在不在」

motivation · membership ADT

很多场景只需要一个问题的答案：「x 在不在这个集合里？」——这条 URL 爬过没？这个 key 在不在数据库？哈希表能精确回答，但它得把元素都存下来。当元素是几亿条且每条还不短时，光存下来就要几十 GB。Bloom filter 换个思路：不存元素，只用一排 bit 记「痕迹」，容忍极小概率误报，把空间压到零头。

1.1 · 先当黑箱观察：它只给两种答案

下面是一个黑箱 Bloom filter（内部 48 bit、3 个哈希，其内部结构见设计演化与机制两节）。加几个词，再查询：它要么说 「一定不在」，要么说 「可能在」——注意它从不漏报，但偶尔会误报。

两条铁律： 其一，说「一定不在」→ 真的不在（没有漏报）; 其二，说「可能在」→ 大概率在，但可能误报（尤其装得越满越容易）。试试查一个没加过的词：大多回「一定不在」，偶尔撞上「可能在」就是一次误报。

1.2 · 省在哪：存 100 万条 URL

假设 100 万条 URL、平均每条 40 字节，只想判断「这条爬过没」：

空间小约 30 倍以上，代价是：其一，偶尔误报；其二，存不回元素本身（它只记痕迹，不记内容）。所以它常做前置筛子：说「不在」就直接放行 / 拦截，说「可能在」再去查真正的（更慢的）数据源确认。

2 · 设计演化：从朴素方案一步步推出 Bloom filter

derivation · why this shape

Bloom filter 的结构是被约束推导出来的。给定同一个目标（用尽量少的空间回答「在不在」、允许极小误报），从最直接的「存哈希」出发，每一步都追问「还能不能更省」，最终会收敛到那个形状：一排 bit + k 个重叠的哈希。下面四种设计装的是同一批词、用的是同样的内存预算(m = 48 bit)，实测误判率摆在一起对比——看着它一档档降下来。

2.1 · 四种设计，同样的内存，实测误判率

同一批词、同样 48 bit 预算，拿所有没加过的三字母组合去查，统计有多少被误判成「可能在」——这就是实测误判率。绿色 = 当前最低。

2.2 · 每一步「为什么更好」

其一，直接存哈希。最朴素：不存原词，只存它的一个 b bit 短哈希（指纹）。查询就看指纹是否在已存集合中。误报来自指纹碰撞（两个不同词碰巧同指纹）。元素少时它很省、误判很低——但装得越多，分给每个的指纹位越少，碰撞随之上升。

其二，改成一排 bit + 单哈希。不再存指纹列表，而是开 m 个 bit,add(x) 把第 h(x) 位置 1。省去了「存哪些指纹」的开销，但只有一个哈希：位很快被填满，一个没加过的词只要撞上任意一个已置位的 bit 就误报——误判偏高。

其三，用 k 个独立的小数组。把内存切成 k 份，各配一个独立哈希、各置一个 bit。查询要求 k 份全部命中才说「可能在」。一次误报得同时撞中 k 份，概率是单份的 k 次方——误判率被压成幂次，断崖式下降。这是关键一跃。

其四，把 k 份「叠」回同一排 bit = Bloom filter。既然要 k 个哈希，何必把内存切开？让 k 个哈希共用整排 m 个 bit:add(x) 点亮 k 个位，query(x) 看这 k 位是否全 1。同样的内存预算下，不切分反而让每个哈希都能用到全部 m 位，误判率≤ 切开的「k 个独立数组」方案，而且实现更简单。推到这里，就正好是 Bloom filter——这就是「它为什么长这样」。

动手验证两件事： 其一，现在元素少，存哈希的误判可能比 重叠 (Bloom) 还低；多加几个词，看它怎样被反超——这正是「集合够大时 Bloom 才划算」的临界点。其二，留意 独立数组 与重叠的误判：同样内存，重叠总是不差于独立数组。

3 · 机制：k 个哈希点亮几个 bit

core · bit array + k hashes

本节放大设计演化推出的最终结构。打开盒子，里面就是一排长度 m 的 bit（初始全 0）和 k 个哈希函数。add(x)：把 x 的 k 个哈希位置全置 1。query(x)：看这 k 位是否全为 1——有一个是 0 就一定不在；全是 1 就可能在。误报的来源很直观：x 的几个位恰好被别的元素点亮了。

为什么 query 全 1 仍可能错？每个 bit 是共享的——位 7 可能同时是 cat 和 dog 的哈希落点。当一个没加过的词，它的 k 个位正好都被此前别的词点亮，就被误判成「可能在」。位填得越满（装的越多 / m 越小 / k 越大），撞上的概率越高——这正是误判率与参数一节要量化的误判率。

注意：Bloom filter 不能直接删除。想删 cat 而把它的位清 0？可那些位可能也是 dog 的——清了就会让 dog 漏报，破坏「不漏报」这一保证。要支持删除需改用计数型 Bloom filter（见误判率与参数一节）。

4 · 哈希：k 个下标到底怎么算出来的

hashing · double hashing

机制一节说「k 个哈希点亮 k 个 bit」，但哪来这么多哈希？难道维护 k 个互不相同的函数？实际上只算两个基础哈希 h1、h2 就够了——剩下的 k 个下标全由它俩派生。这一节拆开本系列一直在用的那套 double hashing，顺带说清：为什么 Bloom filter 偏要用非加密哈希(MurmurHash3 / xxHash / FNV-1a)，而不是 SHA、MD5。

4.1 · 用两个哈希派生出 k 个下标

Kirsch–Mitzenmacher 的结论：第 i 个下标取 $g_i(x) = (h1 + i\cdot h2 + i^2) \mod m$ （i 从 0 数起）。输入一个词，看它的 h1、h2，以及由它俩一步步推出的 k 个位：

**为什么 h2 要强制成奇数？**m 常取 2 的幂，若 h2 与 m 不互质， $i\cdot h2 \mod m$ 会反复落进同几个位、白白浪费；把 h2 置奇(| 1)保证它和 2 的幂互质，k 个下标铺得更开。式子里那个 $+ i^2$ 是 enhanced double hashing 的小修正，进一步打散、避免退化成等差数列。

省在哪：每次 add / query 只跑两次哈希，之后 k 个下标都是几条加法 + 取模——和「真的算 k 个独立哈希」相比，误判率几乎没有变化（这正是 Kirsch–Mitzenmacher 证明的），但快得多。本系列 core/bloom.ts 用的就是这套。

4.2 · 为什么用「非加密」哈希

Bloom filter 对哈希只有两个要求：快、且输出足够均匀地铺满 [0, m)。它不需要抗碰撞、不可逆这些密码学性质——这里没有攻击者要骗，撞了大不了多一次误报。所以非加密哈希正合适：

一句话：选哈希看的是速度 + 分布均匀，不是安全。用 SHA 不会更准，只会更慢。真要更稳，用一个好的非加密哈希(MurmurHash3)配上面的 double hashing 派生 k 个下标即可。

5 · 误判率与参数：m、n、k 怎么定

math · 误判率 / 参数 / 变体

位填得越满，误报越多。三个量决定一切：n（装进多少元素）、m（多少 bit）、k（几个哈希）。误判率有个干净的近似式： $p \approx (1 - e^(-k\cdot n/m))^k$ 。调下面的滑块，实时看 p 怎么变。

5.1 · 误判率随 n / m / k 变化

两个直觉：其一，m 越大（位越多）p 越低，但更费空间；其二，k 不是越多越好——哈希太多会太快把位填满，存在一个最优 k。把上面 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 (1 - e^(-kn/m))^k$ 。（严格说这把 k 位当独立处理，是个很好的近似。）

5.2 · 反过来：定下目标，反推 m 和 k

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

经验值：每元素约 1.44·log₂(1/p) bit。p=1% → ~9.6 bit/元素,0.1% → ~14.4,0.01% → ~19.2。注意：误判率每降一个数量级，空间只是线性增长——这正是 Bloom filter 的性价比所在。

离理论极限有多近？信息论给出一个下界：任何能以误判率 p 回答「在不在」的结构，每元素至少要 $\log _2(1/p)$ bit。Bloom filter 用 ${1.44\cdot \log _2(1/p)}$ ，只比这个下界多 44%（因子 ${1/\ln 2 \approx 1.44}$ ）——换不存元素、O(k) 查询的代价，这点开销几乎可以忽略，所以说它近乎最优。

一个反直觉的点：最优 k 只和 p 有关，与装多少 (n) 无关。把最优 m 代回 $k=(m/n)\cdot \ln 2$ 会得到 $k = \log _2(1/p)$ 。原因：最优配置下每个 bit 恰好有 一半概率为 1，此时 $p = 2^(-k)$ ，反解即得。所以「目标 1% → k≈7」「0.1% → k≈10」是定死的，跟你打算装一万个还是十亿个毫无关系。

5.3 · 不能删除 → 计数型 Bloom filter

普通 Bloom 删元素会清错别人的位、造成漏报。计数型 Bloom filter 把每格从 1 bit 换成一个小计数器:add 时 +1、remove 时 −1，查询看是否都 > 0。代价是空间变几倍（每格 ~4 bit）。试试 add / remove:

还有更省的删法：Deletable Bloom filter (DlBF)。counting BF 删除安全但每格要 ~4 bit、空间翻几倍。DlBF 折中：把位数组切成 r 个 region，另用一张很小的 collision bitmap 标记「哪些 region 发生过多个元素的位重叠」。删除时，只有那些没卷入碰撞的位才允许清 0——于是一部分元素可删、一部分不可删，但永远不会误清而破坏「不漏报」。代价远小于 counting BF，适合「能删一部分就够」的场景。

5.4 · 它都用在哪儿

场景	怎么用
缓存穿透防护	先问 Bloom「这个 key 可能存在吗」，说「不在」直接返回，避免每次都打到 DB
爬虫 URL 去重	几十亿 URL「这条爬过没」，Bloom 说「没」就放心抓
数据库 (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 不上」的行过滤掉，再做 join，省 shuffle
CDN 缓存	过滤 one-hit wonder（只被访问一次的对象）：第二次见到才缓存，Bloom 记「这个 URL 见过没」
弱口令 / 黑名单	判断密码是否在泄露库里，不必下载整个库
推荐 / 去重	「这条内容给该用户推过没」，省内存地过滤已读

**内存节省的量级（推荐去重的估算）：**1000 万用户 × 每人记 5000 条已读文章，用 hash set 精确存大约要 600–800 GB；换成每用户一个误判率 1% 的 Bloom filter（每条 ~9.6 bit），总量降到 ~60 GB 量级——约 节省 90%，代价只是偶尔把一条没推过的当成推过（漏推一条，影响有限）。

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

**一点历史：**Bloom filter 由 Burton Howard Bloom 于 1970 年提出，最初是为了在内存吃紧时做拼写检查的词典查找。半个世纪后，它成了数据库、分布式系统、网络里随处可见的基础结构。

和别的系列串起来看：字符串查找里 Trie 精确回答「这个词在不在字典」、BK-tree 做容错查询；Bloom filter 则用概率把同一个「在不在」压进一排 bit。它和 Rabin-Karp 一样，核心都是哈希。