最小完美哈希

Perfect 与 Minimal ​

给定静态有限键集 $S\subseteq U$，$n=|S|$。函数 $h:U\to [m]$ 若在 $S$ 上单射，就是 perfect hash；若值域恰为

$$[n]=\{0,1,\dots ,n-1\},$$

则 $h{|}_S$ 必为双射，称 minimal perfect hash function（MPHF）。最小性说槽域没有空位，不表示函数描述已经达到最少 bit，也不要求 $h$ 在整个宇宙 $U$ 上单射。

与 FKS 完美哈希公理库完美哈希Perfect hashing · FKS hashing对预先固定的静态键集消除查询碰撞，并以两层随机构造取得线性空间和最坏常数查询。相比，MPHF 把 $n$ 个已知键压成连续编号，适合把外部值数组直接按编号排列。FKS 的二级表总空间虽为 $O(n)$，却通常含空槽，因此不一定 minimal。

四项成本必须分开 ​

一个 MPHF 方案至少要报告：构建时间及失败重试；求值 $h(x)$ 的最坏或期望时间；函数描述占多少 bits per key；为了存关联值和验证 membership 还要多少空间。只写“查询 $O(1)$、空间 $O(n)$”会隐藏最重要的 bit 级差异。

在常见静态随机化构造中，建表对随机种子取期望线性或近线性时间，成功后每次求值为最坏 $O(1)$ 个 word 操作。若一次试验因图结构不合格而失败，必须换种子并重建；成功概率为常数才能把重试计入期望常数轮。

MPHF 描述存在约 $n{\log }_{2}e\approx 1.4427n$ bit 的经典信息论尺度；具体构造还要支付寻址、秩结构和对齐开销。实践中的“每键若干 bit”必须说明是否含键、值、fingerprint 和构建工作区。

可追踪词典编号 ​

设 $S=\{\mathtt{\text{cat}},\mathtt{\text{dog}},\mathtt{\text{emu}}\}$，某个 MPHF 给出

$$h(\mathtt{\text{dog}})=0,h(\mathtt{\text{emu}})=1,h(\mathtt{\text{cat}})=2.$$

关联值数组可按这三个位置连续存储，查 cat 时先算编号 $2$ 再取值。编号没有字典序语义；另一个合法 MPHF 可以给出完全不同排列。

对非成员 fox，函数仍会返回 $0,1,2$ 中某个数，因为 $h$ 定义在 $U$ 上。MPHF 本身无法回答“fox 不在集合中”。精确字典必须在槽中保存原键或可无误核对的外部表示；短 fingerprint 只能把误报概率降到指定水平。

Hypergraph Peeling 构造图像 ​

一类实用构造从数个随机哈希函数建立超图：键是超边，候选槽/辅助变量是顶点。若超图可逐步剥离度为一的顶点，就记录剥离栈，再按逆序给辅助数组赋值，使每条键边最终选择唯一编号。

若剩下不可剥离的 core，当前随机种子失败并重试。赋值阶段的局部异或或模运算只是实现手段；正确性不变量是每个键在逆序处理时仍有一个未被占用的自由变量，最终 $h{|}_S$ 无冲突且覆盖 $[n]$。

静态性与更新边界 ​

插入新键会破坏双射：已有 $n$ 个键已经占满 $[n]$，值域也必须增长。删除则留下空编号，不再 minimal。小批量更新可以用增量层或定期重建包装，但那是另一套动态接口与摊还分析。

MPHF 也不支持范围查询、前驱或排序；连续编号只是空间定位。若需要保持键序，应使用有序字典或显式 rank 映射，不能把任意哈希编号当作秩。

参考资料

• 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.
• Fabiano C. Botelho, Rasmus Pagh, and Nivio Ziviani, “Simple and Space-Efficient Minimal Perfect Hash Functions,” WADS, 2007.
• Torben Hagerup and Torsten Tholey, “Efficient Minimal Perfect Hashing in Nearly Minimal Space,” STACS, 2001.