導讀：本文從哈希表傳統(tǒng)設計與解決思路入手，深入淺出地引出新的設計思路：從盡量規(guī)避哈希沖突，轉向了利?合適的哈希沖突概率來優(yōu)化計算和存儲效率。新的哈希表設計表明 SIMD 指令的并?化處理能?的有效應?能?幅度提升哈希表對哈希沖突的容忍能?，進?提升查詢的速度，并且能幫助哈希表進?極致的存儲空間壓縮。

1 背景

哈希表是?種查找性能?常優(yōu)異的數(shù)據(jù)結構，它在計算機系統(tǒng)中存在著?泛的應?。盡管哈希表理論上 的查找時間復雜度是 O（1），但不同的哈希表在實現(xiàn)上仍然存在巨?的性能差異，因??程師們對更優(yōu)秀 哈希數(shù)據(jù)結構的探索也從未停?。

1.1 哈希表設計的核?

從計算機理論上來說，哈希表就是?個可以通過哈希函數(shù)將 Key 映射到 Value 存儲位置的數(shù)據(jù)結構。那么哈希表設計的核?就是兩點：

1. 怎樣提升將Key映射到Value存儲位置的效率？

2. 怎樣降低存儲數(shù)據(jù)結構的空間開銷？

由于存儲空間開銷也是設計時的?個核?控制點，在受限于有限的空間情況下，哈希函數(shù)的映射算法就存在著?常?的概率將不同的 Key 映射到同?個存儲位置，也就是哈希沖突。?部分哈希表設計的區(qū)別，就在于它如何處理哈希沖突。

當遇到哈希沖突時，有?種常?的解決?案：開放尋址法、拉鏈法、?次哈希法。但是下?我們介紹兩種有趣的、不常?的解決思路，并且引出?個我們新的實現(xiàn)?案——B16 哈希表。

2 規(guī)避哈希沖突

傳統(tǒng)哈希表對哈希沖突的處理會增加額外的分?跳轉和內(nèi)存訪問，這會讓流?線式的CPU指令處理效率變差。那么肯定就有?考慮，怎么能完全規(guī)避哈希沖突？所以就有了這樣?種函數(shù)，那就是完美哈希函數(shù)（perfect hash function）。

完美哈希函數(shù)可以將?個 Key 集合?沖突地映射到?個整數(shù)集合中。如果這個?標整數(shù)集合的??與輸?集合相同，那么它可以被稱為最?完美哈希函數(shù)。

完美哈希函數(shù)的設計往往?常精巧。例如CMPH（http://cmph.sourceforge.net/）函數(shù)庫提供的 CDZ 完美哈希函數(shù)，利?了數(shù)學上的?環(huán)隨機 3-部超圖概念。CDZ通過 3 個不同的 Hash 函數(shù)將每個 Key 隨機映射到3-部超圖的?個超邊，如果該超圖通過?環(huán)檢測，再將每個 Key 映射到超圖的?個頂點上，然后通過?個精?設計的與超圖頂點數(shù)相同的輔助數(shù)組取得 Key 最終對應的存儲下標。

完美哈希函數(shù)聽起來很優(yōu)雅，但事實上也有著實?性上的?些缺陷：

完美哈希函數(shù)往往僅能作?在限定集合上，即所有可能的 Key 都屬于?個超集，它?法處理沒?過的 Key；

完美哈希函數(shù)的構造有?定的復雜度，?且存在失敗的概率；

完美哈希函數(shù)與密碼學上的哈希函數(shù)不同，它往往不是?個簡單的數(shù)學函數(shù)，?是數(shù)據(jù)結構+算法組成的?個功能函數(shù)，它也有存儲空間開銷、訪問開銷和額外的分?跳轉開銷；

但是在指定的場景下，例如只讀的場景、集合確定的場景（例如：漢字集合），完美哈希函數(shù)可能會取得?常好的表現(xiàn)。

3 利?哈希沖突

即便不使?完美哈希函數(shù)，很多哈希表也會刻意控制哈希沖突的概率。最簡單的辦法是通過控制 Load Factor 控制哈希表的空間開銷，使哈希表的桶數(shù)組保留?夠的空洞以容納新增的 Key。Load Factor 像是控制哈希表效率的?個超參數(shù)，?般來說，Load Factor 越?，空間浪費越?，哈希表性能也越好。

但近年來?些新技術的出現(xiàn)讓我們看到了解決哈希沖突的另?種可能，那就是充分利?哈希沖突。

3.1 SIMD 指令

SIMD 是單指令多數(shù)據(jù)流（Single Instruction Multiple Data）的縮寫。這類指令可以使??條指令操作多個數(shù)據(jù)，例如這些年?常?的 GPU，就是通過超?規(guī)模的 SIMD 計算引擎實現(xiàn)對神經(jīng)?絡計算的加速。

?前的主流 CPU 處理器已經(jīng)有了豐富的 SIMD 指令集?持。例如?家可接觸到的 X86 CPU ?部分都已經(jīng)?持了 SSE4.2 和 AVX 指令集，ARM CPU 也有 Neon 指令集。但科學計算以外的?部分應?程序，對 SIMD指令的應?還都不太充分。

3.2 F14 哈希表

Facebook 在 Folly 庫中開源的 F14 哈希表有個?常精巧的設計，那就是將 Key 映射到塊，然后在塊?使? SIMD 指令進??效過濾。因為分塊的數(shù)量?傳統(tǒng)的分桶要更?，這相當于?為增加了哈希沖突，然后在塊中? SIMD 指令再解決沖突。

具體的做法是這樣的：

通過哈希函數(shù)對 Key 計算出兩個哈希碼：H1 和 H2 ， 其中 H1 ?來確定 Key 映射到的塊，H2 只有 8 bits，?來在塊內(nèi)進?過濾；

每個塊?最多存放 14 個元素，塊頭有 16 個字節(jié)。塊頭的前 14 個字節(jié)，存放的是 14 個元素對應的 H2 ，第 15 字節(jié)是控制字節(jié)，主要記錄該塊?有多少個元素是從上?個塊溢出的，第 16 字節(jié)是越界計數(shù)器，主要記錄如果該塊空間?夠?，應該會被放置多少個元素。

在插?時，當 Key 映射到的塊中 14 個位置還有空時，就直接插?；當塊已經(jīng)滿時，就增加越界計數(shù)器，嘗試插?下?個塊中；

在查詢時，通過待查找 Key 計算得到 H1 和 H2 。通過 H1 對塊數(shù)取模確定其所屬的塊后，?先讀取塊頭，通過 SIMD 指令并??較 H2 與 14 個元素的 H2s 是否相同。如果有相同的 H2 ，那么再?對 Key 是否相同以確定最終結果；否則根據(jù)塊頭的第 16 字節(jié)判斷是否還需要?對下?個塊。

F14 為了充分利? SIMD 指令的并?度，在塊內(nèi)使?了 H2 這種 8 bits 的哈希值。因為?個 128 bits 寬度的 SIMD 指令可以進?最多 16 個 8 bits 整數(shù)的并??較。雖然 8 bits 哈希值的理論沖突概率 1/256 并不低，但也相當于有 255/256 的可能性省去了逐個 Key 對?的開銷，使哈希表能夠容忍更?的沖突概率。

4 B16 哈希表

不考慮分塊內(nèi)部的設計，F(xiàn)14 本質(zhì)上是?個開放尋址的哈希表。每個塊頭的第 15、16 字節(jié)被?于開放尋址的控制策略，只剩 14 個字節(jié)留給哈希碼，也因?被命名為 F14。

那么我們考慮能不能從另?個?度出發(fā)，使?拉鏈法來組織分塊。由于省去了控制信息，每個分塊中可以放置 16 個元素，我們把它命名為 B16。

4.1 B16 哈希數(shù)據(jù)結構

△B16 哈希表數(shù)據(jù)結構（3元素示例）

上圖所示就是?每個分塊 3 個元素展示的 B16 哈希表的數(shù)據(jù)結構。中間綠?的是常?的 BUCKET 數(shù)組，存放的是每個分桶中 CHUNK 拉鏈的頭指針。右側的每個 CHUNK 與 F14 相?，少了控制字節(jié)，多了指向下?個 CHUNK 的 next 指針。

B16 也是通過哈希函數(shù)對 Key 計算出兩個哈希碼：H1 和 H2 。例如 “Lemon” 的兩個哈希碼是 0x24EB 和0x24，使? H1 的?位作為 H2 ?般來說?夠了。

在插?時，通過 H1 對桶??取模計算 Key 所在的分桶，例如 “Lemon” 所在的分桶是 0x24EB mod 3 =1。然后在 1 號分桶的分塊拉鏈中找到第?個空位，將 Key 對應的 H2 和元素寫?該分塊。當分塊拉鏈不存在，或者已經(jīng)裝滿時，為拉鏈創(chuàng)建?個新的分塊?于裝載插?的元素。

在查找時，先通過 H1 找到對應的分桶拉鏈，然后對每個塊進?基于 SIMD 指令的 H2 對?。將每個塊的塊頭 16 字節(jié)加載到 128 bits 寄存器中，??包含了 16 個 H2‘ ，把 H2 也重復展開到 128 bits 寄存器中，通過 SIMD 指令進? 16 路同時?對。如果都不同，那就對?下?個塊；如果存在相同的 H2 ，就繼續(xù)對?對應元素的 Key 是否與查找的 Key 相同。直到遍歷完整條拉鏈，或者找到對應的元素。

在刪除時，?先查找到對應的元素，然后?塊拉鏈最尾部的元素覆蓋掉對應的元素即可。

當然，B16 哈希表每個塊的元素個數(shù)可以根據(jù) SIMD 指令的寬度進?靈活調(diào)整，例如使? 256 bits 寬度指令可以選擇 32 元素的塊??。但影響哈希表性能的不僅僅是查找算法，內(nèi)存訪問的速度和連續(xù)性也?常重要?？刂茐K??在 16 以內(nèi)在?多數(shù)情況下能充分利? x86 CPU 的 cache line，是?個較優(yōu)的選擇。

普通的拉鏈式哈希表，拉鏈的每個節(jié)點都只有?個元素。B16 這種分塊式拉鏈法，每個節(jié)點包含 16 個元素，這會造成很多空洞。為了使空洞盡可能的少，我們就必須增加哈希沖突的概率，也就是盡量地縮?BUCKET 數(shù)組的??。我們經(jīng)過試驗發(fā)現(xiàn)，當 Load Factor 在 11-13 之間時，B16 的整體性能表現(xiàn)最好。其實這也相當于把原來存在于 BUCKET 數(shù)組中的空洞，轉移到了 CHUNK 拉鏈中，還省去了普通拉鏈式每個節(jié)點的 next 指針開銷。

4.2 B16Compact 哈希數(shù)據(jù)結構

為了進?步壓榨哈希表的存儲空間，我們還設計了 B16 的只讀緊湊數(shù)據(jù)結構，如下圖所示：

△B16Compact 哈希表數(shù)據(jù)結構（3元素示例）

B16Compact 對哈希表結構做了極致的壓縮。

?先它省去了 CHUNK 中的 next 指針，把所有的 CHUNK 合并到了?個數(shù)組中，并且補上了所有的CHUNK 空洞。例如【圖1】中 BUCKET［1］ 的拉鏈中本來有 4 個元素，包含 Banana 和 Lemon，其中頭兩個元素被補到了【圖2】的 CHUNK［0］ 中。以此類推，除 CHUNK 數(shù)組中最后?個 CHUNK 外，所有的CHUNK 均是滿的。

然后它省去了 BUCKET 中指向 CHUNK 拉鏈的指針，只保留了?個指向原拉鏈中第?個元素所在 CHUNK 的數(shù)組下標。例如【圖1】中 BUCKET［1］ 的拉鏈第?個元素被補到了【圖2】的 BUCKET［0］ 中，那么新的 BUCKET［1］ 中僅存儲了 0 這個下標。

最后增加了?個 tail BUCKET，記錄 CHUNK 數(shù)組中最后?個 CHUNK 的下標。

經(jīng)過這樣的處理以后，原來每個 BUCKET 拉鏈中的元素在新的數(shù)據(jù)結構中依然是連續(xù)的，每個 BUCKET依然指向第?個包含其元素的 CHUNK 塊，通過下?個 BUCKET 中的下標依然可以知道最后?個包含其元素的 CHUNK 塊。不同的是，每個 CHUNK 塊中可能會包含多個 BUCKET 拉鏈的元素。雖然可能要查找的 CHUNK 變多了，但由于每個 CHUNK 都可以通過 SIMD 指令進?快速篩選，對整體查找性能的影響相對較?。

這個只讀哈希表只?持查找，查找的過程跟原來差異不?。以 Lemon 為例，?先通過 H1=24EB 找到對應的分桶1，獲得分桶對應拉鏈的起始 CHUNK 下標為0，結束 CHUNK 下標為1。使?與 B16 同樣的算法在 CHUNK［0］ 中查找，未找到 Lemon，然后繼續(xù)查找 CHUNK［1］，找到對應的元素。

B16 Compact 的理論額外存儲開銷可以通過下式算得：

其中，n 是只讀哈希表的元素個數(shù)。

當 n 取100萬，Load Factor 取13時，B16Compact 哈希表的理論額外存儲開銷是9.23 bits/key，即存儲每個 key 所?出的額外開銷只有1個字節(jié)多?點。這?乎可以媲美?些最?完美哈希函數(shù)了，?且不會出現(xiàn)構建失敗的情況。

B16Compact 數(shù)據(jù)結構僅包含兩個數(shù)組，BUCKET 數(shù)組和 CHUNK 數(shù)組，也就意味著它的序列化和反序列化可以做到極簡。由于 BUCKET 中存儲的是數(shù)組下標，?戶甚?不需要將哈希表整個加載到內(nèi)存中，使??件偏移即可進?基于外存的哈希查找，對于巨?的哈希表來說可以有效節(jié)省內(nèi)存。

5 實驗數(shù)據(jù)

5.1 實驗設定

實驗使?的哈希表的 Key 和 Value 類型均取 uint64_t，Key、Value 對的輸?數(shù)組由隨機數(shù)?成器預先?成。哈希表均使?元素個數(shù)進?初始化，即插?過程中不需要再 rehash。

插?性能：通過 N 個元素的逐?插?總耗時除以 N 獲得，單位是 ns/key；

查詢性能：通過對隨機的 Key 查詢20萬次（全命中） + 對隨機的 Value 查詢20萬次（有可能不命中）獲得總耗時除以40萬獲得，單位是 ns/key；

存儲空間：通過總分配空間除以哈希表??獲得，單位是 bytes/key。對于總分配空間來說，F(xiàn)14和B16均有對應的接?函數(shù)可直接獲取，unordered_map 通過以下公式獲?。?/p>

// 拉鏈節(jié)點總??umap.size（） * （sizeof（uint64_t） + sizeof（std：：pair《uint64_t， uint64_t》） + sizeof（void*））// bucket 總??+ umap.bucket_count（） * sizeof （void *）// 控制元素??+ 3 * sizeof（void*） + sizeof（size_t）;

Folly 庫使? - mavx - O2 編譯，Load Factor 使?默認參數(shù)；B16 使? - mavx - O2 編譯，Load Factor 設定為13；unordered_map 使? Ubuntu 系統(tǒng)?帶版本，Load Factor 使?默認參數(shù)。

測試服務器是?臺4核 8G 的 CentOS 7u5 虛擬機，CPU 是 Intel（R） Xeon（R） Gold 6148 @ 2.40GHz，程序在Ubuntu 20.04.1 LTS Docker 中編譯執(zhí)?。

5.2 實驗數(shù)據(jù)

△插?性能對?

上圖中折線所示為 unordered_map、F14ValueMap 和 B16ValueMap 的插?性能對?，不同的柱?顯示了不同哈希表的存儲開銷。

可以看到 B16 哈希表在存儲開銷明顯?于 unordered_map 的情況下，仍然提供了顯著優(yōu)于unordered_map 的插?性能。

由于 F14 哈希表對 Load Factor 的?動尋優(yōu)策略不同，在不同哈希表??下 F14 的存儲空間開銷存在?定波動，但 B16 的存儲開銷整體仍優(yōu)于 F14。B16 的插?性能在 100 萬 Key 以下時優(yōu)于 F14，但是在 1000萬 Key 時劣于 F14，可能是因為當數(shù)據(jù)量較?時 B16 拉鏈式內(nèi)存訪問的局部性? F14 差?些。

△查找性能對?

上圖中折線所示為 unordered_map、F14ValueMap、B16ValueMap 和 B16Compact 的查找性能對?，不同的柱?顯示了不同哈希表的存儲開銷。

可以看到 B16、B16Compact 哈希表在存儲開銷明顯?于 unordered_map 的情況下，仍然提供了顯著優(yōu)于 unordered_map 的查找性能。

B16 與 F14 哈希表的查找性能對?與插?性能類似，在 100 萬 Key 以下時明顯優(yōu)于 F14，但在 1000 萬時略劣于 F14。

值得注意的是 B16Compact 哈希表的表現(xiàn)。由于實驗哈希表的 Key 和 Value 類型均取 uint64_t，存儲 Key，Value 對本身就需要消耗 16 字節(jié)的空間，? B16Compact 哈希表對不同??的哈希表以穩(wěn)定的約 17.31bytes/key 進?存儲，這意味著哈希結構?為每個 Key 僅額外花費了 1.31 個字節(jié)。之所以沒有達到 9.23bits/key 的理論開銷，是因為我們的 BUCKET 數(shù)組沒有使? bitpack ?式進?極致壓縮（這可能會影響性能），?是使?了 uint32_t。

6 總結

本?中我們從哈希表設計的核?出發(fā)，介紹了兩種有趣的、不算“常?”的哈希沖突解決?法：完美哈希函數(shù)和基于 SIMD 指令的 F14 哈希表。

在 F14 的啟發(fā)下，我們設計了 B16 哈希表，使?了更容易理解的數(shù)據(jù)結構，使得增、刪、查的實現(xiàn)邏輯更為簡單。實驗表明在?些場景下 B16 的存儲開銷和性能? F14 還要好。

為追求極致的存儲空間優(yōu)化，我們對 B16 哈希表進?緊致壓縮，設計了?乎可以媲美最?完美哈希函數(shù)的 B16Compact 哈希表。B16Compact 哈希表的存儲開銷顯著低于 F14 哈希表（介于40%-60%之間），但卻提供了頗有競爭?的查詢性能。這在內(nèi)存緊張的場合，例如嵌?式設備或者?機上，可以發(fā)揮很?的作?。

新的哈希表設計表明 SIMD 指令的并?化處理能?的有效應?能?幅度提升哈希表對哈希沖突的容忍能?，進?提升查詢的速度，并且能幫助哈希表進?極致的存儲空間壓縮。這讓哈希表的設計思路從盡量規(guī)避哈希沖突，轉向了利?合適的哈希沖突概率來優(yōu)化計算和存儲效率。

原文標題：趣談哈希表優(yōu)化：從規(guī)避 Hash 沖突到利? Hash 沖突

文章出處：【微信公眾號：算法與數(shù)據(jù)結構】歡迎添加關注！文章轉載請注明出處。

責任編輯：haq