企业官网建设流程全解析

• 文档
• 教程
• 教育

导读：本篇基于 docs/Chap11/Problems/11-1.md 的原始题面，系统讲解《算法导论》（Introduction to Algorithms, Third Edition）第 11 章 Problem 11-1 的完整推导。该题研究在均匀散列（uniform hashing）假设下，开放寻址散列表逐次插入 n 个元素时所需探测次数（probe）的尾概率上界，并最终证明全部 n 次插入中最长探测序列的期望长度为 O(lg n)。读完本文，你将掌握尾概率链式放缩、联合界（union bound）与尾和公式（tail-sum formula）三种典型的概率分析手法，并理解它们如何组合出散列表最坏情形下的期望行为。

问题定位与背景知识

开放寻址与探测序列

开放寻址（open addressing）是一种将所有元素直接存放在散列表槽位中的冲突解决方式：当插入一个键 k 时，依次考察探测序列

$$h(k, 0), h(k, 1), \ldots, h(k, m-1)$$

直到找到一个空槽。与之相对的是链地址法（chaining），后者在 11.2.md 中有大量配套习题（如 11.2-2 给出了h(k) = k mod 9的分链示例，11.2-6 讨论如何在已知最长链长度 L 时均匀随机抽取一个键）。本问题聚焦开放寻址，其核心随机量是单次插入所需的探测次数X_i 与全程最长探测序列X = max_{1 ≤ i ≤ n} X_i。

均匀散列假设与装载因子

题目要求的推导建立在均匀散列假设之上：每个键的探测序列等可能地是 m 个槽位的任意一种排列（共 m! 种）。因此，在探测过程中，每次新探测到的槽位是"尚未探测过的槽位中的均匀随机一个"，这保证了条件概率的链式放缩是合法的。

记装载因子

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

本问题的关键前提是n ≤ m/2，即装载因子不超过 1/2。这个前提保证了表远未填满，探测很少会"走遍"整张表，从而可以给出指数衰减的尾概率。

前置理论：期望探测次数上界（定理 11.6 与 11.8）

书中第 11.4 节的两个经典上界在本问题的背景中反复出现（仓库配套习题 11.4-3 与 11.4-5 即直接引用这两个定理）：

• 定理 11.6（不成功查找的期望探测次数）：均匀散列下，不成功查找的期望探测次数至多为

$$\frac{1}{1 - \alpha}$$

• 定理 11.8（成功查找的期望探测次数）：均匀散列下，成功查找的期望探测次数至多为

$$\frac{1}{\alpha} \ln \frac{1}{1 - \alpha}$$

11.4-3 代入 α = 3/4 与 α = 7/8 分别得到：不成功查找期望 4 次与 8 次探测；成功查找期望约 1.848 次与约 2.377 次探测。而 11.4-5 利用这两个上界求解方程 1/(1-α) = 2·(1/α)ln(1/(1-α))，得到 α ≈ 0.71533。这些结果关注的是"平均"行为，而 Problem 11-1 关注的是更精细的"尾部"行为与最坏情形，二者互为补充。

原题重述（仓库原文完整保留）

仓库文件 docs/Chap11/Problems/11-1.md 给出了完整题面，其解答部分标注为(Removed)（该仓库对部分题目刻意删去了解答）。题面如下：

Suppose that we use an open-addressed hash table of size $m$ to store $n \le m / 2$ items.

a.Assuming uniform hashing, show that for $i = 1, 2, \ldots, n$, the probability is at most $2^{-k}$ that the $i$th insertion requires strictly more than $k$ probes.

b.Show that for $i = 1, 2, \ldots, n$, the probability is $O(1 / n^2)$ that the $i$th insertion requires more than $2\lg n$ probes.

Let the random variable $X_i$ denote the number of probes required by the $i$th insertion. You have shown in part (b) that $\Pr{X_i > 2\lg n} = O(1 / n^2)$. Let the random variable $X = \max_{1 \le i \le n} X_i$ denote the maximum number of probes required by any of the $n$ insertions.

c.Show that $\Pr{X > 2\lg n} = O(1 / n)$.

d.Show that the expected length $\text E[X]$ of the longest probe sequence is $O(\lg n)$.

四问层层递进：先证明单次插入的指数尾概率（a），再取 $k = 2\lg n$ 得到多项式尾概率（b），随后用联合界把所有 n 次插入"合并"为全程最长探测序列的尾概率（c），最后借助尾和公式把概率界翻译成期望界（d）。下文逐问给出完整推导。

逐问推导与证明

a. 第 i 次插入需要超过 k 次探测的概率至多 $2^{-k}$

在第 i 次插入发生时，表中已经存有 i - 1 个元素。由于均匀散列，第 i 次插入的第 1 次探测命中有元素槽位的概率为

$$\frac{i - 1}{m} \le \frac{n - 1}{m} \le \frac{n}{m} \le \frac{1}{2}$$

若前 j 次探测全部命中已占用槽位，则第 j + 1 次探测命中有元素槽位的条件概率为

$$\frac{i - 1 - j}{m - j} \le \frac{i - 1}{m} \le \frac{1}{2}$$

（分子分母同步减去已探测过的 j 个槽位，比值不会变大。）由概率的链式法则，"第 i 次插入需要严格超过 k 次探测"等价于"前 k 次探测全部命中已占用槽位"，因此

$$\Pr{X_i > k} \le \left(\frac{1}{2}\right)^k = 2^{-k}$$

这里有两个值得注意的细节：

• 条件概率放缩到 (i-1)/m ≤ n/m ≤ 1/2 时，结论与 i 的具体取值无关，因此该上界对 i = 1, 2, ..., n 一致成立；
• 放缩只用到了 $n \le m / 2$，它保证了每步命中的条件概率都不超过 1/2，从而形成指数衰减。

b. 超过 $2\lg n$ 次探测的概率为 $O(1 / n^2)$

直接取 a 问的结论，令 $k = 2\lg n$：

$$\Pr{X_i > 2\lg n} \le 2^{-2\lg n} = \left(2^{\lg n}\right)^{-2} = n^{-2}$$

即

$$\Pr{X_i > 2\lg n} = O!\left(\frac{1}{n^2}\right)$$

这一结果把指数尾界翻译成了关于元素个数 n 的平方倒数，为 c 问的联合界提供了基础。

c. 最长探测序列超过 $2\lg n$ 的概率为 $O(1 / n)$

定义全程最长探测序列 $X = \max_{1 \le i \le n} X_i$。事件 ${X > 2\lg n}$ 等价于"存在某次插入 i 使得 $X_i > 2\lg n$"，即

$${X > 2\lg n} = \bigcup_{i=1}^{n} {X_i > 2\lg n}$$

由联合界（union bound，即 $\Pr{\cup_i A_i} \le \sum_i \Pr{A_i}$），并结合 b 问对每个 i 一致成立的上界：

$$\Pr{X > 2\lg n} \le \sum_{i=1}^{n} \Pr{X_i > 2\lg n} \le n \cdot O!\left(\frac{1}{n^2}\right) = O!\left(\frac{1}{n}\right)$$

这说明：尽管单次插入出现长探测序列的概率只有 $O(1/n^2)$，但由于要"同时管理" n 次插入，全程最长的探测序列突破 $2\lg n$ 的概率被放大到 $O(1/n)$。这一概率仍然趋近于 0，只是衰减得慢了一个数量级。

d. 最长探测序列的期望长度为 $O(\lg n)$

对非负整值随机变量 X，期望可以由尾和公式（tail-sum formula）表示：

$$\text E[X] = \sum_{k = 0}^{\infty} \Pr{X > k}$$

将求和按阈值 $k_0 = 2\lg n$ 分为两段：

第一段（0 ≤ k < 2 lg n）：概率不超过 1，因此这一段至多贡献 $2\lg n$。

第二段（k ≥ 2 lg n）：对任意 $k \ge 2\lg n$，结合 a 问与联合界：

$$\Pr{X > k} \le n \cdot 2^{-k}$$

于是第二段的上界为等比级数：

$$\sum_{k = 2\lg n}^{\infty} n \cdot 2^{-k} = n \cdot \frac{2^{-2\lg n}}{1 - 1/2} = n \cdot 2^{1 - 2\lg n} = \frac{2n}{n^2} = \frac{2}{n}$$

综合两段：

$$\text E[X] \le 2\lg n + \frac{2}{n} = O(\lg n)$$

结论：在 $n \le m/2$（即装载因子至多 1/2）与均匀散列的假设下，开放寻址散列表 n 次插入中最长探测序列的期望长度为 $O(\lg n)$。

这个结果的证明脉络值得单独强调——它展示了概率分析中三个基本工具的"接力"：

边界条件讨论：为什么要求 $n \le m / 2$

a 问的每一步条件概率都放缩到 (i-1)/m ≤ n/m ≤ 1/2，这是整个推导链的地基。如果装载因子 α 接近 1，期望探测次数会急剧恶化：

• 由定理 11.6，不成功查找的期望探测次数为 1/(1-α)，当 α → 1 时趋于无穷；
• 仓库配套习题 11.4-3 也量化了这一点：α = 3/4 时不成功查找期望 4 次探测，α = 7/8 时升至 8 次。

11.4-5 进一步求出不成功查找期望恰好等于成功查找期望两倍的装载因子 α ≈ 0.71533。相比之下，本问题在 α ≤ 1/2 的约束下给出了"最长探测序列期望仅 O(lg n)"的强得多的结论——这正是教科书将"表是否过半满"作为开放寻址实用准则的原因：一旦装载因子超过 1/2，长探测序列的出现频率就会明显上升。

相关习题与延伸阅读（仓库内）

本问题与仓库第 11 章的多个题目形成对照，适合串联阅读：

• 11.4-1：用线性探测、二次探测（c₁ = 1, c₂ = 3）与双重散列（h₁(k) = k, h₂(k) = 1 + (k mod (m-1))）在 m = 11 的表上插入 9 个键，直观展示了三种探测序列的差异，也暴露了二次探测"仅能覆盖偶数偏移"导致键 59 无法插入的缺陷；
• 11.4-2：给出 HASH-DELETE 与改进版 HASH-INSERT 的伪代码，说明开放寻址删除时需引入特殊标记 DELETE，并在插入时把该标记视为空槽；
• Problem 11-2：链地址法下的"最长链期望"分析，结论为 E[M] = O(lg n / lg lg n)，与本问题的 O(lg n) 形成有趣对比——开放寻址的最长探测序列期望（O(lg n)）比链地址法的最长链期望（O(lg n / lg lg n)）多一个 lg lg n 因子；
• 11.5-1：开放寻址下 n 次插入无冲突的概率 p(n, m) ≤ e^{-n(n-1)/(2m)}，即当 n 超过 √m 时冲突几乎不可避免，从"生日问题"视角佐证了本问题中探测序列存在的必然性；
• Problem 11-3 与 Problem 11-4：涉及探测策略的遍历性与 k-全域（k-universal）散列族，其中 11-4 的 (d) 问还给出了一个基于 2-全域散列的消息认证应用，展示了散列分析在密码学场景中的价值。

小结

Problem 11-1 通过四个递进的小问，完整刻画了开放寻址散列表在"均匀散列 + 装载因子 ≤ 1/2"条件下的最长探测序列行为：

1. 单次插入探测超过 k 次的概率至多 $2^{-k}$（指数尾界）；
2. 单次插入探测超过 $2\lg n$ 次的概率为 $O(1/n^2)$；
3. 全程最长探测序列超过 $2\lg n$ 次的概率为 $O(1/n)$；
4. 最长探测序列的期望长度为 $O(\lg n)$。

这套证明方法（条件概率链式放缩 → 多项式尾概率 → 联合界 → 尾和公式）是《算法导论》概率分析章节的典型范式，也可迁移到负载均衡、随机图等"最坏单元"分析场景。仓库原文在 docs/Chap11/Problems/11-1.md 保留了完整题面（解答标注为 Removed），本文的推导可作为阅读题面后的对照参考；相关配套习题请见 11.4.md、11.5.md 与 Problems 目录。

• 文档
• 教程
• 教育