淺談哈希算法

概述

哈希表算法

經(jīng)典策略主要有鏈表法和開放尋址法。如果發(fā)生哈希沖突，鏈表法將在沖突位置設(shè)置鏈表，將沖突元素掛上去；開放尋址法會以例如線性探測、雙散列函數(shù)探測、平方探測的方式對其他位置進行探查，如果有空位置則將沖突元素插入。

表1展示了經(jīng)典哈希算法的查詢表現(xiàn)。其中m是哈希總桶個數(shù)，n是哈希插入元素個數(shù)，a為裝載率。如圖所示，鏈表法具有較好的查詢時間表現(xiàn)，但需要額外的指針開銷空間。

多子表多位置的核心思想是采用多個哈希函數(shù)，設(shè)立多個子表，使元素有多個侯選位置，這樣相比于比單子表單位置，沖突概率會大大降低。

d-left哈希采用“Always-Go-Left”策略，即插入元素時，如果有多個候選位置為空或者有多個長度相同的最短鏈表，則將元素插入到最左邊的候選桶中。

算法分析

d-left的優(yōu)點是有較高的裝載率，同時并行查詢和Always-Go-Left策略可以實現(xiàn)較好的查詢效率。缺點是每個侯選位置都掛有鏈表造成了較大的空間開銷，同時如果不能實現(xiàn)并行查詢則需要對子表的多次訪存。

Lossy哈希主要應(yīng)用在緩存場景下，類似于CPU中的組相連的緩存策略。當插入元素的多個侯選位置均不為空時，Lossy哈希會刪除其中一個侯選位置的元素（比如一個很長時間不被訪問的元素）。

算法分析

相比于傳統(tǒng)的線性探測法，Lossy哈希的優(yōu)點在于有較好的空間利用率， 保證了最差查詢次數(shù)，減少了插入查詢的平均探查次數(shù)。缺點在于有可能會丟棄元素，造成假陰性。

采用例如布隆過濾器，二進制向量，指紋等片內(nèi)摘要輔助哈希表的插入查詢刪除操作。布隆過濾器是一個二進制向量和一系列隨機映射函數(shù)的組合，可用于檢索一個元素是否在一個集合中，優(yōu)點是空間效率和查詢時間較好，缺點是具有一定的假陽性。

孔雀鳥哈希（Peacock hashing）[26]使用了大小等比遞減的多級子表，其中最大子表為主表，其余子表為候選表。插入元素時按照子表大小依存探查，直至插入到一個空位置，如果均有沖突則丟棄該元素。在片內(nèi)對每個候選表設(shè)置一個布隆過濾器。

算法分析

孔雀鳥哈希的優(yōu)點在于使用片內(nèi)摘要有效降低查詢探測次數(shù)，只為候選表設(shè)置片內(nèi)布隆過濾器，節(jié)約了片內(nèi)內(nèi)存。缺點在于有可能丟棄元素。

分段哈希（Segmented hash）[27]有多個大小相等的子表，但只有一個哈希函數(shù)，并在片內(nèi)設(shè)置了二進制向量、計數(shù)器、改進的布隆過濾器。二進制向量表示對應(yīng)桶是否為空，計數(shù)器表示對應(yīng)桶鏈表元素個數(shù)，改良的布隆過濾器用于在有多個侯選位置可選時，將元素插入到置為1個數(shù)最少布隆過濾器對應(yīng)的子表中。

算法分析

分段哈希的優(yōu)點在于使用多種片內(nèi)輔助結(jié)構(gòu)，并改進布隆過濾器，降低插入查詢的訪存次數(shù)，缺點在于占用了較多片內(nèi)空間。

快速哈希（Fast hash table）[2]有一個哈希表和計數(shù)器，哈希表的桶可以掛鏈表，計數(shù)器對應(yīng)每個桶及鏈表元素總數(shù)目。如果有多個候選空位置，插入時將元素插入在計數(shù)器最小且子表索引最小的桶中，并將多個候選位置的計數(shù)器均加1。

算法分析

快速哈希的優(yōu)點在于查詢效率極高，如果所查元素不在表中，不需要進行訪存就可以知道，（計數(shù)器有一個為0）。缺點在于插入刪除操作較為繁瑣，訪存次數(shù)較高。

布谷鳥哈希（Cuckoo hashing）于2001年由Rasmus Pagh和Flemming Friche Rodler提出，該哈希設(shè)計包含兩個大小相等的子表和兩個不同的哈希函數(shù)。插入元素時，依次考慮插入第一二個子表，如果均沒有候選位置，則踢出其中一個元素，安插新元素，之后再進行踢出元素的插入操作。踢的次數(shù)若超過設(shè)置閾值，則需要重建原表。

算法分析

布谷鳥哈希創(chuàng)新性地引入“踢”的機制。這種設(shè)計的優(yōu)點包括：較好地提高裝載率（>95%），從而提升內(nèi)存使用效率；有助于實現(xiàn)相對簡單的查詢，可控的最壞情況是進行兩次探測，因而有利于處理讀較多的操作。缺點是對于寫較多的操作，對具有較高裝載率水平的哈希表需要進行多次探測和踢操作；非動態(tài)更新，踢的次數(shù)一旦超過閾值會觸發(fā)哈希表重建，而重建損害系統(tǒng)性能；查詢平均次數(shù)高于經(jīng)典鏈式哈希。

圖4展示了在布谷鳥哈希中插入元素的過程。注意到，由于布谷鳥哈希插入子表的先后順序固定， 第一個子表裝載率會高于第二個子表，在布谷鳥哈希設(shè)計基礎(chǔ)上提出的非對稱布谷鳥哈希，即第一個子表的大小是第二個子表的兩倍，可以解決這一問題。

Cuckoo Filter的核心思想是設(shè)置每個桶對應(yīng)4個entry，借助計算指紋的哈希函數(shù)，通過兩個哈希函數(shù) ，映射出兩個候選位置i1和i2。如果兩個位置均已有元素，則采取“踢”操作。

算法分析

Cuckoo Filter是Cuckoo Hash的變體。相比于布隆過濾器，Cuckoo Filter計算了關(guān)鍵字的指紋，對元素支持動態(tài)的插入和刪除，在容忍一定假陽性的水平下空間開銷更低。缺點是Cuckoo filter的桶的個數(shù)固定是2^n，并且網(wǎng)絡(luò)流場景下表現(xiàn)不如Bloom filter，尤其當出現(xiàn)重復(fù)元素，若存儲多個指紋時會消耗太多空間，若只存儲一個指紋就不能支持刪除元素。

Hopscotch Hashing于2008年由Maurice Herlihy提出，僅包含一個哈希表和哈希函數(shù)。插入元素時首先進行一定范圍的線性探測，如果線性探測范圍均不為空，則找到最近的一個空桶，嘗試將線性探測范圍內(nèi)的一個元素按照線性探測的規(guī)則插入到該空桶中，如果線性探測范圍內(nèi)所有元素均不能插入到該空桶中，則重建哈希表。

算法分析

Hopscotch Hashing可以采用比較簡單的哈希函數(shù)，比經(jīng)典的線性探測確定性更好，裝載率達90%時仍表現(xiàn)良好。若想加快查詢速度，可以使用位圖輔助。

OSDI 2018提出的level hash采用了Cuckoo hash的思想，同時針對非易失性存儲器（NVM），作寫優(yōu)化。ICDE 2019的Multi-Copy Cuckoo哈希針對FPGA的片內(nèi)片外，作插入查詢優(yōu)化，利用閑置的桶存儲冗余信息。兩者均顯著提升Cuckoo hash表性能。最近幾年發(fā)表在頂級會議上針對Cuckoo哈希的進一步優(yōu)化和變種，還有ATC’19的CoCuckoo、ATC’17的SmartCuckoo和ATC’16的Horton Tables。

完美哈希指的是直接構(gòu)造一個沒有沖突的哈希函數(shù)，就不會產(chǎn)生沖突了。

算法分析

完美哈希的優(yōu)點在于有O(1)的插入查詢，缺點在于完美哈希函數(shù)的構(gòu)建很麻煩，且如果元素候選集發(fā)生改變，需要重新設(shè)計哈希函數(shù)和重建哈希表。

Davi de Castro Reis將多種高效的完美哈希算法進行了比較和實現(xiàn)，并將代碼進行開源[34][35]。比較典型的完美哈希算法有CHD算法（Compress Hash and Displace）[36]， BMZ算法[37]，CHM算法[38]，F(xiàn)CH算法[39]，BDZ算法[40]，其中CHD算法和BDZ算法是效果較好。

Dcuckoo使用多級子表和多個哈希函數(shù)，并在片內(nèi)為每個子表設(shè)置指紋、二進制數(shù)據(jù)和布隆過濾器作為摘要，只有最后一個子表可以掛鏈表，插入元素時采用Cuckoo哈希中“踢”的機制。

算法分析

DCuckoo的優(yōu)點是可以實現(xiàn)較高的裝載率，且減少了片外訪存次數(shù)，只在最后一個子表設(shè)置指針，節(jié)約了內(nèi)存使用。缺點是，如果采用“踢”的機制需要更新布隆過濾器，但是布隆過濾器不支持刪除操作，所以會降低查詢效率。

硬件加速

FPGA（Field－Programmable Gate Array），即現(xiàn)場可編程門陣列。利用FPGA平臺可以在片內(nèi)內(nèi)嵌SRAM，相對于片外有更高的訪問速度，但SRAM價格昂貴，且由于空間限制，片內(nèi)內(nèi)存只能有很小的空間，所以需要將哈希表放在片外，將所需空間較小的摘要存在在片內(nèi)，借助片內(nèi)輔助訪問片外，可減少片外內(nèi)存訪問。

除FGA平臺外，我們還可以使用GPU-CPU實現(xiàn)片內(nèi)-片外架構(gòu)。GPU即圖形處理器，最初主要用于圖形圖像相關(guān)的計算處理。GPU的每個處理器核心的數(shù)字邏輯運算單元相對簡單，但由于其核數(shù)眾多，擁有很強的并行計算能力。隨著CUDA，OpenCL等語言的出現(xiàn)，GPU開始在科學(xué)計算領(lǐng)域得到廣泛的應(yīng)用。哈希函數(shù)的計算也是GPU的強項，因此我們可以將片內(nèi)摘要存儲在GPU的顯存中。雖然GPU與GPU之間的單次通信有一定的延遲，但我們可以把查詢請求一次性發(fā)送給GPU進行處理，以獲得較高的吞吐量。與FGPA相比，GPU的實現(xiàn)成本較低，在消費市場較為常見。

總結(jié)與展望

本文介紹并分析了五大類共13種哈希算法，包括開放尋址法，可分為線性探測、雙散列函數(shù)探測、平方探測等以及鏈表法；多子表多位置哈希算法，包括d-left哈希和Lossy哈希；設(shè)置片內(nèi)摘要的哈希算法，包括Peacock 哈希、Segment哈希、快速哈希；采用踢機制的哈希表包括Cuckoo哈希和Hopscotch哈希；完美哈希及硬件加速相關(guān)內(nèi)容。不同的應(yīng)用場景會對哈希算法提出不同的性能要求，通過了解各種哈希算法的核心設(shè)計和優(yōu)劣性，可以找到最合適應(yīng)用場景的哈希算法。接下來我們希望能夠更好的優(yōu)化哈希算法，提出適合更多應(yīng)用場景的新的哈希算法。同時也希望這些哈希算法能給讀者以啟發(fā)，激發(fā)讀者對哈希算法進行改進和創(chuàng)新的靈感。