第 11 章 袋、集合、映射与哈希 — O(1) 查找的炼成Copy Anchor Link

这一章讲什么: 「查一个值在不在」这个操作的加速史:从链表的一个个比(O(n)), 到跳表的分层跳(平均 O(log n)),到位图和哈希的近乎直达(平均 O(1))。 它在全书链条里的位置:第 9 章搜索的「数据结构版答案」—— 第 9 章说「有序数组上二分 O(log n)」,本章说「换个表示,还能更快」。

1. 顶层全景Copy Anchor Link

  bag(允许重复)/ set(不允许)/ map(key→data,find 返回 data)
      │
      ├─ 有序链表:find 扫一半 → O(n);add/remove 同
      ├─ 跳表:节点带多层 next 指针,高层大步跳、逐层缩小
      │    层数靠抛硬币随机定,平均 O(log n)、最坏 O(n)
      ├─ 自组织列表:命中即移前(MTF),无理论保证,局部性场景实测好
      ├─ 位图:键=下标,find O(1);范围小、无重复、纯数字
      └─ 哈希:hash(值)→槽位
           链地址法:槽位挂链表,装得下任意多,最坏 O(n)
           开放寻址:满了顺藤摸瓜(线性探测);删除用懒惰标记
                     装载因子>0.75 翻倍重建
           双散列:冲突步长由第二个散列函数决定,不同值走不同路线
                   表长取质数 → 探测永不绕环

  图说:每一行都用「更多空间 / 更强假设 / 更复杂代码」换更快的 find。

2. 主线例子:值 22 的哈希之旅(开放寻址走查)Copy Anchor Link

表长 10,hash = value % 10。依次入表:22→槽2;04→槽4;75→槽5; 09→槽9;60→槽0。都一步到位——这就是哈希的理想态。 现在加 12:槽 2 被 22 占了,线性探测到槽 3 落座。 查 63:槽 3(12 不是)、槽 4、槽 5、槽 6——落槽 6,三次探测。 查 73:槽 3、4、5、6、7——槽 7 空,判不在。

删除的坑:直接清掉 22(槽 2 变 EMPTY)会害死对 12 的搜索 (探测到槽 2 就误以为到头)。懒惰删除:槽 2 标成 AVAILABLE—— 搜索时当它「 occupied 继续走」,插入时当它「可用直接坐」¹。

扩容时机:装载因子 = 占用槽/总槽。经验阈值 0.75——超过就建一个 两倍大的新表,把所有值重新散列进去(旧 AVAILABLE 不搬)²。 习题 11.9 给渐进式扩容:新表建好后插入只进新表,查询两表都查, 每次操作顺手搬几个旧值,搬空即切换³。

3. 核心原理Copy Anchor Link

3.1 三个 ADT 的阶梯Copy Anchor Link

bag(第 3 章已定义)add 不问重复;set 的 add 撞见已存在要「忽略或报错」 (书里倾向加的时候顺手查,比先查再加省一遍扫描)⁴。 map 是 set 的直接升级:节点里存 {key, data},find/remove 只认 key, find 命中返回 data 而不是 true——JS 的普通对象、Map、in 运算符 就是它的现成实现,书里提醒「拿对象当集合用有个坑:原型链上的键也会命中」⁵。 位图(第 6 章排序用过)在查找语境下就是 O(1) 集合,限制老三样:纯数字、范围小、无重复⁶。

3.2 有序链表与跳表:从一步步走到一层层跳Copy Anchor Link

有序链表:find/add/remove 都走同一个递归三段式—— 空或首值更大→失败/插此;等于→命中/删首;更大→递归进尾。 全部 O(n),平均扫一半⁷。

跳表(skip list) 的洞察:链表慢在不能跳;那就给每个节点多配几根 指向更远的指针。查找从最高层出发:同层向右直到会走过头,降一层继续; 底层还找不到就是真没有。期望 O(log n)——直觉与二分同构, 但不用旋转、不用平衡,层的分配交给硬币:

  新节点层数 = 连抛硬币的次数(每次 50% 升一层,封顶 MAX_LEVEL=32)
  → 约半数节点在 1 层以上,1/4 在 2 层以上,1/2³² 到顶

add 时先定层数,可能需要「加高」整个表(给 ±∞ 哨兵补指针); remove 后如果顶层空了就把表削矮。哨兵 ±∞ 消掉所有边界特判 (没有「插到最前/最后」,没有空表)⁸。 代价明写:最坏 O(n)(概率极低但存在);习题 11.4 给重建平衡的办法, 11.5 给「按秩查找」的宽度指针技巧⁹。

3.3 自组织列表:用使用模式换速度Copy Anchor Link

移前(move-to-front, MTF):无序链表,find 命中后把节点摘到头部; add 永远塞头部。理论仍是 O(n),但对「热点集中」的访问模式 (GPS 街道名缓存、临时工作集)实测大幅提速——「这不是理论优势, 是完全经验的、实用主义的优势;最坏情况你也不亏」¹⁰。 变体:与前驱交换(一次性访问不扰动大局)、计数排序式(按命中次数降序)。

3.4 哈希三方案的取舍Copy Anchor Link

两个实现细节值得记住。第一,双散列的步长函数绝不能返回 0 (否则原地打转);第二,表长取质数时,任何步长与表长互质, 探测必然遍历全表——绕环检测代码整体删除,add/find/remove 都变干净¹¹。 最坏情况三家一样 O(n)(所有值同槽);平均在键均匀、装载受控时都是 O(1)。

4. 作者的判断与证据Copy Anchor Link

• 「平均 O(1) 的代价是概率与工程」:哈希的平均性能依赖键分布均匀 和装载因子受控;两个条件书里都变成了显式机制(扩容阈值 0.75、双散列步长、 质数表长)而不是祈祷²。
• 懒惰删除被作为「开放寻址的必要复杂度」明说:不能简单清空, 否则会掐断探测链——这是教学上常被略过、实现上必踩的坑¹。
• 跳表 vs 平衡树的立场务实:不旋转、不记账,用随机换简单; 性能表老实列出「最坏 O(n)」;习题再给重建与按秩增强—— 「够用,且可以按需加固」⁸。
• MTF 的诚实边界:「完全经验的、实用主义的」,没有理论承诺; 这是全书中少数把「启发式」与「保证」分得很清的段落¹⁰。

判断(我们的,不是书里的): 本章的选型口诀可以压缩成一行: 「键可控且小→位图;内存宽裕且增删多→链地址;要省内存且增删少→ 开放寻址;探测扎堆→双散列;范围要序→跳表;访问有局部性→MTF」。 原书按历史顺序铺开,我们把它折成决策树——每个分支对应书里一个 「结构 + 性能表 + 边界」的完整单元,没有发明书外的东西。 如果错,会错在: 决策树掩盖了各结构的组合可能(如链地址+跳表桶); 且「装载因子 0.75」是经验值而非定理,把它写进口诀等于把工程惯例当规律。

5. 边界与局限Copy Anchor Link

• 哈希函数本身没展开:书里用 value % slots.length 当示例, 字符串键怎么散列、什么叫好的散列函数(雪崩、分布)没讲—— 这是「哈希教学」与「哈希工程」之间最大的缺口(补充,不在书里)。
• 一致性哈希、布隆过滤器等工程扩展缺席;渐进式扩容只在习题里勾勒。
• 跳表的随机源质量:与第 8 章同源,Math.random() 当公平硬币用。
• 链地址版在书中没有强制扩容逻辑(只一句「可以跟踪并重建」), 开放寻址版才有完整扩容代码。

6. 可带走的Copy Anchor Link

1. bag/set/map 的差别只在 add 的重复策略与 find 的返回值。
2. 有序链表=三段式递归;跳表=多层指针+抛硬币定层,哨兵消边界。
3. 跳表平均 O(log n)、最坏 O(n);MTF 无理论保证但热点场景实测好。
4. 哈希三方案:链地址(删除容易)/ 开放寻址(省空间,要懒惰删除)/ 双散列(打散聚集)。
5. 懒惰删除:AVAILABLE 对搜索算 occupied、对插入算空——一标两用。
6. 装载因子 >0.75 翻倍重建;渐进式扩容:插新查两表、顺手搬运。
7. 双散列步长永不取 0;表长取质数则探测必遍历全表,绕环检测可删。
8. 对象当集合用的原型链坑;位图查找 O(1) 但老三样限制。

7. 原文地图Copy Anchor Link