第8章 The Dictionary Problem：字典问题

从直接寻址、链式与通用哈希推进到静态完美表、动态布谷鸟哈希和允许单侧误差的布隆过滤器，统一分析字典操作的时间、空间与概率保证。

学习目标

能解释“8 The Dictionary Problem”如何比较直接寻址、通用/完美哈希、布谷鸟哈希与布隆过滤器的保证
能逐项核对Direct-Address Tables、Hash Tables、Universal Hashing、A Simple (Static) Perfect Hash Table、Cuckoo Hashing、More on Static and Perfect Hashing: Minimal and Ordered、Bloom Filters，不把平台页数或相邻章节主题冒充原版目录
能固定输入和参数，按“Bloom FPR ≈ (1 - exp(-k n / m))^k”手算一个最小样例，并找到输出或成本的首个分叉
能注入“复用相关哈希或超过设计负载仍声称常数最坏时间与目标误报率”，保存基线、故障、恢复和同输入重放证据

来源、版次与独立重写边界

“8 The Dictionary Problem”对应 Paolo Ferragina 的 Pearls of Algorithm Engineering（Cambridge University Press，2023）。出版社书籍页确认作者、版次、ISBN、318页与算法工程定位；官方目录页和官方前置信息 PDF共同给出16章、61个编号节与索引的正式顺序。

对“8 The Dictionary Problem”而言，当前公开可核验材料是出版社目录、前言与书籍说明，并非获授权完整正文。因此，下方中文讲解、公式推导、代码和实验是按公开目录坐标进行的独立教学重写，不声称逐段翻译原书；涉及“比较直接寻址、通用/完美哈希、布谷鸟哈希与布隆过滤器的保证”的结论必须由本页的最小输入、预言机与成本记录重新证明。

官方目录坐标：8 The Dictionary Problem

8.1 Direct-Address Tables：在本页正文中以“比较直接寻址、通用/完美哈希、布谷鸟哈希与布隆过滤器的保证”的对象、状态、复杂度或工程边界核对。
8.2 Hash Tables：在本页正文中以“比较直接寻址、通用/完美哈希、布谷鸟哈希与布隆过滤器的保证”的对象、状态、复杂度或工程边界核对。
8.3 Universal Hashing：在本页正文中以“比较直接寻址、通用/完美哈希、布谷鸟哈希与布隆过滤器的保证”的对象、状态、复杂度或工程边界核对。
8.4 A Simple (Static) Perfect Hash Table：在本页正文中以“比较直接寻址、通用/完美哈希、布谷鸟哈希与布隆过滤器的保证”的对象、状态、复杂度或工程边界核对。
8.5 Cuckoo Hashing：在本页正文中以“比较直接寻址、通用/完美哈希、布谷鸟哈希与布隆过滤器的保证”的对象、状态、复杂度或工程边界核对。
8.6 More on Static and Perfect Hashing: Minimal and Ordered：在本页正文中以“比较直接寻址、通用/完美哈希、布谷鸟哈希与布隆过滤器的保证”的对象、状态、复杂度或工程边界核对。
8.7 Bloom Filters：在本页正文中以“比较直接寻址、通用/完美哈希、布谷鸟哈希与布隆过滤器的保证”的对象、状态、复杂度或工程边界核对。

从“只需判断键是否存在”开始

dictionary problem维护对象集合 D。对象通常写成 key 与 satellite data 的二元组；本章先只讨论键集 S，再把命中的键映射回附属数据。

Search(k)：判断键 k 是否存在，必要时返回对应对象；
Insert(x)：插入 key[x] 唯一标识的对象；
Delete(k)：若键存在则删除其对象。

只有 Search 的冻结键集是 static dictionary；同时支持三种操作的是 dynamic dictionary。这个区分决定能否花较高构造成本换取最坏常数查询，也决定更新时是局部移动还是全表重建。

先预测：一个 URL 爬虫字典若有十亿个长键，应该存完整 URL、两处槽位，还是只存几位指纹？若业务不能容忍误报，指纹位图不能替代精确字典；若它只负责快速排除“肯定没见过”的 URL，单侧误差反而能以很少空间挡住大多数后端访问。

本页依次收紧三种资源：直接寻址用宇宙大小换最坏常数；哈希把空间降到键数级但引入随机保证；Bloom filters（布隆过滤器）连键本身也不存，再以可调误报换更小空间。

直接寻址表：最简单的最坏常数方案

direct-address tables建立大小 u=|U| 的数组 T。纯成员查询时 T[k] 是一位；带附属数据时 T[k] 是指针，空指针表示不存在。

Search、Insert、Delete 都只访问 T[k]，因此最坏时间是 O(1)。问题是空间取决于 u 而不是 n=|S|：

\text{space}_{\mathrm{direct}} = \Theta(u)

当 n 与 u 同阶，它是最直接也最可靠的工程解；若 32 位学号只用了百万个值，开出 2 的 32 次方个槽就浪费巨大。算法工程的第一条判断不是“能否哈希”，而是宇宙是否足够稠密，能否通过区间压缩或位图先把直接寻址做对。

链式哈希：负载因子决定平均扫描长度

Hash table with chaining 用 m 个数组槽，每个槽指向一条链。哈希函数 h 把宇宙键映射到 0 至 m-1；键 k 位于链 T[h(k)]。

Insert 把新项接到链头，给定 h 为 O(1)；
Search 扫描 T[h(k)]；
Delete 先搜索，再摘除节点。

若键均匀散入槽位，负载因子 alpha=n/m 就是平均链长。成功或失败查询都满足：

\mathbb{E}[T_{\mathrm{search}}] = \Theta\left(1+\frac{n}{m}\right) = \Theta(1+\alpha)

链表指针、键和一级表都要计入空间。令宇宙大小为 u，本页给出的位成本为：

(m+n)\log_2 n+n\log_2 u

长 URL 等键的 n log u 项可能远大于索引指针，这个观察随后直接导向布隆过滤器。

字典大小未知时，以 m=2n0 建表；当 n 小于 n0/2 时减半，当 n 大于 2n0 时加倍，再把当前键全部重哈希。一次重建成本 Theta(n)，但相邻重建之间至少发生 Omega(n) 次更新，故每次操作只分摊 O(1)。

固定的除留余数 h(k)=k mod m 或乘法散列很快，却总存在针对它的坏键集。例如取 m 的倍数会让除留余数全部落到同一槽。未知输入分布下，不可能靠一个事先固定的 h 对所有集合都保持均匀。

通用哈希：随机选择函数，而不是假设输入随机

universal hashing把随机性放到实现内部。对任意不同 x、y，哈希族 H 满足：

\Pr_{h\sim H}[h(x)=h(y)] \le \frac{1}{m}

这与随机 pivot 的 Quicksort 同理：输入可以固定甚至对抗，但运行时才抽取参数。对链式表，任意键 x 与其余 n-1 个键的期望碰撞数小于 alpha，因此不再需要假设键本身独立均匀。

一个可计算的族先选大素数 p 大于宇宙，再随机选 a 大于0、b 不小于0：

h_{a,b}(k) = ((ak+b)\bmod p)\bmod m

另一类在 2 的幂宇宙上用奇数乘法与高位截取，只需机器整数操作，可得到常数倍通用保证。关键不是“某组 a、b 永不碰撞”，而是对每一对键，导致碰撞的参数所占比例有上界。

BuildUniversalTable(keys, m):
  choose random h from a universal family
  for key in keys:
    append key to T[h(key)]
  if longest chain exceeds policy:
    choose a new h and rebuild

单哈希表的最长链仍可能明显大于平均。d-left hashing 分成 d 个子表，插入时检查 d 个候选槽并进入最短链。仅用两个选择，最长链可降到 O(log log n) 量级；这就是 power of two choices，也允许用固定小桶替代指针链，改善局部性。

完美、最小与保序哈希：静态键集换最坏常数

perfect hashing要求不同字典键映射到不同槽。槽数 m 至少为 n；m=n 时称 minimal perfect hash function，查询一次定位且没有空槽。

若还满足 k_i 的顺序早于 k_j 就有 h(k_i) 小于 h(k_j)，它是 order-preserving MPHF，返回值就是冻结字典中的 rank。本页以两组随机哈希 h1、h2 和数组 g 组合：

h(t) = \bigl(g(h_1(t))+g(h_2(t))\bigr)\bmod n

把每个键 t 视为连接 h1(t)、h2(t) 的边；随机图无环时，从每棵树根设 g 值并沿边传播，就能让 h(t) 等于预定 rank。构造平均 O(n)，求值最坏 O(1)，空间 O(n)，但键集变化通常会破坏图和 rank，所以它服务静态字典。

两级完美表：不要求保序时更简单

本页第8.5节给出 FKS 风格两级方案。一级表大小 m=n，用通用 h 把 n 个键分桶；第 j 桶有 n_j 个键，就为它分配 n_j 的平方个二级槽，并独立抽取 h_j，直到该桶无碰撞。

q 个键放进 q 的平方个槽，期望碰撞数小于 1/2，所以平均重抽不到两次。一级各桶平方空间的期望满足：

\mathbb{E}\left[\sum_{j=0}^{m-1}n_j^2\right] \lt 2n

查询只做两次地址计算，但第二槽命中后仍要核对保存的 key；不在集合中的键也可能走到某个非空槽，不能只凭位置返回 true。

SearchPerfect(k):
  j = h(k)
  if T[j] is empty: return false
  i = h_j(k)
  return T[j][i] is not empty and T[j][i].key == k

构造时若一级平方和过大，只重抽一级 h；某个二级桶冲突，只重抽该桶 h_j，不影响其他桶。随机重试因此保持局部，最终提供 O(n) 期望空间和 O(1) 最坏查询。

布谷鸟哈希：两个候选槽与一条逐出路径

cuckoo hashing面向动态精确字典。键 k 只能位于 T[h1(k)] 或 T[h2(k)]，所以 Search 与 Delete 最坏只检查两处。

Insert 若两处都满，就把新键放入一处，逐出旧键；旧键必须转向它的另一个候选槽，不能立刻逐出刚放入的新键。级联直到遇到空槽。

把槽位视为节点、键的两个候选位置视为一条边，就得到 cuckoo graph。边的方向记录当前槽到备用槽；插入逐出链就是沿图走路径。若两条环被新边连接，路径可能永不抵达空槽，系统必须限制逐出步数并重抽 h1、h2 后全表重建。

当表足够稀疏，例如 m 至少为 2cn 且 c 大于1时，长度 L 的连接路径概率按 c 的负 L 次方衰减。查询仍是 O(1) 最坏；一批 Theta(n) 次插入的重哈希总成本是 O(n) 期望，因此单次 Insert 为 O(1) 期望摊还。

InsertCuckoo(k):
  repeat up to MAX_KICKS:
    if one candidate slot is empty:
      place k and return success
    swap k with occupant of the chosen slot
    choose k's other candidate slot next
  rebuild with fresh h1, h2, or place k in a small stash

常数大小 stash 可先收纳检测到环的少数键，把重哈希概率进一步压低。表过满或过空时仍用全局倍增/减半重建；stash 不是无限溢出链，Search 还必须同时查两槽和这块小区域。

布隆过滤器：不存键，只存可控指纹

Bloom filters初始化全零位图 B。插入 k 时把 r 个位置 B[h_i(k)] 置1；查询 y 时，任一位置为0即可断言 y 不在集合，全部为1则返回“可能存在”。

它不存原键，因此标准版本无法列举元素；清除一个共享位会制造假阴性，所以也不能直接 Delete。它最适合作为昂贵精确查询前的否定过滤器，而不是独立的权威字典。

设已插入 n 个键。某位仍为0的概率近似：

p_0 \approx e^{-rn/m}

非成员 y 的 r 个位置恰好都为1，误报率近似：

p_{\mathrm{err}} \approx \left(1-e^{-rn/m}\right)^r

固定 m、n 后最优哈希数是：

r^\star = \frac{m}{n}\ln 2

此时位图约一半为0、一半为1，且误报率约为 0.6185 的 m/n 次方。空间按“每键位数”线性增加，误报却指数下降；工程上把 r 取临近整数，并把哈希计算成本一起纳入预算。

空间下界与三种扩展

任何允许误报 epsilon、禁止假阴性的 n 键成员结构，至少需要：

m \ge n\log_2\frac{1}{\epsilon}

最优参数 Bloom filter 约需 1.44 倍这个下界，因此在渐进空间上只差常数因子。

Compressed Bloom filter 用更大但更稀疏的运行时位图，配合算术编码传输；它可能用更少哈希、在相同传输位数下降低误报，代价是更大运行内存与编解码。Spectral Bloom filter 把位换成计数器，把 r 个计数器最小值作为频次上界估计，并支持多重集增删。

本页还给出分布式集合交应用：机器 A 先把 BF(A) 发给 B；B 用它筛出候选 Q 并回传完整候选键；A 再精确计算 Q 与 A 的交。误报只扩大 Q，不会丢失真实交集，最后一次精确核对恢复正确答案。

用保证矩阵而不是吞吐单值验收

精确结构测试空集、重复插入策略、删除不存在键、扩缩容边界、对抗键集和失败重建。固定随机种子重放布谷鸟逐出轨迹，再用独立集合实现作为 Search 预言机。

Bloom filter 必须分别测假阴性数和假阳性率：已插入键的假阴性必须为0；未插入样本的误报率应在置信区间内接近公式。哈希相关性、位数组长度取整和键编码不一致都会让实测偏离理论。

性能报告至少包含 n、m、alpha、最长链、平均/高分位延迟、重建次数、逐出步数、stash 占用、r、bits/key 与误报率。只报告平均吞吐会掩盖最长链、重哈希暂停和热点查询。

先预测，再操作三个章专属实验

分步1 / 3

1. 成本模型与工作集

在“8 The Dictionary Problem”中先预测层级和访问模式如何改变“Bloom FPR ≈ (1 - exp(-k n / m))^k”，再切换工作集与局部性；最终结果相同不代表代价相同。

Cost-model laboratory

8 The Dictionary Problem

比较直接寻址、通用/完美哈希、布谷鸟哈希与布隆过滤器的保证

工作集所在层级

规模8192

传输256

相对成本8×

Bloom FPR ≈ (1 - exp(-k n / m))^k

不变量：已插入键不能假阴性；误报、空间与更新保证必须与所选结构一致

可重放工程合同

“8 The Dictionary Problem”的实验必须保留：键集、哈希种子、负载因子、逐出路径、位图占用、误报率与真值表。本章性能数据至少预热一次、重复多次并报告分布；正确性必须与独立预言机比较，不能只比较两个共享同一错误的优化实现。

练习与答案

练习

问题 1：正式目录。 “8 The Dictionary Problem”的公开目录边界是什么，平台如何证明没有把其他章主题混入？

问题 2：最小反例。 怎样验证“Bloom FPR ≈ (1 - exp(-k n / m))^k”不是只写在页面上的公式？

问题 3：恢复证据。 怎样证明“复用相关哈希或超过设计负载仍声称常数最坏时间与目标误报率”已经修复？

本章回顾

字典问题按是否支持更新分为静态与动态，并可携带附属数据。
直接寻址表以 Theta(|U|) 空间换三种操作的 O(1) 最坏时间。
链式哈希的期望查询为 Theta(1+alpha)，全局重建保持 alpha 为常数。
通用哈希随机选择函数，使任意不同键对碰撞概率至多 1/m。
两个选择显著降低最长链，并能改善桶局部性。
MPHF 无空槽，OPMPHF 还返回静态有序键的 rank。
两级完美表给每个 q 键桶 q 的平方空间，总空间期望 O(n)，查询最坏 O(1)。
布谷鸟哈希查两槽，插入沿图逐出；环由重哈希、扩容或 stash 处理。
布隆过滤器无假阴性但允许假阳性，最优 r=(m/n)ln2。
压缩和频谱变体分别面向传输带宽与多重集频次。