分享一種最小 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
。
- 給每個 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) 的結果如下表：
keyf1(x) f2(x) apple20 boy00 cat00 dog20
生成的圖是這樣的：
2 --- apple ------ || --- dog ---------0 -- boy - || --- cat -
-
判斷圖 G 是否無環。我們可以隨機選擇一個節點進行塗色，然後遍歷其相鄰節點。如果某個節點被塗過色，說
明當前的圖是有環的。顯然上圖就是有環的。 - 如果有環，增加 N，回到步驟 3。比如增加 N 為 7。
-
如果無環，則對每個節點賦值，確保同一條的兩個節點的值的和為該邊的 ID。
（別忘了有多少個 key 就有多少條邊，而每個 key 都在步驟 1 裡面分配了個 ID）
沿用前面的例子，當 N 為 7 時，f1(x) 和 f2(x) 的結果如下表：
keyf1(x) f2(x) apple50 boy10 cat43 dog64
生成的圖是這樣的：
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 keyf1(x) f2(x) G[f1(x)] G[f2(x)] P(x) apple50000 boy10101 cat43202 dog64123
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），所以這麼改應該沒有
問題。