链地址法
概述
链地址法（Chaining） 是一种处理 散列表 冲突的经典方法。其核心思想是：在散列表 的每个槽位上维护一个链表（或其它动态集合结构），所有被散列函数映射到同一槽位的关键字都存储在该槽位对应的链表中。链地址法实现简单，且对装载因子不敏感，是最常用的冲突处理策略之一。
定义
链地址法
设散列表 ，散列函数 。链地址法将 定义为一个链表的头指针，用于存储所有满足 的元素。当插入关键字为 的元素 时，将 插入到链表 中；搜索时，在链表 中顺序查找关键字为 的元素。
数据结构示意
散列表 T[0..m-1]:
T[0] -> [元素] -> [元素] -> NIL
T[1] -> NIL
T[2] -> [元素] -> NIL
T[3] -> [元素] -> [元素] -> [元素] -> NIL
...
T[m-1] -> [元素] -> NIL
每个槽位 指向一个链表，链表中存储所有散列值等于 的元素。
伪代码
搜索：
CHAINED-HASH-SEARCH(T, k)
x = T[h(k)]
while x != NIL and x.key != k
x = x.next
return x
插入（插入到链表头部，O(1)）：
CHAINED-HASH-INSERT(T, x)
x.next = T[h(x.key)]
T[h(x.key)] = x
删除：
CHAINED-HASH-DELETE(T, x)
// 需要先找到 x 的前驱元素 prev
// 如果 x 是链表头：T[h(x.key)] = x.next
// 否则：prev.next = x.next
插入位置的选择
将新元素插入到链表头部可以在 时间内完成插入操作（无需遍历链表）。如果插入到尾部，则需要 的时间。
核心性质
时间复杂度分析
链地址法的性能取决于链表的平均长度。给定装载因子 ：
简单均匀散列假设（Simple Uniform Hashing）：每个关键字等概率地散列到 个槽位中的任何一个，且独立于其它关键字的散列位置。
在此假设下：
| 操作 | 期望时间 | 最坏时间 |
|---|---|---|
| 搜索（成功） | ||
| 搜索（失败） | ||
| 插入 | （插入链表头部） | |
| 删除 | （需要先找到前驱） |
其中 的含义是： 用于计算散列值， 用于在链表中搜索。
成功搜索的期望代价推导
在简单均匀散列假设下，搜索关键字 的期望时间为：
不对，更精确地：
- 设 为链表 的长度，则 。
- 在简单均匀散列假设下，。
- 不成功搜索的期望代价：（需要遍历整个链表）。
- 成功搜索的期望代价：（平均只需遍历链表的一半）。
装载因子的影响
- 当 较小时（例如 ），链表很短，操作接近 。
- 当 较大时，链表变长，性能退化。
- 与 开放寻址法 不同，链地址法允许 （元素数可以超过槽数）。
- 实际应用中，通常保持 在一个合理范围内（如 0.75 ~ 3），必要时进行扩容（rehashing）。
空间复杂度
- 散列表数组：
- 链表节点：
- 总空间：
章节扩展
链地址法 vs. 开放寻址法
| 特性 | 链地址法 | 开放寻址法 |
|---|---|---|
| 装载因子 | 可 | 必须 |
| 删除操作 | 简单（直接删除链表节点） | 复杂（需要特殊标记） |
| 缓存性能 | 较差（链表节点不连续） | 较好（数据在数组内连续） |
| 指针开销 | 需要额外指针空间 | 无额外指针 |
| 聚类问题 | 无 | 可能出现一次/二次聚类 |
链表的替代实现
除了单链表，每个槽位还可以使用：
- 双向链表：使删除操作变为 （已知目标节点时）
- 动态数组：当链表很短时，数组的缓存友好性更好
- 平衡搜索树：当链表很长时（ 很大），可用树替代链表，保证 最坏搜索