一、前言

??最近在閱讀HashMap的源碼，已經(jīng)將代碼基本過(guò)了一遍，對(duì)它的實(shí)現(xiàn)已經(jīng)有了一個(gè)較為全面的認(rèn)識(shí)。今天就來(lái)分享一下HashMap中比較重要的一個(gè)方法——resize方法。我將對(duì)resize方法的源代碼進(jìn)行逐句的分析。

??若想要看懂這個(gè)方法的源代碼，首先得對(duì)HashMap的底層結(jié)構(gòu)和實(shí)現(xiàn)有一個(gè)清晰的認(rèn)識(shí)，若不清楚的，可以看看我之前寫(xiě)的一篇博客，這篇博客對(duì)HashMap的底層結(jié)構(gòu)和實(shí)現(xiàn)進(jìn)行了一個(gè)比較清晰和全面的講解，同時(shí)博客的最底下附上了兩篇阿里架構(gòu)師對(duì)HashMap的分析，寫(xiě)的非常好，很有參考價(jià)值：

• Hexo鏈接 —— HashMap源碼解讀——深入理解HashMap高效的原因
• 博客園鏈接 —— http://www.rzrgm.cn/tuyang1129/p/12362959.html

二、解析

?2.1 resize方法的作用

??沒(méi)有閱讀過(guò)HashMap源碼的人可能并不知道它有一個(gè)叫resize的方法，因?yàn)檫@不是一個(gè)public方法，這個(gè)方法并沒(méi)有加上訪問(wèn)修飾符，也就是說(shuō)，這個(gè)方法HashMap所在的包下使用。很多人應(yīng)該都知道，HashMap的基本實(shí)現(xiàn)是數(shù)組+鏈表（從JDK1.8開(kāi)始已經(jīng)變成了數(shù)組+鏈表+紅黑樹(shù)），而這個(gè)方法的作用也很簡(jiǎn)單：

1. 當(dāng)數(shù)組并未初始化時(shí)，對(duì)數(shù)組進(jìn)行初始化；
2. 若數(shù)組已經(jīng)初始化，則對(duì)數(shù)組進(jìn)行擴(kuò)容，也就是創(chuàng)建一個(gè)兩倍大小的新數(shù)組，并將原來(lái)的元素放入新數(shù)組中；

?2.2 resize方法中用到的變量

??HashMap中定義了很多的成員變量，而很多都在resize方法中有用到，所以為了看懂這個(gè)方法，首先需要了解這些變量的含義：

• table：用來(lái)存儲(chǔ)數(shù)據(jù)的數(shù)組，即數(shù)組+鏈表結(jié)構(gòu)的數(shù)組部分；
• threshold：閾值，表示當(dāng)前允許存入的元素?cái)?shù)量，當(dāng)元素?cái)?shù)量超過(guò)這個(gè)值時(shí)，將進(jìn)行擴(kuò)容；
• MAXIMUM_CAPACITY：HashMap允許的最大容量，值為1<<30，也就是2^30；
• DEFAULT_INITIAL_CAPACITY：HashMap的默認(rèn)初始容量，值為16；
• loadFactor：負(fù)載因子，表示HashMap中的元素?cái)?shù)量可以到達(dá)總?cè)萘康陌俜种嗌?，默認(rèn)是75%，也就是說(shuō)，默認(rèn)情況下，當(dāng)元素?cái)?shù)量達(dá)到總?cè)萘康?code>75%時(shí)，將進(jìn)行擴(kuò)容；
• DEFAULT_LOAD_FACTOR：負(fù)載因子的默認(rèn)值，也就是0.75；

?2.3 resize方法源碼解讀

??下面就來(lái)看看resize方法的源碼吧，我用注釋的方式，對(duì)每一句代碼進(jìn)行了解讀：

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final HashMap.Node<K,V>[] resize() {
    HashMap.Node<K,V>[] oldTab = table;
    // 記錄Map當(dāng)前的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 記錄Map允許存儲(chǔ)的元素?cái)?shù)量，即閾值（容量*負(fù)載因子）
    int oldThr = threshold;
    // 聲明兩個(gè)變量，用來(lái)記錄新的容量和閾值
    int newCap, newThr = 0;

    // 若當(dāng)前容量不為0，表示存儲(chǔ)數(shù)據(jù)的數(shù)組已經(jīng)被初始化過(guò)
    if (oldCap > 0) {
        // 判斷當(dāng)前容量是否超過(guò)了允許的最大容量
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 若超過(guò)最大容量，表示無(wú)法再進(jìn)行擴(kuò)容
            // 則更新當(dāng)前的閾值為int的最大值，并返回舊數(shù)組
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 將舊容量*2得到新容量，若新容量未超過(guò)最大值，并且舊容量大于默認(rèn)初始容量（16），
        // 才則將舊閾值*2得到新閾值
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }

    // 若不滿足上面的oldCap > 0，表示數(shù)組還未初始化，
    // 若當(dāng)前閾值不為0，就將數(shù)組的新容量記錄為當(dāng)前的閾值；
    // 為什么這里的oldThr在未初始化數(shù)組的時(shí)候就有值呢？
    // 這是因?yàn)镠ashMap有兩個(gè)帶參構(gòu)造器，可以指定初始容量，
    // 若你調(diào)用了這兩個(gè)可以指定初始容量的構(gòu)造器，
    // 這兩個(gè)構(gòu)造器就會(huì)將閾值記錄為第一個(gè)大于等于你指定容量，且滿足2^n的數(shù)（可以看看這兩個(gè)構(gòu)造器）
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 若上面的條件都不滿足，表示你是調(diào)用默認(rèn)構(gòu)造器創(chuàng)建的HashMap，且還沒(méi)有初始化table數(shù)組
    else {               // zero initial threshold signifies using defaults
        // 則將新容量更新為默認(rèn)初始容量（10）
        // 閾值即為（容量*負(fù)載因子）
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 經(jīng)過(guò)上面的步驟后，newCap一定有值，但是若運(yùn)行的是上面的第二個(gè)分支時(shí)，newThr還是0
    // 所以若當(dāng)前newThr還是0，則計(jì)算出它的值（容量*負(fù)載因子）
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }

    // 將計(jì)算出的新閾值更新到成員變量threshold上
    threshold = newThr;

    // 創(chuàng)建一個(gè)記錄新數(shù)組用來(lái)存HashMap中的元素
    // 若數(shù)組不是第一次初始化，則這里就是創(chuàng)建了一個(gè)兩倍大小的新數(shù)組
    @SuppressWarnings({"rawtypes","unchecked"})
    HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
    // 將新數(shù)組的引用賦值給成員變量table
    table = newTab;

    // 開(kāi)始將原來(lái)的數(shù)據(jù)加入到新數(shù)組中
    if (oldTab != null) {
        // 遍歷原數(shù)組
        for (int j = 0; j < oldCap; ++j) {
            HashMap.Node<K,V> e;
            // 若原數(shù)組的j位置有節(jié)點(diǎn)存在，才進(jìn)一步操作
            if ((e = oldTab[j]) != null) {
                // 清除舊數(shù)組對(duì)節(jié)點(diǎn)的引用
                oldTab[j] = null;
                // 若table數(shù)組的j位置只有一個(gè)節(jié)點(diǎn)，則直接將這個(gè)節(jié)點(diǎn)放入新數(shù)組
                // 使用 & 替代 % 計(jì)算出余數(shù)，即下標(biāo)
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 若第一個(gè)節(jié)點(diǎn)是一個(gè)數(shù)節(jié)點(diǎn)，表示原數(shù)組這個(gè)位置的鏈表已經(jīng)被轉(zhuǎn)為了紅黑樹(shù)
                // 則調(diào)用紅黑樹(shù)的方法將節(jié)點(diǎn)加入到新數(shù)組中
                else if (e instanceof HashMap.TreeNode)
                    ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                // 上面兩種情況都不滿足，表示這個(gè)位置是一條不止一個(gè)節(jié)點(diǎn)的鏈表
                // 以下操作相對(duì)復(fù)雜，所以單獨(dú)拿出來(lái)講解
                else { // preserve order
                    HashMap.Node<K,V> loHead = null, loTail = null;
                    HashMap.Node<K,V> hiHead = null, hiTail = null;
                    HashMap.Node<K,V> next;
                    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);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 將新創(chuàng)建的數(shù)組返回
    return newTab;
}

??上面的代碼中，最后一部分比較難理解，所以我將在下面單獨(dú)拿出來(lái)講解。

?2.4 resize方法中的鏈表拆分

??resize方法中的最后一部分，是將原數(shù)組中的一條鏈表的節(jié)點(diǎn)，放入到擴(kuò)容后的新數(shù)組中，而這一部分相對(duì)來(lái)說(shuō)比較難理解。首先我們得知道是怎么實(shí)現(xiàn)的，然后再來(lái)逐句分析代碼。

??首先，我們得知道一個(gè)結(jié)論，那就是：原數(shù)組中一條鏈表上的所有節(jié)點(diǎn)，若將它們加入到擴(kuò)容后的新數(shù)組中，它們最多將會(huì)分布在新數(shù)組中的兩條鏈表上。

??在HashMap中，使用按位與運(yùn)算替代了取模運(yùn)算來(lái)計(jì)算下標(biāo)，因?yàn)?strong>num % 2^n == num & (2^n - 1)，而HashMap的容量一定是2^n，所以可以使用這條定理（這里我假設(shè)大家已經(jīng)了解了HashMap的容量機(jī)制，若不了解的，可以先看看我最上面給出的那篇博客）。我們看下面這張圖，左邊是擴(kuò)容前的數(shù)組+鏈表，右邊是擴(kuò)容后的數(shù)組+鏈表，鏈表矩形中的數(shù)字表示節(jié)點(diǎn)的hash值。左邊數(shù)組的容量為2^3==8，只包含一條四個(gè)節(jié)點(diǎn)的鏈表，右邊數(shù)組的容量為2^4 == 16，左邊鏈表上的節(jié)點(diǎn)重新存儲(chǔ)后，變成了右邊兩條鏈表。正對(duì)應(yīng)了我們上面說(shuō)的結(jié)論。

??那這個(gè)結(jié)論是怎么來(lái)的呢？我們先說(shuō)左邊第一個(gè)節(jié)點(diǎn)，它的hash值是2，轉(zhuǎn)換成二進(jìn)制就是0010，而容量為2^3 == 8，通過(guò)num % 2^n == num & (2^n - 1)這個(gè)公式，我們知道2與容量8的余數(shù)是2 & （8 - 1） == 0010 & 0111 == 0010。任何數(shù)與0111做與運(yùn)算（&），實(shí)際上就是取這個(gè)數(shù)二進(jìn)制的最后三位。而擴(kuò)容之后，容量變成了2^4 == 16，這時(shí)候，取模就是與16-1 == 15做與運(yùn)算了，而15的二進(jìn)制是1111，我們發(fā)現(xiàn)，1111與之前的0111唯一的區(qū)別就是第四位也變成了1（以下說(shuō)的第幾位都是從右往左）。而2 & 15 == 0010 & 1111 == 0010，和0010 & 0111 結(jié)果是一樣的。為什么？因?yàn)?code>0010的第四位是0，所以從0111變成1111，并不會(huì)對(duì)計(jì)算結(jié)果造成影響，因?yàn)?code>0和任何數(shù)做與運(yùn)算，結(jié)果都是0。所以擴(kuò)容后，2這個(gè)節(jié)點(diǎn)，還是放在數(shù)字下標(biāo)為2的位置。我們?cè)趤?lái)看看剩下的三個(gè)數(shù)：

hash值為10，轉(zhuǎn)換成二進(jìn)制1010，1010的第四位為1，所以 1010 & 0111 != 1010 & 1111

hash值為18，轉(zhuǎn)換成二進(jìn)制10010，10010的第四位為0，所以 10010 & 0111 == 10010 & 1111
    
hash值為26，轉(zhuǎn)換成二進(jìn)制11010，11010的第四位為1，所以 11010 & 0111 != 11010 & 1111

??所以擴(kuò)容后，余數(shù)是否發(fā)生改變，實(shí)際上只取決于多出來(lái)的那一位而已，那一位只有兩種結(jié)果：0或者1，所以這些節(jié)點(diǎn)的新下標(biāo)最終也只有兩種結(jié)果。而多出來(lái)的那一位是哪一位呢？8轉(zhuǎn)換成二進(jìn)制是1000，而從8擴(kuò)容到16，取余的數(shù)從0111變成了1111，多出的這個(gè)1剛好在第四位，也就是1000中，唯一一個(gè)1所在的位置；16的二進(jìn)制是10000，擴(kuò)容成32后，取余的數(shù)從1111變成11111，在第五位多出了一個(gè)1，正好是10000的1所在的位置。所以我們可以知道，擴(kuò)容后，節(jié)點(diǎn)的下標(biāo)是否需要發(fā)生改變，取決于舊容量的二進(jìn)制中，1那一位。所以容量為8，擴(kuò)容后，若節(jié)點(diǎn)的二進(jìn)制hash值的第四位為0，則節(jié)點(diǎn)在新數(shù)組中的下標(biāo)不變；若為1，節(jié)點(diǎn)的下標(biāo)改變，而且改變的大小正好是+8，因?yàn)槎喑隽俗罡呶坏?code>1，例如1010 & 0111 = 0010，而1010 & 1111 = 1010，結(jié)果相差1000，也就是舊容量的大小8；所以若下標(biāo)要發(fā)生改變，改變的大小將正好是舊數(shù)組的容量。

??我們?nèi)绾闻袛?code>hash值多出來(lái)的那一位是0還是1呢，很簡(jiǎn)單，只要用hash值與舊容量做與運(yùn)算，結(jié)果不為0表示多出的這一位是1，否則就是0。比如說(shuō)，容量為8（二進(jìn)制1000），擴(kuò)容后多出來(lái)的是第四位，于是讓hash值與1000做與運(yùn)算，若hash值的第四位是1，與1000做與運(yùn)算后結(jié)果就是1000，若第四位是0，與1000做與運(yùn)算后就是0。好，下面我們來(lái)看看代碼吧：

// 創(chuàng)建兩個(gè)頭尾節(jié)點(diǎn)，表示兩條鏈表
// 因?yàn)榕f鏈表上的元素放入新數(shù)組中，最多將變成兩條鏈表
// 一條下標(biāo)不變的鏈表，一條下標(biāo)+oldCap
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.Node<K,V> next;

// 循環(huán)遍歷原鏈表上的每一個(gè)節(jié)點(diǎn)
do {
    // 記錄當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
    next = e.next;
    // 注意：e.hash & oldCap這一步就是前面說(shuō)的判斷多出的這一位是否為1
    // 若與原容量做與運(yùn)算，結(jié)果為0，表示將這個(gè)節(jié)點(diǎn)放入到新數(shù)組中，下標(biāo)不變
    if ((e.hash & oldCap) == 0) {
        // 若這是不變鏈表的第一個(gè)節(jié)點(diǎn)，用loHead記錄
        if (loTail == null)
            loHead = e;
        // 否則，將它加入下標(biāo)不變鏈表的尾部
        else
            loTail.next = e;
        // 更新尾部指針指向新加入的節(jié)點(diǎn)
        loTail = e;
    }
    // 若與原容量做與運(yùn)算，結(jié)果為1，表示將這個(gè)節(jié)點(diǎn)放入到新數(shù)組中，下標(biāo)將改變
    else {
        // 若這是改變下標(biāo)鏈表的第一個(gè)節(jié)點(diǎn)，用hiHead記錄
        if (hiTail == null)
            hiHead = e;
        // 否則，將它加入改變下標(biāo)鏈表的尾部
        else
            hiTail.next = e;
        // 更新尾部指針指向新加入的節(jié)點(diǎn)
        hiTail = e;
    }
} while ((e = next) != null);

// 所有節(jié)點(diǎn)遍歷完后，判斷下標(biāo)不變的鏈表是否有節(jié)點(diǎn)在其中
if (loTail != null) {
    // 將這條鏈表的最后一個(gè)節(jié)點(diǎn)的next指向null
    loTail.next = null;
    // 同時(shí)將其放入新數(shù)組的相同位置
    newTab[j] = loHead;
}
// 另一條鏈表與上同理
if (hiTail != null) {
    hiTail.next = null;
    // 這條鏈表放入的位置要在原來(lái)的基礎(chǔ)上加上oldCap
    newTab[j + oldCap] = hiHead;
}

三、總結(jié)

??resize的邏輯并不算太難，可能只有鏈表拆分這一部分比較難理解。為了能盡可能地說(shuō)清楚，我描述的可能有點(diǎn)啰嗦了，希望對(duì)看到的人能夠有所幫助吧。

四、參考

https://blog.csdn.net/weixin_41565013/article/details/93190786