第 17 章

布隆过滤器——1970年，一位科学家为什么故意发明一种会判断错误的数据结构？

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1970—2026年 · 概率数据结构、哈希函数、位图、数据库索引与近似成员查询1970年7月，美国。《Communications of the ACM》刊登了一篇只有五页的论文。标题是：Space/Time Trade-offs in Hash Coding with Allowable Errors《允许错误的哈希编码中的空间与时间权衡》。作者是一位在 Computer Usage Company 工作的研究人员：Burton H. Bloom。这篇论文提出一个反直觉的问题：假设计算机需要判断一个字符串是否属于一个庞大的集合。如果允许极少数情况下，把一个实际上不存在的字符串误认为可能存在，能否换取大幅度的内存节省？今天我们习惯于认为，程序应该尽可能准确。集合查询尤其如此。如果查询：

"user:10086" in users

我们理所当然地希望获得绝对正确的 True 或 False。但 Bloom 却提出：有些场景根本不需要每一次判断都绝对准确。我们真正需要的是，以极低的成本排除绝大多数不可能存在的数据。他的研究后来成为概率数据结构发展史上的经典成果。^{[DBLP][OpenAIRE - Explore]}而这次，我们要了解的不仅是一种位数组技巧，还包括一个重要的系统设计观念：如果错误的代价不对称，就不一定需要在每一步付出获得绝对准确性的全部成本。

第一幕：为什么“不存在”比“存在”更值得快速判断？

让我们暂时回到1970年的计算环境。当时，主存昂贵，外部存储访问也存在明显的时间成本。假设有一百万条已经保存的记录。程序会不断收到查询请求：“这个编号存在吗？”“这个单词在词典里吗？”“这个消息是不是集合中的一个成员？”最直接的方法是保存一张完整的哈希表。查询时，利用哈希函数找到记录，并比较完整内容。这种办法当然可以准确判断。但完整哈希表需要存储键、指针、元数据或其他信息。对于非常大的集合，主存成本可能很高。而 Bloom 在论文中讨论了一种具有特定特点的应用：绝大多数被查询的消息，其实并不属于目标集合。原论文特别强调 reject time，即拒绝非成员消息所需的时间。因为如果绝大多数查询最终都是“不存在”，我们就有机会通过一种非常紧凑的结构，快速排除它们。^{[jameshunt(.us)]}

用一个现代数据库场景来理解

假设有100万个用户编号，存储在磁盘上的数据库文件里。现在收到一个查询：

user:987654321

这个用户编号根本不存在。如果我们能够在内存中用一个极小的结构，快速确定它不可能在文件中，那么就没有必要再读取磁盘。但是，如果这个小结构说：“它可能存在。”怎么办？没关系。再去数据库查一次。如果存在，就正常返回。如果不存在，只是多进行了一次本来可以避免的查询。于是我们得到了两个完全不同的错误代价。

过滤器结论	后续处理	结果
肯定不存在	直接跳过昂贵查询	节省时间
可能存在	继续查询真实数据	仍可得到准确结果

真正重要的是：只要过滤器不会把已经插入的元素判定为不存在，我们就能够利用它安全地提前拒绝一些查询。这就是布隆过滤器的核心应用模式。

第二幕：一百万个字符串，能不能只用一小块位数组表示？

在第四章《哈希表》中，我们已经了解：哈希函数可以把一个字符串映射为某个数值。例如：

hash("Alice") → 12345678

如果需要把它映射到一个固定大小的空间：

h(x)\bmod m

就可以得到一个数组下标。普通哈希表会在相应位置存储键、值或关联信息。但 Bloom 的方法更加极端。根本不保存原始字符串，只保存几个比特位。假设现在只有16个 bit。初始状态：

一个16 bit的布隆过滤器

0

仅16个比特，也就是2个字节。现在全部为0。

接下来，我们准备插入字符串：Alice不使用一个哈希函数。而是使用三个哈希函数：

h_1,\ h_2,\ h_3

假设它们得到的位置分别是：

2,\ 7,\ 13

那我们只需要：把第2、7、13位设为1。不会储存 Alice 这五个字母。也不会储存它的长度。更不会储存完整的用户对象。现在，再插入 Bob。假设得到：

4,\ 7,\ 11

那么，把第4、7、11位也设为1。其中第7位已经是1。不需要做任何特别处理，继续保持1即可。这就是布隆过滤器的插入操作。整个过程只有：计算哈希 → 设置位。没有链表。没有开放寻址冲突处理。也不需要保存完整键值。这是一种非常激进的空间换准确度方案。

第三幕：亲手制造一次误判

这一幕我们不使用抽象公式。我们直接做实验。准备一个24 bit的布隆过滤器。每个元素使用三个哈希位置。为了保证实验过程可复现，下面使用教学用的确定性字符哈希函数，而不是依赖浏览器随机数。你可以依次加入几个名字，然后查询其他没有加入的名字。

Bloom Filter 实验室

24 bit · 3个哈希函数 · 允许误判

2 个元素

选择要插入的字符串

位数组状态

0

1

0

1

0

1

0

1

0

1

0

1

0

蓝色表示被已有元素置1；带强调边框的格子是当前查询检查的位置。

查询哪个元素？

h1 = 13h2 = 4h3 = 7

过滤器：肯定不存在真实集合：没有插入，正确排除。

这个实验最重要的发现是：某个从未插入的字符串，仍然可能对应三个全部为1的比特位置。因为这些比特可能分别由其他字符串设置。过滤器无法分辨它们究竟来自同一个元素，还是来自不同元素。这就产生了：False Positive（假阳性，误判存在）。但反过来呢？假设你已经插入了 Alice。插入操作一定把它对应的三个位置全部设为1。只要之后没有删除或清空这些位，并且查询时使用同样的哈希函数，那么检查 Alice 时，这三个位置必然仍然是1。因此，标准布隆过滤器具有一个非常重要的性质：没有假阴性（False Negative）。也就是说，它不会把一个确实插入过且尚在有效集合中的元素判定为不存在。当然，这依赖位数组未损坏、参数一致、更新正确，以及没有错误删除等前提。

第四幕：为什么计算机敢回答“肯定没有”，却不敢回答“肯定存在”？

让我们把刚才的实验形式化。假设集合：

S=\{A,B,C\}

对每个元素计算

k

个哈希位置。插入时把这些位设为1。现在查询元素

x

。

情况一：至少一个位置是0

假设：

h_1(x)=3

h_2(x)=9

h_3(x)=15

但位数组中：

bit[9] = 0

那么我们可以立即得出：

\boxed{x\notin S}

为什么？因为如果

x

曾经被插入，插入过程一定会把第9位设为1。现在它仍然为0。这与“已经插入过”矛盾。所以，当前查询元素肯定没有被加入过。

情况二：全部位置都是1

如果三个位置全部为1，我们能够证明什么？只能证明：这些位置曾经被某些元素设置过。但不能证明：它们一定是由同一个元素

x

设置的。这就是误判的来源。你可以把布隆过滤器理解为一种只保存“被访问过的哈希位置痕迹”的结构。它不是完整集合。它丢弃了大量信息。因此，某些不同集合在过滤器中可能得到完全相同的位图。既然信息被主动丢弃，想要再从位图恢复每一个真实元素，自然不可能。这也解释了为什么：标准布隆过滤器不能可靠地枚举所有元素，也不能直接删除单个元素。如果一个元素与其他元素共享某个已经设置为1的位，直接把它清零，就可能让另一个原本存在的元素出现假阴性。后来出现的计数布隆过滤器（Counting Bloom Filter）通过计数器等机制，为删除提供了一种解决路线，但它需要更多空间和额外的正确性约束。

第五幕：1970年论文真正研究的是一种权衡，而不是魔术

Burton H. Bloom 的原始论文

Space/Time Trade-offs in Hash Coding with Allowable ErrorsCommunications of the ACM，1970年7月，第13卷第7期，第422—426页。Bloom 当时的机构署名是 Computer Usage Company，位于美国马萨诸塞州 Newton Upper Falls。阅读1970年原始论文 PDF

这篇论文并不是简单给出“用多个哈希函数设置位数组”的一页说明。Bloom 比较了传统哈希编码与两种允许不同错误行为的新方法。他关心的计算因素包括：存储区域大小。对不存在元素进行拒绝判断所需的时间。以及允许发生错误的比例。尤其重要的是，论文考虑了“查询中绝大多数消息不属于集合”的情形。在这样的工作负载下，如果少量非成员被误判为成员，我们依然可以通过后续精确检查纠正结果。但只要绝大多数非成员能够被快速拒绝，整体性能就可能显著改善。^{[jameshunt(.us)]}这其实是一种相当现代的系统设计思想。很多时候，我们并不需要让每一个子模块都提供最终答案。只要它能够便宜地排除大多数不可能性，就已经很有价值。你可以把它看成：便宜的第一道筛选 + 昂贵但精确的第二道验证。与数据库索引、缓存预检和查询优化器的思想相当接近。

第六幕：三个哈希函数好，还是十个哈希函数好？

现在我们进入本章最重要的数学部分。假设：

m

：位数组的总位数。

n

：插入的元素数量。

k

：每个元素使用的哈希函数数量。直觉上，你可能觉得：哈希函数越多，查询就越准确。因为每个元素要检查更多的位置。一个不存在的元素，想让所有位置恰好都是1，似乎更困难。但我们忽略了另一面。每增加一个哈希函数，插入时就会额外把一些位设为1。如果哈希函数太多，位数组会迅速被填满。等到绝大多数位都是1时，任何查询都有很高概率通过检查。所以：哈希函数太少，不行。哈希函数太多，也不行。中间存在一个最佳值。

第一步：一个比特仍然是0的概率

假设哈希位置近似均匀、独立。一次哈希命中某个指定位置的概率是：

\frac1m

没有命中它的概率：

1-\frac1m

插入

n

个元素，每个使用

k

次哈希，总共有

kn

次设置操作。那么某一指定比特始终没有被命中的概率为：

P_0=\left(1-\frac1m\right)^{kn}

当

m

足够大时，可以近似为：

P_0\approx e^{-kn/m}

因此，这个比特已经被设置为1的概率：

P_1\approx1-e^{-kn/m}

第二步：查询时全部 k 个位置都是1

如果查询一个没有被插入的元素，且近似把它的

k

个探测位视为独立，那么误判概率为：

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

这就是经典的布隆过滤器误判率公式。这里必须明确：它是常见的概率近似，不是对任意实际哈希函数和所有有限规模过滤器都严格精确的恒等式。位之间的相关性、哈希实现和有限空间效应都会影响实际误判概率。^{[boost.org][cse.usf.edu]}

第三步：求出最佳哈希函数数量

对上面的近似误判率进行优化，可以得到：

\boxed{k_{\mathrm{opt}}\approx\frac mn\ln2}

由于哈希函数数量必须是整数，实际要选择适当的整数值。最有趣的是：在最优位置附近，位数组中大约有一半位置是1。这意味着：最佳的布隆过滤器，并不是尽量把所有位填满，而是保持一个合适的0/1分布。

第七幕：亲自计算最佳哈希函数数量

我们做一次完整的参数实验。假设计划存储10万个元素。过滤器分配100万 bit。那么每个元素的平均位预算是：

\frac mn=10

最优哈希函数数量约为：

k_{\mathrm{opt}}=10\ln2\approx6.93

因此通常选择7个哈希函数。此时误判率约为：

p\approx\left(1-e^{-7/10}\right)^7

约为：

0.82\%

也就是说，平均每1000次针对不存在元素的查询，大约有8次会被过滤器误判为“可能存在”，仍需执行后续精确查询。其余大约992次能够被提前拒绝。

实验：三个参数怎样相互影响？

布隆过滤器参数实验室

内存、哈希次数与误判概率

概率模型

预计存储元素数 n100,000

每元素分配 bit 数 m/n10

哈希函数数量 k7

位数组内存

122.1 KiB

当前理论误判率

0.819%

建议哈希函数数

7

建议参数的误判率

0.819%

查看图表数据

k	误判率
1	9.516
2	3.286
3	1.741
4	1.181
5	0.943
6	0.844
7	0.819
8	0.846
9	0.915
10	1.019
11	1.154
12	1.316
13	1.502
14	1.712
15	1.943
16	2.195

上图展示固定10 bit/元素时的典型曲线。上方参数卡片则随滑块实时更新。理论误判率使用经典大规模独立哈希近似。

观察这个模型，你会发现三个规律。首先，预计元素数量

n

增大，如果希望维持同样的误判率，总位数

m

也必须按比例增加。其次，每元素分配的 bit 越多，通常就有机会实现越低的误判率。最后，哈希次数并不是越多越好。当位数组不断饱和，进一步增加哈希函数，反而可能让误判率提高。这一点与第九章 Huffman 的贪心证明有相似之处：看起来直觉上合理的局部增加，并不必然改善整体目标。必须用数学模型分析。

第八幕：如果要保存100万个 key，允许1%误判，需要多少内存？

这才是布隆过滤器最有工程价值的地方。我们不必先分配一个巨大数组，再猜测效果。可以直接根据预计容量和目标误判率计算参数。如果期望误判概率为

p

，插入元素数为

n

，则在经典近似模型下：

\boxed{m\approx-\frac{n\ln p}{(\ln2)^2}}

再得到：

\boxed{k\approx\frac mn\ln2}

现在设：

n=1,000,000

p=0.01

那么：

m\approx9,585,059\text{ bit}

换算成字节：

\frac m8\approx1,198,133\text{ bytes}

也就是大约：

\boxed{1.14\text{ MiB}}

同时：

k\approx6.64

通常选取7个哈希函数。

100万个键 · 目标误判率1%

预计所需内存

1.14 MiB

哈希函数数

7

如果完整键平均占用几十字节，再加上哈希表的槽位、指针和其他元数据，那么完整精确集合可能需要数十 MiB 甚至更多内存。布隆过滤器以约1.14 MiB的位图换取可控误判。这里只计算位数组主体，不包括对象包装、配置元数据和存储格式开销。不是完整精确集合与布隆过滤器的严格基准测试。

但是，这个1.14 MiB不是无限容量。如果最初按照100万个元素设计，却不断往里面加入数据，直到插入200万个元素，那么位数组会更拥挤。实际误判率可能明显高于原来的1%。所以必须提前进行容量规划。对于会持续增长的集合，可以考虑重建过滤器、分层过滤器或可扩展布隆过滤器等方案。另外，目标误判率是关于不存在元素的查询的概率，而不是说所有查询里恰好有1%会得到错误结果。如果查询中有90%本来就存在，那么误判只可能发生在剩下10%的不存在查询里。这对评估真实系统收益非常重要。

第九幕：RocksDB 为什么愿意把这种“不完全准确”的结构用于数据库？

现在，我们来看一个真实的工业级实现。RocksDB 是一种广泛使用的嵌入式键值存储引擎。它基于 LSM Tree（日志结构合并树）组织数据。数据会逐渐从内存结构写入磁盘上的 SST 文件（Sorted String Table）。但这引发一个问题。如果某个 key 不存在，查询引擎可能需要检查多个候选 SST 文件。如果每个文件都要读取数据块，I/O 成本会很高。于是 RocksDB 可以为 SST 文件构建 Bloom Filter。在查询某个 key 时，先检查过滤器。如果过滤器显示肯定不存在，就避免进一步读取该文件的数据块。如果显示可能存在，再执行正常查找。官方 RocksDB 文档明确介绍了这种用途。^[GitHub]

为什么允许误判并不会破坏数据库正确性？

因为过滤器不是最终的数据来源。例如：用户查询：

order:20261027:001

过滤器返回：“可能存在。”但 SST 文件里实际上没有。数据库继续检查真正的数据结构，最后返回不存在。整个数据库结果仍然是正确的。误判只增加了一次不必要的查询成本。而当过滤器返回：“肯定不存在。”数据库就可以直接跳过对应文件。只要过滤器维护正确，就不会漏掉该文件真实存在的键。这是一个非常漂亮的系统设计。允许第一道筛选不精确，但不能允许它错误地排除真实结果。

RocksDB 的工程优化并不止于此

如果一个普通布隆过滤器需要访问

k

个相距很远的内存位置，那么即使总内存占用很小，也可能造成多个 CPU Cache Miss。所以 RocksDB 还采用了块化过滤器、Full Filter 等设计，并针对 CPU 缓存局部性进行优化。官方文档甚至介绍了 Ribbon Filter 这种替代结构，在特定工作负载下可以以更多 CPU 工作换取更低的过滤器内存成本。这说明我们在算法课程里讲的：

O(k)

查询时间，只是理论层面的开始。在工业系统里，缓存行、内存访问布局和实际查询分布同样重要。^{[GitHub][GitHub]}

第十幕：布隆过滤器究竟适合哪些场景？

现在我们把它放回实际软件工程。

场景一：数据库避免无效磁盘读取

这是前面 RocksDB 的典型场景。大量 key 根本不在某个文件中。过滤器能够快速拒绝，减少 I/O。

场景二：缓存穿透保护

假设用户不断访问根本不存在的商品编号。如果每次都穿透缓存访问数据库，可能产生不必要的压力。布隆过滤器可以帮助拦截一部分确定不存在的 key。但在动态业务系统中，必须正确处理新增商品、数据同步以及过滤器过期问题。否则，错误的维护方式可能导致真正存在的商品被误判为不存在。而且过滤器不能代替数据库，也不能单独构成完整的安全防护机制。

场景三：重复处理的预筛选

假设一个爬虫已经见过数百万个 URL。现在又遇到一个 URL。布隆过滤器可以快速判断：“它肯定没有被加入过。”或者：“它可能加入过。”如果需要严格避免漏抓，仍然应该对“可能加入过”的 URL 进行精确确认。因为如果直接把误判当成真正的重复，就可能跳过一条从未访问过的网页。在这种业务里，假阳性会直接转化为业务层面的漏处理。因此，是否允许这种行为，取决于业务要求。

场景四：分布式存储预检

在一些分布式系统中，服务器可以使用紧凑的过滤器，帮助其他节点判断自己是否可能持有某些键。但 Bloom Filter 不负责节点故障处理、数据一致性或副本同步。它只是一种近似成员查询工具。不能因为它出现在分布式系统里，就把它与 Raft、一致性哈希或完整的数据路由机制混为一谈。

第十一幕：自己写一个 Python 布隆过滤器

现在进入编程实践。我们使用标准库：hashlib来生成稳定的哈希值。但为了避免为每个元素完整计算多个不同的密码学哈希，可以采用双重哈希（Double Hashing）思路：

h_i(x)=(h_1(x)+i h_2(x))\bmod m

这是一种常见的实现策略。真实工业级布隆过滤器还会针对哈希质量、位分布和性能进行更细致的设计。

Python 实现

import math
import hashlib


class BloomFilter:
    def __init__(self, capacity, error_rate=0.01):
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        if not 0 < error_rate < 1:
            raise ValueError("invalid error rate")

        self.capacity = capacity
        self.error_rate = error_rate

        self.m = math.ceil(
            -capacity * math.log(error_rate)
            / math.log(2) ** 2
        )

        self.k = max(
            1,
            round(self.m / capacity * math.log(2))
        )

        self.bits = bytearray((self.m + 7) // 8)
        self.count = 0

    def _hashes(self, key):
        data = key.encode("utf-8")

        digest = hashlib.sha256(data).digest()

        h1 = int.from_bytes(digest[:8], "big")
        h2 = int.from_bytes(digest[8:16], "big")

        # 让步长不为零
        h2 = h2 or 1

        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, key):
        for pos in self._hashes(key):
            byte_index = pos // 8
            bit_index = pos % 8

            self.bits[byte_index] |= (1 << bit_index)

        self.count += 1

    def might_contain(self, key):
        for pos in self._hashes(key):
            byte_index = pos // 8
            bit_index = pos % 8

            if not (
                self.bits[byte_index] & (1 << bit_index)
            ):
                return False

        return True

使用方法：

bf = BloomFilter(
    capacity=1_000_000,
    error_rate=0.01
)

bf.add("user:100")
bf.add("user:200")
bf.add("user:300")

print(bf.might_contain("user:100"))
# True

print(bf.might_contain("user:999"))
# 通常 False，也可能 True

特别注意：might_contain() 这个命名是故意的。它不叫：

contains()

因为那样可能让使用者误以为结果就是精确集合成员关系。might_contain() 明确表达：True 只是可能存在。此外，这个教学实现还有几项限制：它不支持单元素删除。它没有持久化格式。count 记录的是插入调用次数，不是去重后的真实元素数。它也没有为接近或超过设计容量的情况自动扩容。更重要的是，双重哈希生成的位置并不完全独立，所以实际误判率应通过测试验证，而不是仅凭经典公式断言精确等于目标值。这些正是把教学算法升级为生产代码时需要处理的细节。

第十二幕：它为什么不能像哈希表一样随意删除？

这是布隆过滤器最著名的限制之一。假设：A 对应位置：2、5、9B 对应位置：5、7、11注意，它们共同使用第5位。如果我们删除 A，并把它的三个位置：2、5、9全部清零，会发生什么？B 本来需要第5位为1。现在第5位被清零。于是查询 B 的时候，过滤器发现一个0，竟然回答：“B 肯定不存在。”但 B 明明已经插入。这产生了假阴性。所以标准布隆过滤器不能简单地通过清零来删除单个元素。

解决方法：把位变成计数器

后来发展出了 Counting Bloom Filter（计数布隆过滤器）。它不再为每个位置只保存0或1。而是保存一个计数。例如：

位置 2 → 1
位置 5 → 2
位置 7 → 1
位置 9 → 1
位置11 → 1

删除 A 时：把 A 对应位置的计数减1。于是第5位从2变成1。B 仍然能够通过查询。当然，这也带来了代价。每个位置不再只占1 bit。还要考虑计数器溢出、并发操作及错误删除等问题。因此，没有一种结构能在准确性、内存、速度、动态更新上同时免费获得全部优点。这再次回到了 Bloom 1970年论文的主题：Space / Time Trade-offs——空间与时间之间的权衡。

终章挑战：哪一种错误可以接受？

假设你正在设计一个数据库查询系统。过滤器负责判断：“某个磁盘文件里是否可能存在指定 key。”真正的数据库文件始终保留，并且可以进行精确查询。你只能选择以下两种错误中的一种。

你会允许哪一种错误？

把不存在的 key 误判为可能存在把真实存在的 key 误判为不存在两种错误都可以，反正后面还有数据库

这道题比记住布隆过滤器公式更加重要。因为它决定你是否真正理解：算法能否允许误判，不取决于我们是否喜欢概率，而取决于不同错误会给系统造成什么后果。

尾声：一位研究者用五页论文，教会计算机有选择地保留信息

1970年，Burton H. Bloom 研究的是哈希编码中的空间、时间和错误率。他发现，如果系统的目标是快速排除大量不属于集合的消息，那么不必在内存中完整保存每个元素。使用一块位数组、多个哈希函数，再接受可控的假阳性，就可能节省大量存储资源。此后，布隆过滤器进入数据库、缓存、网络服务和大规模数据处理中。如今，它甚至还有许多衍生结构：Counting Bloom Filter。Blocked Bloom Filter。Scalable Bloom Filter。Cuckoo Filter。Xor Filter。Ribbon Filter。它们在准确率、空间、查询速度和动态更新之间进行不同权衡。这并不意味着原始布隆过滤器已经过时。恰恰相反。它至今仍然是理解概率数据结构最优雅的入口之一。而这一章与前面课程的联系也越来越清楚了。第四章的哈希表，追求精确查找。第十五章的一致性哈希，追求映射规则在集群成员变化时保持稳定。第十七章的布隆过滤器，则主动放弃部分精确信息，以换取极低的空间开销和快速排除能力。虽然名字里都有 Hash，但它们解决的是完全不同的问题。算法设计不只是追求更快，还要判断：究竟有哪些信息和保证，是当前任务真正需要的。

第十七章知识总结

概念	核心思想
Bloom Filter	利用位数组与多个哈希函数进行近似成员判断
False Positive	不存在的元素被误判为可能存在
False Negative	标准正确维护的布隆过滤器不会出现
Bit Array	用极少的 bit 记录哈希位置是否被设置
$m$	位数组总位数
$n$	插入元素数量
$k$	每个元素使用的哈希次数
False Positive Rate	与 $m,n,k$ 的比例关系有关
Counting Bloom Filter	用计数器支持受约束的删除操作
SST Filter	帮助数据库避免无意义的数据块读取

本章真实历史资料

Burton H. Bloom（1970）：《Space/Time Trade-offs in Hash Coding with Allowable Errors》原始论文 ACM：1970年原论文正式发表记录 Boost Bloom 官方文档：误判率、最佳哈希次数与工程实现美国东北大学：Bloom Filter 参数计算与概率分析 RocksDB 官方文档：布隆过滤器在 SST 文件中的实际应用

下一章预告

第十八章：跳表——1989年，一位研究者为什么认为随机抛硬币可以代替复杂的平衡树？

1989年，计算机科学家 William Pugh 提出了一种非常奇妙的数据结构。它不需要像 AVL 树那样，严格维护每个节点左右子树的高度差。也不需要像红黑树那样，维护复杂的颜色与旋转规则。它只需要：一组有序链表。一些额外的快速索引层。以及一个随机数生成器。当插入一个新节点时，程序仿佛不断抛硬币。正面，就让节点再升高一层。反面，就停止。这样构建出来的结构，竟然可以在期望意义上实现：

O(\log n)

的搜索、插入与删除。它就是：Skip List，跳表。下一章，我们将从 William Pugh 的真实论文出发，了解为什么随机化可以代替一部分复杂的严格平衡操作，以及它后来如何成为 Redis 有序集合等系统中重要的数据结构设计来源。最令人惊讶的问题是：为什么一个没有强制保持完美平衡的链表，平均搜索速度却能接近平衡二叉树？