第 11 章 散列表

订单 ID 到订单对象、证券代码到最新行情快照、因子名到缓存结果、groupby 和 merge 的底层——交易系统里用得最多的数据结构就是散列表。本章回答三个问题：它为什么平均只要 \(O(1)\)；什么情况下会退化成 \(\Theta(n)\)；怎样在设计上避开退化。

学习目标

1. 理解直接寻址表与散列表的关系，能解释装载因子 \(\alpha=n/m\) 的含义。
2. 在简单均匀散列假设下推导链接法成功与不成功搜索的期望代价 \(\Theta(1+\alpha)\)。
3. 会构造除法散列、乘法散列和全域散列，知道各自的适用条件和陷阱（如 \(m\) 取 2 的幂）。
4. 掌握开放寻址的三种探查方式，推导均匀散列下的探查次数上界 \(1/(1-\alpha)\) 与 \(\frac1\alpha\ln\frac1{1-\alpha}\)，并能据此做容量规划。
5. 理解两级完全散列为何能在静态集合上做到最坏 \(O(1)\) 查找、期望 \(O(n)\) 空间。
6. 能把以上结论用到行情快照索引、证券代码表、尾延迟控制等工程问题上。

读前导读

这一章在解决什么问题。 你的系统里有一张"行情表"：给一个证券代码，立刻要拿到它的最新价。最笨的办法是从第一行往下翻，5000 只股票平均翻 2500 行。更聪明的办法是"按号码直接开柜"：准备 100 万个柜子，代码 600519 的数据就放 600519 号柜——这叫直接寻址，一步到位，但大多数柜子空着。散列表是两者的折中：只准备 1 万个柜子，用一个固定的公式（散列函数）把代码换算成柜子编号，比如"代码除以 10007 的余数"。偶尔两个代码算出同一个柜号（冲突），就在柜子里挂个小清单把它们都放进去。只要公式把代码分得够均匀，每个柜子里平均只有一两个东西，查找就几乎是一步。

本章的数学全部围绕一个问题："平均要翻几次"。核心参数是装载因子 \(\alpha\) = 东西数 / 柜子数，相当于"柜子的占用率"。你可以把它类比为银行的资本充足率：占用率低，查询快但浪费柜子；占用率接近 100%，柜子省了，查询时间却会急剧上升——不是线性上升，而是像 \(1/(1-\alpha)\) 那样在接近 1 时爆炸。本章还讨论一个风险管理式的问题：如果有人故意挑一批"全落进同一个柜子"的代码来攻击你，怎么办？答案是随机选公式，让对手猜不到。

需要先想起来的数学。

• 取模 \(k\bmod m\) 与整除。 余数运算，\(100\bmod12=4\)。"\(a\equiv b\pmod m\)"（读作"\(a\) 与 \(b\) 模 \(m\) 同余"）表示 \(a\)、\(b\) 除以 \(m\) 余数相同，例如 \(28\equiv11\pmod{17}\)。素数 \(p\) 有一个关键性质：若 \(p\) 不整除 \(a\) 也不整除 \(b\)，则 \(p\) 不整除 \(ab\)。见 第 00 册第 08 章 读懂数学证明与符号。
• 示性变量与期望的线性性。 \(X=I\{A\}\) 的期望是 \(\Pr\{A\}\)；一堆示性变量之和的期望 = 各自概率之和，不需要独立。本章所有"平均链长""期望冲突对数"都用这一招。见 第 00 册第 07 章 概率中的分析工具。
• 几何级数。 \(1+\alpha+\alpha^2+\cdots=\frac1{1-\alpha}\)（\(0\le\alpha<1\)）。\(\alpha=0.9\) 时和为 10。与永续年金 \(\frac{C}{r}\) 是同一类式子。见 第 00 册第 04 章 级数与收敛。
• 用积分估计求和。 \(\sum_{k=a+1}^{b}\frac1k\le\int_a^b\frac{dx}x=\ln\frac ba\)，因为每个 \(\frac1k\) 是宽度为 1 的矩形，矩形都在曲线 \(1/x\) 下方。\(\ln\) 是自然对数。见 第 00 册第 03 章 积分。
• Markov 不等式。 非负随机变量 \(X\) 满足 \(\Pr\{X\ge t\}\le E[X]/t\)。例：平均损失 1 万的非负损失，超过 10 万的概率不超过 10%。见第 00 册第 07 章"常用不等式"。

怎么读这一章。 11.1、11.2 节和定理 11.1 是基础，必读；定理 11.2 的证明是示性变量的标准练习，值得跟着下面的讲解框推一遍。11.3 节读懂"为什么 \(m\) 不能取 2 的幂"和"全域散列防攻击"的思想即可，定理 11.5 的证明第一次可以只看结论。11.4 节定理 11.6 和"表半满至多 2 次、90% 满至多 10 次"是做容量规划的依据，必读。11.5 完全散列可以只看思路。11.6 节量化实战建议精读第一部分。

11.1 直接寻址表

先看最简单的情形。若关键字全域 \(U=\{0,1,\dots,m-1\}\) 不大，且没有两个元素关键字相同，就开一个数组 \(T[0..m-1]\)，称为直接寻址表（direct-address table）。每个位置叫槽（slot），槽 \(k\) 指向关键字为 \(k\) 的元素，没有则为 NIL。

def DIRECT_ADDRESS_SEARCH(T, k): return T[k]
def DIRECT_ADDRESS_INSERT(T, x): T[x.key] = x
def DIRECT_ADDRESS_DELETE(T, x): T[x.key] = NIL

三个操作都是最坏 \(O(1)\)。量化里它其实很常见：价格按最小变动价位（tick）离散化后，"价格 → 档位"可以直接用下标 \((\text{price}-\text{base})/\text{tick}\) 寻址；A 股六位数字代码的全域只有 \(10^6\)，在内存充足时也可直接开一个百万长的数组。习题 11.1-2 的**位向量（bit vector）**是它的压缩版本：只记录"在不在"，每个关键字一位。

直接寻址的缺点同样明显：全域 \(U\) 很大时（比如 64 位订单 ID、字符串代码），开 \(|U|\) 大小的数组不现实；即使开得起，实际关键字集 \(K\) 远小于 \(U\) 时空间几乎全浪费了。

11.2 散列表与链接法

散列表（hash table）把存储需求降到 \(\Theta(|K|)\)，同时让搜索保持 \(O(1)\)——但这是平均情况，不再是最坏情况。

关键字 \(k\) 存到槽 \(h(k)\)，其中散列函数（hash function） \(h:U\to\{0,1,\dots,m-1\}\)，\(m\ll|U|\)。\(h(k)\) 称为 \(k\) 的散列值（hash value）。两个关键字落到同一个槽叫冲突（collision）。因为 \(|U|>m\)，由鸽笼原理冲突不可避免，所以必须有冲突解决办法。理想的 \(h\) 看起来"随机"，但它必须是确定性的——同一个关键字每次都要算出同一个槽。

白话解释：营业厅有 10 个窗口，规定"身份证尾号是几就去几号窗口"——尾号就是散列函数，窗口号就是散列值。尾号相同的两个人去同一窗口，就是冲突。鸽笼原理：10 个笼子放 11 只鸽子，至少一个笼子有两只；关键字的可能取值远多于槽数，冲突必然发生，所以只能"管理冲突"而不能"消灭冲突"。"确定性"的意思是：同一个人今天来去 3 号窗口，明天来也必须去 3 号窗口，否则就找不到他上次存的东西。

11.2.1 链接法

**链接法（chaining）**把散列到同一槽的元素放进同一个链表，槽 \(j\) 存这条链表的表头指针。

def CHAINED_HASH_INSERT(T, x):  LIST_INSERT(T[h(x.key)], x)   # 最坏 O(1)，假定 x 不在表中
def CHAINED_HASH_SEARCH(T, k):  return LIST_SEARCH(T[h(k)], k) # 正比于链长
def CHAINED_HASH_DELETE(T, x):  LIST_DELETE(T[h(x.key)], x)   # 双向链表时 O(1)

注意两个细节：插入 \(O(1)\) 是因为假定 \(x\) 还不在表中（若要查重，得先搜索）；删除接收元素指针，所以不必搜索，但链表必须是双向的，否则还得找前驱。

11.2.2 链接法的分析

定义装载因子（load factor）

最坏情况很糟：\(n\) 个关键字全落到一个槽，搜索 \(\Theta(n)\)，和一条链表一样。散列表不是为最坏情况设计的。

平均情况依赖于 \(h\) 把关键字分配得多均匀。引入**简单均匀散列（simple uniform hashing）**假设：任一元素等可能地散列到 \(m\) 个槽中的任何一个，且与其他元素散列到哪里无关。记槽 \(j\) 的链长为 \(n_j\)，则 \(n=n_0+\dots+n_{m-1}\)，\(E[n_j]=\alpha\)。另假设计算 \(h(k)\) 只要 \(O(1)\)。

定理 11.1（不成功搜索）：在链接法和简单均匀散列下，不成功搜索的平均时间为 \(\Theta(1+\alpha)\)。

证明. 不在表中的 \(k\) 等可能落到任一槽，搜索要走完整条链 \(T[h(k)]\)，期望长度 \(E[n_{h(k)}]=\alpha\)；加上算散列的 \(O(1)\)，总计 \(\Theta(1+\alpha)\)。\(\square\)

定理 11.2（成功搜索）：同样假设下，成功搜索的平均时间也是 \(\Theta(1+\alpha)\)。

证明. 假定被找的元素等可能是表中 \(n\) 个元素之一。找 \(x\) 检查的元素数 = 1 + 链表中排在 \(x\) 前面的元素数。新元素插在表头，所以排在 \(x\) 前面的恰是在 \(x\) 之后插入且落在同一槽的元素。设 \(x_i\) 是第 \(i\) 个插入的元素，\(k_i\) 为其关键字，定义指示变量 \(X_{ij}=I\{h(k_i)=h(k_j)\}\)，则 \(E[X_{ij}]=1/m\)。期望检查数为

推导拆解：这个式子分三步。 (1) 外层 \(\frac1n\sum_{i=1}^n\)：被找的元素等可能是第 1、2、……、\(n\) 个插入的，所以对 \(i\) 取平均。 (2) 括号里 \(1+\sum_{j>i}X_{ij}\)：找第 \(i\) 个元素要检查"它自己"（1 次）加上"排在它前面的元素"。因为新元素插在链表头，排在它前面的就是比它晚插入（\(j>i\)）又恰好落到同一槽（\(X_{ij}=1\)）的那些。 (3) 取期望，用线性性把期望搬进求和号，\(E[X_{ij}]=\Pr\{\text{两者同槽}\}=1/m\)（简单均匀散列：第 \(j\) 个元素落到哪个槽与第 \(i\) 个无关，正好撞上的概率是 \(1/m\)）。对固定的 \(i\)，\(j\) 从 \(i+1\) 到 \(n\) 共 \(n-i\) 个，所以得 \(1+\frac1{nm}\sum_i(n-i)\)。最后 \(\sum_{i=1}^n(n-i)=0+1+\cdots+(n-1)=\frac{n(n-1)}2\)，代入化简即得 \(1+\frac{n-1}{2m}\)。 数值例：1 万个槽放 5000 只证券（\(\alpha=0.5\)），成功查找平均只检查约 \(1.25\) 个元素。

结论：只要槽数与元素数成正比，\(n=O(m)\)，就有 \(\alpha=O(1)\)，所有字典操作平均 \(O(1)\)。工程上这就是"表满到一定程度就扩容"的理由；扩容（rehash）的摊还代价是 \(O(1)\)，但那一次扩容本身是 \(\Theta(n)\) 的停顿。

习题 11.2-1 的结论值得记住：\(n\) 个不同关键字在简单均匀散列下的期望冲突对数是 \(\binom n2/m\)。

11.3 散列函数

好的散列函数（近似地）满足简单均匀散列，但这通常无法验证，因为我们很少知道关键字的分布，而且关键字之间往往不独立。实践的原则是：让散列值与数据中可能存在的任何规律无关。 多数散列函数假设关键字是自然数；字符串可按某个基数解释为整数，例如 pt 的 ASCII 码为 \((112,116)\)，按 128 进制得 \(112\times128+116=14452\)。

11.3.1 除法散列

例：\(m=12\)、\(k=100\) 时 \(h(k)=4\)。只需一次除法，很快。关键在 \(m\) 的选择：

• \(m\) 不应是 2 的幂。 若 \(m=2^p\)，\(h(k)\) 就是 \(k\) 的最低 \(p\) 位，除非低 \(p\) 位的模式等可能，否则分布会很差。
• 若 \(k\) 是按 \(2^p\) 进制解释的字符串，\(m=2^p-1\) 也很糟：交换字符顺序散列值不变（习题 11.3-3）。
• 好的选择是不太接近 2 的整数幂的素数。 原书例：用链接法存约 2000 个字符串，能接受不成功搜索平均查 3 个元素，取 \(m=701\)（接近 \(2000/3\) 的素数，不接近 2 的幂）。

推导拆解：为什么 \(m=2^p\) 只看最低 \(p\) 位？类比十进制：任何数除以 \(1000=10^3\) 的余数就是它的最后三位，\(123456\bmod1000=456\)，前面的 123 完全不参与。二进制里除以 \(2^p\) 同理。于是关键字的高位信息全部被扔掉，如果低位恰好有规律，散列值就集中。例：价格以"分"为单位存成整数且都是 5 分的整数倍，取 \(m=10\)（十进制版本的"2 的幂"问题）时散列值只会是 0 或 5，10 个槽只用了 2 个。素数没有这种"只看尾巴"的性质，关键字的每一位都会影响余数。11.6.1 节的毫秒时间戳实验就是这个现象。

11.3.2 乘法散列

其中 \(kA\bmod1=kA-\lfloor kA\rfloor\) 是小数部分。它的优点是 \(m\) 的取值不关键，可以取 \(2^p\)，便于用移位实现：设机器字长 \(w\) 位，令 \(A=s/2^w\)（\(s\) 为 \(w\) 位整数），则 \(k\cdot s\) 是 \(2w\) 位的数 \(r_12^w+r_0\)，散列值就是低位字 \(r_0\) 的最高 \(p\) 位。Knuth 建议

原书例：\(k=123456\)，\(p=14\)，\(m=2^{14}=16384\)，\(w=32\)，\(s=2654435769\)。\(k\cdot s=327706022297664=76300\cdot2^{32}+17612864\)，所以 \(r_0=17612864\)，取其最高 14 位得 \(h(k)=67\)。（下文代码验证了这个数。）

11.3.3 全域散列

任何固定的散列函数都有一个弱点：知道它的对手可以挑出 \(n\) 个全落在同一槽的关键字，使每次检索 \(\Theta(n)\)。唯一有效的对策是以与关键字无关的方式随机选择散列函数——**全域散列（universal hashing）**在程序开始时从一族精心设计的函数里随机挑一个。这与随机化快速排序的思路相同：没有哪个输入总是触发最坏情况。

定义：设 \(\mathcal H\) 是把 \(U\) 映射到 \(\{0,\dots,m-1\}\) 的有限函数族。若对每对不同关键字 \(k\ne l\)，使 \(h(k)=h(l)\) 的 \(h\in\mathcal H\) 至多有 \(|\mathcal H|/m\) 个，则称 \(\mathcal H\) 是全域的（universal）。等价地说：随机选 \(h\) 时，任意两个不同关键字的冲突概率不超过 \(1/m\)。

金融直觉：这和审计抽样的道理一样。如果抽样规则固定且公开（"每月只查第 1 周的凭证"），想作弊的人就把问题凭证都放在第 2 周。把规则改成"每次随机抽"，作弊者无从针对。全域散列也是如此：对手可以知道整个函数族，但不知道这次运行抽中的是哪一个。注意这里的概率是对"抽哪个函数"取的，关键字被视为对手事先固定好的；而前面的"简单均匀散列"是假设关键字本身随机。前者是我们自己制造的随机性，后者是对数据的假设，前者可靠得多。

定理 11.3：从全域族随机选 \(h\)，用链接法把 \(n\) 个关键字存进 \(m\) 个槽。若 \(k\) 不在表中，则 \(E[n_{h(k)}]\le\alpha\)；若 \(k\) 在表中，则 \(E[n_{h(k)}]\le1+\alpha\)。

证明. 期望是对 \(h\) 的随机选取求的，不依赖关键字分布。对 \(k\ne l\) 令 \(X_{kl}=I\{h(k)=h(l)\}\)，全域性给出 \(E[X_{kl}]\le1/m\)。令 \(Y_k=\sum_{l\in T,\,l\ne k}X_{kl}\)。若 \(k\notin T\)，\(n_{h(k)}=Y_k\)，\(E[Y_k]\le n/m=\alpha\)；若 \(k\in T\)，\(n_{h(k)}=Y_k+1\)，其他关键字只有 \(n-1\) 个，\(E[n_{h(k)}]\le(n-1)/m+1<1+\alpha\)。\(\square\)

推论 11.4：用全域散列和链接法，在 \(m\) 个槽的空表上执行含 \(O(m)\) 个 INSERT 的任意 \(n\) 个操作序列，期望总时间 \(\Theta(n)\)。意义在于：对手再也挑不出必然导致最坏情况的输入。

构造一个全域族。 取素数 \(p\) 大于所有可能的关键字，\(\mathbb Z_p=\{0,\dots,p-1\}\)，\(\mathbb Z_p^*=\{1,\dots,p-1\}\)。对 \(a\in\mathbb Z_p^*\)、\(b\in\mathbb Z_p\) 定义

定理 11.5：\(\mathcal H_{pm}\) 是全域的。

证明要点. 取 \(k\ne l\)，令 \(r=(ak+b)\bmod p\)，\(s=(al+b)\bmod p\)。

1. \(r\ne s\)：因为 \(r-s\equiv a(k-l)\pmod p\)，\(p\) 是素数、\(a\) 与 \(k-l\) 模 \(p\) 都非零，所以乘积非零。也就是说"模 \(p\) 这一层"没有冲突。
2. \((a,b)\) 的 \(p(p-1)\) 种取值与 \((r,s)\)（\(r\ne s\)）的 \(p(p-1)\) 种取值一一对应：\(a=(r-s)(k-l)^{-1}\bmod p\)，\(b=(r-ak)\bmod p\)。所以随机选 \((a,b)\) 时，\((r,s)\) 均匀地取遍所有不同值对。
3. 冲突概率 = 随机的不同值对满足 \(r\equiv s\pmod m\) 的概率。固定 \(r\)，其余 \(p-1\) 个 \(s\) 中与 \(r\) 同余的至多 \(\lceil p/m\rceil-1\le(p-1)/m\) 个，概率至多 \(1/m\)。\(\square\)

推导拆解：这个证明的结构是"两层取模，分开看"。 第一层 \((ak+b)\bmod p\)：\(r-s\equiv a(k-l)\) 这一步把 \(b\) 消掉了（两边都加了 \(b\)）。\(p\) 是素数，\(a\) 和 \(k-l\) 都不是 \(p\) 的倍数，所以乘积也不是 \(p\) 的倍数，\(r\ne s\)。换句话说，第一层永不冲突。 第 2 步的 \((k-l)^{-1}\) 是"模 \(p\) 的倒数"：满足 \((k-l)\cdot x\equiv1\pmod p\) 的那个 \(x\)，\(p\) 为素数时一定存在。例如模 17 下 \(3^{-1}=6\)，因为 \(3\times6=18\equiv1\)。这一步的意义是：给定想要的 \((r,s)\)，能唯一反解出 \((a,b)\)，所以随机挑 \((a,b)\) 等价于随机挑一对不同的 \((r,s)\)。 第二层 \(\bmod m\)：冲突只可能在这一层发生。\(0..p-1\) 中与 \(r\) 模 \(m\) 同余的数大约每 \(m\) 个出现一个，扣掉 \(r\) 自己，最多 \((p-1)/m\) 个，所以概率 \(\le\frac{(p-1)/m}{p-1}=\frac1m\)。

11.4 开放寻址法

开放寻址（open addressing）把所有元素都存在表本身里，没有链表，因此 \(\alpha\le1\)，表会被填满。它不沿指针走，而是计算要检查的槽序列；省下的指针空间可以换成更多的槽，并且对 CPU 缓存更友好。CPython 的 dict、Google 的 absl::flat_hash_map 都是开放寻址。

把散列函数扩展为带探查号（probe number） \(i\) 的形式 \(h:U\times\{0,\dots,m-1\}\to\{0,\dots,m-1\}\)，要求探查序列（probe sequence） \(\langle h(k,0),\dots,h(k,m-1)\rangle\) 是 \(\langle0,\dots,m-1\rangle\) 的一个排列。

def HASH_INSERT(T, k):
    for i in range(m):
        j = h(k, i)
        if T[j] is NIL:
            T[j] = k; return j
    raise Exception("hash table overflow")

def HASH_SEARCH(T, k):
    for i in range(m):
        j = h(k, i)
        if T[j] == k:   return j
        if T[j] is NIL: return NIL     # 若 k 在表中，当初就会插在这里
    return NIL

删除的陷阱。 删除槽 \(i\) 时不能直接置 NIL，否则那些插入时路过槽 \(i\) 的关键字就"断了路"，再也找不到。办法是写入特殊值 DELETED：插入把它当空槽，搜索把它当占用槽继续往下找。但这样搜索时间不再只由 \(\alpha\) 决定——长期运行、频繁增删的表里 DELETED 越积越多，性能悄悄变差。所以需要频繁删除时更常用链接法，或者定期重建表。

**均匀散列（uniform hashing）**假设：每个关键字的探查序列等可能是 \(m!\) 种排列中的任一种。真正的均匀散列难以实现，常用三种近似：

• 线性探查（linear probing）：\(h(k,i)=(h'(k)+i)\bmod m\)。实现简单、缓存友好，但有一次群集（primary clustering）：已占槽连成长串，一个前面有 \(i\) 个满槽的空槽下一次被填的概率是 \((i+1)/m\)，长串越长越容易变得更长。只有 \(m\) 种探查序列。
• 二次探查（quadratic probing）：\(h(k,i)=(h'(k)+c_1i+c_2i^2)\bmod m\)。比线性好，但初始位置相同的关键字整条序列相同，产生较轻的二次群集（secondary clustering）；\(c_1,c_2,m\) 的取值受限（思考题 11-3：\(m\) 为 2 的幂、\(c_1=c_2=1/2\)，即偏移为三角数 \(i(i+1)/2\) 时可遍历全表）。也只有 \(m\) 种序列。
• 双重散列（double hashing）：\(h(k,i)=(h_1(k)+i\,h_2(k))\bmod m\)。初始位置和步长都依赖关键字，有 \(\Theta(m^2)\) 种序列，表现最接近均匀散列。要求 \(h_2(k)\) 与 \(m\) 互素，常用取法是 \(m\) 为素数，\(h_1(k)=k\bmod m\)，\(h_2(k)=1+(k\bmod m')\)，\(m'\) 略小于 \(m\)。原书例：\(k=123456\)，\(m=701\)，\(m'=700\)，\(h_1=80\)，\(h_2=257\)——先查槽 80，此后每隔 257 个槽查一次。原书图 11.5：\(m=13\)，\(h_1(k)=k\bmod13\)，\(h_2(k)=1+(k\bmod11)\)，插入 14 时依次查槽 1、5、9，放入槽 9。

11.4.1 开放寻址的分析

定理 11.6：装载因子 \(\alpha<1\)，均匀散列下不成功搜索的期望探查次数至多 \(1/(1-\alpha)\)。

证明. 不成功搜索中，除最后一次外每次探查都碰到一个被占且不是目标的槽。设 \(X\) 为探查次数，\(A_i\) 为"第 \(i\) 次探查发生且碰到占用槽"。第 1 次碰到占用槽的概率是 \(n/m\)；在前 \(j-1\) 次都碰到占用槽的条件下，第 \(j\) 次在剩下 \(m-j+1\) 个未查槽里碰到剩下 \(n-j+1\) 个元素之一，概率 \((n-j+1)/(m-j+1)\le n/m\)。于是

推导拆解：两个关键步骤。 (1) 每个因子都 \(\le\alpha\)：\(\frac{n-j+1}{m-j+1}\le\frac nm\) 等价于 \(m(n-j+1)\le n(m-j+1)\)，即 \(-m(j-1)\le-n(j-1)\)，因 \(n<m\) 成立。直觉是：分子分母同时减去相同的数，一个小于 1 的分数只会变小。\(i-1\) 个因子相乘，所以 \(\le\alpha^{i-1}\)。 (2) 尾部求和公式 \(E[X]=\sum_{i\ge1}\Pr\{X\ge i\}\)：对取正整数值的 \(X\)，\(X=3\) 时它在 \(\Pr\{X\ge1\}\)、\(\Pr\{X\ge2\}\)、\(\Pr\{X\ge3\}\) 里各被算一次，恰好贡献 3，所以累加"至少 \(i\) 次的概率"就得到期望。这和"按存续概率累加得到债券的预期存续年数"是同一个公式。 再把 \(\sum\alpha^{i-1}\) 用几何级数求和即得 \(\frac1{1-\alpha}\)。

直观地读 \(1/(1-\alpha)=1+\alpha+\alpha^2+\cdots\)：第一次探查必做；以约 \(\alpha\) 的概率要做第二次；以约 \(\alpha^2\) 的概率要做第三次……表半满时至多 2 次，90% 满时至多 10 次。

推论 11.7：插入一个元素平均至多 \(1/(1-\alpha)\) 次探查（插入 = 一次不成功搜索 + 放进第一个空槽）。

定理 11.8：均匀散列且每个关键字等可能被搜索时，成功搜索的期望探查次数至多

证明. 搜索 \(k\) 重走插入 \(k\) 时的探查序列。若 \(k\) 是第 \(i+1\) 个插入的，由推论 11.7 其代价至多 \(m/(m-i)\)。对 \(n\) 个关键字平均：

推导拆解：(1) 为什么第 \(i+1\) 个插入的关键字代价至多 \(\frac m{m-i}\)：插入它时表里已有 \(i\) 个元素，装载因子是 \(i/m\)，代入推论 11.7 得 \(\frac1{1-i/m}=\frac m{m-i}\)。早插入的元素代价低，晚插入的代价高，成功搜索的平均值是对所有元素取平均。 (2) 换元：令 \(k=m-i\)，\(i\) 从 0 到 \(n-1\) 时 \(k\) 从 \(m\) 降到 \(m-n+1\)；\(\frac mn=\frac1\alpha\) 提到前面。 (3) 求和换积分：\(\frac1k\le\int_{k-1}^k\frac{dx}x\)（\(1/x\) 是递减函数，在区间 \([k-1,k]\) 上处处 \(\ge\frac1k\)），把这些小积分拼起来正好是 \(\int_{m-n}^m\)。积分结果 \(\ln m-\ln(m-n)=\ln\frac m{m-n}=\ln\frac1{1-\alpha}\)。 数值核对：\(\alpha=0.5\) 时 \(\frac1{0.5}\ln2=1.386\)；\(\alpha=0.9\) 时 \(\frac1{0.9}\ln10=2.558\)。

半满时成功搜索少于 1.387 次，90% 满时少于 2.559 次。注意不成功搜索对装载因子敏感得多：这正是"不存在的键"（例如查询一个当日未上市的代码、一个已撤销的订单 ID）在高负载表里格外慢的原因。

11.5 完全散列

当关键字集合是静态的（static）——一旦存入就不再变化，比如编程语言的保留字、当日的证券代码表——散列可以做到最坏情况 \(O(1)\) 次内存访问，称为完全散列（perfect hashing）。

两级方案（原书图 11.6）：第一级用全域族中的 \(h\) 把 \(n\) 个关键字散列到 \(m=n\) 个槽；槽 \(j\) 不挂链表，而是挂一张大小为 \(m_j=n_j^2\) 的二级表，配一个精心挑选的二级函数 \(h_j\)，保证二级无冲突。原书例：\(K=\{10,22,37,40,52,60,70,72,75\}\)，外层 \(a=3,b=42,p=101,m=9\)，75 进入槽 2，再在 \(S_2\) 中放到位置 7。

为什么二级表要取 \(n_j^2\)？

定理 11.9：用全域族中随机选取的 \(h\) 把 \(n\) 个关键字存进大小 \(m=n^2\) 的表，出现任何冲突的概率小于 \(1/2\)。

证明. 共 \(\binom n2\) 对，每对冲突概率至多 \(1/m\)，冲突数 \(X\) 的期望 \(E[X]\le\binom n2\frac1{n^2}<\frac12\)；由 Markov 不等式 \(\Pr\{X\ge1\}\le E[X]<1/2\)。\(\square\)

所以随机试几次就能找到无冲突的二级函数。但 \(n^2\) 的空间对整个集合太大，只能用在每个槽内部。关键在于证明这些平方加起来不大：

定理 11.10：用全域族中随机选的 \(h\) 把 \(n\) 个关键字存进 \(m=n\) 个槽，则 \(E[\sum_jn_j^2]<2n\)。

证明. 用恒等式 \(a^2=a+2\binom a2\)：

推导拆解：恒等式 \(a^2=a+2\binom a2\) 可以直接验证：\(\binom a2=\frac{a(a-1)}2\)，所以右边 \(=a+a(a-1)=a^2\)。它的用处是把"平方"翻译成"计数"：\(\binom{n_j}2\) 正好是槽 \(j\) 里的冲突对数，所有槽加起来就是全表的冲突对数，而冲突对数的期望可以用全域性直接算——\(\binom n2\) 对，每对冲突概率 \(\le\frac1m=\frac1n\)。\(\sum_jn_j=n\) 是因为每个关键字恰好落在一个槽。最后 \(n+2\cdot\frac{n(n-1)}2\cdot\frac1n=n+(n-1)=2n-1\)。 定理 11.9 和推论 11.12 都用 Markov 不等式把"期望小"翻译成"大概率小"：期望冲突数 \(<\frac12\)，所以"至少 1 次冲突"的概率 \(<\frac12\)；期望空间 \(<2n\)，所以"空间 \(\ge4n\)"的概率 \(<\frac12\)。每次失败就重抽，平均不到 2 次就成功，就像抛硬币直到出现正面。

推论 11.12：二级表总空间 \(\ge4n\) 的概率小于 \(1/2\)（Markov 不等式）。于是试几次第一级函数，就能得到总空间 \(O(n)\)、最坏 \(O(1)\) 查找的结构。

11.6 量化实战

11.6.1 关键字有规律时：别让 \(m\) 是 2 的幂

A 股 Level-1 快照大约每 3 秒一笔。假设我们用毫秒时间戳作关键字建索引——这些时间戳都是 3000 的倍数，而 \(3000=2^3\times375\)，所以它们的最低 3 位永远是 0。若取 \(m=2^{12}\) 做除法散列，只有八分之一的槽可能被用到。下面的代码把这一点和开放寻址的理论界一起验证：

import numpy as np
rng = np.random.default_rng(42)

# ---------- 1. 三种散列函数在"有规律的关键字"上的表现 ----------
# 关键字：某交易日 09:30–15:00 每 3 秒一笔快照的毫秒时间戳（都是 3000 的倍数）
t0 = 34_200_000                                        # 09:30:00 距零点的毫秒数
keys = t0 + 3000 * np.arange(4800)                     # 4800 个快照
def load_stats(h, m):
    cnt = np.bincount(h, minlength=m)
    return (cnt > 0).mean(), cnt.max()
A = (np.sqrt(5) - 1) / 2
w, p = 32, 12                                          # 乘法散列：m = 2^p, 用 32 位整数实现
s = int(A * 2**w)                                      # s = 2654435769
cases = {
    "除法 m=4096(2^12)": (keys % 4096, 4096),
    "除法 m=4093(素数)": (keys % 4093, 4093),
    "乘法 m=4096, A≈0.618": (((keys.astype(np.uint64) * np.uint64(s)) % np.uint64(2**w)) >> np.uint64(w - p), 4096),
}
for name, (h, m) in cases.items():
    used, mx = load_stats(h.astype(np.int64), m)
    print(f"{name:<22s} 被占用槽比例 {used:6.1%}   最长链 {mx}")

# 原书例：k=123456, p=14, w=32 → h(k)=67
k = 123456; prod = k * 2654435769
print("原书乘法散列例 h(123456) =", (prod % 2**32) >> (32 - 14))

# ---------- 2. 开放寻址：模拟探查次数 vs 均匀散列理论界 ----------
def simulate(m, alpha, method, trials=3):
    n = int(alpha * m); succ, unsucc = [], []
    for _ in range(trials):
        T = np.full(m, -1, dtype=np.int64)
        ks = rng.choice(10**9, size=n + 2000, replace=False)
        def probe_seq(k):
            h1 = k % m
            if method == "linear":
                return ((h1 + i) % m for i in range(m))
            h2 = 1 + (k % (m - 1))                     # m 为素数，h2 ∈ [1, m-1] 与 m 互素
            return ((h1 + i * h2) % m for i in range(m))
        def insert(k):
            for c, j in enumerate(probe_seq(k), 1):
                if T[j] == -1: T[j] = k; return c
        costs = [insert(int(k)) for k in ks[:n]]       # 插入代价 = 该键日后成功搜索的代价
        succ.append(np.mean(costs))
        for k in ks[n:]:                               # 不在表中的键：不成功搜索
            for c, j in enumerate(probe_seq(int(k)), 1):
                if T[j] == -1: unsucc.append(c); break
    return np.mean(succ), np.mean(unsucc)

m = 10007
print(f"\n{'α':>5s} | {'线性:成功':>9s} {'线性:不成功':>10s} | {'双重:成功':>9s} {'双重:不成功':>10s} | {'界:成功':>8s} {'界:不成功':>9s}")
for alpha in [0.5, 0.75, 0.9]:
    ls, lu = simulate(m, alpha, "linear")
    ds, du = simulate(m, alpha, "double")
    bs, bu = np.log(1/(1-alpha))/alpha, 1/(1-alpha)
    print(f"{alpha:5.2f} | {ls:9.2f} {lu:10.2f} | {ds:9.2f} {du:10.2f} | {bs:8.2f} {bu:9.2f}")

运行输出：

除法 m=4096(2^12)        被占用槽比例  12.5%   最长链 10
除法 m=4093(素数)          被占用槽比例 100.0%   最长链 2
乘法 m=4096, A≈0.618     被占用槽比例  99.8%   最长链 2
原书乘法散列例 h(123456) = 67

    α |     线性:成功     线性:不成功 |     双重:成功     双重:不成功 |     界:成功     界:不成功
 0.50 |      1.50       2.52 |      1.40       2.02 |     1.39      2.00
 0.75 |      2.61       8.92 |      1.84       3.97 |     1.85      4.00
 0.90 |      5.15      40.31 |      2.58       9.93 |     2.56     10.00

第一部分印证了 11.3.1 节的告诫：\(m=2^{12}\) 时只用到 12.5% 的槽，链长被放大 8 倍；换成素数或乘法散列，分布立刻均匀。时间戳、价格（以分为单位，常是 5 或 10 的倍数）、按步长递增的订单号，都是带规律的关键字。

第二部分说明理论界有多准：双重散列的模拟值与均匀散列的上界几乎重合；线性探查在 \(\alpha=0.9\) 时不成功搜索平均要 40 次，比均匀散列的 10 次差 4 倍——这就是一次群集。（作为补充：Knuth 对线性探查给出的近似公式是成功 \(\tfrac12(1+\tfrac1{1-\alpha})\)、不成功 \(\tfrac12(1+\tfrac1{(1-\alpha)^2})\)，在 \(\alpha=0.9\) 时分别约为 5.5 和 50.5，与模拟一致。）

容量规划的结论：低延迟系统关心的是尾延迟而不是平均值。开放寻址表应在开盘前按"当日最大可能条目数 / 目标装载因子"预分配（例如目标 \(\alpha\le0.5\)），盘中禁止触发扩容；若用线性探查（为了缓存友好），装载因子要压得更低。

11.6.2 全域散列与静态代码表的完全散列

第二段代码做两件事：一是演示对手攻击——当关键字恰好全部同余于 \(m\) 时，固定的除法散列退化成一条链，而随机选的 \(h_{ab}\) 不受影响；二是为一张约 5000 只证券的静态代码表构造 FKS 两级完全散列。

import numpy as np
rng = np.random.default_rng(2024)
P = 2_147_483_647                                    # 素数 2^31-1，大于所有关键字

def h_ab(a, b, m):                                   # 全域散列族 H_pm 中的一个函数
    return lambda k: ((a * k + b) % P) % m

# ---------- 1. 对手攻击：固定的 h(k)=k mod m vs 随机选取的 h_ab ----------
m, n = 1024, 1000
evil = [1024 * i + 7 for i in range(n)]              # 对手知道 m，故意让所有键 ≡ 7 (mod m)
fixed = np.bincount([k % m for k in evil], minlength=m)
print("固定除法散列 最长链:", fixed.max())
mx = []
for _ in range(200):                                 # 每次运行随机挑一个 h_ab
    a, b = int(rng.integers(1, P)), int(rng.integers(0, P))
    h = h_ab(a, b, m)
    mx.append(np.bincount([h(k) for k in evil], minlength=m).max())
print("全域散列 最长链: 均值 %.1f, 200 次中最大 %d" % (np.mean(mx), max(mx)))

# ---------- 2. 完全散列（FKS 两级）：当日证券代码表是静态集合 ----------
codes = np.unique(np.concatenate([
    rng.choice(np.arange(600000, 606000), 1700, replace=False),   # 沪市主板
    rng.choice(np.arange(1, 4000), 1500, replace=False),          # 深市主板（000001 等）
    rng.choice(np.arange(300001, 301800), 1300, replace=False),   # 创业板
    rng.choice(np.arange(688001, 689000), 580, replace=False),    # 科创板
]))
n = len(codes)

def build_fks(keys):
    n = len(keys)
    while True:                                      # 第一级：m=n，直到二级总空间 < 4n（期望试 <2 次）
        a, b = int(rng.integers(1, P)), int(rng.integers(0, P))
        slot = ((a * keys + b) % P) % n
        cnt = np.bincount(slot, minlength=n)
        if (cnt ** 2).sum() < 4 * n: break
    tables = []
    for j in range(n):
        ks = keys[slot == j]; mj = len(ks) ** 2
        if mj == 0: tables.append((0, 0, 0, None)); continue
        while True:                                  # 第二级：m_j = n_j^2，无冲突概率 > 1/2
            aj, bj = int(rng.integers(1, P)), int(rng.integers(0, P))
            pos = ((aj * ks + bj) % P) % mj
            if len(np.unique(pos)) == len(ks): break
        T = np.full(mj, -1, dtype=np.int64); T[pos] = ks
        tables.append((aj, bj, mj, T))
    return a, b, tables, int((cnt ** 2).sum())

a, b, tables, space = build_fks(codes)
def lookup(k):                                       # 最坏情况：两次散列 + 一次比较
    aj, bj, mj, T = tables[((a * k + b) % P) % n]
    return mj > 0 and T[((aj * k + bj) % P) % mj] == k
print(f"\n证券数 n={n}, 二级表总槽数 Σn_j^2={space}  (= {space/n:.2f} n；期望 < 2n，构造时要求 < 4n)")
print("所有代码都能查到:", all(lookup(int(k)) for k in codes))
absent = [k for k in range(600000, 600100) if k not in set(codes.tolist())]
print(f"600000–600099 中不在表内的 {len(absent)} 个代码都查不到:", not any(lookup(k) for k in absent))

运行输出：

固定除法散列 最长链: 1000
全域散列 最长链: 均值 2.9, 200 次中最大 14

证券数 n=5080, 二级表总槽数 Σn_j^2=10384  (= 2.04 n；期望 < 2n，构造时要求 < 4n)
所有代码都能查到: True
600000–600099 中不在表内的 70 个代码都查不到: True

读这组结果要分清全域散列保证了什么。它保证的是任意两个关键字的冲突概率不超过 \(1/m\)，因此链长的期望有界（定理 11.3）；它并不保证每一次抽到的函数都把最长链压到很短——200 次里出现过一次最长链 14，这是对手无法预知、也无法稳定复现的偶然事件。实践中的对应物是字符串散列的随机种子：Python 自 3.3 起默认对 str/bytes 的散列加随机盐（可由 PYTHONHASHSEED 控制），目的就是防止有人构造大量冲突的键拖垮服务（所谓 hash flooding）。注意这也意味着 Python 里字符串的 hash() 值在不同进程之间不同，不能拿来做持久化的分片键。

FKS 的结果符合定理 11.10：一次抽样得到的二级表总空间约 \(2n\)；查找最坏只需两次散列和一次比较，延迟是确定的。对每天开盘前生成一次、盘中不变的代码表，这种"预处理换确定性"的做法很合适；若代码表盘中会变（新股上市、临时停牌不影响代码集合，但跨市场品种可能动态加入），就退回到普通散列表。

11.6.3 其他用途与注意事项

• 行情快照表：dict[code] → snapshot 是最自然的实现。若代码范围固定（六位数字），直接寻址数组更快且无冲突；若要按代码顺序遍历或做范围查询（"所有 688 开头的"），散列表不支持有序操作，应改用有序结构（本册第 12 章）或排序数组 + 二分。
• 面板数据的 join / groupby：pandas 的 merge、groupby 在内部对键做散列。键的 dtype 影响很大：把证券代码存为 category 或整数，比存为 Python 对象字符串快得多，因为散列和比较的代价不同。
• 订单 ID 索引：撮合引擎和 OMS 中，订单 ID → 订单结点指针的散列表与上一章的双向链表配合，实现 \(O(1)\) 撤单。订单 ID 通常是递增整数，用乘法散列或直接用低位做开放寻址都要警惕规律性。
• 不要把散列表当成有序容器：从 Python 3.7 起 dict 保持插入顺序，但那是插入顺序而不是关键字顺序。

本章小结

散列表用 \(\Theta(|K|)\) 的空间实现平均 \(O(1)\) 的字典操作，代价是最坏情况 \(\Theta(n)\)。链接法在简单均匀散列下成功和不成功搜索都是 \(\Theta(1+\alpha)\)；开放寻址在均匀散列下不成功搜索至多 \(1/(1-\alpha)\) 次探查、成功搜索至多 \(\frac1\alpha\ln\frac1{1-\alpha}\) 次，装载因子接近 1 时急剧恶化。散列函数的选择决定了"均匀"假设能否近似成立：除法散列取远离 2 的幂的素数，乘法散列可取 \(m=2^p\)，全域散列靠随机选函数抵御对手。静态集合可以用两级完全散列做到最坏 \(O(1)\)。

练习

基础

1. 用 \(h(k)=k\bmod9\) 和链接法依次插入 5, 28, 19, 15, 20, 33, 12, 17, 10，画出散列表。（原书 11.2-2。）
2. 若链表保持有序，链接法各操作的时间如何变化？（原书 11.2-3。提示：不成功搜索可提前停止但渐近不变；插入变为 \(\Theta(1+\alpha)\)。）
3. 用 \(m=1000\)、\(A=(\sqrt5-1)/2\) 计算关键字 61–65 的乘法散列值。（原书 11.3-4。）
4. 用 \(m=11\) 分别以线性探查、二次探查（\(c_1=1,c_2=3\)）、双重散列（\(h_1(k)=k\)，\(h_2(k)=1+(k\bmod10)\)）插入 10, 22, 31, 4, 15, 28, 17, 88, 59。（原书 11.4-1。）
5. 计算 \(\alpha=3/4\) 和 \(7/8\) 时开放寻址成功与不成功搜索的期望探查上界。（原书 11.4-3。答案：不成功 4、8；成功约 1.85、2.38。）

进阶

6. 证明简单均匀散列下 \(n\) 个不同关键字的期望冲突对数为 \(\binom n2/m\)，并据此估算：一张 \(m=2^{16}\) 的表存 5000 只证券代码，期望有多少对冲突？（原书 11.2-1。答案约 190.7 对。）
7. 双重散列中若 \(\gcd(m,h_2(k))=d>1\)，证明不成功搜索只检查表的 \(1/d\) 就回到起点。（原书 11.4-4。）
8. 写出开放寻址的 HASH-DELETE（使用 DELETED 标记），并修改 HASH-INSERT。再思考：一张整天都在插入和删除订单的表，DELETED 越积越多会怎样？应在什么时候、用什么方法清理？（原书 11.4-2 的延伸。）
9. 思考题 11-2：\(n\) 个关键字散列到 \(n\) 个槽，证明最满槽的期望负载为 \(O(\lg n/\lg\lg n)\)。用代码模拟 \(n=10^3,10^4,10^5\) 验证增长速度。
10. 思考题 11-4：说明 2-全域族如何用于消息认证，对手即使知道整个函数族，伪造成功的概率也至多 \(1/p\)。

原书推荐习题：11.2-1、11.2-3、11.3-4、11.4-1、11.4-2、11.4-3，思考题 11-2、11-4。

原书对照