一、HashMap的負(fù)載因子的作用

當(dāng) HashMap 中的元素個數(shù)（包含鏈表、紅黑樹上的元素）達(dá)到數(shù)組長度的0.75倍的時候，開始擴容。

二、HashMap的負(fù)載因子為什么是0.75

主要是為了提高空間利用率和減少查詢成本（也可以說是盡可能減少hash沖突）。

三、為什么槽位數(shù)必須使用2^n

如果想讓 Hash 結(jié)果分布更加均勻，首先想到的就是使用取余（%）操作。重點來了：“取余(%)操作中如果除數(shù)是2的冪次則等價于與其除數(shù)減一的與(&)操作（也就是說 hash % length == hash & (length - 1) 的前提是 length 是 2 的 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é)點存人該地址單元）。查找時探測到開放的地址則表明表中無待查的關(guān)鍵字，即查找失敗。

（1）線性探測法

思想是：通過公式計算出元素在數(shù)組中的下標(biāo)，如果下標(biāo)上沒有元素，直接放進去；如果下標(biāo)中有元素，則公式中的 di 依次 +1 重新計算，直到查找到?jīng)]有元素的下標(biāo)。不然數(shù)組就滿了，需要擴容。

（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）偽隨機數(shù)探測再散列

思想是：di 的值是通過隨機函數(shù)得到的。如果隨機函數(shù)的種子相同，那么得出來的 di 也相同，查詢就ok了。

總之，開放定址法只要在散列表未填滿時，總是能找到不發(fā)生沖突的地址，是我們常用的解決沖突的辦法。

2、拉鏈法

就是當(dāng)產(chǎn)生 Hash 沖突時，在沖突的節(jié)點上形成鏈表，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擴容時元素的位置發(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，那么擴容之后的新數(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 秒

感謝點贊支持下哈

關(guān)于HashMap的一些思考