一、概述

在上一篇文章中，我們分析了HashMap中增刪改查的流程，但這是遠(yuǎn)遠(yuǎn)不夠的，所以在本文中，我們將根據(jù)一些常見問題并結(jié)合源碼來進(jìn)行更具體的分析。

二、常見問題

1. HashMap的數(shù)組長度為什么必須是2的冪？
2. HashMap的默認(rèn)負(fù)載因子是多少，作用是什么？
3. HashMap的默認(rèn)負(fù)載因子為什么是0.75？
4. HashMax數(shù)組最大長度是多少？
5. 什么叫做Hash碰撞？
6. HashMap何時(shí)擴(kuò)容？
7. Jdk 1.8為什么加入了紅黑樹？
8. 什么時(shí)候由鏈表轉(zhuǎn)為紅黑樹？

三、問題解析

1. HashMap的數(shù)組長度為什么必須是2的冪？

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

通過上面的源碼注釋中，就已經(jīng)寫明了：必須是 2 的冪，這是為什么？源碼也不是我們寫的，我們也不知道，不過我們根據(jù)數(shù)組的長度的使用來進(jìn)行分析，在HashMap的putVal方法中，有這樣一段代碼：

n = (tab = resize()).length;
p = tab[i = (n - 1) & hash]

這里的n為數(shù)組的長度，p為計(jì)算出來的下標(biāo)，下標(biāo)通過(16-1) & hash 進(jìn)行計(jì)算的。就是15&hash，我們反向來思考問題，如果數(shù)組長度為15呢？我們來看下圖：

01.png

可以看到，當(dāng)數(shù)組長度為15時(shí)，通過&運(yùn)算，最終計(jì)算出來的下標(biāo)為：0，2，4，6，8，10，12，14，且均發(fā)生了哈希碰撞。那這時(shí)候數(shù)組的1 3 5 7 9 11 位置上不就存不上數(shù)據(jù)了嘛。

接下來我們再看當(dāng)數(shù)組長度為2的冪次方時(shí)的結(jié)果：我們用2的3次方，長度為8舉例

02.png

可以看到，當(dāng)長度為2的冪時(shí)，最終算出的下標(biāo)是均勻分布的，并沒有發(fā)生哈希碰撞。
細(xì)心的人可以發(fā)現(xiàn)，當(dāng)數(shù)組長度不為2的冪時(shí)，二進(jìn)制的最后一位總是為0，這就導(dǎo)致不管hash為多少，最終算出來總是雙數(shù)，進(jìn)而導(dǎo)致了數(shù)組分布不均，有些位置永遠(yuǎn)用不到。

所以：數(shù)組長度為2的冪，是為了減少哈希碰撞，是數(shù)組分布更均勻。

2. HashMap的默認(rèn)負(fù)載因子是多少，作用是什么？

static final float DEFAULT_LOAD_FACTOR = 0.75f;

newCap = DEFAULT_INITIAL_CAPACITY;
float ft = (float)newCap * loadFactor;

默認(rèn)的加載因子為0.75，它與HashMap的擴(kuò)容機(jī)制相關(guān)，當(dāng)數(shù)組長度大于16*0.75=12時(shí)，數(shù)組就會(huì)擴(kuò)容，并不是到達(dá)16時(shí)才會(huì)擴(kuò)容。它決定了HashMap擴(kuò)容的時(shí)機(jī)。

3. HashMap的默認(rèn)負(fù)載因子為什么是0.75？

上面提到了數(shù)組擴(kuò)容是由 長度加載因子，得到一個(gè)閾值，當(dāng)長度達(dá)到這個(gè)閾值時(shí)就會(huì)擴(kuò)容，如果加載因子為1，那就是161,即數(shù)組長度達(dá)到16時(shí)才會(huì)擴(kuò)容，但是這樣會(huì)犧牲時(shí)間效率，如果加載因子0.5時(shí)，那么長度為8時(shí)就擴(kuò)容了，此時(shí)就會(huì)導(dǎo)致數(shù)組中空間利用率降低，所以0.75是一個(gè)比較合適的值。

4. HashMax數(shù)組最大長度是多少？

static final int MAXIMUM_CAPACITY = 1 << 30;

HashMap數(shù)組最大長度為：2的30次冪，1073741824

5. 什么叫做Hash碰撞？

在HashMap中，Hash碰撞就是指計(jì)算出的hash值相同。

6. HashMap何時(shí)擴(kuò)容？

n = (tab = resize()).length; //629行

if (++size > threshold)
            resize();  //663行

在HashMap中，擴(kuò)容由resize()方法完成，
在首次調(diào)用put時(shí)，會(huì)執(zhí)行resize()方法初始化，put之后判斷數(shù)量是否大于閾值，如果大于閾值則擴(kuò)容，
后續(xù)調(diào)用會(huì)直接存入數(shù)據(jù)，然后再判斷數(shù)量是否大于閾值，如果大于閾值則擴(kuò)容，
當(dāng)數(shù)組長度大于加載因子*數(shù)組長度時(shí)，則會(huì)擴(kuò)容。

7. Jdk 1.8為什么加入了紅黑樹？

再Jdk1.7中，HashMap是通過數(shù)組+鏈表實(shí)現(xiàn)的，Jdk1.8中加入了紅黑樹，只有當(dāng)數(shù)組中鏈表的長度大于8時(shí)，才會(huì)轉(zhuǎn)為紅黑樹，紅黑樹相比于鏈表在插入和刪除的操作上，要比鏈表更快，如果說鏈表長度為100時(shí)，那么HashMap要循環(huán)99次才能找到最后一個(gè)節(jié)點(diǎn)，再執(zhí)行插入操作，刪除同理。

8. 什么時(shí)候由鏈表轉(zhuǎn)為紅黑樹？

 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);


if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  64
            resize();

當(dāng)鏈表的長度大于8時(shí)執(zhí)行樹化的方法，隨后如果數(shù)組長度小于64時(shí)，則會(huì)擴(kuò)容，反之轉(zhuǎn)換為紅黑樹。
所以 當(dāng)鏈表長度大于8時(shí) 且 數(shù)組長度小于64時(shí)才會(huì)將鏈表轉(zhuǎn)為紅黑樹。