第11章 散列表 — 章节汇总

章节概览

本章是 Part III 数据结构的核心章节，系统介绍了散列（Hashing）技术——一种实现字典操作（INSERT、DELETE、SEARCH）期望 $O(1)$ 时间的高效方法。从直接寻址表出发，逐步引入散列函数、冲突解决策略（链地址法与开放寻址法），最终讨论工程实践中的散列表设计。散列的核心思想是：通过散列函数将大域关键字映射到小域槽位，以空间换时间，实现接近常数时间的操作。

---

11.1 直接寻址表

小节	核心主题	关键结论
11.1 直接寻址表	直接寻址、位向量	所有操作 $O(1)$ 最坏情况；空间 $\Theta(

核心思路：当关键字全域 $U$ 较小时，使用数组 $T[\mathrm{0..}m-1]$ 直接以关键字为索引存储元素。每个字典操作（SEARCH/INSERT/DELETE）仅需 $O(1)$ 最坏情况时间。局限在于：当 $|U|$ 很大而实际存储的关键字集合 $K$ 很小时，空间浪费严重。

---

11.2 散列表

小节	核心主题	关键结论
11.2 散列表	散列函数、链地址法、装载因子	期望搜索 $\Theta (1+\alpha )$；空间 $\Theta(

核心思路：使用散列函数 $h:U\to \{0,1,\dots ,m-1\}$ 将关键字映射到 $m$ 个槽位（$m\ll |U|$）。当两个关键字映射到同一槽位时发生冲突（collision），通过链地址法（chaining）解决：每个槽位维护一个链表，存储所有映射到该槽位的元素。装载因子 $\alpha =n/m$ 是性能的关键参数。

核心定理：

• 定理11.1：不成功搜索期望时间 $\Theta (1+\alpha )$
• 定理11.2：成功搜索期望时间 $\Theta (1+\alpha )$（使用指示器随机变量 + 期望的线性性证明）

---

11.3 散列函数

小节	核心主题	关键结论
11.3 散列函数	除法散列、乘法散列、全域散列	全域散列保证任意输入下期望 $O(1)$

核心思路：散列函数的质量直接决定散列表的性能。本章介绍了三种层次的散列策略：

1. 静态散列：除法散列 $h(k)=k\mathrm{mod}m$（快但无保证）、乘法散列 $h(k)=\lfloor m(kA\mathrm{mod}1)\rfloor$（Knuth 推荐 $A=(\sqrt{5}-1)/2$）
2. 全域散列（Universal Hashing）：从函数族 $\mathcal{H}$ 中随机选择，保证任意两关键字碰撞概率 $\le 1/m$。两种构造：基于数论的 ${\mathcal{H}}_{p,m}$（定理11.4）和基于乘法移位的 $2/m$-全域族（定理11.5）
3. 长输入散列：密码学散列（SHA-256）+ 加盐技术

---

11.4 开放寻址法

小节	核心主题	关键结论
11.4 开放寻址法	线性探测、双重散列、性能分析	不成功搜索 $\le 1/(1-\alpha )$；成功搜索 $\le \frac{1}{\alpha }\ln \frac{1}{1-\alpha }$

核心思路：所有元素存储在散列表数组内部，不使用额外存储。插入时按探测序列依次检查槽位，直到找到空位。三种探测策略：

核心定理：

• 定理11.6：不成功搜索期望探测次数 $\le 1/(1-\alpha )$
• 定理11.8：成功搜索期望探测次数 $\le \frac{1}{\alpha }\ln \frac{1}{1-\alpha }$

---

11.5 实际应用考虑

小节	核心主题	关键结论
11.5 实际应用考虑	内存层次、线性探测删除、wee散列函数	层次内存模型下线性探测最优；5-独立保证常数期望时间

核心思路：在实际计算机系统中，内存层次结构（寄存器→缓存→主存）使得缓存局部性成为性能关键因素。线性探测因连续探测在同一缓存块而表现优异。wee散列函数基于RC6加密算法，可在寄存器中高效计算，配合线性探测实现高性能散列表。

核心结论：

• 定理11.9（Pagh et al.）：若 $h_1$ 是5-独立且 $\alpha \le 2/3$，线性探测期望常数时间
• wee散列函数计算速度比探测一个随机槽位快2-10倍

---

本章核心知识点

三种字典实现对比

实现方式	搜索	插入	删除	空间	最坏搜索
直接寻址表	$O(1)$	$O(1)$	$O(1)$	$\Theta (\Vert U\Vert )$	$O(1)$
链地址法散列	$O(1+\alpha )$ 期望	$O(1)$	$O(1)$	$\Theta (n+m)$	$O(n)$
开放寻址散列	$O(1/(1-\alpha ))$ 期望	$O(1/(1-\alpha ))$ 期望	复杂	$\Theta (m)$	$O(n)$

散列函数对比

散列方法	公式	优点	缺点	性质
除法散列	$h(k)=k\mathrm{mod}m$	极快	$m$ 选择受限	无保证
乘法散列	$h(k)=\lfloor m(kA\mathrm{mod}1)\rfloor$	$m$ 自由选择	无保证	无保证
乘法移位法	$h_a(k)=(ak\mathrm{mod}{2}^w)\gg (w-\ell )$	三条指令	无保证	$2/m$-全域
全域散列（数论）	$h_{a,b}(k)=((ak+b)\mathrm{mod}p)\mathrm{mod}m$	有理论保证	较慢	全域

开放寻址探测策略对比

探测策略	探测序列	探测序列数	聚类问题	缓存性能
线性探测	$h(k,i)=(h_1(k)+i)\mathrm{mod}m$	$m$	一次聚类	最优
二次探测	$h(k,i)=(h_1(k)+c_{1}i+c_2{i}^2)\mathrm{mod}m$	$m$	二次聚类	中等
双重散列	$h(k,i)=(h_1(k)+i\cdot h_2(k))\mathrm{mod}m$	$\Theta (m^2)$	几乎无	较差

装载因子对性能的影响

$\alpha$	链地址法期望搜索	开放寻址不成功搜索	开放寻址成功搜索
0.5	$\Theta (1.5)$	$\le 2$	$<1.387$
0.75	$\Theta (1.75)$	$\le 4$	$<1.839$
0.9	$\Theta (1.9)$	$\le 10$	$<2.559$

---

与前序章节的知识关联

前序章节	关联方式
第10章 基本数据结构	直接寻址表是数组的直接应用（10.1节）；链表用于链地址法（10.2节）
第5章 概率分析	散列分析依赖指示器随机变量（5.2节）和期望的线性性；全域散列是随机化技术的经典应用（5.3节）
第8章 线性时间排序	散列与比较排序的下界无关，散列不基于比较
第9章 中位数与序统计	散列表不支持高效的序统计操作（min/max/successor）

---

学习路线

第11章学习路径：
  11.1 直接寻址表（O(1)操作→空间局限）
    → 11.2 散列表（散列函数→链地址法→装载因子分析）
      → 11.3 散列函数（除法→乘法→全域散列→长输入）
        → 11.4 开放寻址法（线性探测→双重散列→性能分析）
          → 11.5 实际应用考虑（内存层次→wee散列函数）

学习建议

本章是数据结构部分最重要的章节之一。11.1-11.2 是基础，重点理解从直接寻址到散列的思想跃迁。11.3 是数学最密集的一节，全域散列的构造与证明（定理11.4）需要反复推敲。11.4 的开放寻址性能分析（定理11.6/11.8）是考试重点。11.5 的工程视角（内存层次、wee散列函数）帮助理解理论与实践的差距。建议学完本章后对比第12章的二叉搜索树，理解散列 $O(1)$ 期望 vs BST $O(\lg n)$ 最坏的设计取舍。

散列表