完美哈希 | Codeboy's Blog

形式陈述

对静态有限键集 $S\subseteq U$ ，函数 $h:U\to[m]$ （其中 $[m]=\{0,\ldots,m-1\}$ ）若限制到 $S$ 后为单射，就称为 $S$ 的 perfect hash function；若同时 $m=|S|$ ，称为 minimal perfect。完美性只针对 $S$ ，不要求整个键域无碰撞。

FKS 两层方案令 $n=|S|\ge1$ ；空集用空表直接回答不存在。一级从通用哈希族选函数，把键分进 $n$ 个桶，桶大小为 $n_i$ ；可以采用明确的接受条件 $\sum_i n_i^2\le4n$ ，不满足就重抽一级函数。

桶 $i$ 分配 $m_i=n_i^2$ 个二级槽，并独立抽取哈希函数，若桶内有碰撞便重抽。对于含 $s\ge2$ 个键的桶，由并集界，发生任一碰撞的概率至多为 $\binom{s}{2}/s^2<1/2$ ，所以期望不到两次试验即可成功；单键桶直接存储，空桶无需二级表。假设键、哈希描述和值各占常数个机器字，且一次哈希及键比较为常数时间。查询先计算一级桶，再计算该桶的二级位置并核对键，最坏只做常数次哈希和访问；总空间为 $\sum_iO(n_i^2)=O(n)$ ，随机化构建的期望时间为 $O(n)$ 。

直觉

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

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

例子与边界

图中展示四个桶大小 $3,1,0,2$ ，共有六个键；若严格按上面的 $n=6$ 个一级桶构建，可以把另两个空桶省略不画。此时二级空间按 $9,1,0,4$ 分配。拥挤的三键桶获得九个候选槽，空桶不占二级表；查询仍只访问选中桶，而不是扫描这十四个槽。例如三键桶只有三对不同键，九个槽使失败概率至多 $3/9=1/3$ 。十四个二级槽小于接受阈值 $4n=24$ ，因此这一分桶可接受；单个算例的线性比例本身不是一般空间界的证明。

一般地，设一级同桶的无序键对数为 $C$ ，则 $\sum_i n_i^2=n+2C$ 。通用性给出 $\mathbb E[C]\le\binom n2/n$ ，所以 $\mathbb E[\sum_i n_i^2]<2n$ 。对这个非负随机总量使用Markov 不等式，超过 $4n$ 的概率小于 $1/2$ ，一级也只需期望常数次重试。一级限制总空间，二级分别消除桶内碰撞，两个步骤承担不同任务。

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, 3rd ed., MIT Press, 2009, §11.5：完美哈希。
James Aspnes, Yale University, Notes on Randomized Algorithms 配套在线讲义，HashTables §3: FKS Hashing，平方空间与碰撞对计数（在线版未署统一年份）。

形式陈述 ​

反向链接

形式陈述