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

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

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

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

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

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

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

1 相關(guān)工作

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

1.1 布谷鳥哈希表

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

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

圖1 插入Cuckoo Hash

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

1.2 通過緩解哈希沖突

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

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

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

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

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

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

面向降低寫操作開銷的存儲(chǔ)系統(tǒng)性能優(yōu)化方法CoCuckoo［21］認(rèn)為由于布谷鳥哈希表在執(zhí)行查詢操作時(shí)，需要探測(cè)多個(gè)位置，執(zhí)行遞歸踢出操作，最終可能因循環(huán)踢出超過給定閾值而插入失敗，表現(xiàn)出其慢寫性能?；谶@些，CoCuckoo則是一種面向降低寫操作開銷的并發(fā)布谷鳥哈希方案。CoCuckoo不僅會(huì)預(yù)判插入過程中是否會(huì)發(fā)生無限循環(huán)，并且通過圖粒度鎖機(jī)制使得一次只允許一個(gè)線程訪問共享路徑，從而支持并發(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ù)先識(shí)別踢出是否有必要，有效減少了操作時(shí)間，能夠極大地提升哈希表的負(fù)載率。

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

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

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

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

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

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

2.2 插入操作

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

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

圖4 DC Hash的插入操作流程

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

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

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

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

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

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

2.3 查詢操作

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

圖5 DC Hash的查詢操作流程

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

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

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

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

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

2.4 刪除操作

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

3 性能評(píng)估

3.1 實(shí)驗(yàn)環(huán)境

（1）硬件平臺(tái)

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

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

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

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

（3）實(shí)驗(yàn)設(shè)置

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

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

3.2 性能指標(biāo)

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

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

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

（3）查詢代價(jià)（Search Costs）：查詢一個(gè)元素的內(nèi)存訪問次數(shù)，在這里將查詢一個(gè)元素對(duì)桶內(nèi)的平均訪問次數(shù)作為插入時(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不會(huì)出現(xiàn)插入失敗的情況，但在Linear Hash、Double Hash和布谷鳥哈希中，每當(dāng)插入過程中發(fā)生碰撞時(shí)，就會(huì)嘗試探測(cè)另一個(gè)桶，而這種探測(cè)可能不斷重復(fù)。實(shí)驗(yàn)將會(huì)為這3種方案設(shè)置探測(cè)遞歸的最大次數(shù)500次，每次插入的最大內(nèi)存訪問次數(shù)存在限制。在500次嘗試之后，如果碰撞仍然存在，那么此次無法為鍵值對(duì)找到空桶，為插入失敗。在孔雀哈希和d?left Hash中，為了避免插入失敗，也將子表變成哈希鏈表來避免出現(xiàn)插入失敗。接下來，實(shí)驗(yàn)比較這些哈希方法在負(fù)載因子、插入代價(jià)和查詢代價(jià)方面的性能。

（1）負(fù)載因子

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

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

（2）插入代價(jià)

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

圖7 不同比例下哈希表插入時(shí)間比較

（3）查詢代價(jià)

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

圖8 不同比例下哈希表查詢時(shí)間比較

4 結(jié)束語

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