最小完美哈希 | Codeboy's Blog

形式陈述

Perfect 与 Minimal

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

[n]=\{0,1,\ldots,n-1\},

则 $h|_S$ 必为双射，称 minimal perfect hash function（MPHF）。最小性说槽域没有空位，不表示函数描述已经达到最少 bit，也不要求 $h$ 在整个宇宙 $U$ 上单射。空集合应单独处理：成员查询直接报告不存在；若 $U$ 非空，就不存在全函数 $U\to[0]=\varnothing$ ，不能继续套用本节的全域求值接口。

与 FKS 完美哈希相比，MPHF 把 $n$ 个已知键压成连续编号，适合把外部值数组直接按编号排列。FKS 的二级表总空间虽为 $O(n)$ ，却通常含空槽，因此不一定 minimal。

四项成本必须分开

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

在常见静态随机化构造中，建表对随机种子取期望线性或近线性时间，成功后每次求值为最坏 $O(1)$ 个 word 操作；这里要求键可在常数个机器字内处理，或已经提供所需的常数时间哈希值。长字符串的首次读取和哈希成本应另外计入。若一次试验因图结构不合格而失败，必须换种子并重建；成功概率为常数才能把重试计入期望常数轮。

在足够大的键宇宙中，一族表示若要覆盖所有 $n$ 键子集，其最坏描述空间具有约 $n\log_2 e\approx1.4427n$ bit 的经典信息论下界尺度。这不是每个特定集合都需支付的费用：若宇宙本身只有 $n$ 个已编号键，恒等映射即可。具体构造还要支付寻址、秩结构和对齐开销。实践中的“每键若干 bit”必须说明是否含键、值、fingerprint 和构建工作区。

直觉

MPHF 利用键集预先固定这一条件，把冲突消除工作全部放到构建阶段，查询时只计算一个紧凑编号。值域恰为 $[n]$ 让外部值数组没有空槽，却也意味着任何非成员仍会落到某个合法编号；无冲突编号与 membership 是两种不同接口。

下图用普通图的边简示度一剥离和逆序处理；下面的三哈希构造则以三元超边建模，并在端点选择后增加 rank 编号步骤。

可剥离结构将键压栈并逆序分配连续编号，残余二核触发换种子重试 — 最小完美哈希的剥离赋值与重试

例子与边界

可追踪词典编号

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

h(\texttt{dog})=0,\quad h(\texttt{emu})=1,\quad h(\texttt{cat})=2.

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

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

Hypergraph Peeling 构造图像

一类构造令三个哈希函数分别映入三个不交的顶点区间，再用每键的三个随机位置建立超图：每个不同键保留为一条带身份的超边，辅助数组位置为顶点；相同候选集合的键仍是不同边。若能反复移除含度一顶点的边，就为每条边记下该自由顶点并压栈。逆序赋值时，利用尚未固定的自由变量，使三个辅助值之和模 $3$ 指向这条边选定的端点。

这一步先给 $n$ 个键选择互异的辅助顶点，顶点总数通常大于 $n$ 。再用位图 $B$ 标记被选顶点，并调用半开前缀 rank：选中顶点的零基位置为 $v$ 时，返回 $\operatorname{rank}_1(v)$ ，即它之前被选顶点的个数。这样恰把 $n$ 个选中顶点按位置压成 $[n]$ 中的连续编号，才得到最小完美哈希。只完成剥离赋值还没有消除空编号。对非成员，若计算得到的 rank 越出 $[n]$ ，可返回一个约定的合法兜底编号，以符合本页的全函数约定；是否属于键集仍需另外核验。

若剩下不可剥离的 core，当前随机种子失败并重试。赋值阶段的局部异或或模运算只是实现手段；正确性不变量是每个键在逆序处理时仍有一个未固定的自由变量；端点选择保证无冲突，后续 rank 才保证覆盖 $[n]$ 。

静态性与更新边界

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

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

推论与应用

MPHF 适合编译期词典、静态资源表和大规模键到稠密数组位置的映射，可把编号与关联值分开存储。需要精确拒绝非成员时还要保存键或无误核验信息；需要更新、顺序或前驱查询时则应选择不同结构。

参考资料

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，剥离、赋值与 rank 压缩。
Torben Hagerup and Torsten Tholey, “Efficient Minimal Perfect Hashing in Nearly Minimal Space,” STACS, 2001.

形式陈述 ​

Perfect 与 Minimal ​

四项成本必须分开 ​

可追踪词典编号 ​

Hypergraph Peeling 构造图像 ​