關(guān)于HashMap的一些思考
點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號”
優(yōu)質(zhì)文章，第一時間送達(dá)
作者 | 蝸牛大師
來源 | urlify.cn/na6vae
一、HashMap的負(fù)載因子的作用
當(dāng) HashMap 中的元素個數(shù)（包含鏈表、紅黑樹上的元素）達(dá)到數(shù)組長度的0.75倍的時候，開始擴(kuò)容。
二、HashMap的負(fù)載因子為什么是0.75
主要是為了提高空間利用率和減少查詢成本（也可以說是盡可能減少hash沖突）。
三、為什么槽位數(shù)必須使用2^n
如果想讓 Hash 結(jié)果分布更加均勻，首先想到的就是使用取余（%）操作。重點(diǎn)來了：“取余(%)操作中如果除數(shù)是2的冪次則等價于與其除數(shù)減一的與(&)操作（也就是說 hash % length == hash & (length - 1) 的前提是 length 是 2 的 n 次方）?！?并且采用二進(jìn)制位操作 &，相對于 % 能夠提高運(yùn)算效率，這就解釋了 HashMap 的長度為什么是 2 的冪次方。
四、解決Hash沖突的方法
1、開放地址法
公式：fi(key) = (f(key)+di) MOD m (di=0,1,2,3,......,m-1)
key：待放入數(shù)組（hash表）的元素；m：數(shù)組長度
當(dāng)沖突發(fā)生時，使用某種探測技術(shù)在散列表中形成一個探測序列。沿此序列逐個單元地查找，直到找到給定的關(guān)鍵字，或者碰到一個開放的地址（即該地址單元為空）為止（若要插入，在探查到開放的地址，則可將待插入的新結(jié)點(diǎn)存人該地址單元）。查找時探測到開放的地址則表明表中無待查的關(guān)鍵字，即查找失敗。
（1）線性探測法
思想是：通過公式計算出元素在數(shù)組中的下標(biāo)，如果下標(biāo)上沒有元素，直接放進(jìn)去；如果下標(biāo)中有元素，則公式中的 di 依次 +1 重新計算，直到查找到?jīng)]有元素的下標(biāo)。不然數(shù)組就滿了，需要擴(kuò)容。
（2）二次探測法
思想是：通過改變 di 的計算方式來查詢沒有元素的下標(biāo)，具體計算方式就是 di=-12,12,-22,22,…,-(q * 10 + 2),(q * 10 + 2)，q <=m / 2。至于這個 di 的取值我也沒研究，摘抄過來的，但是這個探測法的思想得知道。
考慮的情況是，如果通過公式計算出來下標(biāo)之后的所有下標(biāo)都有元素占據(jù)了，而這個下標(biāo)的前面的有空閑的，通過第一種方法可以算出來，但是計算的次數(shù)比較多，通過這個方法可以減少計算次數(shù)。
（3）偽隨機(jī)數(shù)探測再散列
思想是：di 的值是通過隨機(jī)函數(shù)得到的。如果隨機(jī)函數(shù)的種子相同，那么得出來的 di 也相同，查詢就ok了。
總之，開放定址法只要在散列表未填滿時，總是能找到不發(fā)生沖突的地址，是我們常用的解決沖突的辦法。
2、拉鏈法
就是當(dāng)產(chǎn)生 Hash 沖突時，在沖突的節(jié)點(diǎn)上形成鏈表，HashMap 就是使用的拉鏈法解決的 Hash 沖突。
五、為什么鏈表長度達(dá)到 8 的時候就要轉(zhuǎn)為紅黑樹了？
當(dāng)使用 0.75 作為負(fù)載因子時，鏈表中的長度達(dá)到 8 幾乎是不可能的，均衡策略吧。
引用 HashMap 源碼中的注釋：
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
六、HashMap擴(kuò)容時元素的位置發(fā)生了什么變化？
分為三種情況：
對于數(shù)組上的元素：直接使用已經(jīng)計算出來的hash值重新計算新下標(biāo)放入新數(shù)組。
對于鏈表：將一條鏈表拆分為兩條，hash值大于數(shù)組長度的新鏈表放在新數(shù)組，小于的就放在原數(shù)組。
對于紅黑樹：將數(shù)拆為兩條鏈表，hash值大于數(shù)組長度的新鏈表放在新數(shù)組，小于的就放在原數(shù)組，最后，重新判斷兩條鏈表是否需要轉(zhuǎn)為紅黑樹。
關(guān)鍵代碼：
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
例如：oldCap 是 16，那么擴(kuò)容之后的新數(shù)組長度就是 32，鏈表上的元素分別是 7,23,39。（整數(shù)的hash值就是本身）
7 ：0000 0111
& 16：0001 0000
---------------
= ：0000 0000 # 0，仍舊在原位
17：0001 0001
& 16：0001 0000
---------------
= ：0001 0000 # 非0，需要放在 [17, 32) 之間
23：0001 0111
& 16：0001 0000
---------------
= ：0001 0000 # 非0，需要放在 [17, 32) 之間
39：0010 0111
& 16：0001 0000
---------------
= ：0000 0000 # 0，仍舊在原位，因為它的的值大于數(shù)組的長度
粉絲福利：Java從入門到入土學(xué)習(xí)路線圖
??????
??長按上方微信二維碼 2 秒
感謝點(diǎn)贊支持下哈 