前面的查找方法都靠比较缩小范围。散列表换了一条路线：用散列函数从关键字直接计算存储地址。它不维护全局有序性，却能在分布良好、装填适度时提供平均 $O(1)$ 的精确查找。

学习目标

• 说明散列函数、散列地址、冲突、同义词和装填因子；
• 构造线性探测、平方探测、双散列和链地址表；
• 解释开放定址删除为何需要墓碑标记；
• 分别计算查找成功与失败的平均查找长度；
• 分析散列函数、冲突策略和装填因子如何共同影响性能；
• 判断何时应再散列，以及散列表何时不适合使用。

从关键字到地址

散列函数 $H(key)$ 把关键字映射到表地址。对整数关键字，常见做法是除留余数法：

$$H(key)=keymodp.$$

其中 $p$ 通常不大于表长。选择与关键字分布关系较弱的 $p$（常取素数），有助于避免大量关键字集中到少数地址。

一个实用散列函数应当：

• 对相同关键字始终给出相同结果；
• 计算开销低；
• 尽可能均匀使用地址空间；
• 充分利用关键字中有区分度的信息。

DEF定义 · 冲突与同义词

不同关键字得到相同初始散列地址，称为冲突。这些关键字互为同义词。只要关键字集合大于地址空间，冲突就不可能完全避免；散列表设计的目标是让冲突少且容易处理。

IDEA直觉 · 为什么冲突不可避免

地址空间只有 $m$ 个位置，而关键字可能有无限多种。把 $>m$ 个不同关键字塞进 $m$ 个"抽屉"，抽屉原理保证至少有一个抽屉放进两个关键字，冲突必然发生。因此散列的目标不是消灭冲突，而是让冲突发生得少、且处理冲突的成本可控。

装填因子

设表中已有 $n$ 个关键字，散列表容量为 $m$，装填因子为：

$$\alpha =\frac{n}{m}.$$

开放定址法要求 $\alpha \le 1$；链地址法每个桶可挂多个结点，因此 $\alpha$ 可以大于 1。装填因子越大，平均探测次数或平均链长通常越大。

O(·)复杂度 · 平均 O(1) 的前提

散列表的平均常数时间依赖散列近似均匀且装填因子受到控制。若大量关键字聚集到同一位置，查找仍会退化到 $O(n)$。

条件	后果
散列均匀 + α 适中	平均 $O(1)$
大量聚集或 α 接近 1	平均退化到 $O(n)$

开放定址法

开放定址法把所有关键字都存放在表数组中。发生冲突后，按照探测序列检查其他槽位：

$$H_i(key)=(H(key)+d_i)modm.$$

插入在第一个可用槽位停止；查找沿相同序列前进，命中则成功，遇到从未使用过的空槽则失败。

线性探测

$$d_i=0,1,2,\dots ,m-1.$$

线性探测会逐个检查后续槽位，并在表尾回绕。只要表未满，它一定能找到空位；但连续占用区会越来越长，形成一次聚集。

EX示例 · 线性探测的聚集

假设表长为 7，$H(key)=keymod7$，依次插入 22, 43, 15：

关键字	初始地址	探测序列	最终地址	成功查找比较次数
22	1	1	1	1
43	1	1 → 2	2	2
15	1	1 → 2 → 3	3	3

三个关键字都映射到地址 1（因为它们都 $mod7=1$），于是线性探测把它们依次塞进 1、2、3，形成连续占用区。成功 ASL 为 $(1+2+3)/3=2$。

若再插入 29（$29mod7=1$），它会从 1 探测到 4 才找到空位，比较 4 次。这就是"堆积"让新关键字的插入代价越来越高。

平方探测

常见增量序列为：

$$d_i=0,1^2,-1^2,2^2,-2^2,\dots$$

平方探测能缓解线性探测的一次聚集，但探测位置不一定遍历整张表。即使表中仍有空位，也可能因表长和装填条件不合适而无法到达它。

ANTI反例 · 平方探测找不到空位

若表长 $m=8$，$H(key)=keymod8$，探测序列为 $0,1^2,2^2,\dots$。由于 $i^{2}mod8$ 只取 0, 1, 4 三个值（$1^2=1,2^2=4,3^2=9mod8=1,\dots$），平方探测永远到不了地址 2、3、5、6、7。即使表中仍有这些空槽，从某个初始地址出发也探测不到。

这证明"只要表没满就能找到空位"对平方探测不成立；它只在表长满足某些条件（如表长为素数且装填因子 < 0.5）时才保证覆盖。

双散列

$$H_i(key)=(H_1(key)+i{H}_2(key))modm.$$

第二个散列函数决定步长。为了遍历完整地址空间，$H_2(key)$ 应与表长 $m$ 互素，并且不能为 0。双散列通常比固定步长更不容易聚集。

同义词与二次冲突

同义词必然从同一初始地址开始，但探测中的冲突不一定只发生在同义词之间。两个初始地址不同的关键字，可能在后续探测时争用同一槽位。因此，"线性探测处理的冲突一定发生在同义词之间"是错误的。

ANTI反例 · 非同义词也可能碰撞

表长 7，$H(k)=kmod7$。关键字 8 初始地址 1，15 初始地址 1，它们互为同义词。但把 43（$43mod7=1$）插到地址 1，冲突后线性探测到地址 2；这时若再来一个初始地址就是 2 的关键字（比如 $k=9$，因为 $9mod7=2$），它想占地址 2，就会和已经停在那里的 43 相撞。这两个关键字的初始地址并不相同，所以这是一次非同义词之间的二次冲突。因此"线性探测处理的冲突一定发生在同义词之间"是错的。

开放定址删除：空槽与墓碑不同

直接把被删除槽位置为空，会截断其他关键字的探测链。例如某关键字因冲突存到后面，查找经过被清空位置时会提前判定失败。

WARN易错点 · 为什么删除不能直接清空

在开放定址表中，一个关键字可能因为冲突被放在离初始地址很远的位置。查找它是沿着探测序列一路走过来的。若把中途某个槽清成 EMPTY，查找在到达目标之前就会先遇到这个空槽，误以为"从未使用过"而提前判定失败。因此删除必须用墓碑标记，让查找继续走完探测链。

开放定址表至少需要三种状态：

EMPTY      从未使用；查找遇到它可以失败
OCCUPIED   保存有效关键字
DELETED    曾经使用但已删除；查找必须继续

DELETED 常称为墓碑标记。插入可以复用遇到的第一个墓碑，但仍要继续探测到空槽或原关键字，避免插入重复项。墓碑过多会拉长失败查找，因此需要周期性重建表。

EX示例 · 墓碑保证删除后仍能查到

表长 5，$H(k)=kmod5$。依次插入 1（地址 1）、6（地址 1，探测到 2）。此时表为 [_, 1, 6, _, _]。

• 删除 1 并直接清空：把地址 1 设为 EMPTY。查找 6 时从地址 1 出发，遇到 EMPTY 判定失败，虽然 6 还在地址 2。
• 删除 1 但写墓碑：把地址 1 设为 DELETED。查找 6 时从地址 1 出发，遇到墓碑继续，到地址 2 命中。

所以开放定址删除必须用墓碑，不能清空。

链地址法

链地址法为每个散列地址维护一条链（也可使用动态数组或平衡树）。所有同义词进入同一桶：

Value* find(vector<vector<Entry>>& table, int key) {
    auto& bucket = table[hash(key) % table.size()];
    for (auto& entry : bucket) {
        if (entry.key == key) return &entry.value;
    }
    return nullptr;
}

hash-chaining.cpp

链地址法的特点：

• 删除只需从链中摘除结点，没有墓碑问题；
• 装填因子可以大于 1；
• 需要额外指针或容器开销，局部性通常弱于开放定址；
• 分布均匀时，平均链长约为 $\alpha$。

O(·)复杂度 · 链地址法的查找

在均匀散列、链内无特殊顺序优化时：

• 成功查找：平均比较约 $1+{\displaystyle \frac{\alpha }{2}}$ 次（命中在链中平均位置）；
• 失败查找：平均检查约 $\alpha$ 个链结点（链的平均长度）。

具体公式会受头插/尾插、成功关键字分布和是否把访问桶计入比较影响。考试中应优先按实际链形逐项计算。

如何计算成功 ASL

查找成功时，对每个已存关键字沿其实际查找路径计数，再按成功概率加权。等概率时：

$$AS{L}_{success}=\frac{\text{所有已存关键字的成功比较次数之和}}{n}.$$

• 开放定址：比较次数是从初始地址到关键字最终位置经过的槽位数；
• 链地址：比较次数是该关键字在桶链中的位置，若从链头开始则第一个为 1。

插入时的探测次数通常就是日后成功查找该关键字的比较次数，前提是表未发生删除、移动或再散列。

如何计算失败 ASL

失败查找必须确定可能的初始地址集合。若 $H(key)=keymodp$，初始地址只有 $0$ 到 $p-1$，即使表长 $m>p$，也不能擅自按 $m$ 个入口平均。

对每个初始地址，沿探测序列数到第一个 EMPTY 为止；DELETED 和已占用但关键字不同的槽位都要继续。若各初始地址等概率：

$$AS{L}_{fail}=\frac{\text{各初始地址失败比较次数之和}}{\text{可能的初始地址数}}.$$

EX示例 · 失败 ASL 的完整计算

表长 $m=7$，$H(k)=kmod7$，插入 22, 43, 15 后，地址 1、2、3 被占用，其余为空。

失败入口只可能是地址 0～6（因为 $H$ 的值域是 $0\sim 6$）。对每个初始地址，数到第一个 EMPTY：

初始地址	探测	失败比较次数
0	0（空）	1
1	1 → 2 → 3 → 4（空）	4
2	2 → 3 → 4（空）	3
3	3 → 4（空）	2
4	4（空）	1
5	5（空）	1
6	6（空）	1

$$AS{L}_{fail}=\frac{1+4+3+2+1+1+1}{7}=\frac{13}{7}\approx 1.86.$$

注意失败入口数是 7（$m$ 的取值），但如果散列函数是 $H(k)=kmodp$ 且 $p<m$，分母应换成 $p$ 而不是 $m$。

示例：值域与表长不同

表长为 11，但散列函数是 $H(key)=keymod7$，则失败入口只有 0～6。不能把 7～10 当作同等可能的初始散列地址。线性探测形成连续占用区时，要分别从 0～6 数到第一个空槽，再除以 7。

WARN易错点 · 失败 ASL 的分母

失败 ASL 的分母是可能的初始地址数，由散列函数的值域决定，不总等于表长 $m$。例如 $H(k)=kmod7$ 且 $m=11$，失败入口只有 0～6 共 7 个，分母是 7，不是 11。

堆积如何影响性能

堆积不会改变已经选定的表长，也不会反过来改变散列函数或装填因子；它直接拉长探测序列，因此增大平均查找长度。改善方法包括：

• 选择分布更均匀的散列函数；
• 降低装填因子；
• 用平方探测或双散列减轻一次聚集；
• 使用链地址法；
• 超过阈值时扩容并再散列。

扩容与再散列

扩容不能只把旧数组复制到更大的数组。表长变化后，H(key) mod m 和探测序列都会变化，必须把每个有效关键字按新容量重新插入。

一次再散列需要 $O(n)$，但若容量按固定倍数增长，分摊到多次插入上的平均扩容成本仍可为 $O(1)$。开放定址表常在 $\alpha$ 接近某个阈值（例如 0.7～0.8，具体取决于策略）时扩容；这不是数据结构定义规定的唯一常数。

O(·)复杂度 · 再散列的均摊成本

一次扩容要搬 $n$ 个已有关键字，单次成本 $O(n)$。但若表长按固定倍数增长（如翻倍），那么在两次扩容之间会发生 $\mathrm{\Theta }(n)$ 次插入，每次插入分摊到 $\mathrm{\Theta }(1)$ 的扩容成本。因此整体平均仍是 $O(1)$。

散列表与有序结构的取舍

需求	散列表	平衡搜索树 / B+ 树
精确查找	平均 $O(1)$	$O(\log n)$
最坏保证	通常 $O(n)$	$O(\log n)$
范围查询	不擅长	擅长
有序遍历	需额外排序	结构天然支持
前驱/后继	不直接支持	支持
主要代价	冲突、扩容、空间	比较、旋转或结点 I/O

易错点

• 冲突不可完全避免；优秀散列函数只是让分布更均匀。
• 装填因子增大通常会降低而不是提高查找效率。
• 线性探测只要表未满就能遍历到空位，平方探测没有无条件的同样保证。
• 探测冲突可能发生在非同义词之间。
• 删除槽不能直接改为 EMPTY；墓碑不终止失败查找。
• 失败 ASL 的分母取决于可能的初始地址，而不总等于表长。
• 再散列必须重新计算每个关键字的位置。

交互式演示

用演示亲手比较四种冲突处理策略：输入 22, 43, 15（三个关键字都映射到地址 1），在线性探测下看到它们被逐个塞进 1、2、3 形成聚集；切到链地址则同义词进同一桶。演示会实时显示每个关键字的探测序列，并统计成功与失败 ASL、装填因子与冲突次数。

观察三个对照

先用线性探测插入 22, 43, 15，对比成功 ASL 与失败 ASL；再切到链地址看同义词聚集有哪些不同；最后尝试删除开放定址中的一个关键字，观察它留下的墓碑如何让查找继续走完探测链。

配套 Lab

完成 Lab 09-E-01：散列表实现与冲突统计，比较链地址与线性探测，并用不同装填因子测量成功、失败 ASL；进阶做 Lab 09-P-01：散列索引引擎——冲突策略与再散列大综合。

小结

散列表用地址计算替代有序比较，速度取决于散列函数、冲突策略和装填因子三者的组合。做构造题时，逐个写出初始地址和探测序列；做 ASL 题时，把成功关键字与失败入口分开计数。这样比背一个平均公式更可靠。

练习

1. 表长为 11，$H(key)=keymod11$，依次插入 22, 41, 53, 46, 30, 13, 1, 67。分别构造线性探测与链地址表。
2. 对上题计算成功 ASL，并逐个初始地址计算线性探测的失败 ASL。
3. 在线性探测表中删除一个位于聚集区中间的关键字，分别说明直接清空和使用墓碑的查找结果。
4. 解释为什么表长为 12、第二散列步长恒为 4 时，双散列可能找不到仍然存在的空位。
5. 某系统既需要按 ID 精确查询，也需要按时间范围扫描。应使用一张散列表、一个有序索引，还是同时维护两种结构？说明更新成本。