最近看到一篇有关 Perfect Hash 生成算法的文章，感觉很有必要写篇文章推荐下：http://ilan.schnell-web.net/p…。
先解释下什么是 Perfect Hash：Perfect Hash 是这样一种算法，可以映射给定 N 个 keys 到 N 个不同的的数字里。由于没有 hash collision，这种 Hash 在查找时时间复杂度是真正的 O(1)。外加一个“最小”前缀，则是要求生成的 Perfect Hash 映射结果的上界尽可能小。举个例子，假设我有 100 个字符串，如果存在这样的最小 Perfect Hash 算法，可以把 100 个字符串一一映射到 0 ～99 个数里，我就能用一个数组存储全部的字符串，然后在查找时先 hash 一下，取 hash 结果作为下标便可知道给定字符串是否在这 100 个字符串里。总时间复杂度为 O(n) 的 hash 过程 + O(1) 的查找，而所占用的空间只是一个数组（外加一个图 G，后面会讲到）。
听到前面的描述，你可能想到 trie（前缀树）和类似的 AC 自动机算法。不过讨论它们之间的优劣和应用场景不是本文的主题（也许以后我有机会可以写一下）。本文的主题在于介绍一种生成最小 Perfect Hash 算法。
这种算法出自于一篇 1992 年的论文《An optimal algorithm for generating minimal perfect hash functions》。算法的关键在于把判断某个 hash 算法是否为 perfect hash 算法的问题变成一个判断图是否无环的问题。注意该算法最终生成的图 G 在不同的运行次数里大小可能不一样，你可能需要多跑几次结果生成多个 G，取其中最小者。
以下就是算法的步骤：
假设你有 K 个 keys，比如 apple，boy，cat，dog。
给每个 keys 分配一个从零开始递增的 ID，比如
apple 0
boy 1
cat 2
dog 3
选择一个稍微比 K 大一点的数 N。比如 N = 6。
随机选择两个 hash 函数 f1(x) 和 f2(x)。这两个函数接收 key，返回 0 ～ N-1 中的一个数。比如
f1(x) = (x[0] + x[1] + x[2] + …) % N
f2(x) = (x[0] * x[1] * x[2] * …) % N
之所以随机选择 hash 函数，是为了让每次生成的图 G 不一样，好找到一个最小的。
以 f1(x) 和 f2(x) 的结果作为节点，连接每个 f1(key) 和 f2(key) 节点，我们可以得到一个图 G。这个图最多有 N 个节点，有 K 条边。
比如前面我们挑的函数里，f1(x) 和 f2(x) 的结果如下表：
key f1(x) f2(x)
apple 2 0
boy 0 0
cat 0 0
dog 2 0
生成的图是这样的：
2 — apple ——
| |
— dog ———0 — boy –
| |
— cat –
判断图 G 是否无环。我们可以随机选择一个节点进行涂色，然后遍历其相邻节点。如果某个节点被涂过色，说 明当前的图是有环的。显然上图就是有环的。
如果有环，增加 N，回到步骤 3。比如增加 N 为 7。
如果无环，则对每个节点赋值，确保同一条的两个节点的值的和为该边的 ID。（别忘了有多少个 key 就有多少条边，而每个 key 都在步骤 1 里面分配了个 ID）
沿用前面的例子，当 N 为 7 时，f1(x) 和 f2(x) 的结果如下表：
key f1(x) f2(x)
apple 5 0
boy 1 0
cat 4 3
dog 6 4
生成的图是这样的：
0 — apple — 5
|
—- boy — 1
4 — cat — 3
|
—- dog — 6
显然上图是无环的。接下来的工作，就是给各个节点赋值，确保同一条边两个节点的值的和为该边的 ID。即 0 号节点的值 + 5 号节点的值为 apple 的 ID 0。
我们可以每次选择一个没被赋值的节点，赋值为 0，然后遍历其相邻节点，确保这些节点和随机选择的节点的值的和为该边的 ID，直到所有节点都被赋值。这里我们假设随机选取了 5 号节点和 3 号节点，赋值后的图是这样的：
0(0) — apple — 5(0)
|
—- boy — 1(1)
4(2) — cat — 3(0)
|
—- dog — 6(1)
现在图 G 可以这么表示：
int G[7] = {
0, // 0 号节点值为 0
1,
0, // 2 号节点没有用到，可以取任意值
0,
2,
0,
1 // 6 号节点值为 1
}
最终得到的最小 Perfect Hash 算法如下：
P(x) = (G[f1(x)] + G[f2(x)]) % N
# N = 7
key f1(x) f2(x) G[f1(x)] G[f2(x)] P(x)
apple 5 0 0 0 0
boy 1 0 1 0 1
cat 4 3 2 0 2
dog 6 4 1 2 3
P(x) 返回的值正好是 key 的 ID，所以拿这个 ID 作为 keys 的 offset 就能取出对应的 key 了。
注意，如果输入 x 不一定是 keys 中的一个 key，则 P(x) 的算出来的 offset 取出来的 key 不一定匹配输入的 x。你需要匹配下 x 和 key 两个字符串。
关于图 G，有两点需要解释下：
如果步骤 3 中随机选取的 f1(x)，f2(x) 不同，则最终生成的 G 亦不同。实践表明，最终生成的 G 大小为 K 的 1.5 ～ 2 倍。你应该多次运行这个最小 Perfect Hash 生成算法，取其中生成的 G 最小的一次。
由于 G 是无环的，所以其用到的节点数至少为 K + 1 个。而 G 里面用到的节点数最多为 1.5K 到 2K。所以有一半以上的节点是有值的。这也是为什么可以用一个 G 数组来表示图 G 里面每个点对应的值。
这个算法背后的数学原理并不深奥。
如果你能找到这样的 P(key)，令 P(key) 的结果恰好等于 key 在 keys 里面的 offset，则 P(key) 必然是最小 Perfect Hash 算法。因为 keys[P(key)] 只能是 key，不可能会有两个结果；而且也找不到比比 keys 的个数更小的 Perfect Hash 了，再小下去必然会有 hash collision。
如果我们设计出这样的一个图 G，它有 K 条边，每条边对应一个 key，边的两端节点的和为该边（key）的 offset，则 P(x) 就是先算得两端节点的值，然后求和。两端节点的值可以通过随机选取一个节点为 0，然后给每个相邻节点赋值的方式决定，前提是这个图必须是无环的，否则一个节点就可能被赋予两个值。所以我们首先要检查生成出来的图 G 是否是无环的。
你可能会问，为什么生成出来的 P(x) 是 (G[f1(x)] + G[f2(x)]) % N，而不是 G[f1(x)] + G[f2(x)]？我看了原文里面的代码实现（就在本文开头所给的链接里），他在计算每个节点值时，不允许值为负数。比如节点 A 为 5，边的 ID 为 3，N 为 7，则另一端的节点 B 为 9（而不是 -2）。之所以这么做，是因为论文里面说 G(x) 是一个映射 x 到 [0,K] 的函数，然后 P(x) 里面需要 % K。而代码里则把 G(x) 实现成映射 x 到 [0,N] 的函数，顺理成章地后面就要 % N 了。
但其实如果我们允许值为负数，则 G[f1(x)] + G[f2(x)] 就能满足该算法背后的数学原理了。这么改的好处在于计算时可以省掉一个相对昂贵的取余操作。
我改动了下代码实现，改动后的结果也能通过所有的测试（我另外还添了个 fuzzy test），所以这么改应该没有问题。