完美哈希 | Codeboy's Blog

形式陈述

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

FKS 两层方案令 $n=|S|$ 。一级从通用哈希族选函数，把键分进 $n$ 个桶，桶大小为 $n_i$ ；重新抽样直到

\sum_i n_i^2=O(n).

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

直觉

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

普通哈希表把碰撞留给查询时处理；完美哈希把代价前移到构建阶段，换取每次查询固定次数的定位。这一交换依赖键集不再变化。

例子与边界

若一级桶大小依次为 $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.

形式陈述 ​

反向链接

形式陈述