第 11 章散列表 (Hash Tables)

核心结论

字典操作 (Dictionary Operations)：INSERT、SEARCH、DELETE——所有平均 \(O(1)\) 时间（合理假设下）；最坏 \(\Theta(n)\)。
直接寻址 (Direct Addressing)：键值域 \(U\) 小（≤ 几百万）时，用大小 \(|U|\) 的数组 + 键当下标——所有操作 \(O(1)\) 最坏。
散列函数 (Hash Function)：把键 \(k\) 映射到 \(\{0, 1, ..., m-1\}\) 的桶号 \(h(k)\)；三种主流方法：除法、乘法、通用散列 (universal hashing)——后者用随机化保证对手不能制造最坏输入。
冲突解决：链接法 (Chaining)：每桶维护一个链表——所有操作平均 \(\Theta(1+\alpha)\)，α = n/m 是负载因子；实现简单、支持删除。
冲突解决：开放寻址 (Open Addressing)：所有元素存在表内，无指针——三种探查：线性、二次、双散列；删除难（需 DELETED 标记）；负载因子必须 < 1。
完全散列 (Perfect Hashing)：键集静态时可用两级散列——第一级到大小 n 的桶、第二级桶大小 n_j²——保证无冲突、SEARCH 最坏 \(O(1)\)、期望空间 \(O(n)\)。

本章主旨

本章是「动态集合 INSERT / SEARCH / DELETE」的工程首选实现——散列表 (hash table)。核心思想：用一个「散列函数」把大键值域压缩到小数组下标，用「冲突解决」处理多键 hash 到同槽的情况。三个关键层次：(1) §11.1 直接寻址——当键值域小时最优；(2) §11.2-11.4 散列 + 链接法 / 开放寻址——把大小缩到 O(n) 且 SEARCH 平均 O(1)；(3) §11.5 完全散列——特殊场景（静态键集）的最坏 O(1)。本章也是「随机化算法」「概率分析」「通用散列」理论的精彩展示。

一、核心概念

本章围绕 6 个核心概念展开：从直接寻址（最朴素）开始，引入散列函数、链接法冲突解决，再给出开放寻址的多种探查策略，最后讨论通用散列与完全散列。

概念	定义 + 重要性	实现提示
直接寻址表 (Direct-Address Table)	当键值域 \(U = \{0, 1, ..., m-1\}\) 时，用大小 m 的数组 T——T[k] 指向键为 k 的元素；所有操作 \(O(1)\) 最坏。	§11.1；缺点：当 \(\lvert U \rvert\) 巨大（字符串、电话号码）时不可行，浪费内存。
散列函数 (Hash Function)	把键 \(k\) 映射到桶号 \(h(k) \in \{0, 1, ..., m-1\}\)；三种方法：除法 (h(k) = k mod m)、乘法 (h(k) = ⌊m(kA mod 1)⌋)、通用散列 (随机化)。	§11.3；A ≈ (√5 - 1)/2 ≈ 0.618 是 Knuth 推荐值；通用散列克服固定函数被对手利用。
链接法 (Chaining)	每桶维护一个链表存储 hash 到该桶的所有元素；INSERT/DELETE 链表头插/删除，SEARCH 顺序扫描；平均 \(\Theta(1+\alpha)\)。	§11.2；α = n/m 是负载因子；最坏 \(\Theta(n)\)（所有键到一个桶）；实际中 α 适度时表现稳定。
冲突分析 (Collision Analysis)	简单均匀散列假设下，链接法期望 SEARCH 时间 = \(\Theta(1+\alpha)\)（定理 11.1, 11.2）；指示变量法严格证明。	§11.2；CHAINED-HASH-SEARCH 不成功 = \(\Theta(1+\alpha)\)、成功 = \(\Theta(1+\alpha)\)；插入 = \(O(1)\)。
开放寻址 (Open Addressing)	所有元素存在散列表内不外挂链表；探查序列由 \(h(k, i)\) 决定；三种：线性（主簇）、二次（次簇）、双散列（接近均匀）；必须 α < 1。	§11.4；HASH-INSERT / HASH-SEARCH / HASH-DELETE；DELETED 标记处理删除；空间利用率 vs 链接法。
完全散列 (Perfect Hashing)	静态键集 + 两级散列：第一级大小 n 桶，第二级桶大小 n_j²；用通用散列保证第二级无冲突；SEARCH 最坏 \(O(1)\)，期望空间 \(O(n)\)。	§11.5；定理 11.9（生日悖论变体）；适用于编译器的保留字表、CD 文件名表等。

概念

定义 + 重要性

实现提示

直接寻址表 (Direct-Address Table)

当键值域 \(U = \{0, 1, ..., m-1\}\) 时，用大小 m 的数组 T——T[k] 指向键为 k 的元素；所有操作 \(O(1)\) 最坏。

§11.1；缺点：当 \(\lvert U \rvert\) 巨大（字符串、电话号码）时不可行，浪费内存。

散列函数 (Hash Function)

把键 \(k\) 映射到桶号 \(h(k) \in \{0, 1, ..., m-1\}\)；三种方法：除法 (h(k) = k mod m)、乘法 (h(k) = ⌊m(kA mod 1)⌋)、通用散列 (随机化)。

§11.3；A ≈ (√5 - 1)/2 ≈ 0.618 是 Knuth 推荐值；通用散列克服固定函数被对手利用。

链接法 (Chaining)

每桶维护一个链表存储 hash 到该桶的所有元素；INSERT/DELETE 链表头插/删除，SEARCH 顺序扫描；平均 \(\Theta(1+\alpha)\)。

§11.2；α = n/m 是负载因子；最坏 \(\Theta(n)\)（所有键到一个桶）；实际中 α 适度时表现稳定。

冲突分析 (Collision Analysis)

简单均匀散列假设下，链接法期望 SEARCH 时间 = \(\Theta(1+\alpha)\)（定理 11.1, 11.2）；指示变量法严格证明。

§11.2；CHAINED-HASH-SEARCH 不成功 = \(\Theta(1+\alpha)\)、成功 = \(\Theta(1+\alpha)\)；插入 = \(O(1)\)。

开放寻址 (Open Addressing)

所有元素存在散列表内不外挂链表；探查序列由 \(h(k, i)\) 决定；三种：线性（主簇）、二次（次簇）、双散列（接近均匀）；必须 α < 1。

§11.4；HASH-INSERT / HASH-SEARCH / HASH-DELETE；DELETED 标记处理删除；空间利用率 vs 链接法。

完全散列 (Perfect Hashing)

静态键集 + 两级散列：第一级大小 n 桶，第二级桶大小 n_j²；用通用散列保证第二级无冲突；SEARCH 最坏 \(O(1)\)，期望空间 \(O(n)\)。

§11.5；定理 11.9（生日悖论变体）；适用于编译器的保留字表、CD 文件名表等。

二、详细笔记

11.1 直接寻址表

What：当键值域 \(U\) 小且实用时，用大小等于 \(|U|\) 的数组 T——T[k] 直接指向键为 k 的元素。

Why：最简单的「数组当字典」；所有操作 \(O(1)\) 最坏——但要求 |U| 不可太大。

How：

操作接口（§11.1）：

\[\begin{array}{rl} & \textbf{DIRECT-ADDRESS-SEARCH}(T, k) \\ 1 & \textbf{return } T[k] \\ & \textbf{DIRECT-ADDRESS-INSERT}(T, x) \\ 1 & T[x.\text{key}] = x \\ & \textbf{DIRECT-ADDRESS-DELETE}(T, x) \\ 1 & T[x.\text{key}] = \text{NIL} \end{array}\]

所有操作 \(O(1)\)。
位向量变体（练习 11.1-2）：每个槽用 1 bit 代替指针——节省空间，但只支持「是否有键」信息，无法存卫星数据。
不支持不重复键（练习 11.1-3）：每个 T[k] 改存链表头——支持多元素；但 INSERT / DELETE 都成平均 \(\Theta(1 + \text{链长})\)。

When： . 键值域小（≤ 几百万）且不浪费内存 → 直接寻址最优。 . 键值域巨大（如 64 位整数、字符串）→ 必须用散列表。 . 极端性能要求（最坏 O(1)） + 键集小 + 静态 → 完全散列（§11.5）。

Example：键值域 U = {0, 1, …, 9}，实际键 K = {2, 3, 5, 8}，则 T = ⟨NIL, NIL, ptr2, ptr3, NIL, ptr5, NIL, NIL, ptr8, NIL⟩；T[k] 直接即答案。

11.2 散列表（链接法）

What：用散列函数 h 把键压缩到大小 m 的桶号；冲突的元素用链表串联；负载因子 α = n/m。

Why：当 |U| ≫ n 时，需要 size = O(n) 的表而非 O(|U|)；链接法是最简单的冲突解决方案且支持删除。

How：

操作接口（§11.2）：

\[\begin{array}{rl} & \textbf{CHAINED-HASH-INSERT}(T, x) \\ 1 & \textbf{insert } x \textbf{ at the head of list } T[h(x.\text{key})] \\ & \textbf{CHAINED-HASH-SEARCH}(T, k) \\ 1 & \textbf{search for an element with key } k \textbf{ in list } T[h(k)] \\ & \textbf{CHAINED-HASH-DELETE}(T, x) \\ 1 & \textbf{delete } x \textbf{ from the list } T[h(x.\text{key})] \end{array}\]
性能分析（§11.2，定理 11.1, 11.2）：
- 假设：简单均匀散列——每个键独立等概率散到任一桶。
- 不成功 SEARCH：期望扫描整条 T[h(k)]；E[n_{h(k)}] = α；总期望时间 Θ(1 + α)。
- 成功 SEARCH：设查找 x_i（i 在插入顺序中），其后插入的键与 x_i 同桶则会被检查；用指示变量 X_{ij} = I{h(k_i) = h(k_j)}，E[X_{ij}] = 1/m；
  
  \[E[\text{probes}] = \frac{1}{n} \sum_{i=1}^{n} \left(1 + \sum_{j=i+1}^{n} \frac{1}{m}\right) = 1 + \frac{n-1}{2m} = 1 + \frac{\alpha}{2} - \frac{\alpha}{2n}\]
- 总时间 = Θ(1 + α)；m ≥ 比例 n 时 α = O(1)，操作平均 Θ(1)。

When： . 不知道键分布、想让平均 O(1) → 链接法。 . 要支持 DELETE → 链接法（开放寻址删除难处理）。 . 极端负载（α ≫ 1）+ 偶尔查询 → 链接法仍可工作（虽然慢）。

Example（示范）：表大小 m = 9，h(k) = k mod 9；插入 5, 28, 19, 15, 20, 33, 12, 17, 10： * h(5) = 5, h(28) = 1, h(19) = 1, h(15) = 6, h(20) = 2, h(33) = 6, h(12) = 3, h(17) = 8, h(10) = 1。 * 最终表：T[1] = 28 → 19 → 10；T[2] = 20；T[3] = 12；T[5] = 5；T[6] = 15 → 33；T[8] = 17；其余 NIL。 * 不成功 SEARCH (k = 7)：扫描 T[7] = NIL → 1 步；成功 SEARCH (k = 19)：扫描 T[1] → 28 → 19，2 步。

11.3 散列函数

What：设计散列函数的方法论——满足「简单均匀散列」假设；三种方法：除法（h(k) = k mod m）、乘法（h(k) = ⌊m(kA mod 1)⌋）、通用散列（h_{ab}(k) = ((ak+b) mod p) mod m）。

Why：散列函数的选择决定散列表性能的「实际意义」——即使平均 Θ(1+α)，如果键被故意构造为「全散到同桶」，最坏仍是 Θ(n)；只有通用散列能阻止对手。

How：

除法（§11.3.1）：
- h(k) = k mod m；
- 避免 m 为 2 的幂（h(k) 只看低 p 位）；
- m 应是不太接近 2 的幂的素数——例 m = 701（接近 2000/3 又是素数且远离 2 的幂）。
乘法（§11.3.2）：
- h(k) = ⌊m(kA mod 1)⌋，0 < A < 1；
- 取 A ≈ (√5 - 1)/2 ≈ 0.618；
- 用 w 位字：s = ⌊A · 2^w⌋，hash = 截 r_0（low w 位的高 p 位）；
- m 不必特殊，取 2^p 较方便。
通用散列（§11.3.3）：
- 集合 H_{pm} = \{h_{ab}(k) = ((ak+b) mod p) mod m | a ∈ Z_p*, b ∈ Z_p\}；
- 大小 = p(p-1)；
- 关键定理 11.5：对任意不同 k, l，Pr{h(k) = h(l)} ≤ 1/m，故 H_{pm} 是 universal。
- 定理 11.3：用通用散列，期望链长 ≤ α（不成功）/ ≤ 1 + α（成功）——与「键分布是否独立」无关。
- 推论 11.4：用通用散列 + 链接法，任何 n 个操作（含 O(m) 次 INSERT）的期望总时间 Θ(n)——对手无法制造最坏。

When： . 对手可能构造输入（如网络攻击、安全哈希）→ 通用散列。 . 已知输入分布（与散列函数一致）→ 除法/乘法。 . 「理论保证」是必要条件 → 通用散列。

Example（通用散列）：p = 17, m = 6, h_{3,4}(8) = ((3·8 + 4) mod 17) mod 6 = (28 mod 17) mod 6 = 11 mod 6 = 5。任何不同 k, l 碰撞概率 ≤ 1/6。

11.4 开放寻址

What：所有元素存在散列表内（不外挂链表）；用探查序列 h(k, 0), h(k, 1), …, h(k, m-1) 找到空位；要求是 {0, 1, …, m-1} 的排列。

Why：比链接法省指针（缓存友好、内存利用率高）；但删除复杂（需 DELETED 标记），且负载因子 α 必 ≤ 1。

How：

通用探查算法（§11.4）：

\[\begin{array}{rl} & \textbf{HASH-INSERT}(T, k) \\ 1 & i = 0 \\ 2 & \textbf{repeat} \\ 3 & \quad j = h(k, i) \\ 4 & \quad \textbf{if } T[j] = \text{NIL} \\ 5 & \quad\quad T[j] = k \\ 6 & \quad\quad \textbf{return } j \\ 7 & \quad \textbf{else } i = i + 1 \\ 8 & \textbf{until } i == m \\ 9 & \textbf{error “hash table overflow”} \end{array}\]
三种探查策略：
- 线性探查：h(k, i) = (h'(k) + i) mod m——简单，但主簇 (primary clustering)（连续占用块延长），m 种序列。
- 二次探查：h(k, i) = (h'(k) + c_1 i + c_2 i^2) mod m——缓解主簇，但次簇（同起始位置则同序列），m 种序列。
- 双散列：h(k, i) = (h_1(k) + i h_2(k)) mod m——m² 种序列，接近理论最优（均匀散列）。
开放寻址分析（§11.4，定理 11.6, 11.8）：
- 假设：均匀散列（每种 m! 排列等概率）。
- 不成功 SEARCH = INSERT = 期望 ≤ 1/(1-α) 探查。
- 成功 SEARCH：平均 (1/α) ln(1/(1-α)) 探查。
- 当 α ≤ 1/2 时，不成功 SEARCH ≤ 2 探查；α = 0.9 时 ≤ 10 探查。
删除困难：直接 NIL 化会破坏探查链（让本应找到的元素找不到）；用「DELETED」特殊标记，SEARCH 跳过、INSERT 当 NIL 用。缺点：SEARCH 时间不再依赖 α——所以频繁删除用链接法。

When： . 只插入 + 偶尔查找 → 开放寻址。 . 频繁查找 + 不删除 + 内存敏感 → 开放寻址 + 双散列。 . 频繁插入删除 → 链接法。

Example（双散列）：m = 13，h_1(k) = k mod 13，h_2(k) = 1 + (k mod 11)；插入 14：j₀ = 1 占用 → j₁ = (1+3) mod 13 = 4 占用 → j₂ = (1+6) mod 13 = 7 空 → 插入 T[7] = 14。共 3 探查。

11.5 完全散列

What：当键集静态（编译后不再变）时，用两级散列——第一级桶大小 n、第二级桶大小 n_j² 平方——保证无冲突、SEARCH 最坏 O(1)。

Why：通用散列期望 O(1)，但最坏仍是 O(n)（罕见但可能）；完全散列给出最坏保证，适合静态字典（编译器保留字表、CD 文件名表）。

How：

两级结构（§11.5，图 11.6）：
- 第一级：m = n 个桶，h ∈ H_{pm} 随机选。
- 第二级：每个第一级桶 j 用专用散列函数 h_j ∈ H_{p,m_j}，m_j = n_j²（n_j = 第 j 桶的键数）。
- 选 h_j 试几次直到无碰撞（定理 11.9：随机选 n² 大小的表无碰撞的概率 > 1/2）。
空间分析（§11.5，定理 11.10）：
- E[Σm_j] = E[Σn_j²] ≤ n + 2 · E[ΣC(n_j, 2)] = n + (n-1) = 2n - 1 < 2n。
- 用恒等式 \(a^2 = a + 2\binom{a}{2}\) 与 Markov 不等式。
- 推论 11.12：总存储空间 < 4n 的概率 > 1/2——只要试几次就能找到「节省空间」的函数。

When： . 编译器的关键字表 → 完全散列。 . 静态查找表（不变数据集的快速查找）→ 完全散列。 . 键集动态变化 → 普通散列（链接法或开放寻址）。

Example（图 11.6）：K = {10, 22, 37, 40, 52, 60, 70, 72, 75}，第一级 m = 9，a = 3, b = 42, p = 101；h(75) = ((3·75+42) mod 101) mod 9 = 267 mod 101 mod 9 = 65 mod 9 = 2。所有 75 这类到桶 2 的键（共 1 个，因为 n_2 = 1）独立用 h_2 ∈ H_{p,m_2}（m_2 = 1² = 1）二次散列——无冲突。

三、关键图表

核心公式对照表

式编号

内容

§11.1 直接寻址

T[k] 存键为 k 的元素；所有操作 Θ(1) 最坏

§11.2 负载因子

α = n/m

定理 11.1

链接法不成功 SEARCH 平均 Θ(1 + α)

定理 11.2

链接法成功 SEARCH 平均 Θ(1 + α)

式 11.3

通用散列 h_{ab}(k) = ((ak+b) mod p) mod m

式 11.4

通用散列族 H_{pm} 大小 = p(p-1)

Knuth 推荐 A

A ≈ (√5 - 1)/2 ≈ 0.6180339887

§11.4 三种探查

线性 / 二次 / 双散列 (m / m / m² 种序列)

定理 11.6

开放寻址不成功 SEARCH 期望 ≤ 1/(1-α)

定理 11.8

开放寻址成功 SEARCH 期望 ≤ (1/α) ln(1/(1-α))

定理 11.9

m = n² 时 random h 无冲突概率 > 1/2

式 11.6

\(a^2 = a + 2\binom{a}{2}\)

定理 11.10

E[Σn_j²] < 2n（完全散列二级表总大小）

推论 11.12

Pr{Σm_j ≥ 4n} < 1/2

四、思维导图

mindmap
  root((第 11 章 散列表))
    直接寻址
      键当下标
      O(1)最坏
      浪费空间
    散列函数
      除法
      乘法
      通用散列
    链接法
      每桶链表
      1+α
      支持删除
    开放寻址
      线性
      二次
      双散列
      DELETED
    性能分析
      负载因子α
      期望O(1)
      最坏Θ(n)
    完全散列
      静态键
      两级
      平方大小
      最坏O(1)
    应用
      编译器符号
      缓存
      字典

五、重点与易错点

「平均 O(1)」不是「最坏 O(1)」——这是散列表与完全散列 / 直接寻址的关键差异；前者靠「输入随机」假设、后者靠「函数随机」或「键集静态」。
除法散列 m 应是素数且远离 2 的幂 — 否则 h(k) 只看部分位（如 m = 2^p 看 k 的低 p 位）；字符键用 \(m = 2^p - 1\) 时同字母异序同 hash（练习 11.3-3）。
链接法最坏 Θ(n) — 当所有键 hash 到同桶（Fn = 1 桶）；通用散列保证任何输入「期望」，固定函数被对手利用可能「构造」worst case。
开放寻址不允许 α ≥ 1 — 必须有空位才能插入；通常 α ≤ 0.5、0.7 较好；α 0.9 时不成功 SEARCH 平均 10 探查。
开放寻址删除必须用 DELETED 标记 — 直接 NIL 会切断探查链；缺点：DELETED 槽不释放 → SEARCH 时间不依赖 α。
双散列要求 h_2(k) 与 m 互素 — 否则只探查 1/d 的表就回环；常让 m 为素数，h_2(k) 返回 1..m-1。
线性探查的主簇问题 — 一旦连续占用块形成，会越长越长；α = 0.5 时线性探查期望 ≈ 1.5 探查但尾部可达 50+ 探查。
二次探查只缓解主簇不消除次簇 — 两个键同起始位置则后续序列完全相同；m 种序列的设计本质受限。
均匀散列是理想化假设 — 实际不可实现（无法枚举 m! 序列）；双散列是「最接近」的实用方案。
完全散列只用于静态键集 — 一旦 INSERT/DELETE 动态变化，必须重建散列；这是完全散列的工程局限。
完全散列二级表 m_j = n_j² — 看似浪费但 E[Σn_j²] < 2n（用恒等式 + 通用散列）；推论用 Markov 不等式 → 试几次能找到省空间的 h_j。
「散列 + 链表」在 Java HashMap 是经典组合 — 桶 = 链表/红黑树；桶内多元素时升级为红黑树（Java 8+）以保持最坏 O(lg n)。
「同义词 = 散列同桶的元素」 — 主簇 / 次簇 / 双散列的分别即「同义词聚集程度」。
「散列和 BST 的选择」：纯字典操作（仅 INSERT/SEARCH/DELETE）→ 散列表；需有序遍历/范围查询/中位数 → BST。
问题 11-4 的 2-通用与认证 — 2-universal 比 universal 强；这构成消息认证 (MAC) 的数学基础。

补充：与其他章节的衔接

第 5 章（概率分析）：通用散列与随机化 quicksort 同模式——「随机选避免最坏」。
第 10 章（基本数据结构）：链接法 / 自由表都用链表（第 10.2 节）；开放寻址不用指针，体现内存布局优势。
第 12 章（BST）：BST 是有序字典的中枢；散列表是「无序」的字典（无 SUCCESSOR）。
第 13 章（红黑树）/ 第 19 章（斐波那契堆）：实际工程中常把散列桶升级为树结构（Java HashMap）应对大量 hash 冲突。
第 31 章（数论）：通用散列的理论（定理 11.5）依赖「a(k-l) mod p ≠ 0」（p 素数，乘法逆元存在）；第 31 章铺垫这些数论工具。
第 35 章（近似算法）：完全散列可看作「键集预知 = 完全优化」的特例——一般问题只能近似。

第 11 章 散列表 (Hash Tables)

核心结论

一、核心概念

二、详细笔记

11.1 直接寻址表

11.2 散列表（链接法）

11.3 散列函数

11.4 开放寻址

11.5 完全散列

三、关键图表

四、思维导图

五、重点与易错点

补充：与其他章节的衔接

第 11 章散列表 (Hash Tables)