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

1 背景

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

1.1 哈希表設(shè)計的核?

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

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

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

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

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

2 規(guī)避哈希沖突

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

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

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

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

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

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

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

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

3 利?哈希沖突

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

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

3.1 SIMD 指令

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

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

3.2 F14 哈希表

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

具體的做法是這樣的：

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

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

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

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

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

4 B16 哈希表

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

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

4.1 B16 哈希數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

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

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

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

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

4.2 B16Compact 哈希數(shù)據(jù)結(jié)構(gòu)

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

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

B16Compact 對哈希表結(jié)構(gòu)做了極致的壓縮。

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

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

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

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

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

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

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

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

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

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

5.1 實驗設(shè)定

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

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

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

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

// 拉鏈節(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 設(shè)定為13；unordered_map 使? Ubuntu 系統(tǒng)?帶版本，Load Factor 使?默認參數(shù)。

測試服務(wù)器是?臺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，可能是因為當(dāng)數(shù)據(jù)量較?時 B16 拉鏈?zhǔn)絻?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 進?存儲，這意味著哈希結(jié)構(gòu)?為每個 Key 僅額外花費了 1.31 個字節(jié)。之所以沒有達到 9.23bits/key 的理論開銷，是因為我們的 BUCKET 數(shù)組沒有使? bitpack ?式進?極致壓縮（這可能會影響性能），?是使?了 uint32_t。

6 總結(jié)

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

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

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

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

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

文章出處：【微信公眾號：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責(zé)任編輯：haq