完美哈希

形式陈述 ​

对有限静态键集 $S\subseteq U$，函数 $h:U\to [m]$ 若在 $S$ 上单射，就称为 $S$ 的 perfect hash function；若同时 $m=|S|$，称为 minimal perfect。完美性只针对 $S$，不要求整个键域无碰撞。

FKS 两层方案令 $n=|S|$。一级从通用哈希公理库通用哈希Universal hashing · Universal hash family从函数族随机选择哈希函数，使任意预先固定的不同键对以至多 1/m 的概率碰撞。族选函数，把键分进 $n$ 个桶，桶大小为 $n_i$；重新抽样直到

$$\sum _i{n}_i^2=O(n).$$

桶 $i$ 分配 $m_i=n_i^2$ 个二级槽，并独立抽取哈希函数，若桶内有碰撞便重抽。通用性使任一二级试验发生碰撞的概率受常数界，故期望常数次即可成功。查询先计算一级桶，再计算该桶的二级位置并核对键，最坏只做常数次哈希和访问；总空间为 $\sum _{i}O(n_i^2)=O(n)$，随机化构建的期望时间为 $O(n)$。

直觉 ​

静态集合已经知道全部键，因而可以反复试验哈希函数，直到这些键恰好不冲突。FKS 不强求一级无碰撞，而是给拥挤桶二次空间：桶大小平方后的槽数让随机无碰撞有常数成功概率，一级再保证所有平方空间之和仍为线性。

普通哈希表公理库哈希表Hash table用哈希函数把键映射到桶并处理冲突的字典结构。把碰撞留给查询时处理；完美哈希把代价前移到构建阶段，换取每次查询固定次数的定位。这一交换依赖键集不再变化。

例子与边界 ​

若一级桶大小依次为 $3,1,0,2$，二级空间按 $9,1,0,4$ 分配。拥挤的三键桶获得九个候选槽，空桶不占二级表；查询仍只访问选中桶，而不是扫描这十四个槽。平方分配的意义是把桶内成对碰撞概率总和压到常数，而非随意放大容量。

perfect 不等于 minimal perfect：FKS 总空间线性，却通常拥有空槽；minimal perfect 还要求值域正好有 $n$ 个位置。查询无冲突也不等于构建确定性线性时间，FKS 的线性构建界对随机选择取期望。

插入一个新键可能与现有二级函数冲突，删除则留下空位；频繁动态更新会触发局部或整体重建。若工作负载不是静态字典，应使用动态哈希方案，不能沿用 FKS 的最坏常数查询与期望线性一次构建而忽略维护成本。

推论与应用 ​

完美哈希适合编译器保留字、静态路由表和生成后只读的键集合。它还能把静态成员查询变成固定的两次定位，并通过键核对安全处理不属于 $S$ 的查询。

minimal perfect hashing 进一步压缩槽域，常用于大型静态词典；它解决的是空间编号问题，不自动保存值、排序或范围查询。是否需要最小性，应由存储预算决定，而不是把它当作完美哈希的必备条件。

参考资料

• Michael L. Fredman, János Komlós, and Endre Szemerédi, “Storing a Sparse Table with O(1) Worst Case Access Time,” Journal of the ACM 31(3), 1984, pp. 538–544.
• Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, §11.5, static hashing.