哈希表出现冲突，不代表查找可以返回错误记录。精确字典必须在同一桶中继续比较完整键；随机散列影响的是这一步要检查多少条记录。若要说“期望常数时间”，还需指出随机选择了什么，以及输入是否能观察这个选择。

第 03 篇的摊还分析不需要概率。本篇固定键集，对散列函数的随机选择取期望，再把碰撞成本与扩容成本分开。讨论链式散列，不把开放寻址、密码散列或 Python 字典的内部实现自动归入同一个定理。

先固定概率空间

输入为互异整数键的集合 S，大小 n；桶数 m≥1。每个桶保存完整键值记录，散列值只决定访问哪个桶。插入相同键时覆盖还是拒绝要由字典 API 决定，碰撞分析只统计不同键。

设 H 为一族函数，每个函数把键映到 [0,m)。称它具有本篇所需的通用性，是指任意事先固定的不同键 x、y 都满足：

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

键集 S 和待查询键必须在 h 随机选定前固定，或至少独立于这次选择。函数选定后，一次运行中的 h 不再变化；期望指重新抽取函数时的成本分布，不是把一次固定函数上的用户请求随意平均。MIT 的散列讲义以随机函数族建立这一保证。MIT 6.006 Lecture 4

一次碰撞上界怎样变成链长

对固定的缺失查询键 x，定义指示变量 $I_y$ ：当 y 与 x 同桶时为 1，否则为 0。扫描的候选数 $L_x=\sum_{y\in S}I_y$ 。由期望的线性性：

\mathbb E[L_x]=\sum_{y\in S}\mathbb E[I_y]\le n/m.

若 x 已在 S 中，桶中至少含 x 自身，其余不同键贡献至多 $(n-1)/m$ ，所以所在链的期望长度至多 $1+(n-1)/m$ 。成功查找可能提前找到 x，扫描量不超过整条链长。计算 h、访问桶和比较键若均为单位成本，查找的期望成本为 O(1+n/m)。

这一步不需要所有碰撞事件相互独立。线性期望对相关变量也成立；独立性只在其他更强结论中可能需要。通用族给出的是每一对固定不同键的碰撞上界，不能把它说成所有桶独立均匀。

当负载因子 $\alpha=n/m$ 受正常数控制，期望查询才为 O(1)。固定 m 而让 n 任意增大，公式本身就告诉出线性链长风险。空间为 O(m+n)，预先建立空桶需要 O(m)，这些成本不能因为查询快而消失。

一个可以穷举的小函数族

取素数 p，键域限制为 [0,p)，均匀选择 $a\in\{1,\ldots,p-1\}$ 与 $b\in\{0,\ldots,p-1\}$ ，定义：

h_{a,b}(x)=((ax+b)\bmod p)\bmod m.

这里假定 m≤p。对不同 x、y，令 $r=ax+b\pmod p$ 、 $s=ay+b\pmod p$ 。由于 p 为素数，x-y 在模 p 下可逆；对任意不同 r、s，恰有一组非零 a 与 b 对应。因此 (r,s) 均匀分布在全部 p(p-1) 个有序不同余数对上。

第二次模 m 把 p 个余数分成 m 组，每组大小最多 $\lceil p/m\rceil$ 。固定 r 后，与之同组的其他 s 最多 $\lceil p/m\rceil-1\le(p-1)/m$ 个，所以碰撞概率至多 $1/m$ 。这是一般参数的证明，既解释了非零 a，也解释了素数条件为何出现在构造中。

若允许 a=0，这些函数全部把键映到同一个桶，会改变概率；若把 p 换为合数，x-y 可能没有逆元，均匀有序对的论证失效。某些参数仍可能碰巧工作，但不能再沿用这份证明。

教学程序 universal_hash.py 固定 p=17、m=5，枚举 16×17=272 个函数和 136 对不同键。实际运行得到每对键的最大碰撞次数为 42，因此最大比率为 42/272，小于 1/5。检查使用整数交叉相乘，避免浮点舍入把边界弄错。这个有限枚举只验证此参数族，不能替代任意素数 p 的证明。

看见函数以后选择键

固定函数 h(x)=x%5 时，键 0,5,10,15 全部进入同一桶。对更大的整数域，可继续构造任意长序列。这与通用散列定理并不矛盾：定理先固定键，再随机抽函数；攻击例先固定并知道函数，再选择输入。

即使函数来自通用族，若对手观察散列值后自适应构造下一条键，键与 h 之间已产生依赖。上面的期望计算不能原样应用，需要新的对手模型和更强的分析。CMU 的散列复习题也专门区分了观察函数结果后选键的场景；它提供问题设定，不提供本程序的安全证明。CMU Hashing review

密码散列讨论单向性或抗碰撞计算困难性；通用散列讨论一个函数族在随机选择下的成对碰撞概率。两者的问题、成本和威胁模型不同。这里的线性模函数不能用于密码存储，也没有承诺抵御能观察参数的攻击者。

期望不等于高概率

链长的期望为常数，不等于每次查找都只扫描常数条，更不等于全部桶的最大链长有同样界。对非负随机变量，Markov 不等式至多从当前信息得到 $\Pr[L_x\ge t]\le\mathbb E[L_x]/t$ 。若阈值 t 也是固定常数，失败概率不一定随 n 变小。

高概率保证必须写出明确事件和随参数变化的失败概率，例如“概率至少为 $1-n^{-c}$ ”。这里没有证明这样的最大链结论，因此不把一次穷举中较短的链当作高概率证据。不同随机事件共享同一个 h，随意相乘概率同样没有依据。

第 00 篇榜单还依赖动态字典扩容。碰撞扫描的期望界与整段序列的搬迁摊还界是两项分析：在合适散列假设、受控负载、合理重建规则下，才组合成“期望摊还 O(1) 更新”。第 03 篇证明的容量增长本身不能保证桶内碰撞少。

复跑与两道练习

1	`python3 examples/advanced-algorithms/check_foundations.py`

输出中的散列部分包含函数数、键对数、最大碰撞次数及固定取模攻击，原始记录在 examples/advanced-algorithms/results/foundations.json。本篇检查卡注明键域与概率空间。整数乘法和模运算在固定机器字假设下计常数；Python 大整数的真实成本随位长增长，本实验没有测 word-RAM 性能。

删除构造中的随机 b，只选非零 a。先解释为什么本篇“任意有序不同余数对恰有一个参数对”的证明不再成立，再对 p=17、m=5 穷举碰撞。区分“这份证明失效”与“命题必然为假”。
固定一个缺失查询键 x，手算 n 个碰撞指示变量的期望和。随后让查询键从观察到的最长链中选择，指出哪一个“固定”条件被破坏。设计程序分别记录固定查询与自适应查询的链长，不把结果误称为同一个随机实验。