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

1 背景

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

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

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

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

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

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

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

2 規(guī)避哈希沖突

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

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

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

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

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

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

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

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

3 利?哈希沖突

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

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

3.1 SIMD 指令

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

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

3.2 F14 哈希表

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

具體的做法是這樣的：

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

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

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

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

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

4 B16 哈希表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)數(shù)據(jù)

5.1 實(shí)驗(yàn)設(shè)定

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

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

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

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

// 拉鏈節(jié)點(diǎn)總??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 庫(kù)使? - mavx - O2 編譯，Load Factor 使?默認(rèn)參數(shù)；B16 使? - mavx - O2 編譯，Load Factor 設(shè)定為13；unordered_map 使? Ubuntu 系統(tǒng)?帶版本，Load Factor 使?默認(rèn)參數(shù)。

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

5.2 實(shí)驗(yàn)數(shù)據(jù)

△插?性能對(duì)?

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

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

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

△查找性能對(duì)?

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

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

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

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

6 總結(jié)

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

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

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

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

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

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

責(zé)任編輯：haq