hash表的實(shí)現(xiàn)原理
推薦 + 挑錯(cuò) + 收藏(0) + 用戶評(píng)論（0）
軟件開發(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表的第一感覺是：如果將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)，我們用下圖來展示空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超過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）來表示。
非常好我支持^.^
(0) 0%
不好我反對(duì)
(0) 0%