第十讲 hashing

	Search	Insert	Delete
Ordinary BST	$O(tree depth)$	$O(treedepth)$	$O(treedepth)$
Treap	$O(\log n)$	$O(\log n)$	$O(\log n)$
Skip-List	$O(\log n)$	$O(\log n)$	$O(\log n)$
RB-tree	$O(\log n)$	$O(\log n)$	$O(\log n)$

直接寻址表（Direct-address Tables）

全集 $U$ (Universe)：指所有可能的关键字构成的集合。例如，如果关键字是 0 到 100 之间的整数，那么 $|U| = 101$。

集合 $I$：指当前实际存储在字典中的 $n$ 个关键字。通常 $n \ll |U|$。

实现方式：

系统分配一个长度为 $|U|$ 的数组。
每一个关键字 $k \in U$ 直接映射到数组的一个位置（下标）$k$。
插入、查找、删除均在 $O(1)$ 时间内完成。
- Insert(2)：将数据存入下标为 2 的位置。
- Insert(3)：将数据存入下标为 3 的位置。
- Search(2)：直接检查下标 2，返回结果。
- Delete(3)：将下标 3 的位置清空。

如果关键字不是整数，是二进制字串，可映射为整数。

矛盾：
- 巨大的全集 $U$：可能的关键字总数非常多（例如，所有可能的 18 位身份证号，全集大小为 $10^{18}$）。
- 稀疏的输入 $I$：虽然可能的关键字很多，但我们实际需要存储的元素 $n$ 却很少。
- 空间存储目标：我们不希望分配 $|U|$ 那么大的数组，而只想分配一个大小与 $n$ 相当的数组 $m$（即 $m \approx n$）。
理念：
- 不使用关键字 $k$ 直接作为下标，引入哈希函数 $h$：将每一个关键字 $k$ 映射到较小范围 $[m]$ 中，即 $h(k) \in \{0, 1, \dots, m-1\}$

冲突的解决

冲突定义：两个不同关键字 $k_1$ 和 $k_2$ 经哈希函数计算后，映射到相同下标 $h(k_1) = h(k_2)$。
必然性：把一个巨大的全集 $U$ 映射到很小的空间 $m$ 中（$m \ll |U|$），冲突是数学上无法避免的。

解决方案：链地址法

既然多个元素要挤在同一个位置，那就在这个位置挂一个链表。数组的每个槽位不再直接存放数据，而是存放一个指向链表的指针。所有哈希到同一位置的元素都存入该链表中。
空间代价：$\Theta(m)$：存放数组（桶）本身。$\Theta(n)$：存放实际的 $n$ 个元素及链表指针。
查找：计算哈希值并遍历链表。时间取决于链表的长度。
插入：“头插法” $O(1)$ 时间。
删除：找到该元素再删除，时间取决于链表长度。

问题所在：最坏情况下，所有元素可能哈希到同一个桶中，导致查找和删除时间复杂度退化到 $O(n)$。
如果哈希函数 $h$ 是均匀随机的，那么每个桶的期望长度是很短的。
数学推导：
- 假设 $h(k)$ 是在 $[m]$ 空间内均匀随机选取的。
- 对于集合 $I$ 中的任意关键字 $k$，它落入某个特定桶 $L_i$ 的概率 $\Pr[k \in L_i] = \frac{1}{m}$。
- 根据期望的线性性质，桶 $L_i$ 的期望长度 $E[|L_i|] = \sum_{k \in I} \Pr[k \in L_i] = n \cdot \frac{1}{m} = \frac{n}{m}$。
- 平均查找时间是 $1 + \frac{n}{m}$、
致命缺陷：上述“均匀随机函数”在实际中无法存储。因为其完全随机，我们难以记下来每个键值哈希得到的值。
空间悖论（没搞懂）：如果要定义一个对每个 $k \in U$ 都真正随机的函数，你必须记录下每一个 $k$ 对应的随机值是什么。这本质上又需要一个大小为 $|U|$ 的表。这违背了我们最初使用哈希表的目的（即为了避免 $O(|U|)$ 的空间开销）。
目标重述：我们需要设计一种既能快速计算（公式简单）、占用空间极小，但在表现上又“看起来像随机”的哈希函数。

字母索引求和（Sum of letter indices）

方法：直接将单词中每个字母的顺序索引相加。
致命缺陷：取值范围太小。绝大多数英语单词长度在 10 左右，哈希值大多落在 $260$ 内。导致极其严重的碰撞。

除法取余法（The division method）

改进思路：将关键字转换成一个巨大的整数 $k$，然后利用 $h(k) = k \mod m$ 将其映射到大小为 $m$ 的表中。
字符串转换：将字符串看作 26 进制数 的做法。
- "hash" = $8 \cdot 26^3 + 1 \cdot 26^2 + 19 \cdot 26^1 + 8 \cdot 26^0 = 141,786$考虑了字母的顺序（"stop" 和 "pots" 结果不同）。
取模：设 $m=1009$（素数），则 $141,786 \mod 1009 = 526$
缺点：在 CPU 底层运算中，除法（取模）是相对耗时的操作，不如位运算快。
核心矛盾：虽然“除法取余法”看起来很随机，但它是确定性的。
风险点：函数固定，如果攻击者知道了你使用的哈希函数，他可以故意构造一组数据，让它们全部发生碰撞，导致哈希表退化成单链表，性能从 $O(1)$ 暴跌至 $O(n)$，这在安全领域被称为哈希洪水攻击。

从“固定哈希函数”到“随机化算法”

这种方法被称为全域哈希（Universal Hashing），它是现代编程语言处理哈希碰撞安全性的核心原理。

目标矛盾：我们想要哈希函数具有“随机性”，以保证元素分布均匀。但我们不能给每个关键字真的分配随机值（因为通过之前的“空间悖论”已知，这样做需要 $O(|U|)$ 的存储空间，不可行）。
解决：设计一个带随机参数 $r$ 的函数族 $h_r(k) = h(k, r)$
在程序启动时，随机选取一次参数 $r$。在接下来的运行中，固定使用这一个 $h_r$。通过这种方式，我们只需要存储极小的随机因子 $r$，却能通过随机选择函数来瓦解攻击者构造的“碰撞序列”。
定义：一个函数族 $\mathcal{H}$ 被称为是全域（Universal）的，当且仅当：对于 $U$ 中任意一对不同的关键字 $x$ 和 $y$，随机从 $\mathcal{H}$ 中选出一个函数 $h_r$，它们碰撞的概率 $\Pr\{h_r(x) = h_r(y)\} \leq \frac{1}{m}$。这意味着从函数族中随机挑一个函数，其防冲突的效果等同于理论上完美的“真随机函数”。
等价表述：在整个函数族中，会导致 $x$ 和 $y$ 发生碰撞的函数数量，最多不超过总数的 $1/m$。

全域哈希在实际应用中的高效性：

结论：对于任何关键字 $k$，其所在桶（链表）的期望长度 $E[|L_{h_r(k)}|] \leq 1 + n/m$。这意味着全域哈希在平均情况下的性能达到了 $O(1)$

点积哈希（Dot-Product Hash）（期中不考）是一种基于向量空间结构的哈希方法。

前提假设：哈希表大小 $m = p$ ，$p$是素数。将全集 $U$ 的大小设为 $p^r$，我们可以把每一个关键字 $k$ 看作是一个 $r$ 维的向量：$k = (k_0, k_1, \dots, k_{r-1})$，其中每个分量都在 $[0, p-1]$ 之间。
构造方法：随机选取一个同样维度的向量 $a = (a_0, a_1, \dots, a_{r-1})$ 作为哈希函数的“种子”。
计算公式：$h_a(k) = \sum_{i=0}^{r-1} a_i k_i \pmod p$。这本质上是向量 $a$ 和 $k$ 的内积（点积）并在素数域下取模。
结论（没搞懂）：对于任何两个不相等的关键字 $k_1 \neq k_2$，随机选择 $a$ 导致它们哈希值相等的概率正好是 $1/p$。这完美符合全域哈希的定义。

公式定义：$h_a(k) = \sum_{i=0}^{r-1} a_i k_i \pmod p$

假设有两个不同的关键字 $k$ 和 $k'$。发生了碰撞意味着： $$\sum_{i=0}^{r-1} a_i k_i \equiv \sum_{i=0}^{r-1} a_i k'_i \pmod p$$ $$\sum_{i=0}^{r-1} a_i (k_i - k'_i) \equiv 0 \pmod p$$

为简洁，我们令 $d_i = (k_i - k'_i) \pmod p$，于是等式变为： $$a_0 d_0 + a_1 d_1 + \dots + a_{r-1} d_{r-1} \equiv 0 \pmod p$$

因为 $k \neq k'$，所以这两个向量至少有一个分量是不相等的。假设在第 $j$ 个位置上，它们第一次不相等，即 $k_j \neq k'_j$。这意味着 $d_j \neq 0$。

把第 $j$ 项单独拎出来，剩下的项全部移到等号右边： $$a_j d_j \equiv - \sum_{i \neq j} a_i d_i \pmod p$$

我们令等号右边那一堆复杂的求和结果为常数 $C$（假设我们已经随机选好了除 $a_j$ 以外的所有 $a_i$）： $$a_j d_j \equiv C \pmod p$$

现在的问题变成了：在 $[0, p-1]$ 中随机选一个 $a_j$，能使这个等式成立的概率是多少？

由于 $p$ 是素数，且我们已知 $d_j \not\equiv 0 \pmod p$，根据初等数论中的费马小定理推论（或模运算性质）： * 在模 $p$ 的环境下，任何非零数 $d_j$ 都存在唯一的乘法逆元 $d_j^{-1}$。 * 我们可以把等式两边同时乘以 $d_j^{-1}$： $$a_j \equiv C \cdot d_j^{-1} \pmod p$$

这意味着，无论右边的 $C$ 是多少，在 $a_j$ 可选的 $p$ 个数（$\{0, 1, \dots, p-1\}$）中，有且仅有一个值能让等式成立。

由于 $a$ 是均匀随机选取的，每一个 $a_j$ 被选中的概率都是 $1/p$。因此，碰撞发生的概率就是： $$\Pr = \displaystyle \frac{\text{能使等式成立的 } a_j \text{ 的个数}}{\text{总共可选的 } a_j \text{ 的个数}} = \frac{1}{p}$$

Carter & Wegman 哈希 (1977)是目前计算机科学中最常用、最经典的构造全域哈希族的方法。

找一个比全集 $U$ 还要大的素数 $p$（即 $p > |U|$），哈希表大小为 $m$
函数定义：$h_{a,b}(k) = ((ak + b) \pmod p) \pmod m$。
- 两个随机变量：$a$ 是从 $\{1, 2, \dots, p-1\}$ 中随机选的（不能为 0）；$b$ 是从 $\{0, 1, \dots, p-1\}$ 中随机选的。
- $\mathcal{H}_{p,m}=\{h_{a,b}(\cdot)|a\in\mathbb{Z}_p\setminus \{0\},b\in\mathbb{Z}_p\}$
双重模运算逻辑：
- 第一层 $\pmod p$：在素数域内进行线性变换，将关键字打散。
- 第二层 $\pmod m$：将结果压缩到实际的哈希表大小范围内。
核心结论：对于全集中的任意两个不同元素 $k_1 \neq k_2$，在随机选择 $a, b$ 的情况下，碰撞概率 $\Pr_{a,b} \{h_{a,b}(k_1) = h_{a,b}(k_2)\} \leq 1/m$。
假设 $k_1 \neq 0$。
设定变量：令 $s_1 = (ak_1 + b) \pmod p$ 为第一个关键字 $k_1$ 映射到素数域上的中间值。
解出 $a$：通过代数变换，我们可以把 $a$ 用 $s_1$ 和 $b$ 表示出来：$a \equiv (s_1 - b)k_1^{-1} \pmod p$。
代入第二个关键字：将 $a$ 的表达式代入序列 $s_2 = (ak_2 + b) \pmod p$ 中：
- 经过化简（利用分配律和逆元），得到 $s_2 \equiv (1 - k_1^{-1}k_2)b + s_1k_1^{-1}k_2 \pmod p$。
关键线性性质：因为 $k_1 \neq k_2$，系数 $(1 - k_1^{-1}k_2)$ 在素数域下不为 0。这意味着当随机选择 $b$ 时，$s_2$ 会在除 $s_1$ 以外的所有 $p-1$ 个值中均匀分布。

为什么当 $b$ 随机变动时，计算出来的 $s_2$ 也是均匀分布的？

公式如下（已经在 $\pmod p$ 下）： $$s_2 = (1 - k_1^{-1}k_2)b + s_1k_1^{-1}k_2$$

为了方便观察，我们给常数项起个简单的名字：

令系数 $M = (1 - k_1^{-1}k_2)$
令常数 $C = s_1k_1^{-1}k_2$

于是式子变成了我们最熟悉的直线方程： $$s_2 = M \cdot b + C \pmod p$$

在素数域 $\mathbb{Z}_p$ 中，$k_1^{-1}$ 是 $k_1$ 的倒数。如果 $M = 0$，意味着： $1 - k_1^{-1}k_2 = 0 \implies k_1^{-1}k_2 = 1 \implies k_2 = k_1$ 但我们的前提是 $k_1 \neq k_2$（两个不同的关键字）。结论：只要关键字不同，这个直线的“斜率” $M$ 就绝对不是 0。而在模素数域下，斜率不为 0 的直线是一个“双射”（一一对应）。

在模 $p$ 的世界里，如果 $M \neq 0$，那么当你尝试每一个不同的 $b \in \{0, 1, \dots, p-1\}$ 时，算出来的 $s_2$ 也会产生 $p$ 个互不相同的结果。

我们可以做一个小实验，假设 $p=5, M=2, C=1$：

当 $b=0 \implies s_2 = (2\cdot 0 + 1) \pmod 5 = 1$
当 $b=1 \implies s_2 = (2\cdot 1 + 1) \pmod 5 = 3$
当 $b=2 \implies s_2 = (2\cdot 2 + 1) \pmod 5 = 0$
当 $b=3 \implies s_2 = (2\cdot 3 + 1) \pmod 5 = 2$
当 $b=4 \implies s_2 = (2\cdot 4 + 1) \pmod 5 = 4$ 你看，当 $b$ 遍历 $0\sim 4$ 时，$s_2$ 也把 $0\sim 4$ 这五个数不重不漏地全跑了一遍。这就是所谓的“均匀分布”。

PPT 中说 $s_2$ 分布在“除 $s_1$ 以外”的 $p-1$ 个值里，这是因为在算法定义里有一个隐藏约束：$a$ 不能等于 0。

回想 $s_1 \equiv ak_1 + b \pmod p$，如果 $a=0$，则 $b \equiv s_1 \pmod p$。因为我们规定了 $a \neq 0$，所以 $b$ 绝对不能等于 $s_1$。

同理，计算 $s_2 - s_1$： $$s_2 - s_1 = (ak_2 + b) - (ak_1 + b) = a(k_2 - k_1)$$ 因为 $a \neq 0$ 且 $k_2 - k_1 \neq 0$，它们的乘积在素数域下也绝对不可能是 0。结论：$s_2$ 永远不可能等于 $s_1$。

这个性质之所以成立，本质上是因为在素数域 $\mathbb{Z}_p$ 中，每一个非零元素都有乘法逆元。

计算碰撞概率：
- 在 $[0, p-1]$ 范围中，有多少个数字 $s_2$ 会满足 $s_2 \equiv s_1 \pmod m$？
- 由于 $p$ 被分成 $m$ 个桶，每个桶里大约有 $p/m$ 个数，去掉 $s_1$ 本身，剩下的候选碰撞点约为 $\frac{\lceil p/m \rceil - 1}{p-1}$。
- 数学推导得出这个值恒 $\leq 1/m$。
- 令 $p = qm + r$，其中 $r$ 是余数 ($1 \leq r < m$)。
- 那么向上取整 $\lceil p/m \rceil$ 的值就是 $q+1$（如果 $r>0$）。
- 代入表达式： $$\frac{(q+1) - 1}{qm + r - 1} = \frac{q}{qm + (r-1)}$$
- 观察分母：由于 $r \geq 1$，所以 $r-1 \geq 0$。
- 因此分母 $qm + (r-1) \geq qm$。
- 整个分式 $\frac{q}{qm + r - 1} \leq \frac{q}{qm} = \frac{1}{m}$。

证明方法二：

双射关系 (One-to-One)：
- 这是一组线性方程组：$\begin{cases} ak_1 + b = s_1 \\ ak_2 + b = s_2 \end{cases} \pmod p$。
- 由于 $k_1 \neq k_2$ 且 $p$ 是素数，对于每一对 $(s_1, s_2)$，都有且仅有一组唯一的 $(a, b)$ 与其对应。
- 因此，随机选择 $(a, b)$ 等同于在所有可能的 $(s_1, s_2)$ 组合（且 $s_1 \neq s_2$）中随机选择一对。
统计“坏”组合的数量：
- 我们要找有多少对 $(s_1, s_2)$ 满足 $s_1 \equiv s_2 \pmod m$。
- 对于每一个固定的 $s_1$（共 $p$ 个选择），能与之在模 $m$ 意义下碰撞的 $s_2$ 数量最多是 $\lceil p/m \rceil - 1$ 个。
- 所以总的“坏对”数量最多为 $p(\lceil p/m \rceil - 1)$。
最终概率：
- $\text{概率} = \frac{\text{坏对数量}}{\text{总对数量}} = \frac{p(\lceil p/m \rceil - 1)}{p(p-1)} \leq \frac{1}{m}$。
承上启下：Carter & Wegman 证明了全域性，但它也有缺点。它需要两次取模操作（$\pmod p$ 和 $\pmod m$）。在计算机底层，取模运算是非常昂贵的。
引出新话题：Multiply-shift hashing (1997)。这是一种现代改进方案，它利用了计算机位运算（移位）来代替取模，速度极快，同时依然能保持类似的全域性质。

乘法移位哈希 (Multiply-Shift Hashing)（期中不考）。

核心优势：彻底抛弃开销巨大的素数取模运算，利用 CPU 最擅长的乘法和位移来实现全域哈希。

解决：利用 $2$ 的幂次作为模数，并配合位运算。
算法参数：
1. 哈希表大小：$m = 2^r$（即表长是 $2$ 的整数次幂，正好对应哈希值的 $r$ 个位）。
2. 机器字长：$w$ 位的关键字全集（例如 32 位或 64 位整数）。
3. 随机参数：随机选一个奇数 $a。
哈希函数定义：$h_a(k) = (a \cdot k \mod 2^w) \gg (w-r)$
- 直观理解：先把 $k$ 乘以随机奇数 $a$，在 $w$ 位的寄存器里只保留低 $w$ 位（这相当于自动做了 $\pmod{2^w}$），然后向右平移，取出结果中最高端的那 $r$ 个位。
碰撞概率 $\leq 2^{1-r}$。
注意：理想状况下是 $1/m = 1/2^r$，这里是 $2/m$。虽然比素数取模略高，但依然属于同一数量级，性能极佳。
证明逻辑简述：
1. 考虑两个不同的关键字的差值 $x = k_1 - k_2$。
2. 由于 $k_1 \neq k_2$，在二进制下，$x$ 一定可以写成如下形式： $$x = 2^i \cdot \ell$$
$i$ 代表 $x$ 的二进制表示中末尾 $0$ 的个数（即最低非零位的位置）。
$\ell$ 是一个奇数（因为我们提光了所有的因数 $2$）。

哈希函数定义为：取 $a \cdot k \pmod{2^w}$ 的高 $r$ 位。如果 $h_a(k_1) = h_a(k_2)$，这意味着 $a \cdot k_1$ 和 $a \cdot k_2$ 的高 $r$ 位完全相同。

在模运算下，如果两个数的高位相同，它们的差值 $a(k_1 - k_2) = a \cdot x$ 的高 $r$ 位必然只有两种可能： 1. 全为 0 ($0^r$)：当减法没有发生跨位借位时。 2. 全为 1 ($1^r$)：当减法导致了高位的借位（产生全 $1$ 的补码效果）时。

所以 PPT 中写道：Collision $\implies h_a(x) \in \{0^r, 1^r\}$。

我们的随机变量是 $a$，它是一个随机奇数。考虑乘积中的一部分：$s = a \cdot \ell \pmod{2^w}$。 * 因为 $a$ 是随机奇数，$\ell$ 也是奇数。 * 在模 $2^w$ 的群中，奇数项构成一个缩剩余系。一个随机奇数乘以一个固定奇数，结果仍然是一个随机奇数。 * 因此，$s$ 是 $\{1, 3, 5, \dots, 2^{w}-1\}$ 集合中均匀分布的一个随机值。这个集合的大小是 $2^{w-1}$。

那么，我们要考察的对象就变成了：$a \cdot x = s \cdot 2^i \pmod{2^w}$。

我们要看 $s \cdot 2^i$ 的高 $r$ 位落在 $\{0^r, 1^r\}$ 的概率。

情况 (1)：当 $i > w - r$

这意味着 $x$ 的末尾 $0$ 太多了，也就是 $x$ 本身已经非常趋近于 $2^w$（或者说 $x$ 的有效位非常短）。 * 当 $i > w - r$ 时，$s \cdot 2^i$ 的低 $i$ 位全是 $0$。 * 由于 $i$ 很大，剩下的可变位（来自 $s$）已经不足以覆盖高 $r$ 位的所有可能性。 * 经过数学计算，在这种情况下，高 $r$ 位要么不可能是全 $0$，要么不可能是全 $1$。PPT 结论是：在这种情况下，碰撞几乎不可能发生（概率为 0）。

当 $i \leq w - r$（最常见的情况）

这是证明的核心。我们关注 $a \cdot x = s \cdot 2^i$。 * 乘以 $2^i$ 相当于把随机奇数 $s$ 向左移了 $i$ 位。 * 此时，$a \cdot x$ 的二进制结构如下： * 低 $i$ 位：全是 $0$。 * 第 $i$ 位：一定是 $1$（因为 $s$ 是奇数，末位是 $1$）。 * 第 $i+1$ 到第 $w-1$ 位：由于 $s$ 是随机的，这些位也是均匀随机的。

我们要考查的是整个 $w$ 位中的最高 $r$ 位。由于 $i \leq w-r$，最高 $r$ 位完全落在了上述的“均匀随机位”区间内（或者包含了第 $i$ 位那个确定的 $1$）。

计算概率：
- 总共有多少个随机奇数 $s$？答案是 $2^{w-1}$ 个。
- 能让高 $r$ 位成为 $0^r$ 或 $1^r$ 的 $s$ 有多少个？
- 在高位确定的情况下，剩下的自由位有 $w - 1 - r$ 位。
- 对于 $0^r$ 有 $2^{w-1-r}$ 种可能，对于 $1^r$ 有 $2^{w-1-r}$ 种可能。
- 合计：$2 \cdot 2^{w-1-r} = 2^{w-r}$。

$$P =\displaystyle \frac{\text{符合条件的 } s}{\text{总共的 } s} = \frac{2^{w-r}}{2^{w-1}} = \frac{2^{w-r}}{2^{w-1}} = 2^{1-r}$$ 因为 $m = 2^r$，所以 $2^{1-r} = 2/m$。这证明了对于任何不同的 $k_1, k_2$，使用乘法移位哈希，碰撞的概率被严格限制在 $2/m$ 之内。

完全哈希 (Perfect Hashing)。核心目标是在静态数据（数据集合提前已知，不再增删）的情况下，通过两层映射实现 $O(1)$ 的最坏情况查询时间，并解决碰撞问题。

定义：给定含 $n$ 个键的固定集合 $I$，完全哈希要求完全没有碰撞。
场景限制：只支持“查询”，不支持“插入”和“删除”。因为一旦数据变动，原本构造好的无碰撞函数就会失效。
核心挑战：如果我们追求零碰撞，需要多少存储空间？

为了实现零碰撞，最简单的办法是提供远超过数据量的空间。 * 数学逻辑： * 假设有 $n$ 个元素，哈希桶数量为 $m = n^2$。 * 在全域哈希家族中，任意一对元素碰撞的概率是 $1/m$。 * 碰撞的总对数（期望值）：$n$ 个数中选出 2 个数的组合数是 $\binom{n}{2}$。所以期望碰撞次数为： $$E[\text{collisions}] \leq \binom{n}{2} \cdot \frac{1}{n^2} = \frac{n(n-1)}{2} \cdot \frac{1}{n^2} < \frac{1}{2}$$ * 结论：根据马尔可夫不等式（或者简单的概率直觉），既然平均碰撞对数小于 $0.5$，那么有超过 $50\%$ 的概率我们随机选一个哈希函数能做到零碰撞。 * 缺点：空间开销太大。如果你有 100 万个数，需要 1 万亿个位置，这在实际中是不可接受的。

FKS 哈希（以 Fredman, Komlós 和 Szemerédi 三人命名），它巧妙地将平方空间的思想应用到了局部。

二级哈希结构：
1. 第一级：使用一个大小 $m \approx n$ 的普通哈希表（允许碰撞，图中用链地址法展示）。
2. 第二级：针对每一个发生了碰撞的桶（假设桶 $i$ 里有 $L_i$ 个元素），不再使用链表，而是再建立一个微型的哈希表。
3. 局部平方空间：为这个微型表分配 $|L_i|^2$ 的空间。根据前一页的结论，在这个小空间里实现零碰撞是非常容易的。
虽然每个桶用了平方空间，但总体空间是 $\sum |L_i|^2$。 数学扩展结论：对于全域哈希，可以证明 $\sum_{i=1}^m |L_i|^2$ 的期望值是 $O(n)$。
这意味着：虽然局部浪费了空间，但在宏观上，总空间依然和数据量成正比。
我们知道 $|L_i|^2 = |L_i| + 2 \cdot (\text{桶 } i \text{ 内部的碰撞对数})$。（注：其实是 $|L_i|^2 = |L_i| + |L_i|(|L_i|-1)$）
对所有桶求和： $$\sum_{i=1}^m |L_i|^2 = \sum |L_i| + 2 \cdot (\text{全表总碰撞对数})$$
其中 $\sum |L_i| = n$。
根据全域哈希的性质，总碰撞对数的期望值 $\leq \binom{n}{2} \cdot \frac{1}{m}$。
如果我们取 $m = n$，则： $$E\left[\sum |L_i|^2\right] \leq n + 2 \cdot \frac{n(n-1)}{2 \cdot n} = n + (n-1) = 2n - 1$$

	Search	Insert	Delete
Ordinary BST	\(O(tree depth)\)	\(O(treedepth)\)	\(O(treedepth)\)
Treap	\(O(\log n)\)	\(O(\log n)\)	\(O(\log n)\)
Skip-List	\(O(\log n)\)	\(O(\log n)\)	\(O(\log n)\)
RB-tree	\(O(\log n)\)	\(O(\log n)\)	\(O(\log n)\)