11. 位图、布隆过滤器与跳表

0. 本章先解决什么问题

前面讲的结构大多是“精确保存元素”。但高性能系统里经常有更强的约束:

• 数据量巨大。
• 内存有限。
• 只需要判断是否存在。
• 可以接受少量误判。
• 需要有序但希望实现比平衡树简单。

本章讲三个实用结构:

• 位图:用 bit 表示集合。
• 布隆过滤器:用概率换空间。
• 跳表:用多级索引实现有序查找。

它们体现的是数据结构选型中的空间、概率和层级 trade-off。

这张图怎么读

这张图把本章两个关键 trade-off 放在一起:Bloom Filter 用多个 hash 和 bit 数组做“可能存在/一定不存在”的预过滤,代价是假阳性;Skip List 用随机层级给有序链表加快速通道,代价是概率化的层级维护。

1. 位图 Bitmap

位图用一个 bit 表示一个状态。

如果要表示整数集合 {0, 2, 5}:

index: 0 1 2 3 4 5
bit:   1 0 1 0 0 1

判断 x 是否存在:

看 bit[x] 是否为 1

插入 x:

bit[x] = 1

删除 x:

bit[x] = 0

2. 位图适合什么

位图适合:

应用:

• 用户签到。
• 状态标记。
• 去重。
• 权限位。
• 大范围布尔集合。

位图不适合 key 范围极大但实际元素很少的情况,因为会浪费大量空位。

3. 布隆过滤器

布隆过滤器解决:

如何用很少空间判断一个元素是否可能存在?

它使用:

• 一个 bit 数组。
• 多个哈希函数。

插入 key:

hash1(key) -> 位置 a,置 1
hash2(key) -> 位置 b,置 1
hash3(key) -> 位置 c,置 1

查询 key:

如果这些位置都为 1:
key 可能存在
如果任一位置为 0:
key 一定不存在

4. 布隆过滤器的误判

布隆过滤器有两条核心性质:

可能误判存在
不会误判不存在

也就是:

为什么会误判?

不同 key 可能把相同 bit 位置置 1。后来查询某个未插入 key 时,它对应的位置可能刚好都被其他 key 置 1。

5. 布隆过滤器适合什么

适合:

• 先过滤明显不存在的数据。
• 减少昂贵查询。
• 大规模去重的预判断。
• 缓存穿透防护。
• 黑名单/白名单预过滤。

不适合:

• 不能接受误判的精确场景。
• 需要删除元素的普通场景。
• 需要列出所有元素。

如果需要删除,可以用计数布隆过滤器,但空间和复杂度会上升。

6. 布隆过滤器参数

误判率受这些因素影响:

布隆过滤器不是随便开个 bit 数组就结束。要根据预期元素量和可接受误判率设计参数。

机制深挖:Bloom 什么时候会失效

Bloom Filter 的误判率不是固定属性,它会随着插入元素数量变化。直觉上,bit 数组里 1 越多,未插入 key 查询时“所有 hash 位置都刚好为 1”的概率越高。

所以 Bloom 的排障指标不只是“有没有这个结构”,还要看:

• 设计容量是多少。
• 实际插入了多少。
• bit 占用率是否过高。
• 误判率是否超过业务能接受的范围。
• 是否需要重建或分层 Bloom。

一个常见工程错误是:上线初期 Bloom 很有效,数据增长后误判率上升,但系统没有容量告警。最后 Bloom 还在消耗 CPU,却已经挡不住昂贵查询。

7. 跳表 Skip List

跳表是有序链表加多级索引。

底层是完整有序链表:

1 -> 3 -> 5 -> 7 -> 9 -> 11

上层抽取部分节点作为快速通道:

查找时从高层开始:

能向右就向右
不能向右就下沉一层

平均查找成本接近 O(log n)。

8. 跳表和树的对比

跳表适合希望实现相对简单、支持有序范围的场景。

9. 跳表插入

插入时:

1. 查找插入位置。
2. 随机决定新节点层数。
3. 在每一层把它接入链表。

随机层数让高层节点数量逐层减少。

直觉:

底层所有节点
上一层约一半节点
再上一层约四分之一节点

这形成类似二分的跳跃能力。

跳表为什么要靠随机层级

跳表的目标是让高层节点逐渐变少。理想情况下:

• 第 0 层:所有节点
• 第 1 层:大约 1/2 节点
• 第 2 层:大约 1/4 节点
• 第 3 层:大约 1/8 节点

这样查找时可以先在高层快速跨过大段范围,再逐层下沉到精确位置。随机层级的意义是避免每次插入都做复杂旋转或全局调整,用概率分布维持“高层稀疏、低层完整”的结构。

但随机并不等于随便:

读跳表时要抓住一句话:它用随机层级换掉复杂旋转,用额外指针换来有序查找和范围遍历。

10. 联系实际:如何避免昂贵查询

假设有一个昂贵存储,查询一次很慢。

你可以在前面加布隆过滤器:

请求 key
-> 布隆过滤器判断
-> 一定不存在: 直接拒绝
-> 可能存在: 再查真实存储

这样可以挡掉大量明显不存在的请求。

但必须接受:

布隆过滤器说可能存在时,仍要查真实存储确认。

它是预过滤,不是最终真相。

设计卡:Bloom 负责挡掉不存在,真实存储负责确认

Bloom Filter 的正确使用方式是:

常见错误:

Skip List 的选型也要看语义:

这两个结构的共同点是:它们都不是为了“高级”,而是利用约束换工程收益。

手推:Bloom 的误判率为什么会随填满程度上升

Bloom Filter 的核心动作是:

插入一个 key -> 用 k 个 hash 函数打到 k 个 bit -> 把它们置 1
查询一个 key -> 这些 bit 都是 1,则可能存在;有任意 0,则一定不存在

当插入很少时,bit 数组里 0 很多。一个不存在的 key 查询时,只要有一个位置是 0,就能被挡掉。

当插入越来越多:

越来越多 bit 被置 1
不存在的 key 也更容易碰到全是 1 的位置

极端情况下,如果 bit 数组几乎全是 1:

任何 key 查询都会“可能存在”

这时 Bloom 仍然不会误判“不存在”,但它已经失去过滤价值。它不会给错否定,但会给太多没用的肯定。

所以 Bloom 参数不是装饰:

判断 Bloom 是否还有效,不只看有没有这个结构,还要看:

实际插入量是否超过设计容量?
bit 填充率是否过高?
误判导致的回源比例是否还能接受?

边界条件:普通 Bloom 不能直接删除

普通 Bloom 只知道某个 bit 是否为 1,不知道这个 1 是哪些 key 贡献的。

假设:

key A -> bit 3, bit 8
key B -> bit 3, bit 9

如果删除 A 时直接把 bit 3 和 bit 8 清 0:

bit 3 被清掉
key B 查询时需要 bit 3 和 bit 9 都为 1
=> B 可能被误判为不存在

这破坏了 Bloom 最重要的承诺:

不存在假阴性。

所以普通 Bloom 适合:

只增或周期性整体重建;
允许误判存在;

不需要精确删除。

如果确实需要删除,就要换模型,例如计数 Bloom 或其他可删除结构,但代价是更多空间和更新复杂度。

反例:跳表随机层级不是越高越好

新节点层级越高,查找时可跳过的范围可能越大,但它也会增加指针数量和维护成本。

如果大量节点都被提升到高层:

高层不再稀疏
每层要扫描的节点变多
空间开销增加
插入/删除要更新更多指针

如果几乎没有节点被提升:

高层太少
结构退化接近普通链表
查找要在底层走很久

跳表依赖的是概率分布形成的层级梯度:

底层完整;
越往上越稀疏;
高层负责快速跨越;

低层负责精确定位。

因此跳表的工程判断不只是“会 O(log n)”,还要问:

最大层数是否合理?
晋升概率是否匹配数据规模?
随机源是否稳定?
范围查询是否真的需要有序结构?

否则它可能既占空间,又没有得到预期的跳跃效率。

11. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 位图如何用 bit 表示集合?
2. 位图适合什么范围和 key 类型?
3. 布隆过滤器为什么能节省空间?
4. 布隆过滤器为什么会误判存在,但不会误判不存在?
5. 布隆过滤器适合放在哪些昂贵查询之前?
6. 跳表如何用多级索引加速有序链表?
7. 跳表和平衡树如何取舍?
8. 如何在空间、误判率、实现复杂度之间做 trade-off?

这些结构的重点不是“更高级”,而是它们敢于利用问题约束:整数范围、允许误判、随机层级,从而换取更好的工程成本。

延伸阅读

• skiplist
• from - zero · data-structures