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

baishancloud

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

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

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

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

· 37% 的bucket是空的

· 37% 的bucket里只有1個(gè)key

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

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

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

而實(shí)際上，bucket里key的分布在n較小時(shí)非常不均勻；當(dāng)n增大時(shí)，才會(huì)逐漸趨于平均。

key的數(shù)量對(duì)3類(lèi)bucket數(shù)量的影響

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

更直觀一點(diǎn)，我們用下圖來(lái)展示空bucket率和沖突率隨n/b值的變化趨勢(shì)：

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

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

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

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

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

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

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

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

未使用統(tǒng)計(jì)中常用的均方差法去描述key分布的不均勻程度，是因?yàn)檐浖�開(kāi)發(fā)過(guò)程中，更多時(shí)候要考慮最壞情況下所需準(zhǔn)備的內(nèi)存等資源。

Load Factor：n/b<0.75

hash表中常用一個(gè)概念 load factor α=n/b，來(lái)描述hash表的特征。

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

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

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

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

hash表特性小貼士：

· hash表本身是一個(gè)通過(guò)一定的空間浪費(fèi)來(lái)?yè)Q取效率的算法。低時(shí)間開(kāi)銷(xiāo)(O(1))、低空間浪費(fèi)、低沖突率，三者不可同時(shí)兼得；

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

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

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

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

· hash表在n/b較小時(shí)，不會(huì)均勻分配key。

Load Factor：n/b>1

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

鏈表只在n/b不是很大時(shí)適用。因?yàn)殒湵淼牟檎倚枰?/font>O(n)的時(shí)間開(kāi)銷(xiāo)，對(duì)于非常大的n/b，有時(shí)會(huì)用tree替代鏈表來(lái)管理bucket內(nèi)的key。

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

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

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

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

avg=n/b

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

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

結(jié)論:

計(jì)算

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

每類(lèi)bucket的數(shù)量




空bucket 數(shù)量

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

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

已知：

空bucket率是：

空bucket數(shù)量為：

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

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

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

多個(gè)key的bucket

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

key在bucket中分布的均勻程度

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

這就是著名的二項(xiàng)式分布。

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

通過(guò)正態(tài)分布來(lái)近似

當(dāng) n, b 都很大時(shí)，二項(xiàng)式分布可以用正態(tài)分布來(lái)近似估計(jì)key分布的均勻性：

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

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

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

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

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

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

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

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

x可以認(rèn)為這個(gè)x就是bucket里key數(shù)量的最小值，而這個(gè)hash表中，不均勻的程度可以用key數(shù)量最大值與最小值的差異來(lái)描述: 因?yàn)檎龖B(tài)分布是對(duì)稱(chēng)的，所以key數(shù)量的最大值可以用 μ + (μ-x) 來(lái)表示。最終，bucket中key數(shù)量最大值與最小值的比例就是：

（μ是均值n/b）

程序模擬

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