哈希表：拉链法

2026 大纲 六（七）散列（hash）表 · 基本概念、散列函数构造与拉链法（开放定址法见另一篇）。

用一次计算，代替一串比较

前面所有查找方法都在做同一件事：靠比较把候选范围一点点压小。顺序查找每次排除一个，折半查找每次排除一半，B 树每次排除 $\frac{m-1}{m}$。

散列查找换了条路：由关键字直接算出地址，一步到位。

$$p=H(key)$$

代价也很直接：记录的位置与关键字的大小再无关系。于是散列表不能做范围查询、不能有序输出——这是它换来 $O(1)$ 所付的全部代价。

而这条路上有一个绕不开的麻烦：

🔴 $ke{y}_1\ne ke{y}_2$ 却 $H(ke{y}_1)=H(ke{y}_2)$，这叫冲突，两者互称同义词。冲突只能减少，不能消除。

为什么消不掉？因为关键字的取值集合通常远远大于地址空间。以标识符为例，不超过 8 位、字母开头的字母数字串有 ${10}^{12}$ 量级那么多，而编译器的符号表只有一千个槽位。把 ${10}^{12}$ 个可能的关键字塞进 ${10}^3$ 个地址，鸽笼原理直接判死刑。

所以散列查找必须同时研究两个问题：怎么构造散列函数（少产生冲突），以及冲突了怎么办。本篇讲前者和拉链法，开放定址法在另一篇。

先动手看一眼

加载可视化中...

除留余数法：$p$ 的两条要求各管一件事

五种构造方法里除留余数法最常用、适用范围最广：

$$H(key)=keymodp,p\text{取不大于表长的最大质数}$$

这两条要求各管各的：

• $p\le m$ 保证算出的地址落在表内——这是硬性的正确性要求。
• $p$ 取质数保证关键字里隐含的周期性不被 $mod$ 放大成地址聚集。

第二条值得验算一下。若 $p$ 是合数，设 $d$ 是它的一个因子，那么所有 $d$ 的倍数这类关键字算出来的地址也全是 $d$ 的倍数。取 $p=10$、关键字恰好都是 5 的倍数：

$key$	5	15	25	35	45
$keymod10$	5	5	5	5	5

五个关键字全撞在地址 5 上，其余九个地址一个都用不到。换成质数 $p=11$：

$key$	5	15	25	35	45
$keymod11$	5	4	3	2	1

完全散开。质数没有除 1 和自身以外的因子，所以关键字里隐含的任何周期性都不会被 $mod$ 放大成地址上的聚集。

⚠️ $p$ 与表长 $m$ 未必相等（$m=100$ 时 $p$ 取 97）。$p<m$ 时下标 $p\sim m-1$ 永远不会成为任何一次查找的起点——这条会直接决定失败 ASL 的分母，是本章最大的失分点之一。

其余四种方法列在这里，考到的多是"哪种方法适用于什么情形"：

方法	做法	适用情形
直接定址法	$H(key)=key$ 或 $a\cdot key+b$	关键字小且连续，绝不冲突，但浪费空间
数字分析法	挑分布最均匀的若干位做地址	关键字集合事先已知、各位分布不均
平方取中法	取 $ke{y}^2$ 的中间几位（受每一位影响都大）	各位分布不均且不知分布规律
折叠法	分成等长几段相加，取和的后几位	地址位数少、关键字位数多

拉链法：同义词各挂各的链

散列地址相同的记录放在同一条单链表（同义词链表）里，$m$ 个散列地址就有 $m$ 条链表，用数组 HT[0..m-1] 存各链表的头指针。

#define M 13   // 散列表槽位数，本例中 p 也取 13

typedef struct Node { int key; struct Node *next; } Node;
typedef struct { Node *head; } HashTable[M];

// 查找：返回结点指针，NULL 表示失败
Node* search(HashTable ht, int key) {
    int idx = key % M;            // 这一步是计算，不算关键字比较
    Node *p = ht[idx].head;
    while (p != NULL) {
        if (p->key == key) return p;
        p = p->next;              // 每前进一步就是一次关键字比较
    }
    return NULL;
}

// 删除：找到并摘除结点，返回是否成功
int delete_key(HashTable ht, int key) {
    int idx = key % M;
    Node *p = ht[idx].head, *pre = NULL;
    while (p != NULL && p->key != key) { pre = p; p = p->next; }
    if (p == NULL) return 0;
    if (pre == NULL) ht[idx].head = p->next;   // 🔴 删的是链头，要改数组里的头指针
    else pre->next = p->next;
    free(p);
    return 1;
}

⚠️ pre == NULL 那一支不能少：漏掉它，删除每条链的第一个结点都会失效。

这个结构带来三条性质，每一条都和开放定址法形成对照：

1. 表不会满，$\alpha$ 可以大于 1。 链表想挂多长挂多长，$n>m$ 只是让平均链长超过 1。
2. 删除直接摘结点，不需要墓碑标记。 开放定址法必须打墓碑，否则截断探测链。
3. 不产生堆积。 不同的散列地址在不同的链上，互不干扰；开放定址法的线性探测则会让非同义词互相争抢。

这三条合起来就是"频繁插入删除时优先选拉链法"的完整理由。

还有一条：头插还是尾插，对成功 ASL 没有影响——一条长度 $L$ 的链，各元素的比较次数恒为 $1,2,\cdots ,L$ 这一组数，变的只是"某个特定关键字比几次"。

装填因子：ASL 是 $\alpha$ 的函数，不是 $n$ 的函数

$$\alpha =\frac{\text{记录数 }n}{\text{表长 }m}$$

🔴 散列表的平均查找长度是 $\alpha$ 的函数，而不是记录个数 $n$ 的函数。 这句话就是"散列查找接近 $O(1)$"的准确含义——表长跟着记录数一起涨、$\alpha$ 保持不变时，查找代价就不随 $n$ 增长。

拉链法的平均查找长度是 $O(1+\alpha )$：1 次计算散列地址，加上平均扫过 $\alpha$ 个链结点。最坏是 $O(n)$——全部关键字都是同义词时，散列表退化成一条长为 $n$ 的单链表。

怎么触发最坏情形：$H(key)=keymod13$ 而关键字恰好都是 13 的倍数，全部落进槽位 0。

失败 ASL 的分母，以及两种计数算法

成功 ASL 的分母是元素个数 $n$，$C_i$ 是该元素在链中的位置，没有争议。

失败 ASL 的分母是散列函数的值域大小——不是 $n$，也不一定是表长。理由在《查找基本概念》里：失败查找从 $H(key)$ 这个地址出发，能当起点的地址只有 $H$ 的值域那么多。

但拉链法这里还多一层麻烦，是真实存在的教材分歧：

算法	"走到链尾发现 NULL"算不算比较	长度 $L$ 的链贡献	全表结果
A（严蔚敏教材）	算	$L+1$	${\displaystyle \frac{n+r}{r}}={\alpha }^{\prime }+1$
B（只数关键字比较）	不算	$L$	${\displaystyle \frac{n}{r}}={\alpha }^{\prime }$

（$r$ = 散列函数值域大小，$r=m$ 时 ${\alpha }^{\prime }=\alpha$。）

题目写明"空指针也算一次比较"或给出教材算法 → 算法 A；只说"求平均查找长度" → 多数复习材料按算法 B（此时失败 ASL 恰等于 $\alpha$，与理论结论对得上）。答题时把用的是哪一种写出来（"设走到空指针不计入比较次数"），阅卷可辨。

⚠️ 开放定址法没有这个分歧：它遇到空位必须算 1 次（那是一次真实的单元访问，判定失败正是靠它）。两种冲突处理方法失败 ASL 的数法本来就不同，别把一边的习惯搬到另一边。

建表与两个 ASL 的完整推演（第一次学、或想手动模拟时展开）

设 $H(key)=keymod13$，关键字序列 $(19,14,23,1,68,20,84,27,55,11,10,79)$ 共 12 个，用拉链法处理冲突，按插入顺序尾插。逐个算散列地址：

$key$	19	14	23	1	68	20	84	27	55	11	10	79
$H(key)$	6	1	10	1	3	7	6	1	3	11	10	1

得到散列表：

槽位	链表	链长 $L_j$
0	空	0
1	14 → 1 → 27 → 79	4
2	空	0
3	68 → 55	2
4	空	0
5	空	0
6	19 → 84	2
7	20	1
8	空	0
9	空	0
10	23 → 10	2
11	11	1
12	空	0

校验：$4+2+2+1+2+1=12$ ✓ 与关键字个数一致。装填因子 $\alpha =\frac{12}{13}\approx 0.92$。

成功 ASL（$C_i$ = 该元素在链中的位置）：链头的 6 个（14、68、19、20、23、11）各比 1 次；链上第 2 个的 4 个（1、55、84、10）各比 2 次；第 3 个的 27 比 3 次；第 4 个的 79 比 4 次。

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1\times 6+2\times 4+3+4}{12}=\frac{21}{12}=1.75$$

通用写法：一条长度为 $L$ 的链贡献 $1+2+\cdots +L=\frac{L(L+1)}{2}$ 次比较，故

$$AS{L}_{\mathrm{成}\mathrm{功}}=\frac{1}{n}\sum _j\frac{L_j(L_j+1)}{2}$$

代入验证：$\frac{4\cdot 5}{2}+\frac{2\cdot 3}{2}\times 3+\frac{1\cdot 2}{2}\times 2=10+9+2=21$，$\frac{21}{12}=1.75$ ✓

失败 ASL（分母 = 值域大小 13）。算法 A（空槽比 1 次，长度 4 的链比 5 次）：

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{1+5+1+3+1+1+3+2+1+1+3+2+1}{13}=\frac{25}{13}\approx 1.92$$

算法 B（只统计与真实关键字的比较，空槽 0 次）：

$$AS{L}_{\mathrm{失}\mathrm{败}}=\frac{0+4+0+2+0+0+2+1+0+0+2+1+0}{13}=\frac{12}{13}\approx 0.92$$

两个结果恰好相差 1，因为每个入口都差了"和 NULL 比的那一次"。

理论 ASL 公式与直接计算为什么对不上（题目只给装填因子时展开）

在等概率、散列函数均匀的假设下：

指标	公式	与上面算例对照
$AS{L}_{\mathrm{成}\mathrm{功}}$	$\approx 1+{\displaystyle \frac{\alpha }{2}}$	$1+0.46=1.46$ vs 直接计算 1.75
$AS{L}_{\mathrm{失}\mathrm{败}}$	$\approx \alpha +e^{-\alpha }$	$0.92+0.40=1.32$ vs 算法 B 的 0.92

⚠️ 对不上是正常的。 理论公式的前提是"关键字在各地址上均匀随机分布"，而具体的一张表总有它自己的偏斜。题目给了具体的表就必须直接计算，不许套公式；只有题目只给 $\alpha$ 时才用理论公式估算。

$\alpha$ 为什么可以大于 1：链表长度不受限，$n$ 超过 $m$ 只会让平均链长超过 1，不会"装不下"。工程上 $\alpha$ 取到 1 附近仍然可用；明显大于 1 时 $O(1+\alpha )$ 里的 $\alpha$ 项开始主导，就该扩容重散列了。

构造散列函数的完整考量与复杂度来历（想补齐基本概念的完整表述就展开）

构造散列函数要考虑的五个因素：散列表长度、关键字长度、关键字的分布情况、计算函数的时间、记录的查找频次。

两条原则：① 计算要简单，每个关键字只对应一个散列地址；② 函数的值域必须落在表长范围内，且算出的地址分布应尽量均匀。

复杂度的来历：

操作	平均	最坏	怎么来的
查找	$O(1+\alpha )$	$O(n)$	1 次计算散列地址 + 平均扫过 $\alpha$ 个链结点；最坏是全部关键字同义
插入	$O(1+\alpha )$	$O(n)$	先查找再头插（$O(1)$）
删除	$O(1+\alpha )$	$O(n)$	先查找再摘链结点，$O(1)$ 完成摘除

空间复杂度 $O(m+n)$：$m$ 个头指针 + $n$ 个链结点（每个结点还要多存一个 next 指针）。

插入代码（先查后插，避免重复；头插 $O(1)$）：

void insert(HashTable ht, int key) {
    if (search(ht, key) != NULL) return;
    int idx = key % M;
    Node *s = (Node*)malloc(sizeof(Node));
    s->key = key;
    s->next = ht[idx].head;
    ht[idx].head = s;
}

拉链法与开放定址法的逐项对照（在两者之间做选择时展开）

比较维度	拉链法	开放定址法
冲突处理	同义词挂在同一条链表上	按探测序列在表内找空位
装填因子	可以 $>1$	必须 $<1$
删除操作	直接摘除链结点	只能逻辑删除（打墓碑），否则截断探测链
堆积（聚集）	不会产生——不同地址在不同链上	会产生，线性探测尤其严重
空间开销	每个结点多一个指针，结点动态申请	无指针开销，但要预留空位
表长是否需预知	不需要	需要，且要留出余量
适用场景	表长不确定、频繁插入删除	表长已知、较少删除
失败 ASL 遇空时	有两种算法（空指针算不算一次）	必算 1 次，无分歧

考点速记

三条结论：

1. 冲突只能减少不能消除（关键字空间远大于地址空间）；散列查找必答"构造函数"和"处理冲突"两件事。
2. ASL 是 $\alpha$ 的函数，不是 $n$ 的函数——这是"接近 $O(1)$"的准确表述。
3. 拉链法三特性：$\alpha$ 可 $>1$、删除直接摘结点、不产生堆积。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 提高散列表查找效率的措施：设计冲突少的散列函数 ✓、处理冲突时避免堆积 ✓、增大装填因子 ✗（方向反了）。这道题同时挂在拉链法和开放定址法下，因为三个选项对两种方法都成立。
• 作为其他题目的算法载体：拉链法本身在近年的选择题里不单独成题，开放定址法那边的计算题密度高得多。复习时把重心放在开放定址法的 ASL 计算上，拉链法只需记住三条特性和"分母是值域"这一条。

易错：失败 ASL 的分母是散列函数的值域大小，$H(key)=keymod13$ 而表长 16 时分母是 13。

易错：拉链法失败 ASL 有两种算法，开放定址法没有。 前者的"走到 NULL"算不算比较，两种教材不一致，答题写明用的是哪一种；后者遇到空位必算 1 次。

易错："增大装填因子能提高效率"是反的。 $\alpha$ 越大，平均链长越长，ASL 越大。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）7.4.1 节「散列表的基本概念」，p220： 散列函数与散列地址、散列表、冲突和同义词的定义—— "对不同的关键字可能得到同一散列地址……这种现象称为冲突。 具有相同函数值的关键字对该散列函数来说称作同义词"； 以及"散列查找法主要研究以下两方面的问题：（1）如何构造散列函数；（2）如何处理冲突"。
• 同书 7.4.2 节「散列函数的构造方法」，p221–p223：构造散列函数要考虑的五个因素与两条原则； 数字分析法、平方取中法、折叠法、除留余数法。其中除留余数法： "假设散列表表长为 $m$，选择一个不大于 $m$ 的数 $p$，用 $p$ 去除关键字， 除后所得余数为散列地址……这个方法的关键是选取适当的 $p$，一般情况下， 可以选 $p$ 为小于表长的最大质数。例如，表长 $m=100$，可取 $p=97$"。
• 同书 7.4.3 节，p224：链地址法——"把具有相同散列地址的记录放在同一个单链表中， 称为同义词链表。有 $m$ 个散列地址就有 $m$ 个单链表， 同时用数组 HT[0..m-1] 存放各个链表的头指针"；例 7.2 给出的关键字序列 $(19,14,23,1,68,20,84,27,55,11,10,79)$ 与 $H(key)=keymod13$ 正是本篇算例的出处。
• 同书 p227–p228：装填因子的定义与"散列表的平均查找长度是 $\alpha$ 的函数， 而不是记录个数 $n$ 的函数"；表 7.3 给出链地址法的理论平均查找长度 （成功 $1+\frac{\alpha }{2}$，失败 $\alpha +e^{-\alpha }$）； p228 用例 7.2 的数据直接计算得 $AS{L}_{succ}=1.75$、$AS{L}_{unsucc}=1.92$ （该书把"指针域为空"计作一次比较，即本篇的算法 A），并指出 "链地址法的平均查找长度小于开放地址法"、"链地址法的结点空间是动态申请的， 无需事先确定表的容量，因此更适用于表长不确定的情况"。

相关知识

开放定址法（另一种冲突处理方案，计算题主要出在那边）｜ 查找基本概念（散列失败 ASL 分母为什么与众不同）｜ 单链表（每个槽位挂的就是它）｜ B 树、B+ 树（需要范围查询时的替代）｜ 查找算法分析与对比

相关文章

• 查找基本概念
• 顺序查找
• 折半查找（二分查找）
• 分块查找
• 二叉排序树查找 → 见树章节
• 平衡二叉树查找 → 见树章节
• 红黑树查找 → 见树章节
• B 树
• B+ 树
• 哈希表：开放定址法
• 查找算法对比

交互体验

前往完整可视化页面 →

真题练习

相关真题（2题）

2015Q4115分2011Q92分