深入理解完美哈希

作者：foxxiao，騰訊 WXG 後開開發工程師

本文對完美 Hash 的概念進行了梳理，通過 Hash 構建步驟來了解它是如何解決 Hash 衝突的，並比較了 Hash 表和完美 Hash 表。下面介紹常見的 Hash 與 Perfect Hash 函數及它們在不同場景的應用。

散列函數（英語：Hash function）又稱散列算法、哈希函數，是一種從任何一種數據中創建小的數字 “指紋” 的方法。散列函數把消息或數據壓縮成摘要，使得數據量變小，將數據的格式固定下來。該函數將數據打亂混合，重新創建一個叫做散列值（hash values，hash codes，hash sums，或 hashes）的指紋。散列值通常用一個短的隨機字母和數字組成的字符串來代表。

Hash 函數是一種將集合 S 轉換成具有固定長度的、不可逆的的集合 U 的單射，它的值一般爲數字合字母的組合，Hash 函數擁有無限的輸入空間，卻只有有限的輸出空間，這意味着 Hash 函數一定會產生碰撞，一個好的 Hash 函數可以顯著的降低碰撞概率。Hash 函數一般有一下特徵：

1. 一致性。Hash 函數可以接受任意大小的數據，並輸出固定長度的散列值，同時輸出不同值的概率應該儘可能一致。如 CityHash128，不管原始數據有多大，計算得到的 hash 值總是 128 bit。

2. 雪崩效應。原始數據哪怕只有一個字節的修改，得到的 hash 值都會發生巨大的變化。

3. 單向。只能從原始數據計算得到 hash 值，不能從 hash 值計算得到原始數據。所以散列算法不是加密解密算法，加密解密是可逆的，散列算法是不可逆的。

4. 避免衝突。幾乎不可能找到一個數據和當前計算的這個數據計算出一樣的 hash 值，因此散列函數能夠確保數據的唯一性。在 Hash 函數保證不同值出現的概率一致的情況下，CityHash128 出現碰撞的概率只有 2 ^ -128。因爲不同 Key 的碰撞概率很小，所以在某些情況下我們可以直接使用較短的 Hash 值代替較長原始數據存儲。

Hash 函數

常見的 Hash 函數有：

• CRC32：CRC32 能夠快速的生成 32 位 Hash 值，一般在數據庫系統或數據傳輸中出現，用於快速校驗數據是否完整；

• SipHash：SipHash 並不是爲了速度設計的，與其他 Hash 函數相比速度上不佔優勢，而提供了 HashDoS 保護，是 Rust 中的 Hash 函數的默認實現，最新 Redis 中也在使用 SipHash；

• MurMurHash：經典快速的 Hash 函數，目前最新的版本是 MurMurHash3，可以生成 32 位或者 128 位 Hash 值；

• CityHash：來自於 Google 實現，受到 MurmurHash 啓發，但是比 MurmurHash 更快，可以輸出 64 位、128 位或者 256 位 Hash 值。ClickHouse 內置；

• xxHash：針對小數據集速度非常快，支持輸出 32 位、64 位、128 位 Hash 值，Github 開源，SSE 支持。ClickHouse 內置。

xxHash 的 benchmark，統計了常用 Hash 函數的性能：

常見用法：

Hash 表：通過 Hash 算法將 Key 均勻映射到不同的位置上，訪問單個 key 時可以達到 O(1) 的平均時間複雜度，加快訪問速度。

安全 Hash 函數

安全 Hash 函數（或者叫加密 Hash 函數）是一種優秀的 Hash 函數，無法（或者很難）通過 Hash 值猜測出 Key，更精確的說，安全 Hash 必須滿足抗碰撞和不可逆兩個條件：無法通過 Hash 值的統計學方法逆向，以及無法通過算法層逆向。常見的安全 Hash 算法包括：

• SHA2，SHA3 系列

• BLAKE 系列

SHA0、SHA1、MD5 算法已經被認爲是不安全的，存在已知的漏洞，不要使用這些不安全的 Hash 函數來簽名。

常見用法：

安全 Hash 函數廣泛應用於數字簽名技術中：對原文進行 Hash 後，將 Hash 結果通過私鑰簽名，避免原文被泄露或者被修改；工作量證明：如加密貨幣中挖礦就是通過給定值，計算符合條件的 Hash 輸入；文件 ID：在網站下載地址旁往往提供了文件的 MD5 或者 SHA-1，確保下載的文件完整且沒有被調包。

HashDoS 與全域 Hash（universal hash）

全域 Hash 解決的是確定性 Hash 算法無法應對特殊輸入的問題。在鏈式 HashMap 裏，假設 m = bucket size，考慮我們有輸入集合 S 和 Hash 函數 H，其中 H = H’ % m，攻擊者在知道 Hash 函數的情況下，容易構造集合 S 使得集合中每一個元素的 Hash 值相同，那 HashMap 會退化成鏈表。最壞情況下，HashMap 查找的時間複雜度變成了 O(n)，插入 n 個元素時需要 O(n2) 的時間複雜度，所以也叫 HashDoS 攻擊。

全域 Hash 解決的問題是：對於精心構造的輸入，衝突率仍然在 1 / m。一個簡單的想法是隨機選一個 Hash 函數，不是在每一次操作時選一個，而是在輸入前選一個 Hash 函數，之後所有的操作都基於該 Hash 函數。

當然 H 也不是隨便定義的，具體來說是在 |H| 個 Hash 函數 H 中隨機的選擇一個 Hash 函數作爲所有 key 的 Hash 函數，H 中所有的 Hash 函數 H’ 對於不相等的關鍵詞 x 和 y，使得 H’(x) 和 H’(y) 值相等的函數 H’ 的數量個數等於 |H| / m，此時衝突概率爲 1/m。

完美 Hash 函數

傳統的 Hashmap 總會有分支預測開銷與內存對比，最差時間複雜度是 O(n)，有那麼一種 Hash 函數：完美 Hash 函數（ Perfect Hash Function，PHF），它可以在最壞情況下取得 O(1) 的時間複雜度。當然魚和熊掌不可兼得，完美 Hash 要求有一個靜態的輸入集合，查找的 Key 必須存在於靜態輸入集合中，導致使用場景受限。它有幾個特點：

1. 完美 Hash 大部分都要求輸入 Key 的集合是已知的，用於提前構建數據結構；

2. 構造算法複雜，大部分情況下需要比較大的內存，特別是時間複雜度高，需要很長的時間建立索引，構建海量 key 的完美 Hash 可能會失敗；

3. 完美 Hash 在實現上並不是只有一個 Hash 函數，而是多個普通 Hash 函數與數據結構算法上的組合，這意味着需要額外空間存儲 Hash 衝突信息。

儘管它有一些缺點，但是在一些場景如漢字拼音映射，詞典，以及程序中預定義的映射關係都有它的應用。

Perfect Hash Function 對於給定的集合 S，可以將 S 中所有的 Key 映射到整數 [0, m) 中，其中 m >= |S|。當 m = |S| 時，稱爲最小完美 Hash 函數（Minimal Perfect Hash Function, MPHF）。即作爲一個特例，如果完美 Hash 可以將 N 個 key 映射到 0 到 N-1 的整數，那它可以被稱爲最小完美 Hash 函數。

更進一步，如果 Hash 後給出 key 的順序沒有發生變化，稱爲完美 Hash 函數是保序的。如果一個 Hash 函數在給定區域不超過 t 次衝突，那這個 Hash 函數稱爲 t - 完美 Hash 函數。

目前開源的 Perfect Hash 庫有：

• cmph：C/C++，集合了大部分知名完美 Hash 算法的庫，針對不同的數據集合有推薦不同的算法，參數可調，文檔不多，LGPL 協議

• gperf：C/C++，專門針對於小數據集完美 Hash 的生成庫，GPL 協議；

• rust-phf：使用 CHD 算法生成完美 Hash，使用簡單，10 w 個 key 只需 0.4s 就能生成。

下文會討論 FCH，CHD，PTHASH 是如何巧妙解決了 Hash 衝突並實現了最差 O(1) 時間複雜度的。

完美 Hash 首先需要離線構造得到 Hash 衝突的信息離線保存下來，需要查詢時，利用先前生成的信息計算得到唯一的整數 Hash value。

在描述算法之前，先假設：

對於已知大小 n = |S| 的輸入集合 S，已知的負載因子 alpha 和參數 c，table 的數量 table_size = n * alpha，桶的數量 m = cn / (log2 n + 1)。一般來說，c 在 2-8 左右，確保每個桶有合適數量的 key，同時不會空出太多的桶。最終所有的 key 會映射到 [0, table_size) 中的 整數。當 alpha = 1，table_size = n，爲 MPHF。

FCH

A Faster Algorithm for Constructing Minimal Perfect Hash Functions 由 Fox, Chen, Heath 發明的一種生成完美 Hash 的算法，FCH 是一個相當經典的 Perfect Hash 的實現，後續多種算法均受到 FCH 算法的啓發。

FCH 是一種基於二級 Hash 表的完美 Hash 函數：

將數據通過一級 Hash 映射到 T 空間中，然後衝突的數據隨機選取新的哈希函數映射到 S 空間中，且 S 空間的大小 m 是衝突數據的平方（例如 T2 中有三個數字產生衝突，則映射到 m 爲 9 的 S2 空間中，m 即爲避免桶內 Hash 衝突的參數），此時可以容易找到避免碰撞的哈希函數（這個避免衝突的過程稱爲 position 或者 displace）。最差情況下所需存儲空間爲 O(n2)，但只要適當選擇哈希函數減少一級哈希時的碰撞，則可以使預期存儲空間爲 O(n)。

構造 FCH 需要分爲三個步驟：

1. Mapping

Mapping 階段爲了將 60% 的 key 分佈到 30 % 的桶裏，將 n 個 key 分爲 S1 和 S2 兩個集合，其中 S1 稱爲 dense set，key 的數量大概保持在 0.6 * n，S2 爲 sparse set，key 的數量大概在 0.4 * n 左右。同時，把所有桶分爲兩個部分 B1 和 B2，B1 數量 p2 = 0.3 * m，稱爲 dense buckets，B2 數量 0.7 * m，稱爲 sparse bucket。使用普通的 Hash 函數如 Cityhash/MurmurHash，將 S1 通過 H1 映射到 B1 中，同樣道理將 S2 通過 H2 映射到 B2 中。

用數學語言描述：

2. Ordering

Ordering 階段將所有的桶按照桶內衝突的數量排序，衝突數量最多的桶放在最前面。

3. Searching

Searching 階段會依次處理每個桶裏的衝突，嘗試將不重複的 Hash 值分配給每一個 key。經過了上一個階段排序，該階段會優先處理衝突最多的桶。對於每一個桶，嘗試參數 di, bi，給桶內每一個 key 分配 Hash 值 position(x, di, bi) = (h(x, s2 + b1) + di) mod table_size，這個值在 [0, table_size) 之間，其中 s2 是全局隨機種子，bi 是單個 bit，di 是一個從 0 開始的遞增的整數，如果 Hash 值在桶內和之前計算過的 Hash 值衝突，則改變 bi 或者 di 直到 Hash 值不發生衝突（爲了加速 di 的尋找，原始論文中提出了輔助數據結構和壓縮方法，感興趣可以參考論文）。

處理完衝突後，最終可以得到 m 個參數 bi，di 存入 P 數組中，只佔用大概 m * ((log2 n) + 1) = cn bit （這只是理論上的結果，如何存儲 bi 和 di 不在我們討論範圍內），即每一個 key 只佔用了 c 個 bit。

查詢時：對於給定的 key，計算一級 Hash，得到桶編號，通過該桶的 bi，di 和全局 s2 參數來計算二級哈希，即完成了一次查找，可以發現，任何 key 的查詢步驟都時相同的，沒有循環，即所有步驟都是確定的 O(1)。注意到這裏無法判斷 key 是否存在。

在 FCH 中，c 越大，構造越快，但是空間利用率越低，特別是 FCH 尋找 MPHF 需要耗費巨量的時間：c = 3 時，1 億 uint64 的數據需要花費 1 小時以上生成，所以它並不是一個實用的算法。

CHD

爲了解決 FCH 構建過慢的問題，出現了基於 FCH 思想的 CHD，一種實現簡單的 Perfect Hash 算法，支持 MPHF，空間利用率更高，但 lookup 更慢。

主要不同地方：使用通用 Hash 函數計算出爲每一個 key 計算出三個 Hash 值：h, h0, h1，h 用來表示桶號，h0、h1 用來計算最終的 position，position 定義爲 position = (h0 + (h1 * d1) + d0) mod table_size。

與 FCH 相同，CHD 一共分爲三個階段：

1. Mapping

Mapping 階段不需要像 FCH 拆分兩個集合，而是直接映射到一個集合中。

使用 c++ 來描述：

buckets.resize(m);
for (auto key : keys) {
  auto [h, h0, h1] = hash(key);
  buckets[h].hash = h;
  buckets[h].keys.push_back(make_tuple(h0, h1));
}

2. Ordering

與 FCH 相同。

sort(buckets.begin(), buckets.end(), [](auto &lhs, auto &rhs){
  return lhs.keys.size() > rhs.keys.size();
});

3. Searching （也叫 displace）

Searching 階段同樣是處理每個桶裏的衝突，不同的是 position 函數發生了變化：爲每一個桶初始化一個 pilot，其中 pilot = d0 * table_size + d1，使用 position 公式計算 key 的 Hash 值，發生衝突時，pilot 加上一（相當與 d1 加上 1，此時 position 的結果會發生較大的變化）重新計算 position 直到桶裏所有 key 都不發生衝突。

bool_vector position_used, position_used_in_bucket;
vector<uint32> p; // 結果數組

position_used.resize(table_size);
position_used_in_bucket.resize(buckets[0].keys.size());
p.resize(m);

for (auto &bucket : buckets) {
  if (bucket.keys.size() == 0) continue;
  // 單個桶 pilot = d0 * table_size + d1
  int d0 = 0;
  int d1 = 0;
  while(true) {
    bool ok = true;
    position_used_in_bucket.clear();

    for (auto [h0, h1] : bucket.keys) {
      uint64 position = (h0 + (h1 * d1) + d0) % table_size;
      if (position_used[position]) {
        // hash 結果衝突，換一個 pilot
        ok = false;
        break;
      }
      if (position_used_in_bucket[position]) {
        // 桶內 hash 結果衝突，換一個 pilot
        ok = false;
        break;
      }
      position_used_in_bucket[position] = true;
    }

    if (ok) {
      // 單個桶處理完畢
      position_used.union(position_used_in_bucket);
      // pilot 存到 p 數組中
      p[bucket.h] = d0 * table_size + d1;
      break;
    }
    d1++;
    if (d1 >= table_size) {
      d1 = 0;
      d0++;
      if (d0 > table_size) {
        // 構建失敗，找不到一個可用的 pilot
        throw ...
      }
    }
  }
}

最終得到的 m 個 pilot 存入 P 數組中。

查詢時：對於給定的 key，使用固定出的 Hash 函數計算出 h, h0, h1，根據 P[h] 得到 pilot 與 d0, d1，使用 poisition 易求得 Hash 值，即完成了一次查找（至少 4 次除法 or 求餘操作，h < m）

auto [h, h0, h1] = hash(key);
auto pilot = p[h];
auto d0 = pilot / table_size;
auto d1 = pilot % table_size;
return (h0 + (h1 * d1) + d0) % table_size;

結果集 P 中，pilot 往往很小，有壓縮空間，在作者的論文中，爲了壓縮 P 數組的大小，採用 FN Encoding，可以壓縮到 2.08 bit/key 的開銷，自己的實現可以直接用 bit vector（aka compact） 壓縮，實現起來更簡單。

compact 壓縮：給定一系列整數 S，已知 S 中最大的整數 x 需要使用 y 個 bit 表示，我們可以將所有的整數都通過固定 y bit 來表示而不犧牲精度和訪問時間。

CHD 算法比較簡單，Github 上也有不同語言的實現， rust 語言的實現。Go 語言實現。

PTHash

雖然 CHD 實現簡單，但其中包含了大量除法求餘計算，Encoding 後效率並不高，lookup 耗時過久。最近有一篇文章提出了 PTHash 方法，在 FCH 上改進了構建時間，並提高了空間利用率，作者還提供了源代碼供參考。

設計思路和 FCH 相似，只不過 position 定義變成了 position(x, pilot) = (h(x, s) xor h(pilot, s)) mod table_size，其中 h 是普通 Hash 函數，x 是 key，s 是全局種子。與 FCH 相比可以提前計算所有 key 的 Hash h(x, s)，節約構造時間 。使用 compact 壓縮方式效果很好，lookup 耗時也能達到 FCH 水平。

1. Mapping

與 FCH 相同

2. Ordering

與 FCH 相同

3. Searching

使用新的公式計算 position，得到 n 個 pilot，由 position 公式定義，可以發現大部分 pilot 都是比較小的值，作者還介紹了一種 Front-Back Encoding，將結果集前 30% 拆分成 front 集，後 (1- 30%) 拆分爲 back 集，代價是運行時多一次分支判斷。

由於 front 集合裏的桶是最先處理衝突的，衝突發生次數低，大部分 pilot 都比 back 集合內的要小，壓縮率更高。將 Front 和 Back 集合裏的 pilot 通過 Compact 編碼後，稱爲 Compact-Compact Encoding。

查詢時，按照 bucket id 確定去 front 還是 back 集合查詢 pilot，不考慮解壓過程，只需要兩次除法 or 求餘操作。

當然這裏也可以犧牲部分空間，不做 Front-Back Encoding 以取得更快的查詢速度，根據不同的 Encoding 方式，可以在時間 & 空間上取得平衡：

benchmark：

HashMap

HashMap 本質上是根據給定的 key 獲得 value 的地址。設計核心主要在於：

1. HashMap 的空間開銷：key 和 value 如何組織？單個 key 需要多少額外空間存儲元信息？

2. HashMap 的查詢與插入：如何通過 key 計算出 value 的地址？衝突如何處理？

3. 不同的 HashMap 不同點在於衝突如何處理，除了常規可讀可寫的 HashMap，存在只讀 HashMap，存儲更小，性能更優。

常規 HashMap

在各個語言都有內置的 HashMap 實現，除了使用不同的 Hash 函數，不同實現對 Hash 衝突的解決方案也不同：

• 拉鍊法：每一個桶都存着鏈表的 head 節點，衝突 key 將會被插入鏈表；

• 升級紅黑樹：Java8 在鏈表長度超過 8 時轉換成紅黑樹；

• 線性探測法：發現衝突時向後找到第一個沒有佔用的桶存儲，緩存命中率高，負載因子越高，插入效率越低；

• 多級 Hash 法：單次 Hash 結果衝突時，換一個 Hash 函數直到 Hash 值無衝突。

F14 & B16 系列 HashMap

F14 & B16 是一種利用 SIMD 技術進行查找的鏈式 HashMap，它爲每一個 Key 計算兩個 Hash 值：H1 和 H2，H1 決定 Key 放在哪一個桶裏，H2 用來處理桶內衝突，一般要求負載因子比較高，以獲得較高的空間利用率。同時對桶內的 H2 通過 SIMD 指令對比，一次對比 14 個 key 或者 16 個 key，相比 PerfectHashMap，它可以支持動態插入，但是查找性能不如 PerfectHashMap。

PerfectHashMap

有沒有辦法把 Prefect Hash 利用起來做 HashMap？由於 Perfect Hash 已經映射到 [0, table_size) 內的整數，完全不需要考慮 key 的衝突處理，所以想用起來比較簡單：

• 當 hashmap 的 value 定長時，我們可以直接通過 Hash 值（Index）計算出 value 的 offset，無需使用任何額外空間。

• 當 hashmap 的 value 不定長時，引入一層 relocation，存儲每一個 Hash 值對應 value 的 offset，由於 Hash 值是從 0 遞增的，因此 offset 也是遞增的，可以通過一定方法去壓縮 value offset。

完美 Hash 要求查詢的 key 需要存在於輸入集內，其他 HashMap 沒有這麼苛刻的要求，如果使用一個不在輸入集中的 key 會怎麼樣呢？從 CHD 算法的 lookup 過程來分析，輸入未知 key 時可以認爲返回一個隨機的 Index，如果我們需要確認 key 是否存在 HashMap 裏，需要將原始 key 存下來放在 Index 對應的 Value 中，查詢到 Index 後再對比一次才能確認 key 是否存在。

PerfectHashMap 一般用法是先離線生成 map 信息，再讀到 buffer 裏，或者像 rust-phf 一樣編譯時內置到二進制，直接讀 P 數組，如果 HashMap 特別大，還可以通過 mmap 只讀方式載入到內存中。

Benchmark

測試設備：MacBookPro m1 Pro 32G，MacOS 12.4，clang 13.1.6。

比較對象：

• unordered_map：標準庫自帶的 HashMap，鏈式實現；

• Folly F14：Facebook HashMap 實現，使用 SIMD 優化查詢過程；

• abseil swiss table：Google HashMap 實現，爲速度優化，包括使用額外指針的 node_hash_map，與原地存儲適合小 value 的 flat_hash_map；

• PTHashMap：PTHash + Value offset 映射，（內部使用 CityHash128），c = 7, alpha = 0.98，Compact-Compact Encoding，Value offset 使用 MILC 壓縮。不存儲 key；

• PTHashMap3：與 PTHashMap 參數不同：c = 3, alpha=0.99；

• PTHashMap10：與 PTHashMap 參數不同：c = 10, alpha=0.94。

string

測試場景：輸入 100w 隨機不重複不定長字符串（平均長度 8 bytes）作爲 key，value 與 key 相同。全部隨機 lookup 一遍。

meta data 排除了 key 和 Value 之後統計佔用內存大小，folly 使用 computeStats() 統計內存數據；total memory 值插入所有 key 後使用 gpertools 統計佔用內存大小，包含 key 和 value 部分；注意 PTHashMap meta data 統計單位是 bit。

uint64

測試場景：輸入 100w 隨機不重複 uint64 數字作爲 key，value 與 key 相同，全部隨機 lookup 一遍。

由於該場景數據是長度固定，PTHashMap 去掉了 Value offset 映射表。

結論

完美 Hash 的概念擴展了 Hash 的使用場景，最近出現的新型完美 Hash 算法在運行速度 & 構建速度上取得了較大的進步，針對海量只讀場景使用完美 HashMap 不僅可以提升速度，同時能夠節省大量內存佔用。

參考文章

1. 什麼是哈希算法？

2. 安全 Hash

3. MurmurHash wiki

4. 哈希表和完美哈希

5. 全域哈希是什麼意思

6. 完美 Hash 技術調研

7. 倒排索引壓縮技術在 58 搜索的實踐

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/M8Wcj8sZ7UF1CMr887Puog