分享一种最小 Perfect Hash 生成算法

最近看到一篇有关 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。

1. 给每个 keys 分配一个从零开始递增的 ID，比如

apple 0
boy 1
cat 2
dog 3

1. 选择一个稍微比 K 大一点的数 N。比如 N = 6。
2. 随机选择两个 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 不一样，好找到一个最小的。

1. 以 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 -

1. 判断图 G 是否无环。我们可以随机选择一个节点进行涂色，然后遍历其相邻节点。如果某个节点被涂过色，说
   明当前的图是有环的。显然上图就是有环的。
2. 如果有环，增加 N，回到步骤 3。比如增加 N 为 7。
3. 如果无环，则对每个节点赋值，确保同一条的两个节点的值的和为该边的 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，有两点需要解释下：

1. 如果步骤 3 中随机选取的 f1(x)，f2(x) 不同，则最终生成的 G 亦不同。实践表明，最终生成的 G 大小为 K
   的 1.5 ～ 2 倍。你应该多次运行这个最小 Perfect Hash 生成算法，取其中生成的 G 最小的一次。
2. 由于 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），所以这么改应该没有
问题。