導(dǎo)讀：本文從哈希表傳統(tǒng)設(shè)計(jì)與解決思路入手，深入淺出地引出新的設(shè)計(jì)思路：從盡量規(guī)避哈希沖突，轉(zhuǎn)向了利?合適的哈希沖突概率來(lái)優(yōu)化計(jì)算和存儲(chǔ)效率。新的哈希表設(shè)計(jì)表明 SIMD 指令的并?化處理能?的有效應(yīng)?能?幅度提升哈希表對(duì)哈希沖突的容忍能?，進(jìn)?提升查詢(xú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ī)理論上來(lái)說(shuō)，哈希表就是?個(gè)可以通過(guò)哈希函數(shù)將 Key 映射到 Value 存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。那么哈希表設(shè)計(jì)的核?就是兩點(diǎn)：

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

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

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

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

2 規(guī)避哈希沖突

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

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

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

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

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

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

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

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

3 利?哈希沖突

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

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

3.1 SIMD 指令

SIMD 是單指令多數(shù)據(jù)流（Single Instruction Multiple Data）的縮寫(xiě)。這類(lèi)指令可以使??條指令操作多個(gè)數(shù)據(jù)，例如這些年?常?的 GPU，就是通過(guò)超?規(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ù)中開(kāi)源的 F14 哈希表有個(gè)?常精巧的設(shè)計(jì)，那就是將 Key 映射到塊，然后在塊?使? SIMD 指令進(jìn)??效過(guò)濾。因?yàn)榉謮K的數(shù)量?傳統(tǒng)的分桶要更?，這相當(dāng)于?為增加了哈希沖突，然后在塊中? SIMD 指令再解決沖突。

具體的做法是這樣的：

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

每個(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è)塊中；

在查詢(xún)時(shí)，通過(guò)待查找 Key 計(jì)算得到 H1 和 H2 。通過(guò) H1 對(duì)塊數(shù)取模確定其所屬的塊后，?先讀取塊頭，通過(guò) 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ì)?的開(kāi)銷(xiāo)，使哈希表能夠容忍更?的沖突概率。

4 B16 哈希表

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

那么我們考慮能不能從另?個(gè)?度出發(fā)，使?拉鏈法來(lái)組織分塊。由于省去了控制信息，每個(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 也是通過(guò)哈希函數(shù)對(duì) Key 計(jì)算出兩個(gè)哈希碼：H1 和 H2 。例如 “Lemon” 的兩個(gè)哈希碼是 0x24EB 和0x24，使? H1 的?位作為 H2 ?般來(lái)說(shuō)?夠了。

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

在查找時(shí)，先通過(guò) H1 找到對(duì)應(yīng)的分桶拉鏈，然后對(duì)每個(gè)塊進(jìn)?基于 SIMD 指令的 H2 對(duì)?。將每個(gè)塊的塊頭 16 字節(jié)加載到 128 bits 寄存器中，??包含了 16 個(gè) H2‘ ，把 H2 也重復(fù)展開(kāi)到 128 bits 寄存器中，通過(guò) 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)存訪問(wèn)的速度和連續(xù)性也?常重要?？刂茐K??在 16 以?xún)?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)過(guò)試驗(yàn)發(fā)現(xiàn)，當(dāng) Load Factor 在 11-13 之間時(shí)，B16 的整體性能表現(xiàn)最好。其實(shí)這也相當(dāng)于把原來(lái)存在于 BUCKET 數(shù)組中的空洞，轉(zhuǎn)移到了 CHUNK 拉鏈中，還省去了普通拉鏈?zhǔn)矫總€(gè)節(jié)點(diǎn)的 next 指針開(kāi)銷(xiāo)。

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］ 的拉鏈中本來(lái)有 4 個(gè)元素，包含 Banana 和 Lemon，其中頭兩個(gè)元素被補(bǔ)到了【圖2】的 CHUNK［0］ 中。以此類(lèi)推，除 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)過(guò)這樣的處理以后，原來(lái)每個(gè) BUCKET 拉鏈中的元素在新的數(shù)據(jù)結(jié)構(gòu)中依然是連續(xù)的，每個(gè) BUCKET依然指向第?個(gè)包含其元素的 CHUNK 塊，通過(guò)下?個(gè) BUCKET 中的下標(biāo)依然可以知道最后?個(gè)包含其元素的 CHUNK 塊。不同的是，每個(gè) CHUNK 塊中可能會(huì)包含多個(gè) BUCKET 拉鏈的元素。雖然可能要查找的 CHUNK 變多了，但由于每個(gè) CHUNK 都可以通過(guò) SIMD 指令進(jìn)?快速篩選，對(duì)整體查找性能的影響相對(duì)較?。

這個(gè)只讀哈希表只?持查找，查找的過(guò)程跟原來(lái)差異不?。以 Lemon 為例，?先通過(guò) 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ǔ)開(kāi)銷(xiāo)可以通過(guò)下式算得：

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

當(dāng) n 取100萬(wàn)，Load Factor 取13時(shí)，B16Compact 哈希表的理論額外存儲(chǔ)開(kāi)銷(xiāo)是9.23 bits/key，即存儲(chǔ)每個(gè) key 所?出的額外開(kāi)銷(xiāo)只有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ì)于巨?的哈希表來(lái)說(shuō)可以有效節(jié)省內(nèi)存。

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

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

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

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

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

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

// 拉鏈節(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ǔ)開(kāi)銷(xiāo)。

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

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

△查找性能對(duì)?

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

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

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

值得注意的是 B16Compact 哈希表的表現(xiàn)。由于實(shí)驗(yàn)哈希表的 Key 和 Value 類(lèi)型均取 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é)。之所以沒(méi)有達(dá)到 9.23bits/key 的理論開(kāi)銷(xiāo)，是因?yàn)槲覀兊?BUCKET 數(shù)組沒(méi)有使? 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ǔ)開(kāi)銷(xiāo)和性能? F14 還要好。

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

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