程序員必讀: 摸清Hash表的脾性

baishancloud

作者簡介：
張炎潑（XP）
    白山云科技合伙人兼研發(fā)副總裁，綽號XP。
張炎潑先生于2016年加入白山云科技，主要負責對象存儲研發(fā)、數(shù)據(jù)跨機房分布和修復(fù)問題解決等工作。以實現(xiàn)100PB級數(shù)據(jù)存儲為目標，其帶領(lǐng)團隊完成全網(wǎng)分布存儲系統(tǒng)的設(shè)計、實現(xiàn)與部署工作，將數(shù)據(jù)“冷”“熱”分離，使冷數(shù)據(jù)成本壓縮至1.2倍冗余度。
張炎潑先生2006年至2015年，曾就職于新浪，負責Cross-IDC PB級云存儲服務(wù)的架構(gòu)設(shè)計、協(xié)作流程制定、代碼規(guī)范和實施標準制定及大部分功能實現(xiàn)等工作，支持新浪微博、微盤、視頻、SAE、音樂、軟件下載等新浪內(nèi)部存儲等業(yè)務(wù)；2015年至2016年，于美團擔任高級技術(shù)專家，設(shè)計了跨機房的百PB對象存儲解決方案：設(shè)計和實現(xiàn)高并發(fā)和高可靠的多副本復(fù)制策略，優(yōu)化Erasure Code降低90%IO開銷。

軟件開發(fā)中，一個hash表相當于把n個key隨機放入到b個bucket中，以實現(xiàn)n個數(shù)據(jù)在b個單位空間的存儲。

我們發(fā)現(xiàn)hash表中存在一些有趣現(xiàn)象：

hash表中key的分布規(guī)律當hash表中key和bucket數(shù)量一樣時（n/b=1）：

· 37% 的bucket是空的

· 37% 的bucket里只有1個key

· 26% 的bucket里有1個以上的key(hash沖突)

下圖直觀的展示了當n=b=20時，hash表里每個bucket中key的數(shù)量（按照key的數(shù)量對bucket做排序）：

往往我們對hash表的第一感覺是：如果將key隨機放入所有的bucket，bucket中key的數(shù)量較為均勻，每個bucket里key數(shù)量的期望是1。

而實際上，bucket里key的分布在n較小時非常不均勻；當n增大時，才會逐漸趨于平均。

key的數(shù)量對3類bucket數(shù)量的影響

下表表示當b不變，n增大時，n/b的值如何影響3類bucket的數(shù)量占比（沖突率即含有多于1個key的bucket占比)：

更直觀一點，我們用下圖來展示空bucket率和沖突率隨n/b值的變化趨勢：

key數(shù)量對bucket均勻程度的影響

上面幾組數(shù)字是當n/b較小時有意義的參考值，但隨n/b逐漸增大，空bucket與1個key的bucket數(shù)量幾乎為0，絕大多數(shù)bucket含有多個key。

當n/b超過1（1個bucket允許存儲多個key)， 我們主要觀察的對象就轉(zhuǎn)變成bucket里key數(shù)量的分布規(guī)律。

下表表示當n/b較大，每個bucket里key的數(shù)量趨于均勻時，不均勻的程度是多少。

為了描述這種不均勻的程度，我們使用bucket中key數(shù)量的最大值和最小值之間的比例（(most-fewest)/most)來表示。

下表列出了b=100時，隨n增大，key的分布情況。

可以看出，隨著bucket里key平均數(shù)量的增加，其分布的不均勻程度也逐漸降低。

和空bucket或1個key的bucket的占比不同，均勻程度不僅取決于n/b的值，也受b值的影響，后面會提到。

未使用統(tǒng)計中常用的均方差法去描述key分布的不均勻程度，是因為軟件開發(fā)過程中，更多時候要考慮最壞情況下所需準備的內(nèi)存等資源。

Load Factor：n/b<0.75

hash表中常用一個概念 load factor α=n/b，來描述hash表的特征。

通常，基于內(nèi)存存儲的hash表，它的 n/b ≤0.75。這樣設(shè)定，既可節(jié)省空間，也可以保持key的沖突率相對較低，低沖突率意味著低頻率的hash重定位，hash表的插入會更快。

線性探測是一個經(jīng)常被使用的解決插入時hash沖突的算法，它在1個bucket出現(xiàn)沖突時，按照逐步增加的步長順序向后查看這個bucket后面的bucket，直到找到1個空bucket。因此它對hash的沖突非常敏感。

在n/b=0.75 這個場景中，如果不使用線性探測（譬如使用bucket內(nèi)的鏈表來保存多個key)，大約有47% 的bucket是空的；如果使用線性探測，這47%的bucket中，大約一半的bucket會被線性探測填充。

在很多內(nèi)存hash表的實現(xiàn)中，選擇n/b<=0.75作為hash表的容量上限，不僅是考慮到?jīng)_突率隨n/b增大而增大，更重要的是線性探測的效率會隨著n/b的增大而迅速降低。

hash表特性小貼士：

· hash表本身是一個通過一定的空間浪費來換取效率的算法。低時間開銷(O(1))、低空間浪費、低沖突率，三者不可同時兼得；

· hash表只適合純內(nèi)存數(shù)據(jù)結(jié)構(gòu)的存儲：

° hash表通過空間浪費換取了訪問速度的提升；磁盤的空間浪費是無法忍受的，但對內(nèi)存的少許浪費是可接受的；

° hash表只適合隨機訪問快的存儲介質(zhì)。硬盤上的數(shù)據(jù)存儲更多使用btree或其他有序的數(shù)據(jù)結(jié)構(gòu)。

· 多數(shù)高級語言（內(nèi)建hash table、hash set等)都保持 n/b≤0.75；

· hash表在n/b較小時，不會均勻分配key。

Load Factor：n/b>1

另外一種hash表的實現(xiàn)，專門用來存儲比較多的key，當 n/b>1時，線性探測失效（沒有足夠的bucket存儲每個key)。這時1個bucket里不僅存儲1個key，一般在一個bucket內(nèi)用chaining，將所有落在這個bucket的key用鏈表連接起來，來解決沖突時多個key的存儲。

鏈表只在n/b不是很大時適用。因為鏈表的查找需要O(n)的時間開銷，對于非常大的n/b，有時會用tree替代鏈表來管理bucket內(nèi)的key。

n/b值較大的使用場景之一是：將一個網(wǎng)站的用戶隨機分配到多個不同的web-server上，這時每個web-server可以服務(wù)多個用戶。多數(shù)情況下，我們都希望這種分配能盡可能均勻，從而有效利用每個web-server資源。

這就要求我們關(guān)注hash的均勻程度。因此，接下來要討論的是，假定hash函數(shù)完全隨機的，均勻程度根據(jù)n和b如何變化。

n/b 越大，key的分布越均勻

當 n/b 足夠大時，空bucket率趨近于0，且每個bucket中key的數(shù)量趨于平均。每個bucket中key數(shù)量的期望是：

avg=n/b

定義一個bucket平均key的數(shù)量是100%：bucket中key的數(shù)量剛好是n/b，下圖分別模擬了 b=20，n/b分別為 10、100、1000時，bucket中key的數(shù)量分布。

可以看出，當 n/b 增大時，bucket中key數(shù)量的最大值與最小值差距在逐漸縮小。下表列出了隨b和n/b增大，key分布的均勻程度的變化：

結(jié)論:

計算

上述大部分結(jié)果來自于程序模擬，現(xiàn)在我們來解決從數(shù)學(xué)上如何計算這些數(shù)值。

每類bucket的數(shù)量




空bucket 數(shù)量

對于1個key, 它不在某個特定的bucket的概率是 (b−1)/b

所有key都不在某個特定的bucket的概率是( (b−1)/b)n

已知：

空bucket率是：

空bucket數(shù)量為：

有1個key的bucket數(shù)量

n個key中，每個key有1/b的概率落到某個特定的bucket里，其他key以1-(1/b)的概率不落在這個bucket里，因此，對某個特定的bucket，剛好有1個key的概率是：

剛好有1個key的bucket數(shù)量為：

多個key的bucket

剩下即為含多個key的bucket數(shù)量：

key在bucket中分布的均勻程度

類似的，1個bucket中剛好有i個key的概率是：n個key中任選i個，并都以1/b的概率落在這個bucket里，其他n-i個key都以1-1/b的概率不落在這個bucket里，即：

這就是著名的二項式分布。

我們可通過二項式分布估計bucket中key數(shù)量的最大值與最小值。

通過正態(tài)分布來近似

當 n, b 都很大時，二項式分布可以用正態(tài)分布來近似估計key分布的均勻性：

p=1/b，1個bucket中剛好有i個key的概率為：

1個bucket中key數(shù)量不多于x的概率是：

所以, 所有不多于x個key的bucket數(shù)量是：

bucket中key數(shù)量的最小值，可以這樣估算: 如果不多于x個key的bucket數(shù)量是1，那么這唯一1個bucket就是最少key的bucket。我們只要找到1個最小的x，讓包含不多于x個key的bucket總數(shù)為1, 這個x就是bucket中key數(shù)量的最小值。

計算key數(shù)量的最小值 x

一個bucket里包含不多于x個key的概率是：

Φ(x) 是正態(tài)分布的累計分布函數(shù)，當x-μ趨近于0時，可以使用以下方式來近似：

這個函數(shù)的計算較難，但只是要找到x，我們可以在[0~μ]的范圍內(nèi)逆向遍歷x，以找到一個x 使得包含不多于x個key的bucket期望數(shù)量是1。

x可以認為這個x就是bucket里key數(shù)量的最小值，而這個hash表中，不均勻的程度可以用key數(shù)量最大值與最小值的差異來描述: 因為正態(tài)分布是對稱的，所以key數(shù)量的最大值可以用 μ + (μ-x) 來表示。最終，bucket中key數(shù)量最大值與最小值的比例就是：

（μ是均值n/b）

程序模擬

以下python腳本模擬了key在bucket中分布的情況，同時可以作為對比，驗證上述計算結(jié)果。