hash表的實現原理
軟件開發中，一個hash表相當于把n個key隨機放入到b個bucket中，以實現n個數據在b個單位空間的存儲。
我們發現hash表中存在一些有趣現象：
hash表中key的分布規律
當hash表中key和bucket數量一樣時（n/b=1）：
37% 的bucket是空的
37% 的bucket里只有1個key
26% 的bucket里有1個以上的key（hash沖突）
下圖直觀的展示了當n=b=20時，hash表里每個bucket中key的數量（按照key的數量對bucket做排序）：
往往我們對hash表的第一感覺是：如果將key隨機放入所有的bucket，bucket中key的數量較為均勻，每個bucket里key數量的期望是1。
而實際上，bucket里key的分布在n較小時非常不均勻；當n增大時，才會逐漸趨于平均。
key的數量對3類bucket數量的影響
下表表示當b不變，n增大時，n/b的值如何影響3類bucket的數量占比（沖突率即含有多于1個key的bucket占比）：
更直觀一點，我們用下圖來展示空bucket率和沖突率隨n/b值的變化趨勢：
key數量對bucket均勻程度的影響
上面幾組數字是當n/b較小時有意義的參考值，但隨n/b逐漸增大，空bucket與1個key的bucket數量幾乎為0，絕大多數bucket含有多個key。
當n/b超過1（1個bucket允許存儲多個key）， 我們主要觀察的對象就轉變成bucket里key數量的分布規律。
下表表示當n/b較大，每個bucket里key的數量趨于均勻時，不均勻的程度是多少。
為了描述這種不均勻的程度，我們使用bucket中key數量的最大值和最小值之間的比例（（most-fewest）/most）來表示。
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%