从 dictionary 查询选择存储方式
Dictionary 把每个 key 对应到一个 value。若用未排序的 list 存储，查找可能需要检查每个 entry；若保持数组有序，可以用 binary search，但插入新 key 时可能需要移动大量 entry。直接用 key 作为数组下标可以省去搜索，却要求 key 属于合适的整数范围；任意字符串并不提供这样的下标。
Hash table 从 key 计算 index，只搜索分配到该位置的候选项。它不维护排序关系，以减少 lookup 与 update 的期望工作量。不过，有限 index 无法区分所有可能的 key，因此即使发生 collision，表示方式仍须保留各个不同 entry。
Dictionary 契约
定义 1.2.1
（Dictionary semantics of the table）
Hash table 是一种 dictionary。对于每个 key，表应该支持 insert、lookup 和 delete。如果同一个 key 再次插入，新的 value 应该覆盖旧的 association，而不是复制出第二份 key。
例题 1.2.2
（Enter 会更新已存在的 key）
假设 table 已经存着：
"cat" -> 3"dog" -> 8
如果再执行 Enter(table, "cat", 9)，结果不应该出现两份 "cat"。正确结果是
"cat" 对应的 association 被更新，之后 Lookup(table, "cat") 会返回 9。
Enter 为指定的 key 插入 value；如果 key 已经存在，就会 overwrite 旧 value。
用 opaque pointer 表示 value
下面的 C interface 使用 void * 表示 value，使接口不依赖 value 的具体类型。
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 决定。
从 key 计算合法 index
定义 1.2.3
（Hash function）
Hash function 会把 key 映射成固定范围内的整数 index，通常是
[0, H_SIZE)。
合适的 hash function 应符合四项要求：
- 永远返回合法 bucket index；
- 尽量减少 collision；
- 尽量平均分散 key；
- 计算本身要足够快。
Hash 的计算成本是每次 lookup 的一部分。即使分布均匀，昂贵的计算仍可能抵消缩小搜索范围所节省的工作。
例题 1.2.4
（一个简单的字符串 hash 例子）
对字符串 key，一种简单的入门写法可以是：
int Hash(char *s, int nBuckets) {
int h = 0;
while (*s != '\0') {
h += *s;
s++;
}
return h % nBuckets;
}
这个规则容易计算，但字符总和相等，或者除以 nBuckets 后余数相同的字符串一定会 collision；互为字符重排的字符串就是最直接的例子。这段程序还假设 nBuckets > 0、输入字符按非负值（例如 ASCII byte）解释，并且累加结果不会超出 int 范围。因此它适合跟踪计算过程，但正式实现应使用定义清楚的 unsigned hash state 和更强的混合规则。
测试一个简单的 hash-and-bucket 模型
逐个插入 key。每个 key 放进 bucket（字符编码之和）mod 7；留意会否有两个 key 落在同一个 bucket。
- insert("cat");
- insert("dog");
- insert("cow");
- insert("cod");
| Bucket 编号 | Keys | 数目 |
|---|---|---|
| 0 | 空 | 0 |
| 1 | 空 | 0 |
| 2 | 空 | 0 |
| 3 | 空 | 0 |
| 4 | 空 | 0 |
| 5 | 空 | 0 |
| 6 | 空 | 0 |
还未插入任何 key。
- 这一条
- —
- Hash 值
- —
- 有 key 的 bucket
- 0 / 7
- Collision 数量
- 0
未定：每个已插入的 key 都独占一个 bucket
还未插入任何 key；全部 7 个 bucket 都是空的。
要留意Collision 数量把每个 bucket 第一个 key 以外的 key 加起来：同一个 bucket 有三个 key 时算 2，不是 3 对。这个简化 hash 把每个字符的首个 UTF-16 编码单元相加。
不同 key 为何会共用 bucket
定义 1.2.5
（Collision）
两个不同 key 被映射到同一个 bucket index，就发生了 collision。
如果 key 的取值范围包含的 key 多于 bucket 数量，就至少有两个可能的 key 对应同一 index。这并不表示每个小规模输入已经发生 collision，而是表示任何映射到该有限范围的 hash function 都无法对所有合法输入排除 collision。 Hashing 只确定候选项，仍须比较 key，才能确认某个候选项正是查询目标。
Chaining 把 collision 的 entry 存入 bucket 所连接的 list；open addressing 则把它们存入同一个 table 的其他 slot，并通过可重复的 probe sequence 找回。两者都必须找到 key 相同的 entry，不能直接采用遇到的第一个非空位置。
看清 hash table 在两个不同 key 发生 collision 时，如何仍保持 dictionary 操作正确。
Hashing 只是第一步。正确 lookup 和 update 仍取决于 collision strategy 是否沿 chain 或 probe sequence 检查 key。
Chaining：以链表保存同 bucket 的 entry
Chaining 把碰撞的 entry 保留在 bucket 旁边的 linked list 中。
定义 1.2.6
（Chaining）
Chaining 会让每个 bucket 指向一条 linked list，把所有 hash 到同一 bucket 的 key-value entry 串在一起。
Bucket chain 使用的仍是 pointer 连接的 node：
typedef struct cellT {
char *key;
void *value;
struct cellT *next;
} cellT;
因此 lookup 可以分成两层：
- 先 hash key，选出 bucket；
- 再只扫描该 bucket 下面的 linked list。
例题 1.2.7
（Chaining 下的 lookup）
假设 Hash("cat") = 3，而 bucket 3 的 chain 是
("cow", value1) -> ("cat", value2) -> ("cod", value3)。
当执行 Lookup(table, "cat") 时，程序会：
- 先算出 bucket
3； - 沿 bucket
3的 linked list 扫描； - 逐个比较 key；
- 找到
"cat"时返回value2。
Collision 不会改变 lookup 的正确结果，但会增加这个 bucket 所需的 key 比较。
Bucket 内的次序不属于 dictionary 契约。实现可以在链首、链尾或按其他一致规则插入，只要 lookup 与 overwrite 仍能找到正确的 key。这个选择改变的是表示方式，不是 key-value 对应的含义。
例题 1.2.8
（Chaining 下的插入和 lookup）
假设 table 只有五个 bucket，而 hash rule 会让 "ape" 和 "ant" 撞进同一个
bucket。
- 先插入
"ape"。 - 再插入
"ant"。 - 再插入
"apple"。 - lookup
"ant"。
如果 "ape" 和 "ant" 碰撞，它们会出现在同一条 bucket chain。lookup "ant"
时，程序先 hash 一次，再只扫描该 chain，逐个比较 key，直到找到精确对应的
entry。
Occupancy 与期望搜索成本
即使 hash function 的分布合适，table 的 occupancy 仍会影响搜索成本。
设 table 中有 n 个 entry、m 个 bucket，load factor 通常写成
对 chaining 来说，n 可以大于 m，所以 可以大于 1。对 open
addressing 来说，每个 slot 最多存一个 live entry，因此
；要插入新的 key，不但要有 ，probe sequence
还必须能够到达空 slot。
定理 1.2.9
（Chaining 的计数恒等式）
设 是 bucket 中 chain 的长度，其中 。那么
在 chaining 中，各条 bucket chain 把 n 个 entry 划分开来：每个 entry
恰好属于一条 chain。因此，把所有 chain length 相加会把每个 entry 计算一次，得到 ；再除以 m，就得到平均 occupancy 。
这是一个确定性的计数恒等式，本身并不能保证 lookup 是常数时间。要得到 这类期望界，还需要适当的 hash function 或 key distribution 假设。没有这个假设时，即使 load factor 很小，也可能出现一条很长的 chain。
当 table 的 load 增加时：
- chaining 的平均 chain length 严格等于 ，但各条 chain 的实际长度取决于 key 的分布；
- 当 接近
1时，open addressing 的 probe sequence 通常会变长，而且仍要满足 probe coverage 条件； - 如果分布或 load 没有受到控制，平均 lookup 会偏离理想的常数时间。
所以 resize 不只是工程细节，也是保护 hashtable 效能模型的一部分。
Open addressing：在同一 table 内 probing
Open addressing 把 entry 存在 table 内；首选 slot 已被占用时，便按 probe rule 继续检查其他位置。
Collision 的成本因此转移到 probing rule 本身。
- linear probing 会检查下一格，再下一格，一路向前；
- quadratic probing 会跳平方步；
- double hashing 会用第二个 hash function 产生 step size。
定义 1.2.10
（Linear probing）
Linear probing 在首选 slot 已满时依序检查后续位置，必要时绕回表首，直到找到空位或相同 key。
Linear probing 很容易形成一长串连续 filled buckets。这个现象叫 primary clustering。cluster 越长，之后的 probe 就越容易撞到同一段区域，性能也就越差。
Quadratic probing 就是针对这个问题。
定义 1.2.11
（Quadratic probing）
Quadratic probing 会用平方形式的 offset，例如 i^2。因为步长增长较快，它可以减少 primary clustering。
例题 1.2.12
（Quadratic probing 的具体插入）
从一个 size 为 10 的空表开始，hash rule 是 h(k) = k % 10。依次插入
89, 18, 49, 58, 69，使用 quadratic probes
，其中 ：
89去 bucket918去 bucket849hash 到9，撞了之后 probe 到058hash 到8，先撞9，再 probe 到269hash 到9，先撞0，再 probe 到3
所以最后 occupied buckets 是：
0 -> 492 -> 583 -> 698 -> 189 -> 89
最终位置取决于初始 hash、probe rule，以及搜索过程中遇到的已占用位置。
常见错误
（Quadratic probes 未必能到达所有 slot）
减少 primary clustering 并不保证 probe sequence 覆盖所有 slot。例如，当 Nbuckets = 7、F(i) = i^2 时，probe
sequence 会重复，而且有些 slot 甚至完全不会被 probe 到。
例题 1.2.13
（为什么 probe sequence 会漏格）
设 Nbuckets = 7、h0 = 0，使用 probes (h0 + i^2) % 7；令 i = 0, 1, ..., 6，得到 probe sequence
0, 1, 4, 2, 2, 4, 1
这个 sequence 只到达四个不同位置。若它们已被占用，即使另外三个位置仍然空置，probe 也找不到可用 slot。因此，load factor 与 probe coverage 是两项不同的条件。
定义 1.2.14
（Double hashing）
对于 size 为 的 table，double hashing 用第二个 hash function 产生 step ，并按
进行 probing。只有当 时，probe sequence 才保证覆盖全部 个 slot。只要求 step 非零，或者只要求 ，都不够。
设 table size 为 10、h(k) = k % 10，第二个 hash 为
。对 key 23，step 为
。从 bucket 3 开始时，因为
，probe 只会在 3 与 8 之间循环；如果两格都已被占用，它就无法到达其他空 slot。合适的第二个 hash 可以让 probe 分布更好，但 table
size 与 step rule 必须一起设计。
Deletion 还必须保留搜索路径，让后续插入到同一 probe sequence 的 entry 仍然可达。直接把删除位置标成从未使用的空位，可能中断这条路径。这里的 probe 示例讨论 insertion 与 lookup，没有规定 deletion 的具体实现。
Bucket 数量改变后需要 rehash
Bucket 数量参与 index 的计算。即使底层 hash code 不变，改变 bucket 数量也可能把已有 entry 分配到新位置。因此，每个 entry 都须按新规则重新放置；这个过程称为 rehashing。
例题 1.2.15
（模数改变，bucket 也可能改变）
采用 h(k) = k % m 时，key 18 在 m = 10 的表中属于 bucket 8，在 m = 20 的表中却属于 bucket 18。直接把旧 cell 复制到较大数组，会使该 entry 留在新 lookup 不会预期的位置。Rehashing 重新计算位置；若采用
open addressing，还须重新建立符合新 probe rule 的存放关系。
Collision 策略的取舍
不同方案适合不同条件，选择时须比较各自的 tradeoff。
- Chaining 容易理解，而且用 linked list 就能处理 collision。
- Linear probing 简单，但容易出现 primary clustering。
- Quadratic probing 可以减少 clustering，但对 load factor 更敏感。
- Double hashing 通常 probe 分散得更好，但因为要第二个 hash function，所以更贵、更复杂。
选择取决于 table size、预期 load、内存布局及 update pattern。Probe rule 必须先满足 coverage 条件，才有比较其速度的意义。
常见错误
常见错误
（Hash 相同不代表 key 相同）
若 Hash(key1) == Hash(key2)，只代表两个 key 去到同一个 bucket，不代表两者本身相同。
常见错误
（合法的 hash 范围不保证均匀分布）
一个 function 即使永远返回合法 bucket index，仍然可能因为分布太集中而很差。
常见错误
（平均常数时间需要模型假设）
Hash table lookup 的期望 O(1) 界需要合适的 hash function 或 key distribution
及受控的 load factor，不能省略这些条件。
总结
Dictionary 契约规定每个 key 对应的 value，表示方式则决定这个关联存在哪里。 Hashing 选择候选项，key comparison 确认目标，collision handling 保持每个已存 key 可达。期望效率依赖 key/hash 的模型与 occupancy；改变表的大小后，必须通过 rehashing 使存放位置与 lookup 使用的规则继续一致。
快速检查
快速检查
（Hashing 里的 collision 是什么？）
用 key 与 bucket index 来回答。
解答 · 答案
Collision 就是两个不同 key 被映射到同一个 bucket index。
快速检查
（Chaining 下，算完 bucket 之后下一步要做什么？）
想想程序会去哪里继续找。
解答 · 答案
它会沿该 bucket 下面的 linked list 继续扫描，直到找到 matching key 或者链结结束。
练习
快速检查
（为什么 hashtable 在 hashing 之后，仍然要做 key comparison？）
请从 collision 角度回答。
解答 · 引导解答
Hashing 只是把搜索范围缩到某个 bucket。因为不同 key 仍然可能 collision，所以实现仍然要逐个比较 bucket 内的实际 key，才能确认找到的是正确 entry。
快速检查
（解释 chaining 与 open addressing 的一个取舍。）
用额外工作发生在哪里来说明。
解答 · 引导解答
Chaining 把 collision 放到 bucket 旁边的 linked list；open addressing 则把 collision 变成 table 内部的 probing。前者较依赖 pointer structure，后者较依赖 occupancy 与 probe sequence 设计。
快速检查
（为什么 Enter 在 key 已经存在时要覆盖旧 value？）
请用 dictionary contract 来答，而不要只讲 code 行为。
解答 · 引导解答
因为 ADT 是按 key 定义唯一 association 的。相同 key 再插入时，应该更新原本的 association，否则 table 就不再有清楚的 key-to-value 对应。
快速检查
（Quadratic probing 相比 linear probing，减少了哪种 clustering？）
请直接说出 clustering 的名称。
解答 · 答案
Quadratic probing 减少 primary clustering，也就是 linear probing 容易形成的长串连续 filled buckets。
快速检查
（从 size 为 10 的空表开始，依次插入 89、18、49、58、69，使用 probes ，其中 。49 和 69 最后落在哪个 bucket？）
请用 probe sequence 来答。
解答 · 引导解答
49 先 hash 到 9，撞了之后去 0。69 先 hash 到 9，再撞 0，最后去
3。
快速检查
（Double hashing 怎样改善 probe 分布，又需要什么额外计算？）
请说明它额外需要什么。
解答 · 引导解答
Double hashing 通常可以让 probe path 较均匀地分散，但需要计算第二个 hash function，并使 step 与 table size 满足互质条件。额外 hash 计算是其成本。