基于D維映射的布谷鳥哈希表

朱海婷，李 男，張 璐，何高峰，宛俊美，鄧瑩瑩

（1.南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210003 2.南京審計大學(xué)信息工程學(xué)院，江蘇 南京 211815）

隨著云計算、物聯(lián)網(wǎng)、社交網(wǎng)絡(luò)等技術(shù)的快速發(fā)展，大數(shù)據(jù)時代已經(jīng)到來，傳統(tǒng)的數(shù)據(jù)處理、存儲和分析技術(shù)存在著查詢效率低等問題［1］。截至2021年6月30日，F(xiàn)acebook的全球每月活躍用戶超過29億，平均每天有19.1億人登錄Facebook進(jìn)行瀏覽、上傳信息，每日活躍用戶同比增長7%［2］。因此如何在有限的資源內(nèi)處理海量數(shù)據(jù)成為計算機(jī)科學(xué)及數(shù)理統(tǒng)計等領(lǐng)域的挑戰(zhàn)。

鍵值存儲通過鍵值對 （Key?Value Pairs，KV Pairs）的形式存儲數(shù)據(jù)，是現(xiàn)代大規(guī)模存儲系統(tǒng)不可或缺的一部分。哈希表是根據(jù)鍵（key）而直接訪問內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)，能夠支持快速查詢，被廣泛應(yīng)用于數(shù)據(jù)挖掘、數(shù)據(jù)庫、存儲、網(wǎng)絡(luò)等各個領(lǐng)域［3-6］。但當(dāng)負(fù)載較高時，哈希沖突會頻繁發(fā)生，為了更好地解決沖突，誕生了許多解決方案和哈希表存儲結(jié)構(gòu)。

線性探查法（Linear Hash）和雙重哈希函數(shù)法（Double Hash）是傳統(tǒng)解決哈希沖突方法中的開放尋址法，但其需要額外的時間和資源來解決沖突，會影響插入和查找的性能。經(jīng)典哈希表數(shù)據(jù)結(jié)構(gòu)還包括鏈?zhǔn)焦１恚↙ink Hash），孔雀哈希（Peacock Hashing）［7］，d?left Hash［8］等。與傳統(tǒng)哈希結(jié)構(gòu)為每個數(shù)據(jù)元素提供一個候選位置不同，布谷鳥哈希表（Cuckoo Hash）［9］是一種通過多個哈希函數(shù)實現(xiàn)多位置選擇來解決哈希沖突問題的數(shù)據(jù)結(jié)構(gòu)。Cuckoo Hash能夠?qū)崿F(xiàn)高負(fù)載率，且其在最壞情況下具有常數(shù)級查找時間，目前已成為許多領(lǐng)域的首選散列技術(shù)，例如存儲系統(tǒng)［10］、數(shù)據(jù)處理［11］等。

本文是在鍵值對存儲的架構(gòu)下，設(shè)計優(yōu)化其中的內(nèi)存數(shù)據(jù)組織結(jié)構(gòu)——哈希表，以實現(xiàn)更高性能的鍵值對存儲。布谷鳥哈希表作為經(jīng)典的哈希表算法，具有其優(yōu)點的同時也存在一些可以改進(jìn)的地方：（1）布谷鳥哈希在一次查找過程中需要探查多個桶，當(dāng)表太大時，會產(chǎn)生較多額外的訪問，影響效率；（2）當(dāng)在插入過程中無法解決沖突時，布谷鳥哈希建議進(jìn)行重新哈希，極大浪費時間和空間資源；（3）布谷鳥哈希不能預(yù)知鍵值對在插入時是否存在空的候選桶，只能隨機(jī)方式選擇桶探測，需花費大量時間才能找到空余候選桶，甚至可能陷入無限循環(huán)。

為進(jìn)一步解決上述問題，本文提出了基于D維映射的布谷鳥哈希算法 DC Hash（D?Dimensional Cuckoo Hash），主要思想如下：（1）通過對哈希表進(jìn)行屬性劃分，在查找鍵值對時預(yù)先縮小可能包含該鍵值對的桶的子集范圍，減少內(nèi)存訪問時間，有效提高了查找性能；（2）引入鏈表結(jié)構(gòu)到布谷鳥哈希表結(jié)構(gòu)中，以存儲插入失敗的所有鍵值對，而不必進(jìn)行重新哈希；（3）增加輔助數(shù)據(jù)結(jié)構(gòu)，以預(yù)知鍵值對在插入時是否存在空的候選桶，預(yù)先識別踢出是否有必要，減少操作時間，提高效率。最后在NYTimes數(shù)據(jù)集和來自CAIDA的被動測量數(shù)據(jù)集上進(jìn)行了對比實驗，結(jié)果表明，DC Hash有效改進(jìn)了布谷鳥哈希存在的問題，且從平衡綜合性能考慮優(yōu)于其他幾種常見的哈希表。

1 相關(guān)工作

近年來，布谷鳥哈希算法得到了廣泛關(guān)注，且為了提高布谷鳥哈希在查找和插入方面的性能，提出了大量的改進(jìn)方案。本節(jié)首先介紹了傳統(tǒng)的布谷鳥哈希算法，然后對不同方向的改進(jìn)方案進(jìn)行簡單介紹。

1.1 布谷鳥哈希表

為了解決哈希沖突，Pagh等［9］于2004年最早提出了布谷鳥哈希算法。布谷鳥哈希使用d個哈希函數(shù)為每個待插入的鍵值對提供多個候選存儲桶，以減少沖突。它包含d個長度為n的哈希表（T1，T2，…，Td）和 d 個哈希函數(shù)（H1，H2，…，Hd），把每一個鍵值對在哈希表中的對應(yīng)位置叫做一個桶（bucket）。需要插入的鍵值對（key，value）通過哈希函數(shù)求得d個散列值 H1（key），H2（key），…，Hd（key），對應(yīng)于 d 個哈希表中的候選桶位置，將被存儲在其中一個。因此當(dāng)查詢一個鍵值對時，只需要檢查這d個桶。但是，如果在插入期間所有候選桶都已被占用，則需要“踢”出其中一個占用者以騰出空間放入需要插入的項。被踢出的項同樣通過哈希函數(shù)尋找其他表中的候選桶是否為空，否則“踢出”將繼續(xù)，直到每個項找到存儲的桶。踢出機(jī)制使得Cuckoo Hash相比其他的哈希算法能夠更高效靈活地解決沖突，且實現(xiàn)了高負(fù)載率。

d＝2的布谷鳥哈希表的示例如圖1所示，包含兩個長度為4的哈希表（分別為T1，T2），每個哈希表對應(yīng)一個哈希函數(shù)（分別為Hash1，Hash2）。圖1分別展示了布谷鳥哈希在執(zhí)行插入操作時可能會出現(xiàn)的3種情況。圖1（a）中兩個映射位置均為空，則任意選擇一個位置插入；圖1（b）中映射位置僅一個為空，直接插入該空桶；圖1（c）中兩個映射位置都已經(jīng)存在鍵值對，選擇＜k1，v1＞從當(dāng)前桶中踢出，將＜k2，v2＞插入該桶，再將＜k1，v1＞重新在另一個表中使用相應(yīng)哈希函數(shù)尋找位置插入桶中。在插入過程中，若被踢出的次數(shù)達(dá)到設(shè)定的閾值，則認(rèn)為哈希表己滿，進(jìn)行重新哈希。

圖1 插入Cuckoo Hash

重新哈希是指讀取所有需要插入的項，并使用不同的哈希函數(shù)將它們放入一個更大的表中，在此期間哈希表完全不可用，這不僅極大浪費時間和空間資源，并且代價高昂。因此自從提出布谷鳥哈希以來這個問題就引起了廣泛關(guān)注，接下來介紹常見的改進(jìn)方案。

1.2 通過緩解哈希沖突

緩解哈希沖突的方法也有多種。第一種是對哈希表本身進(jìn)行擴(kuò)展緩解哈希沖突，例如 d?ary Cuckoo［12］和 blocked Cuckoo［13］哈希表將原始的布谷鳥哈希表從單個桶存儲單個鍵值對的簡單設(shè)計擴(kuò)展到在每個存儲桶中存儲l個鍵值對，可將負(fù)載率提高到90%以上。由于這兩種方法都是針對對象的“乘法”擴(kuò)展，因此經(jīng)常將兩者結(jié)合起來，使數(shù)據(jù)結(jié)構(gòu)更加靈活。另外一種是針對哈希沖突的特性，改變哈希沖突處理方式或者預(yù)先識別哈希沖突來處理。例如Min?Counter［14］在構(gòu)造哈希表時統(tǒng)計了每個桶內(nèi)發(fā)生哈希沖突的次數(shù)，發(fā)現(xiàn)在此過程中，每個哈希桶中發(fā)生沖突的頻率不平衡。Min?Counter的核心思想是在鍵值對插入過程中發(fā)生踢出操作時，自主選擇計數(shù)器數(shù)值最小的桶來形成“不忙碌”的踢出路徑以盡快找到空桶，從而緩解哈希沖突和實現(xiàn)數(shù)據(jù)遷移，進(jìn)而提高了空間效率和減少了插入延遲。

1.3 通過增加輔助數(shù)據(jù)結(jié)構(gòu)

為了在插入過程中減少內(nèi)存中不必要的桶探測，一種策略是在探測所有候選桶之前使用一個小的summary來確定鍵值對的位置。增加的summary需要足夠小，以便存儲在快速內(nèi)存中（如 ASIC/EPGA中的SRAM、CPU緩存）。整個哈希表往往由于太大，只能存儲在慢內(nèi)存中（如 DRAM）。Fast Hash［15］是第一個在快速內(nèi)存中使用summary來減少慢內(nèi)存中內(nèi)存訪問的方案。另一種方法是使用Bloom Filter記錄每個子表的存儲情況。由于對快速內(nèi)存的訪問速度很快，此時哈希表的查詢性能取決于慢內(nèi)存部分所消耗的時間，因此可以使用桶探測數(shù)作為查詢性能的衡量標(biāo)準(zhǔn)。例如孔雀哈希［7］和分段哈希［16］（Segmented Hash），在這類哈希表中，由于Bloom Filter的誤報率與插入的鍵值對數(shù)量成正比，一個關(guān)鍵問題是如何減少插入到summary中鍵值對數(shù)量。孔雀哈希很大程度上減少了這個數(shù)量，但由于它使用了多個Bloom Filter，這使得查詢輔助數(shù)據(jù)結(jié)構(gòu)更加復(fù)雜。對孔雀哈希進(jìn)行改進(jìn)的方案有移位哈希表（SHT）［17］。SHT中的哈希表部分將鍵值對分為 abroad和 at?home兩類，在 summary中只插入abroad的項。在summary部分，提出使用一個增強(qiáng)的Bloom Filter來代替多個Bloom Filter，實現(xiàn)了更快的查詢速度。

Kirsch等［18］提出 CHS 機(jī)制 （Cuckoo Hashing with a Stash）來緩解哈希沖突，CHS在Cuckoo哈希表的基礎(chǔ)上增加一個額外緩沖空間（Stash）。Stash用于臨時存儲踢出次數(shù)超過閾值的鍵值對而不是立刻重新哈希。Multi?Copy Cuckoo Hashing［19］則將鍵值對的副本同時插入d個哈希表中，因此當(dāng)有多個候選桶可用時，不必在插入時隨便選擇一個候選桶。

1.4 其他改進(jìn)方案

其他改進(jìn)方案如Single Hash［20］認(rèn)為其他方案的哈希計算開銷都很高，因為這些方案數(shù)據(jù)結(jié)構(gòu)中需要多個哈希函數(shù)，而性能好的哈希函數(shù)通常都非常復(fù)雜。哈希函數(shù)的計算是在CPU上進(jìn)行的，將占用大量CPU資源，進(jìn)而影響系統(tǒng)性能。因此，Single Hash提出減少哈希函數(shù)的數(shù)量到一個。Single Hash顯著提高了基于哈希的數(shù)據(jù)結(jié)構(gòu)的速度，同時保持準(zhǔn)確性不變。它可以應(yīng)用于使用多個哈希函數(shù)的大多數(shù)數(shù)據(jù)結(jié)構(gòu)，并提高它們的性能。

面向降低寫操作開銷的存儲系統(tǒng)性能優(yōu)化方法CoCuckoo［21］認(rèn)為由于布谷鳥哈希表在執(zhí)行查詢操作時，需要探測多個位置，執(zhí)行遞歸踢出操作，最終可能因循環(huán)踢出超過給定閾值而插入失敗，表現(xiàn)出其慢寫性能。基于這些，CoCuckoo則是一種面向降低寫操作開銷的并發(fā)布谷鳥哈希方案。CoCuckoo不僅會預(yù)判插入過程中是否會發(fā)生無限循環(huán)，并且通過圖粒度鎖機(jī)制使得一次只允許一個線程訪問共享路徑，從而支持并發(fā)寫入和讀取操作，提高吞吐量性能。

2 D維布谷鳥哈希表

本文在布谷鳥哈希的基礎(chǔ)上進(jìn)行改進(jìn)，提出了基于 D維的布谷鳥哈希表，稱為 DC Hash（D?Dimensional Cuckoo Hash Table，DC Hash），它包括哈希表數(shù)據(jù)結(jié)構(gòu)和輔助數(shù)據(jù)結(jié)構(gòu)兩部分。本結(jié)構(gòu)以布谷鳥哈希表的踢出機(jī)制為基礎(chǔ)，不僅有效改善了哈希表中遇見沖突需要重新哈希的問題，并且能夠預(yù)先識別踢出是否有必要，有效減少了操作時間，能夠極大地提升哈希表的負(fù)載率。

2.1 數(shù)據(jù)結(jié)構(gòu)

為了達(dá)到理想的插入查找性能，DC Hash建立哈希表數(shù)據(jù)結(jié)構(gòu)。如圖2所示，DC Hash的數(shù)據(jù)結(jié)構(gòu)包括兩個部分：哈希表及輔助數(shù)據(jù)結(jié)構(gòu)。

（1）哈希表T包含t個子表（t是D的倍數(shù)，D為DC Hash的維數(shù)），各子表的大小相等，其中最后一個子表（Tt-1）為鏈?zhǔn)浇Y(jié)構(gòu)表。每個子表內(nèi)有k個桶（bucket），每一個桶能存儲一個鍵值對。DC Hash根據(jù)D的值對哈希表T進(jìn)行劃分，圖2為D＝2時的DC Hash結(jié)構(gòu)圖。當(dāng)D＝2時，對于哈希表部分，DC Hash 將 T0與 T1，T2與 T3，至 Tt-2與 Tt-1分別結(jié)合在一起，得到t/2組大小相等的哈希表，至此哈希表T 被分為兩個屬性（兩個組）：T0，T2，…，Tt-2為同一屬性（同一組），T1，T3，…，Tt-1為同一屬性（同一組），形成2維映射空間。

（2）輔助數(shù)據(jù)結(jié)構(gòu)部分包含布隆過濾器（Bloom Filter）和位圖（Bitmap）［22］。如圖 2 所示，t個哈希子表（T0，T1，…，Tt-1）對應(yīng) t個布隆過濾過濾器（BF0，BF1，…，BFt-1）。當(dāng) D＝2，DC Hash 將哈希子表進(jìn)行結(jié)合時同樣將其對應(yīng)的布隆過濾器進(jìn)行結(jié)合，得到t/2個大小相等的布隆過濾器（B0，B1，…，Bt/2-1），然后將這些大小相等的過濾器疊加在一起，形成一個統(tǒng)一的多位布隆過濾MB（Multi?bit Bloom Filter）。另外每個子表有一個相對應(yīng)的 Bitmap，Bitmap中的每一個比特與其對應(yīng)子表中的一個桶相對應(yīng)；空桶對應(yīng)位圖中的比特為0，反之對應(yīng)位圖中的比特為1。利用上述哈希表數(shù)據(jù)結(jié)構(gòu)和輔助數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)鍵值對的插入。

圖2 DC Hash結(jié)構(gòu)圖（D＝2）

接下來詳細(xì)介紹DC Hash的基本操作，包括鍵值對的插入、查詢和刪除。

2.2 插入操作

插入給定鍵值對（key，value）的過程如圖3和4所示，包括以下幾個步驟。

圖3 DC Hash 插入鍵值對（t＝4，D＝2，k＝4）

圖4 DC Hash的插入操作流程

（1）判定備選哈希表屬性。將鍵值對中的key值經(jīng)過主哈希函數(shù)Hm進(jìn)行計算，得到對應(yīng)哈希值p＝Hm（key），根據(jù) p 決定備選哈希表的屬性（共 t/D個備選哈希表）。

（2）求得備選桶位置。將鍵值對中的key分別通過在步驟1中確定的備選哈希表對應(yīng)的哈希函數(shù)H1、H2求得相應(yīng)的哈希值 j1＝H1（key），j2＝H2（key），即為其在備選表中對應(yīng)的備選桶位置。

（3）判斷備選桶是否為空。通過位圖判斷這t/D個哈希表內(nèi)的備選桶是否為空，B［p］［j］＝0 代表該位置為空，反之不為空。

（4）插入鍵值對。若備選桶中僅存在一個空桶，則直接插入；若備選桶存在多個空桶，則將鍵值對插入映射位置為空的負(fù)載率最小的哈希表中；若所有同屬性子表不存在空桶，則采取踢出機(jī)制：按順序選擇出各個候選子表的對應(yīng)桶的值，首先預(yù)判是否能找出另外一個能容納候選桶，若有，選擇負(fù)載因子最小的哈希表進(jìn)行插入，若沒有，則進(jìn)行盲踢（盲踢與踢出機(jī)制類似，為第二個被踢出值采用同樣方式尋找候選桶）。若盲踢達(dá)到閾值上限θ，在最后一個子表上掛鏈表，使用指針將鍵值對掛在鏈表上。

（5）更新多位布隆過濾器MB和位圖。假設(shè)要插入的子表的索引為m（0≤m≤t-1），則更新m所在組的布隆過濾器，并更新對應(yīng)子表的Bitmap。

圖3在步驟4展示了插入操作備選桶的3種存在情況示例。情況1為僅有一個位置為空，直接插入該空桶；情況2為兩個位置均為空，選擇負(fù)載因子較小的表進(jìn)行插入；情況3為兩個位置均不為空，則為原本桶中元素尋找新的位置（通過哈希表對應(yīng)的哈希函數(shù)），若能找到位置，將其從原位置踢出并放入新桶中，然后將待插入元素插入（踢出成功）；若不能找到位置，則將待插入元素掛在最后一個子表的鏈表上。

2.3 查詢操作

若要查詢給定key的value值或者判斷鍵值對是否存在哈希表中，則可以通過查詢操作查詢給定值。過程如圖5所示，包括以下幾個步驟。

圖5 DC Hash的查詢操作流程

（1）首先在多位布隆過濾器中查詢key值的返回值。若返回i，表明key的所在組為Bi，則執(zhí)行步驟 2；若返回 false，表明 key不存在于哈希表中。

（2）通過代入主哈希函數(shù)計算出鍵值對具體存在哈希子表的屬性。

（3）在返回的哈希子表的對應(yīng)位圖中判斷此處是否存在鍵值對。

（a）若存在，則查找對應(yīng)哈希子表的映射位置的key是否與其相同：若相同，返回其value值，查找結(jié)束；若不相同且為最后一個哈希鏈表，則到鏈表中查詢鍵值對。

（b）若不存在，說明不存在于哈希子表中。

2.4 刪除操作

若需刪除鍵值對，則首先需要在哈希表中查詢到具體值，若查詢到的相應(yīng)key的value值與需要刪除的鍵值對相同，則進(jìn)行桶內(nèi)部清空操作，最后將對應(yīng)位置的位圖置零；若value值不相同，則代表刪除失敗。

3 性能評估

3.1 實驗環(huán)境

（1）硬件平臺

所有實驗在一臺4核（8線程，Intel Core i5@4.0 GHz）電腦上運行，所有哈希算法均用C++實現(xiàn)。

（2） 數(shù)據(jù)集

實驗數(shù)據(jù)共有兩組，第一組來自DocWords中的NYTimes數(shù)據(jù)集。其來自于UCI機(jī)器學(xué)習(xí)存儲庫，它是數(shù)據(jù)庫、領(lǐng)域理論和數(shù)據(jù)生成器的集合。NYTimes數(shù)據(jù)集總共包含大約7 000萬個項，它包括5個單詞包形式的文本集合，實驗將DocID和WordID組合在一起以形成每個鍵值對的key，value是集合中的單詞總數(shù)，選擇前80 000個項組成鍵值對作為第一個數(shù)據(jù)集dataset1。

第二組來自CAIDA上的被動測量數(shù)據(jù)集，CAIDA通過操作主動和被動測量基礎(chǔ)設(shè)施，并收集、管理、歸檔和共享這些設(shè)施測量產(chǎn)生的數(shù)據(jù)集。被動測量數(shù)據(jù)集包含CAIDA與各種操作網(wǎng)絡(luò)基礎(chǔ)設(shè)施的機(jī)構(gòu)合作被動監(jiān)測選定鏈路上的流量。實驗選擇2016年CAIDA的equinix?chicago監(jiān)視器在高速互聯(lián)網(wǎng)骨干鏈路上的一分鐘匿名流量。將數(shù)據(jù)包中提取的源IP地址設(shè)置為每個鍵值對的key，將value設(shè)置為一分鐘內(nèi)此IP地址出現(xiàn)的頻次。由于一分鐘內(nèi)產(chǎn)生了48萬個不重復(fù)的IP地址，因此將這48萬個鍵值對作為第二個數(shù)據(jù)集dataset2。

（3）實驗設(shè)置

將采集到的數(shù)據(jù)集作為輸入來對哈希表性能進(jìn)行測試。數(shù)據(jù)集中每一條項目為一個（key，value）鍵值對，其中每個鍵值對的value值的大小固定為8位。使用β來表示所有子表中的桶的總個數(shù)與需要插入的總項目數(shù)的比率；使用n表示需要插入到哈希表中的鍵值對的數(shù)量，使用T表示哈希子表數(shù)量，則哈希子表的總大?。ㄍ暗膫€數(shù)）為β×n，每個子表大小為β×n/T；使用D表示DC Hash的維數(shù)；使用θ表示盲踢次數(shù)，踢出的次數(shù)達(dá)到閾值則會停止盲踢，并將此鍵值對插入到最后一個哈希鏈表中。

DC Hash的最后一個哈希表為鏈?zhǔn)焦１恚核怯梢粋€帶有b個桶的哈希表和一個哈希函數(shù)組成，具有均勻分布的輸出。每個桶都有單元鏈，每個單元有3個字段組成，即鍵、值和指針，指針字段指向鏈中的下一個單元（如果有下一個）。每個哈希表的大小根據(jù)插入元素的個數(shù)決定。

3.2 性能指標(biāo)

通過如下衡量指標(biāo)比較不同哈希表之間的性能：

（1）哈希表負(fù)載因子（load factor）：是指元素個數(shù)counter與空間大小Tsize的比值。計算方法如式（1）所示。當(dāng)哈希表大小相同且插入相同的數(shù)據(jù)時，哈希表的負(fù)載因子越大，代表哈希表性能越好。

（2）插入代價（Insert Costs）：插入一個元素的內(nèi)存訪問次數(shù)，在這里將插入一個元素對桶內(nèi)的平均訪問次數(shù)作為插入時間。內(nèi)存訪問次數(shù)越少，說明哈希表的性能越好。

（3）查詢代價（Search Costs）：查詢一個元素的內(nèi)存訪問次數(shù)，在這里將查詢一個元素對桶內(nèi)的平均訪問次數(shù)作為插入時間。內(nèi)存訪問次數(shù)越少，說明哈希表的性能越好。

3.3 性能比較

將不同維數(shù)的DC Hash與6種已知的哈希表即Link Hash、Linear Hash、Double Hash、布谷鳥哈希、d?left Hash和孔雀哈希進(jìn)行比較。將盲踢次數(shù)θ設(shè)置為1，β從1.05變化到6。由于存在哈希鏈表，DC Hash不會出現(xiàn)插入失敗的情況，但在Linear Hash、Double Hash和布谷鳥哈希中，每當(dāng)插入過程中發(fā)生碰撞時，就會嘗試探測另一個桶，而這種探測可能不斷重復(fù)。實驗將會為這3種方案設(shè)置探測遞歸的最大次數(shù)500次，每次插入的最大內(nèi)存訪問次數(shù)存在限制。在500次嘗試之后，如果碰撞仍然存在，那么此次無法為鍵值對找到空桶，為插入失敗。在孔雀哈希和d?left Hash中，為了避免插入失敗，也將子表變成哈希鏈表來避免出現(xiàn)插入失敗。接下來，實驗比較這些哈希方法在負(fù)載因子、插入代價和查詢代價方面的性能。

（1）負(fù)載因子

在不同的比例下，各個哈希表的負(fù)載因子變化如圖6所示，負(fù)載因子隨著β的增大而減小，兩者成反比。從圖中可以看出，對于DC Hash，當(dāng)D＝2時負(fù)載因子最高，且隨著選擇維數(shù)D的增加，負(fù)載因子呈遞減的趨勢，即越來越低。當(dāng)β為1.05時，可以發(fā)現(xiàn)DC Hash（D＝2，3），Double Hash 和 Linear Hash 均達(dá)到了0.9以上，Link Hash負(fù)載因子最小，為0.6左右。以情況最好的D＝2時為DC Hash的代表，當(dāng)β在1.05～4.00區(qū)間時，DC Hash的負(fù)載因子是最大的，能夠達(dá)到Link Hash的1.5倍。也就是說，DC Hash可以在給定空間的大小下，存儲更多的鍵值對，能夠更充分地利用空間。當(dāng)β更大時（到達(dá)6）Peacock Hash和d?left Hash才能獲得高的負(fù)載因子，即它們需要更大的內(nèi)存空間才能獲得高的負(fù)載因子。

圖6 不同比例下哈希表負(fù)載因子比較

（2）插入代價

在不同比例下，各個哈希表每次插入的內(nèi)存訪問次數(shù)如圖7所示，插入時間隨著β的增大而減小。從圖中可以看出，在β較小時（1.05～2.00區(qū)間），隨著選擇維數(shù)D的增大，DC Hash的插入代價呈遞減趨勢，即越來越小。除了Link Hash每次插入時內(nèi)存訪問次數(shù)最少，DC Hash的訪問代價均低于其他算法。當(dāng)β大于2時，幾乎所有哈希表每次插入內(nèi)存的訪問次數(shù)都在2次以下，而當(dāng)β很小時，Cuckoo Hash和Linear Hash的插入速度非常慢，d?left Hash次之，Link Hash最小。DC Hash在所有的哈希表中，達(dá)到除了Link Hash之外的內(nèi)存訪問次數(shù)最少。這證明了，由于Bloom filters和Bitmap的輔助，DC Hash能夠在實現(xiàn)高負(fù)載率的情況下還能夠有較低的訪問內(nèi)存代價，而其他算法需要更大的內(nèi)存空間才能獲得與DC Hash相似的內(nèi)存訪問代價。

圖7 不同比例下哈希表插入時間比較

（3）查詢代價

在不同比例下，各個哈希表每次查詢的內(nèi)存訪問次數(shù)如圖8所示，插入時間隨著β的增大而減小，兩者成反比。從圖中可以看出，隨著選擇維數(shù)D的增大，DC Hash的查詢代價呈遞減趨勢，即越來越小。且DC Hash同一維數(shù)的查詢代價隨著β的增大并沒有明顯的變化?？傮w來看，Cuckoo Hash查詢最快，其次是 Link Hash和 Double Hash。由于 DC Hash對哈希表進(jìn)行了劃分屬性，所以查詢代價相較于其他算法會略高一些。當(dāng)維數(shù)D選取高于2的值時，可以實現(xiàn)與其他算法接近的查詢代價。

圖8 不同比例下哈希表查詢時間比較

4 結(jié)束語

布谷鳥哈希算法是被廣泛認(rèn)可的高效利用存儲空間的哈希算法，本文針對布谷鳥哈希表在進(jìn)行哈希操作時，由于高負(fù)載而產(chǎn)生大量沖突導(dǎo)致最終有元素?zé)o法插入而重新哈希，浪費大量時間和空間的缺點，對哈希表進(jìn)行屬性劃分，加入鏈表結(jié)構(gòu)，并將哈希表數(shù)據(jù)結(jié)構(gòu)和輔助數(shù)據(jù)結(jié)構(gòu)兩部分進(jìn)行結(jié)合，提出了一種解決沖突的實現(xiàn)方法 DC Hash（D?Dimensional Cuckoo Hash），能夠預(yù)先識別踢出是否有必要，有效減少了操作時間，提升哈希表的負(fù)載率。最后在NYTimes數(shù)據(jù)集和來自CAIDA的被動測量數(shù)據(jù)集上進(jìn)行了對比實驗，結(jié)果發(fā)現(xiàn)，在相同的內(nèi)存空間下，當(dāng)選用合適的維度D時，DC Hash的負(fù)載率大于其他哈希表，且最多能達(dá)到Link Hash負(fù)載率的1.5倍；插入時能夠?qū)崿F(xiàn)除了Link Hash之外的最少內(nèi)存訪問次數(shù)。從平衡綜合性能考慮，DC Hash優(yōu)于其他幾種常見的哈希表。