1.2 Hash table 与 collision 策略

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

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

仍然要先从 ADT 角度开始

Hashtable tutorial 仍然先从操作出发，而不是先从 bucket 出发：

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

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

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

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

Hash function 应该做什么

本地 tutorial 特别强调一个好 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 正确”。

Chaining：在 bucket 下面挂一条链

Lecture material 用 chaining 作为最直观的补救方法。

这个做法与上一节的 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

Tutorial 也介绍 open addressing。它不是在 bucket 下面挂 linked list， 而是在首选 slot 被占用时，继续到 table 内其他位置 probing。

常见 probing 方式包括：

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

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

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

所以 deletion、clustering 与 probe sequence 设计就变得很重要。

Load factor 为什么重要

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

Load factor 通常写成

当 $\alpha$ 上升时：

• chaining 的链会变长；
• open addressing 的 probe sequence 会变长；
• 平均情况下的 lookup 会慢慢偏离理想的常数时间。

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

Generic pointer 让 ADT 可复用

本地 hashtable lecture 使用 $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

Lecture 其实不是先讲 bucket，而是先讲 ADT contract。这个顺序很重要，因为 hash table 首先是 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

Tutorial 和 lecture 都讲了 open addressing。这种方法不是在 bucket 下面挂 linked list，而是当首选 slot 已经被占用时，继续在 table 里寻找下一个位置。

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

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

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

Quadratic probing 就是针对这个问题。

这就是 CSCI2520 很典型的 tradeoff：更精细的规则可以换来更好的分布，但实现 也会更复杂。

Rehashing 是改 table 形状的代价

当 bucket 数量改变时，hash function 也要跟着改。原本已经存进去的 entry，就要 用新 rule 再插一次。这个过程叫 rehashing。

Lecture 也提醒过，rehashing 对大多数应用来说并不常见，但概念上一定要理解， 因为它说明 hash table 不是一个固定不变的 memory picture。

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

Source material 并不是叫你选一个“永远最好”的方案，而是要你看懂 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 时先问这几件事

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

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

更多练习