哈希表總結及其高級話題討論

05-09

哈希表（hash table）是一種快速查找場景下常用的數據結構，本文對其主要問題及其高級應對方法進行有限的總結和討論：

負載不夠均衡，此時會有哈希衝突（collision）出現，導致哈希表性能下降
負載高時，若不進行空間擴展則性能下降，若進行空間擴展，擴展行為的（瞬間）代價通常較高

由於這篇文章數學公式比較多，而且知乎的數學公式編輯難度簡直突破天際，強烈建議去我的博客圍觀這篇文章（傳送門在此）。

先回顧一下哈希表的數學模型：

所有數據所在的空間集合為 S
通過哈希表存儲的數據集合為 U
所有哈希桶（bucket）的下標集合為 R
通過某種方式將 S 中的元素映射到 R 集合，不妨記為函數 h

一般 S 的大小遠大於 R，但是通過哈希表存儲的數據集合 U 與 R 的大小相差不會太懸殊。

如果有 x∈S, y∈S 並且 x≠y∧h(x)=h(y)，則稱 x 與 y 衝突（collision）。

如果 h 可以將 U 單射（injective）到 R，則稱此種情況為完美哈希（perfect hashing）。這意味著 U 的大小小於等於 R 的大小。特別的，當 U 的大小與 R 的大小相等時，稱此種情況為最小完美哈希（minimal perfect hashing）。

如果 U 預先給定，並且不再進行調整，則稱此種情況為靜態哈希表（static hash table），否則稱為動態哈希表（dynamic hash table）。

哈希衝突

哈希衝突的解決方案有兩種：

衝突避免
衝突解決

衝突避免

如果哈希函數 h 選得足夠好，並且 U 的大小小於等於 R，就有可能形成完美哈希的情況。對於靜態哈希表，有確定性的策略 [1]可以找到這樣的 h 來達成最小完美哈希 。對於動態哈希表，由於我們不能預測 U 中元素的分布，我們不能預先設計 h 以達成完美哈希。特別的，由於 U 中的元素是變動的，U?S 且 S 的大小遠大於 R，因此對於使用確定性策略構成的哈希函數 h，總是存在一個對抗性的集合 U，可以使得哈希衝突儘可能的多。因此， 對於動態哈希表，必須使用非確定性的策略來構成哈希函數 h，才有可能保證避免哈希衝突 。這一問題稱為 Dynamic Perfect Hashing 問題。一個可行的方案是預先準備一族哈希函數，在使用過程中隨機從中選擇一個哈希函數。可以想像，這一族哈希函數應該具有某種性質，使得相同分布的輸入不會產生相同分布的輸出。這樣一來，針對某一個特定哈希函數的對抗性策略就不會對其他哈希函數生效，因此隨機選擇哈希函數即可抵抗確定性的對抗策略。當然，這涉及到一個問題，即在查找的時候該怎麼知道用哪一個哈希函數進行查找？這一問題在後面衝突解決中的 Two-way Chaining 中進一步討論。

如果存在這樣一組哈希函數，H={h:U→R} 滿足 $forall x, y in U, x e y: Pr_{h in H}[h(x) = h(y)] le 1/{|R|}$ ，則稱 H 為全域哈希族（universal hashing） [2]。這一數學式的意義是，在 U 中任選兩個不同的元素 x,y，在 H 中任選一個哈希函數 h，則 h(x),h(y) 是獨立（均勻分布）的。

全域哈希族的加強形式為全域 k 哈希（universalk hashing) [3]，其需要滿足如下條件：給定 k 個兩兩不等的元素 (x1,...,xk)∈Uk，和 k 個哈希值（無需兩兩不等）(y1,...,yk)∈Rk，有

$Pr_{h in H} [ h(x_1) = y_1 land dots land h(x_k) = y_k ] = m^{-k}$

這一加強形式通常不容易達到，因此我們有時選擇其寬鬆型式 (μ,k)-universal：

$forall ext{distinct} (x_1, ldots, x_k) in U^k, forall (y_1, ldots, y_k) in R^k,$

$Pr_{h in H} [ h(x_1) = y_1 land dots land h(x_k) = y_k ] lt mu/|R|^k$

其中 μ 越接近 1 越好。

衝突解決

經過上面的討論可知，對於動態哈希表很難達成完美哈希，因此我們必須考慮如何處理哈希衝突。常見的衝突解決策略有：

Open Addressing
Separate Chaining
Two-way Chaining

Open Addressing

Open Addressing 是一種常見的衝突解決策略，其常見的細分策略有：

Linear probing
Quadratic probing
Double hashing

其中 Linear probing 由於對緩存友好，性能最高，比較常用。Linear probing 可能帶來衝突聚集的情況，為了避免這一現象，有時也會使用 Quadratic probing 策略。使用 Quadratic probing 也會被對抗性策略所困，因此有時也會使用 Double hashing 配合 Universal hashing 獲得更好的效果。

Separate Chaining

Open Addressing 在裝載因子較高時性能會急劇下降，為了應對這一情況，也常使用 Separate Chaining 策略。Separate Chaining 一般使用鏈表，有時也會使用查找樹結構。

Two-way Chaining

Two-way Chaining 就像是 Double hashing，區別在於 Double hashing 使用一個哈希表，而 Two-way Chaining 使用兩個哈希表 T1和 T2。在插入時，T[h1(x)] 和 T[h2(x)] 中哪個裝載的元素更少，就插入到哪兒。查找時需要訪問兩個哈希表。

Cuckoo Hashing

Cuckoo Hashing [4] 是 Two-way Chaining 的進階版本，其同樣使用兩個哈希表，但是不再進行 Chaining，而是進行 Evicting，演算法如下：

procedure insert(x) if lookup(x) then return loop MaxLoop times x ? T1[h1(x)] if x = ⊥ then return x ? T2[h2(x)] if x = ⊥ then return end loop rehash(); insert(x)end

Cuckoo Hashing 不使用 Chaining，意味著這是一種 Dynamic Perfect Hashing 的方案。

P.S. Cuckoo Hashing 論文 [4] 中對其所使用的 (μ,k)-universal 哈希函數族有著更進一步的優化。

動態大小調整

隨著哈希表的裝載因子上升，哈希衝突的概率會不斷上升，直到裝載因子超過 1 時，必然發生哈希衝突（抽屜原理）。對於動態哈希表，由於 U 的大小不能預先得知，所以必然需要動態調整哈希表的大小。常見的策略是當裝載因子超過某一閾值後，線性擴展哈希表的大小為原來的若干倍；當裝載因子低於某一閾值時，線性收縮哈希表的大小為原來的若干分之一。使用兩個閾值的原因是為了避免抖動。由於 R 發生變化，因此對應的哈希函數也必須發生變化。調整大小時，另行分配內存，然後將原哈希表中的所有元素 rehash 後存儲到新的哈希表中，這種策略稱為 Copy All 策略。儘管該操作可以均攤到插入操作中，使得整體的均攤時間複雜度仍為一個常數，但是這一策略會帶來較長時間的停頓。為了改善這一問題，又有其他改進策略 [5]，其中較為知名的有：

Linear Hashing
Spiral Storage
Extendible Hashing

哈希表不能夠均勻地增長，其根本原因在於 rehash，只要能夠不 rehash 但是調整 R，就可以解決這一問題。

Linear Hashing

Linear Hashing [5][6] 同時使用 2 個哈希函數來解決動態調整大小的問題。考慮這樣一族哈希函數：

$h_0: U ightarrow {0, 1, dots, N - 1}, h_i: U ightarrow {0, 1, dots, 2^i N - 1}$

對於任意給定的 x∈U 或者有 $h_i(x) = h_{i - 1}(x)$ ，或者有 $h_i(c) = h_{i - 1}(c) + 2^{i - 1} N$ 。一般來說簡單取模即可符合這一要求。

當哈希數組需要擴張大小時，從前向後進行，當前正在擴張的 bucket 下標記為 p。對於在 p 之前的位置，使用 $h_{i + 1}$ ，對於 p 及其之後的位置仍然使用 hi。這樣就可以非常平滑的，每次操作只擴張一個 bucket，而不需要把所有的元素都 rehash。不過這樣做有一個缺點，就是有可能有一個位置上比較靠後的 bucket 一直比較擁擠，經過很多次插入後，才能對這個 bucket 進行擴張以緩解性能下降。對於這一問題，Spiral Storage 的方法處理的比較好。

Spiral Storage

Spiral Storage [5] 總是將負載更多的放在哈希表靠前的位置上，而非均勻地將負載分配到整個哈希表中。這樣儘管是像 Linear Hashing 一樣，總是從哈希表的頭部開始進行 bucket 的分裂，也不會有不及時處理非常滿的 bucket 的問題。

Spiral Storage 的思路是這樣的。哈希表的負載從前向後逐漸降低；擴展大小時，需要將表頭的 bucket 中的元素分配到多個新 bucket 中並添加到哈希表的末尾，並且依然保持負載從前向後逐漸下降的性質。假設每去掉表頭的一個 bucket 就添加 d 個新 bucket，稱 d 為哈希表的增長因子。考慮到哈希表是非線性增加大小的，應該採用一個非線性增長的哈希函數族，將 U 映射到 R。易發現指數函數滿足這樣的性質。為了滿足負載逐漸下降的性質，可以將 u∈U 先均勻的映射到 x∈[S,S+1)，然後再使用指數函數 $y = d^x in R$ 。R 的大小會隨著 S 的變化而指數級增長，並且其中的元素的負載分布是指數級下降的。哈希表擴張時，將原本 $y = d^x, x in [S, S)$ 的元素映射到了新的區間 $y = d^x, x in [S + 1, S + 1)$ ，區間的大小增長了 d。

論文 [5] 中提到了 Spiral Storage 的具體實現細節及一些優化方法。

Extendible Hashing

Extendible Hashing [7] 將 bucket 和 bucket 的索引分別存放，使用 bucket 對應 key 的前綴對其進行索引，這樣在擴展哈希表的大小時，就無需複製所有對象調整索引部分即可。

使用場景

單機場景

在 Facebook F4 這種只讀存儲服務的場景下，或者是批量更新的 Index Serving 場景下，適合使用 Minimal Perfect Hashing 的策略。

對於動態哈希表的使用場景，如果可以預先知道或部分知道數據的分布，則可以針對性的設計哈希函數，以儘可能達到 perfect hashing。

如果沒有關於數據的額外信息，則只能考慮衝突避免策略。在可以保證負載因子較低的情況下，應該盡量選擇 Linear Probing 策略以較好的利用緩存。不能保證負載因子的情況下，如果需要有最壞情況保證的話，應該考慮 Separate Chaining 平衡搜索樹的策略，或者乾脆不使用哈希表。希望獲得較高的裝載因子，同時性能下降不太嚴重，又可以接受一定長尾的話，可以考慮 Cuckoo Hashing。

哈希表的動態大小調整一般選擇 Copy All 策略，這樣對哈希函數的限制最小，實現也最容易。個人感覺 Spiral Storage 要比 Linear Hashing 好一些，原因已在上面 [spiral-better] 說明過。Google 有一個 Spiral Storage 的開源實現： https://code.google.com/p/sparsehash/ 。PostgreSQL 中使用 Linear Hashing，見 https://www.postgresql.org/docs/8.0/static/sql-createindex.html 。

多機場景

哈希函數的選擇同單機場景。這裡只討論動態大小調整的問題。

儘管在早期有將 Linear Hashing 和 Extendible Hashing 擴展到多機的嘗試 [8][9]，但是最終被一致性哈希所統治。多機場景下，由於不希望出現單點瓶頸，所以使用 P2P 結構，更多的問題在於如何快速的將請求匹配到實際存儲數據的節點。這一問題被歸類為如何將對等節點自組織成某種結構，並在其上進行消息路由，這方面的總結見論文筆記：關於 P2P 的一些綜述。這些路由演算法的時間複雜度一般都是 O(logn) 級別的。對於 LAN 環境下的快速查找場景，尤其是使用哈希表的情況下，我們一般期望常數級別的時間複雜度，這方面可以參考 [10][11]，或者是乾脆緩存所有節點的映射信息。

哈希表的動態大小調整，個人覺得 Amazon Dynamo [12] 做的比較好，最近 Google 也出了一篇論文 [13] 似乎能保證移動數據量的上界。

其他

因為哈希表一般需要保持較低的負載因子，在哈希表較大時元素會非常稀疏。如果需要支持 scan 操作的話，需要考慮在非空 bucket 之間建立聯繫。

如果不在乎計算複雜度的話，可以使用密碼學哈希函數（Cryptographic hash function）以獲得較為均勻的結果。

References

[1] Martin Dietzfelbinger. (2007). Design Strategies for Minimal Perfect Hash Functions. Stochastic Algorithms: Foundations and Applications. SAGA 2007. Lecture Notes in Computer Science, vol 4665. https://doi.org/10.1007/978-3-540-74871-7_2

[2] Carter, J. L., & Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences, 18(2), 143–154. https://doi.org/10.1016/0022-0000(79)90044-8

[3] Wegman, M. N., & Carter, J. L. (1981). New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22(3), 265–279. https://doi.org/10.1016/0022-0000(81)90033-7

[4] Pagh, R., & Rodler, F. F. (2004). Cuckoo hashing. Journal of Algorithms, 51(2), 122–144. https://doi.org/10.1016/J.JALGOR.2003.12.002

[5] Larson, P.-A. (1988). Dynamic hash tables. Communications of the ACM, 31(4), 446–457. https://doi.org/10.1145/42404.42410

[6] Hiemstra, D., Kushmerick, N., Domeniconi, C., Paice, C. D., Carroll, M. W., Jensen, C. S., … Mankovskii, S. (2009). Linear Hashing. In Encyclopedia of Database Systems (Vol. 0, pp. 1619–1622). Boston, MA: Springer US. https://doi.org/10.1007/978-0-387-39940-9_742

[7] Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, and H. Raymond Strong. 1979. Extendible hashing?—?a fast access method for dynamic files. ACM Trans. Database Syst. 4, 3 (1979), 315–344. https://doi.org/10.1145/320083.320092

[8] Witold Litwin, Marie-Anne Neimat, and Donovan A Schneider. 1993. LH*: Linear Hashing for distributed files. Proc. 1993 ACM SIGMOD Int. Conf. Manag. data (1993), 327–336. https://doi.org/10.1145/170035.170084

[9] Victoria Hilford, Farokh B. Bastani, and Bojan Cukic. 1997. EH* - Extendible Hashing in a distributed environment. Proc. - IEEE Comput. Soc. Int. Comput. Softw. Appl. Conf. (1997).

[10] Venugopalan Ramasubramanian and Emin Gun Sirer. 2004. Beehive: O(1)lookup performance for power-law query distributions in peer-to-peer overlays. System 1, 1 (2004), 8. Retrieved from http://portal.acm.org/citation.cfm?id=1251175.1251183

[11] Tonglin Li, Xiaobing Zhou, Kevin Brandstatter, Dongfang Zhao, Ke Wang, Anupam Rajendran, Zhao Zhang, and Ioan Raicu. 2013. ZHT: A light-weight reliable persistent dynamic scalable zero-hop distributed hash table. Proc. - IEEE 27th Int. Parallel Distrib. Process. Symp. IPDPS 2013 (2013), 775–787. https://doi.org/10.1109/IPDPS.2013.110

[12] Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. 2007. Dynamo: Amazon』s Highly Available Key-value Store. Proc. Symp. Oper. Syst. Princ. (2007), 205–220. https://doi.org/10.1145/1323293.1294281

[13] Vahab Mirrokni, Mikkel Thorup, and Morteza Zadimoghaddam. 2016. Consistent Hashing with Bounded Loads. (2016), 587–604. Retrieved from [1608.01350] Consistent Hashing with Bounded Loads