Appearance
哈希表：拉链法
为什么需要哈希表：拉链法
在顺序查找和折半查找中，查找效率依赖于比较次数，无法突破 O(log n) 的下界。哈希表（散列表）提供了一种全新的思路：通过哈希函数直接计算元素的存储地址，理想情况下可以实现 O(1) 的查找。
然而，不同的关键字可能映射到同一地址，产生冲突（碰撞）。拉链法（链地址法）是解决冲突最常用的方法之一，它将所有映射到同一地址的元素用链表串联起来，结构简单，且不会出现"堆积"现象。408 考研中，拉链法是散列表章节的核心考点。
核心思想
拉链法的核心特点：
- 哈希函数定位：通过 H(key) 计算出数组下标，O(1) 时间定位到对应槽位
- 链表解决冲突：每个槽位维护一个链表，所有哈希值相同的元素挂在同一链表上
- 动态扩展：链表长度不受限制，无需担心表满溢出
哈希表的基本结构：
下标: 0 1 2 ... p-1
槽位: [头指针] [头指针] [头指针] ... [头指针]
↓ ↓ ↓ ↓
链表 链表 链表 链表每个槽位存储一个链表头指针，冲突元素依次挂在对应链表上。
交互可视化
通过下方的交互动画，你可以逐步观察哈希表：拉链法的执行过程：
操作详解
哈希函数
408 考研中最常考的哈希函数是除留余数法：
H(key) = key % p其中 p 通常取不大于表长的最大素数，这样可以使关键字的分布更均匀，减少冲突。
例如，表长 m = 13，则取 p = 13；表长 m = 15，则取 p = 13。
冲突的定义：若 key₁ ≠ key₂，但 H(key₁) = H(key₂)，则称 key₁ 和 key₂ 发生了冲突，它们互为同义词。
拉链法原理
拉链法的数据结构定义：
c
#define MAX_SIZE 13 // 哈希表长度
typedef struct Node {
int key;
struct Node *next;
} Node;
typedef struct {
Node *head; // 每个槽位的链表头指针
} HashTable[MAX_SIZE];构造过程示例：设哈希函数 H(key) = key % 13，依次插入关键字 {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77}：
下标 链表
0 → NULL
1 → [16] → [29] → NULL
2 → [54] → NULL
3 → [16] (注: 16%13=3)
...实际映射结果：
| 关键字 | H(key) = key % 13 |
|---|---|
| 16 | 3 |
| 74 | 9 |
| 60 | 8 |
| 43 | 4 |
| 54 | 2 |
| 90 | 12 |
| 46 | 7 |
| 31 | 5 |
| 29 | 3 |
| 88 | 10 |
| 77 | 12 |
H(16) = H(29) = 3，H(90) = H(77) = 12，它们分别产生冲突，挂在同一链表上。
查找与插入
查找操作：
- 计算 H(key)，定位到对应槽位
- 在该槽位的链表中顺序查找目标关键字
- 找到则返回节点指针；遍历完链表未找到则查找失败
c
Node* search(HashTable ht, int key) {
int idx = key % MAX_SIZE;
Node *p = ht[idx].head;
while (p != NULL) {
if (p->key == key)
return p; // 查找成功
p = p->next;
}
return NULL; // 查找失败
}插入操作：
- 先查找，若已存在则不插入（或更新）
- 若不存在，创建新节点，采用头插法插入到对应链表的表头
c
void insert(HashTable ht, int key) {
if (search(ht, key) != NULL)
return; // 已存在，不重复插入
int idx = key % MAX_SIZE;
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->next = ht[idx].head; // 头插法
ht[idx].head = newNode;
}删除操作：
- 计算 H(key)，定位到对应槽位
- 在链表中找到目标节点并删除
拉链法的删除操作非常方便，直接在链表中摘除节点即可，这是相比开放定址法的一大优势。开放定址法删除时只能做"逻辑删除"（打标记），不能直接物理删除，否则会中断查找链。
ASL 分析
设哈希表长为 m，存储了 n 个元素，装填因子 α = n / m。
查找成功的 ASL：对每个已存入的元素，计算查找它需要的比较次数，然后取平均。
$$ASL_{成功} = \frac{1}{n} \sum_{i=1}^{n} C_i$$
其中 Cᵢ 是查找第 i 个元素所需的比较次数（即该元素在链表中的位置，第 1 个节点比较 1 次，第 2 个比较 2 次...）。
查找不成功的 ASL：对每个槽位，计算查找失败需要的比较次数（即遍历该链表的全部节点数），然后对所有槽位取平均。
$$ASL_{失败} = \frac{1}{m} \sum_{j=0}^{m-1} L_j$$
其中 Lⱼ 是第 j 个槽位链表的长度。
理论结论：在等概率条件下，拉链法的平均查找长度为：
| 指标 | 公式 |
|---|---|
| ASL 成功 | ≈ 1 + α/2 |
| ASL 失败 | ≈ α |
α 越小（表越空），查找效率越高。通常建议 α ≤ 1。
计算示例：上述 11 个关键字存入表长 m = 13 的哈希表，α = 11/13 ≈ 0.85。
查找成功 ASL：各元素比较次数求和后除以 n。对于链表中第 1 个插入的节点（在链尾），比较次数等于该链表长度；最后插入的节点（在链头），比较次数为 1。具体值需要根据插入顺序计算每个节点在链表中的位置。
查找失败 ASL：各槽位链表长度之和除以 m。
复杂度分析
| 操作 | 平均时间复杂度 | 最坏时间复杂度 | 说明 |
|---|---|---|---|
| 查找 | O(1+α) | O(n) | 平均取决于装填因子 α |
| 插入 | O(1+α) | O(n) | 先查找后头插 |
| 删除 | O(1+α) | O(n) | 链表删除，无需逻辑删除 |
空间复杂度：O(m + n)，m 为槽位数组空间，n 为链表节点空间。
与开放定址法的对比：
| 比较维度 | 拉链法 | 开放定址法 |
|---|---|---|
| 冲突处理 | 链表存储同义词 | 探测下一个空位 |
| 装填因子 | 可 > 1 | 必须 < 1 |
| 删除操作 | 直接删除节点 | 只能逻辑删除（打标记） |
| 堆积现象 | 不会产生 | 会产生聚集（堆积） |
| 空间利用 | 需要额外指针空间 | 无额外指针开销 |
| 适用场景 | 表长不确定、频繁增删 | 表长已知、较少删除 |
考研高频考点
- ⭐ 给定关键字序列和哈希函数，画出拉链法的哈希表（选择/填空/综合题高频）
- ⭐ ASL 成功和 ASL 失败的计算（必考计算题）
- ⭐ 装填因子 α 的定义及对查找效率的影响（概念题）
- ⭐ 拉链法 vs 开放定址法的优缺点对比（简答题高频）
- 冲突、同义词的概念辨析（选择题）
- 除留余数法中 p 的选取原则（选择题）
- 拉链法中删除操作的优势（对比开放定址法的逻辑删除）