拉链法（链地址法）
定义
拉链法（Separate Chaining，也称链地址法）是解决哈希冲突的一种方法。其核心思想是：
哈希表的每个数组位置不直接存储键值对，而是存储一个链表（或其他容器）。所有哈希到同一索引的键值对都放入该位置的链表中。
基本原理
索引: 0 1 2 3 4
┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐
table │ │ │ ●───►│ │ │ │ │ │
└─┘ └─┘ └─┘ └─┘ └─┘
│
▼
● (key=1, value=A)
│
▼
● (key=11, value=B)
│
▼
null
当 hash(1) = 1 且 hash(11) = 1 时（发生冲突），两个键值对都会存储在 table[1] 的链表中。
操作复杂度
| 操作 | 平均情况 | 最坏情况 | 说明 |
|---|---|---|---|
| 查找 | O(1) | O(n) | 最坏情况为所有 key 都冲突，链表退化为线性表 |
| 插入 | O(1) | O(n) | 假设哈希函数均匀分布 |
| 删除 | O(1) | O(n) | 需要先查找再删除 |
与开放寻址法对比
| 特性 | 拉链法 | 开放寻址法（线性探查） |
|---|---|---|
| 存储方式 | 数组 + 链表 | 纯数组 |
| 负载因子 | 可以 > 1 | 必须 ≤ 1 |
| 缓存友好性 | 较差（指针跳转） | 较好（连续内存） |
| 删除操作 | 简单（链表删除） | 复杂（需要标记删除位） |
| 空间开销 | 指针开销较大 | 无额外指针开销 |
关键设计考虑
1. 底层容器选择
- 链表：实现简单，但缓存不友好
- 平衡树（Java 8+ HashMap）：当链表长度 > 8 时转为红黑树，避免 O(n) 退化
- 动态数组：某些场景可用，但插入删除效率低
2. 负载因子影响
- 负载因子 = 元素总数 / 数组容量
- 拉链法允许负载因子 > 1（一个桶可以有多个元素）
- 但负载因子过大会导致链表过长，影响性能
3. 哈希函数要求
- 必须均匀分布，避免大量冲突导致链表过长
- 计算必须 O(1)，否则影响整体性能
代码示例（简化版）
来自 哈希表链地址法 的简化假设：
// 哈希函数：简单取模
int hash(int key) {
return key % table.length;
}
// put: 插入到链表头部
void put(int key, int value) {
int index = hash(key);
Node head = table[index];
// 遍历链表，如果 key 存在则更新，否则插入新节点
}
// get: 遍历链表查找
int get(int key) {
int index = hash(key);
Node node = table[index];
while (node != null) {
if (node.key == key) return node.value;
node = node.next;
}
return -1; // key 不存在
}
实际应用
- Java HashMap/Hashtable：JDK 8+ 使用数组 + 链表/红黑树
- C++ std::unordered_map：通常实现为链地址法
- Python dict：类似链地址法，但使用开放寻址的变体