軟件開發(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類bucket數(shù)量的影響

　　下表表示當(dāng)b不變，n增大時(shí)，n/b的值如何影響3類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)表示。