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

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

　　hash表中key的分布規(guī)律

　　當(dāng)hash表中key和bucket數(shù)量一樣時（n/b=1）：

　　37% 的bucket是空的

　　37% 的bucket里只有1個key

　　26% 的bucket里有1個以上的key（hash沖突）

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

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

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

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

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

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

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

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

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

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

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