1.2 Hash table 与 collision 策略

当 ADT、pointer 与基本 node 结构已经建立之后，下一个问题就是：怎样高效 支持 dictionary 类操作？Hash table 是其中一个标准答案。它不保留排序结构， 而是先用 hash function 把 key 跳到某个 bucket。

这个跳转很有力，但永远不会完美。整章内容都在解释：这个跳转可以保证什么、 collision 怎样出现，以及当多个 key 撞进同一位置时，实现怎样补救。

动机

先列出 hash table 需要支持的 dictionary 操作：

• 为某个 key 插入 value；
• 按 key 找回 value；
• 删除已有的 key-value entry。

所以逻辑对象首先是 dictionary 或 symbol table。Hash table 只是实现这个 ADT 的其中一种方法。

这个定义已经暗示两条设计线：

• key 怎样被转成 bucket index；
• 如果两个 key 去到同一个 index，实作会怎样处理。

Hash function 应该做什么

一个好 hash function 应具备四点：

• 永远返回合法 bucket index；
• 尽量减少 collision；
• 尽量平均分散 key；
• 计算本身要足够快。

最后一点不能忽略，因为如果 hash 规则本身太慢，就算分散效果好，lookup 也未必值得。

int Hash(char *s, int nBuckets) {
   int h = 0;
   while (*s != '\0') {
      h += *s;
      s++;
   }
   return h % nBuckets;
}

Collision 不是例外，而是常态

只要 bucket 数量有限，而 key 空间足够大，collision 就几乎无可避免。所以 真正要问的不是“如何完全避免 collision”，而是“有 collision 时仍然如何 保持 dictionary 正确”。

观看 collision handling 如何保持 dictionary 正确

下面的短图解会保留 ADT contract，同时比较两种主要补救方式。Hashing 只决定从哪里开始搜索；chaining 与 probing 则解释 table 如何在 collision 之后仍不混淆不同 key。

Chaining：在 bucket 下面挂一条链

Chaining 把碰撞的 entry 保留在 bucket 旁边的 linked list 中。

这个做法与上一节的 pointer / node 模型完全配合：

typedef struct cellT {
   char *key;
   void *value;
   struct cellT *next;
} cellT;

因此 lookup 可以分成两层：

1. 先 hash key，选出 bucket；
2. 再只扫描该 bucket 下面的 linked list。

Open addressing：不用链，而是继续 probing

Open addressing 把所有 entry 留在 table 内。它不是在 bucket 下面挂 linked list， 而是在首选 slot 被占用时，继续到 table 内其他位置 probing。

常见 probing 方式包括：

• linear probing；
• quadratic probing；
• double hashing。

与 chaining 最大的区别是：额外工作发生在哪里。

• chaining 把 collision 放到 bucket 旁边的 linked structure；
• open addressing 把 collision 变成 table 内部的续搜。

所以 clustering 与 probe sequence 设计就变得很重要。Deletion 还需要额外规则 来保持 probe path；本节把 delete 列为 ADT 操作，但不展开这个独立 invariant。

Load factor 为什么重要

即使 hash function 本身不差，只要 table 太满，效能都会变坏。

设 table 中有 n 个 entry、m 个 bucket，load factor 通常写成

对 chaining 来说，n 可以大于 m，所以 $\alpha$ 可以大于 1。对 open addressing 来说，每个 slot 最多存一个 live entry，因此 $0 \le \alpha \le 1$；要插入新的 key，不但要有 $\alpha < 1$，probe sequence 还必须真的能够到达空 slot。

定理 / 命题

证明思路

在 chaining 中，各条 bucket chain 把 n 个 entry 划分开来：每个 entry 恰好属于一条 chain。因此，把所有 chain length 相加会把每个 entry 计算一次， 得到 $\sum_j\ell_j=n$；再除以 m，就得到平均 occupancy $\alpha$。

这是一个确定性的计数恒等式，本身并不能保证 lookup 是常数时间。要得到 $O(1+\alpha)$ 这类期望界，还需要适当的 hash function 或 key distribution 假设。没有这个假设时，即使 load factor 很小，也可能出现一条很长的 chain。

当 table 的 load 增加时：

• chaining 的平均 chain length 严格等于 $\alpha$，但各条 chain 的实际长度 取决于 key 的分布；
• 当 $\alpha$ 接近 1 时，open addressing 的 probe sequence 通常会变长， 而且仍要满足 probe coverage 条件；
• 如果分布或 load 没有受到控制，平均 lookup 会偏离理想的常数时间。

所以 resize 不只是工程细节，也是保护 hashtable 效能模型的一部分。

Generic pointer 让 ADT 可复用

下面的 C interface 使用 void * 作为 value，这是一个重要的 ADT 设计选择。

typedef struct hashtableCDT *hashtableADT;

hashtableADT EmptyHashtable();
void Enter(hashtableADT table, char *key, void *value);
void *Lookup(hashtableADT table, char *key);

Table 本身不需要知道 value 的具体类型。它只需要维持 key 与某个 opaque pointer 之间的关联，而真正怎样解释那个 pointer，则由 client 决定。

常见错误

快速检查

练习

更仔细地读 implementation

读 implementation 时，先明确 ADT contract，再检查 bucket 布局。Contract 规定了每种存放方式都必须实现的 dictionary 操作。

这个 overwrite 行为很容易被忽略，但它正是为什么这个 ADT 是 dictionary， 而不是 multiset。

为什么 hashing 之后还要比较 key

Hashing 只是缩小搜索范围，不是完成搜索。这个直觉在 collision 章节里最重要。

如果两个 key 落到同一个 bucket，table 仍然要比较存进去的 key 和查询 key 是 不是完全一样。否则就分不清是真命中，还是只是碰巧落在同一个 bucket。

Chaining 的好处是把 collision structure 分开存

最直观的 collision strategy 就是 chaining。每个 bucket 指向一条 linked list， 所有 hash 到同一个 bucket 的 entry 都挂在同一条 chain 上。

这种做法有一个实际好处：chain 里面的顺序不是 dictionary contract 的一部分。 你可以把新 entry 放前、放后，或者按别的稳定规则插入，只要 lookup 和 overwrite 行为正确，ADT 就仍然成立。

Open addressing：不用链，而是继续 probing

Open addressing 不是在 bucket 下面挂 linked list，而是当首选 slot 已经被 占用时，继续在 table 内找下一个位置。

Collision 的成本因此转移到 probing rule 本身。

• linear probing 会检查下一格，再下一格，一路向前；
• quadratic probing 会跳平方步；
• double hashing 会用第二个 hash function 产生 step size。

Linear probing 很容易形成一长串连续 filled buckets。这个现象 叫 primary clustering。cluster 越长，之后的 probe 就越容易撞到同一段区域， 性能也就越差。

Quadratic probing 就是针对这个问题。

设 table size 为 10、h(k) = k % 10，第二个 hash 为 $s(k)=7-(k\bmod 7)$。对 key 23，step 为 $s(23)=7-(23\bmod 7)=5$。从 bucket 3 开始时，因为 $\gcd(5,10)=5$，probe 只会在 3 与 8 之间循环；如果两格都已被占用， 它就无法到达其他空 slot。合适的第二个 hash 可以让 probe 分布更好，但 table size 与 step rule 必须一起设计。

Rehashing 是改 table 形状的代价

当 bucket 数量改变时，从 hash code 缩减到 bucket index 的规则也会改变。 即使底层 hash-code computation 保持不变，原本已经存进去的 entry 仍要按新的 bucket rule 重新放置。这个过程叫 rehashing。

在固定容量的实现中，rehashing 可能不常发生；但概念上一定要理解， 因为它说明会增长的 hash table 不是一个固定不变的 memory picture。

怎么选 chaining、linear probing、quadratic probing、double hashing

没有一个方案永远最好；选择时需要比较各自的 tradeoff。

• Chaining 容易理解，而且用 linked list 就能处理 collision。
• Linear probing 简单，但容易出现 primary clustering。
• Quadratic probing 可以减少 clustering，但对 load factor 更敏感。
• Double hashing 通常 probe 分散得更好，但因为要第二个 hash function，所以更 贵、更复杂。

如果你在读 C code，最安全的问题不是“理论上哪个最快？”而是“这个 table 的 size、load 和 update pattern，究竟更适合哪种策略？”

总结

读 code 时，可以先用下面这份简短 checklist：

1. key 是什么，value 是什么？
2. Enter 遇到已经存在的 key 时会怎样？
3. lookup 之后有没有再比较 stored key？
4. collision 是由 chain 处理，还是由 probe sequence 处理，或者两者都有？
5. table 太满时会发生什么？

如果这五个答案清楚，hash table implementation 就会容易得多。

更多练习