Appearance
408
数据结构
散列表（哈希表）
定位信息
| 项目 | 内容 |
|---|---|
| 章节 | 第六章 查找 · 6.7 |
| 知识单元编号 | DS-06-07 |
| 核心概念 | 散列函数、冲突处理（开放定址法、链地址法）、装填因子、ASL |
| 前置知识 | 顺序查找、模运算 |
| 考试权重 | ★★★★（高频重点，选择题和综合题常考） |
知识点讲解
一、散列表的基本概念
散列表（Hash Table）是一种基于散列函数直接计算关键字存储位置的查找结构，理论上可以达到 O(1) 的查找效率。
核心概念：
- 散列函数 H(key)： 将关键字映射到散列表的地址。理想情况下，不同关键字映射到不同地址。
- 冲突（Collision）： 当 key₁ ≠ key₂ 但 H(key₁) = H(key₂) 时，称为冲突。冲突不可避免，但可以通过好的散列函数和冲突处理策略减少。
- 同义词（Synonym）： 发生冲突的不同关键字互为同义词。
- 装填因子 α = 已存元素数 / 表长： α 越大，冲突越多，查找效率越低。
二、常用散列函数
| 散列函数 | 公式 | 特点 |
|---|---|---|
| 除留余数法 | H(key) = key mod p（p ≤ m） | 最常用，p 取素数效果好 |
| 直接定址法 | H(key) = a × key + b | 关键字分布连续时使用 |
| 数字分析法 | 取关键字中某几位 | 关键字位数多且分布已知 |
| 平方取中法 | 取 key² 的中间几位 | 关键字各位分布不均匀时 |
三、冲突处理方法（重点）
（一）开放定址法（Open Addressing）
所有元素都存在散列表内，冲突时按某种探测序列寻找下一个空位。
| 探测方法 | 公式 | 特点 |
|---|---|---|
| 线性探测 | Hᵢ = (H(key) + i) mod m, i=1,2,... | 简单但易产生聚集 |
| 二次探测 | Hᵢ = (H(key) ± i²) mod m | 减少聚集，但可能遗漏空位 |
| 伪随机探测 | Hᵢ = (H(key) + dᵢ) mod m | dᵢ 为伪随机序列 |
线性探测的聚集问题： 冲突元素会连成一片（一次聚集），导致后续查找的探测长度增加。
（二）链地址法（拉链法）
将所有同义词存储在同一个链表中。散列表的每个槽（bucket）指向一个链表头。
散列表 H[m]:
[0] → NULL
[1] → 结点A → 结点D → NULL
[2] → 结点B → NULL
[3] → NULL
[4] → 结点C → 结点E → 结点F → NULL
...链地址法 vs 开放定址法对比表：
| 对比维度 | 链地址法 | 开放定址法 |
|---|---|---|
| 冲突处理 | 链表存储同义词 | 探测下一个空位 |
| 删除操作 | 容易（链表删除） | 困难（需标记删除/重建） |
| 装填因子限制 | α 可 > 1 | α 必须 < 1 |
| 空间利用 | 动态分配，灵活 | 预分配，可能浪费 |
| 聚集问题 | 无 | 线性探测有聚集 |
| ASL（查找） | 1 + α/2（成功） | 与探测方法有关 |
| 实际应用 | 更常用（如 Java HashMap） | 特定场景 |
四、ASL 计算公式
链地址法（等概率）：
- 查找成功：ASL = 每个元素查找次数之和 / 元素个数
- 查找失败：ASL = 每个槽的探测次数之和 / 槽的数量（遍历到链表末尾）
开放定址法（线性探测）：
- 查找成功：对每个元素，计算从其散列位置到该元素的探测次数，取平均
- 查找失败：对每个地址 i，计算从 i 开始到第一个空位的探测次数，取平均
五、散列表查找伪代码（C 风格——线性探测法）
c
// 散列表结构（开放定址法-线性探测）
#define EMPTY 0 // 空位
#define DELETED -1 // 已删除标记
typedef struct {
KeyType key;
int status; // 0=空, 1=占用, -1=已删除
} HashEntry;
// 散列函数：除留余数法
int Hash(KeyType key, int m) {
return key % m; // m 为表长
}
// 线性探测法插入
void Hash_Insert(HashEntry HT[], int m, KeyType key) {
int addr = Hash(key, m); // 计算初始散列地址
int i = 0;
while (i < m) {
int pos = (addr + i) % m; // 线性探测
if (HT[pos].status != 1) { // 找到空位或已删除位
HT[pos].key = key;
HT[pos].status = 1;
return;
}
if (HT[pos].key == key)
return; // 关键字已存在，不插入
i++;
}
// 表满，插入失败
}
// 线性探测法查找
int Hash_Search(HashEntry HT[], int m, KeyType key) {
int addr = Hash(key, m); // 计算初始散列地址
int i = 0;
while (i < m) {
int pos = (addr + i) % m;
if (HT[pos].status == 0)
return -1; // 遇到空位，查找失败
if (HT[pos].status == 1 && HT[pos].key == key)
return pos; // 查找成功
i++; // 继续探测
}
return -1; // 遍历全表未找到
}六、散列表 ASL 计算示例对比
假设散列表长 m = 11，H(key) = key mod 11，插入 {25, 38, 16, 49, 22}：
线性探测法：
| 元素 | H(key) | 探测过程 | 探测次数 |
|---|---|---|---|
| 25 | 3 | 位置 3 空，直接插入 | 1 |
| 38 | 5 | 位置 5 空，直接插入 | 1 |
| 16 | 5 | 位置 5 占 → 位置 6 空 | 2 |
| 49 | 5 | 位置 5 占 → 6 占 → 7 空 | 3 |
| 22 | 0 | 位置 0 空，直接插入 | 1 |
成功 ASL = (1+1+2+3+1)/5 = 1.6
链地址法：
| 槽 | 链表内容 | 查找次数累加 |
|---|---|---|
| 0 | 22 | 1 |
| 3 | 25 | 1 |
| 5 | 38 → 16 → 49 | 1+2+3=6 |
成功 ASL = (1+1+1+2+3)/5 = 1.6（巧合相同，通常链地址法更优）
记忆辅助
- "除留余数取素数，装填因子定效率" — 散列函数首选除留余数法，p 取素数；α 越小效率越高。
- "线性探测会聚集，链地址法最灵活" — 线性探测容易产生一次聚集，链地址法无此问题且支持删除。
- "查找失败看空位，查找成功看元素" — 查找失败 ASL 是对每个地址到空位的探测次数取平均；查找成功是对每个元素的探测次数取平均。
- "α = n/m，越小越好" — 装填因子直接影响 ASL，一般控制在 0.7 以下。
例题精解
例题 1：线性探测法构造散列表
设散列表长 m = 11，H(key) = key mod 11，用线性探测法依次插入 {47, 7, 29, 11, 16, 92, 22}，画出散列表并计算成功 ASL。
解题四步法：
① 审题： 表长 11，除留余数法，线性探测。
② 分析： 计算每个关键字的散列地址，冲突时线性探测下一个空位。
③ 过程：
| 元素 | H(key) | 探测过程 | 位置 | 次数 |
|---|---|---|---|---|
| 47 | 47%11=3 | 位置 3 空 | 3 | 1 |
| 7 | 7%11=7 | 位置 7 空 | 7 | 1 |
| 29 | 29%11=7 | 7 占 → 8 空 | 8 | 2 |
| 11 | 11%11=0 | 位置 0 空 | 0 | 1 |
| 16 | 16%11=5 | 位置 5 空 | 5 | 1 |
| 92 | 92%11=4 | 位置 4 空 | 4 | 1 |
| 22 | 22%11=0 | 0 占 → 1 空 | 1 | 2 |
散列表：
下标: 0 1 2 3 4 5 6 7 8 9 10
[11][22][ ][47][92][16][ ][ 7][29][ ][ ]成功 ASL = (1+1+2+1+1+1+2)/7 = 9/7 ≈ 1.29
④ 结论： 线性探测法构造散列表，成功 ASL ≈ 1.29。注意 29 和 22 分别与 7 和 11 冲突，需要额外探测。
例题 2：链地址法 ASL 计算
设散列表长 m = 7，H(key) = key mod 7，用链地址法插入 {19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}，计算成功和失败的 ASL。
解题四步法：
① 审题： 表长 7，链地址法，12 个关键字。
② 分析： 计算每个关键字的散列地址，统计链表长度。
③ 过程：
| 槽 | 关键字（按插入顺序） | 链表 |
|---|---|---|
| 0 | 14, 21→实际无21, 但14%7=0 | 14 → NULL |
| 1 | 01, 15→无15, 但01%7=1, 但01 实际为 1 | 1 → NULL |
让我重新计算所有 key mod 7：
- 19 % 7 = 5
- 14 % 7 = 0
- 23 % 7 = 2
- 01 % 7 = 1
- 68 % 7 = 5
- 20 % 7 = 6
- 84 % 7 = 0
- 27 % 7 = 6
- 55 % 7 = 6
- 11 % 7 = 4
- 10 % 7 = 3
- 79 % 7 = 2
| 槽 | 链表 | 长度 | 查找次数累加 |
|---|---|---|---|
| 0 | 14 → 84 | 2 | 1+2=3 |
| 1 | 01 | 1 | 1 |
| 2 | 23 → 79 | 2 | 1+2=3 |
| 3 | 10 | 1 | 1 |
| 4 | 11 | 1 | 1 |
| 5 | 19 → 68 | 2 | 1+2=3 |
| 6 | 20 → 27 → 55 | 3 | 1+2+3=6 |
成功 ASL： 每个元素的查找次数 = 它在链表中的位置 = (1+2 + 1 + 1+2 + 1 + 1 + 1+2 + 1+2+3) / 12 = (3+1+3+1+1+3+6) / 12 = 18/12 = 1.5
失败 ASL： 每个槽查找失败时需遍历整个链表 = (2+1+2+1+1+2+3) / 7 = 12/7 ≈ 1.71
④ 结论： 链地址法下成功 ASL = 1.5，失败 ASL ≈ 1.71。装填因子 α = 12/7 ≈ 1.71，ASL 仍可控。
考情分析
| 维度 | 说明 |
|---|---|
| 考频 | 高频，每年必考 |
| 题型 | 选择题（ASL 计算、冲突判断、散列函数）、综合题（完整构造散列表过程） |
| 命题趋势 | 线性探测法构造散列表 + ASL 计算是经典综合题；链地址法 ASL 计算 |
| 常见陷阱 | 线性探测查找失败时的终止条件；链地址法成功/失败 ASL 计算方式不同 |
易错点
- 散列表的查找效率与关键字个数和表长的比值（装填因子 α）有关，与关键字个数 n 的绝对值无关。 α 相同则 ASL 相同。
- 线性探测法查找失败时，从散列地址开始探测到第一个空位就停止。 不是遍历整个表！
- 链地址法查找失败时，要遍历整个链表才能确认失败。 所以失败 ASL 用链表长度计算。
- 开放定址法中删除元素不能直接置空！ 需要用特殊标记（如 DELETED），否则会截断后续元素的查找路径。
- 除留余数法中 p 选素数可以减少冲突。 如果 p 含有公因子，某些地址永远不会被映射到。
来源标注
| 来源 | 说明 |
|---|---|
| 王道考研 | 2026 版数据结构讲义 · 第六章 查找 |
| 天勤考研 | 数据结构高分笔记 · 查找部分 |
| 严蔚敏 | 《数据结构（C 语言版）》第 9 章 |
| 教材参考 | 《数据结构》（第 5 版）李春葆 · 查找章节 |