摘要：不過在鏈表過長時(shí)會(huì)將其重構(gòu)為紅黑樹，這樣，其最壞的時(shí)間復(fù)雜度就會(huì)降低為，這樣使得表的適應(yīng)場(chǎng)景更廣。該節(jié)點(diǎn)代表一棵紅黑樹。調(diào)用紅黑樹的相關(guān)方法完成操作。同樣，和鏈表的一樣，也是將紅黑樹拆分成兩條子樹。

接上一篇博文，來吧剩下的部分寫完。
總體來說，HashMap的實(shí)現(xiàn)內(nèi)部有兩個(gè)關(guān)鍵點(diǎn)，第一是當(dāng)表內(nèi)元素和hash桶數(shù)組的比例達(dá)到某個(gè)閾值時(shí)會(huì)觸發(fā)擴(kuò)容機(jī)制，否則表中的元素會(huì)越來越擠影響性能；
第二是保存hash沖突的鏈表如果過長，就重構(gòu)為紅黑樹提升性能。

關(guān)于第二點(diǎn)，對(duì)于HashMap來說，達(dá)到O(1)的查詢性能只是平均時(shí)間復(fù)雜度，這需要key的hash值對(duì)應(yīng)的位置分布的足夠均勻。

來設(shè)想一種極端情況，假設(shè)某個(gè)黑客故意構(gòu)造一組特定的數(shù)據(jù)，這些數(shù)據(jù)的hash值正好一樣。當(dāng)插入hash表中時(shí)，它們的位置也一樣。
那么，這些數(shù)據(jù)會(huì)全部被組織到該位置的鏈表中，hash表退化為鏈表，這時(shí)的查詢的時(shí)間復(fù)雜度為O(N)，也是hash表查詢時(shí)間復(fù)雜度的最壞情況。

不過HashMap在鏈表過長時(shí)會(huì)將其重構(gòu)為紅黑樹，這樣，其最壞的時(shí)間復(fù)雜度就會(huì)降低為O(logN)，這樣使得hash表的適應(yīng)場(chǎng)景更廣。

擴(kuò)容分兩個(gè)步驟：

計(jì)算擴(kuò)容之后的大小。

進(jìn)行具體的擴(kuò)容操作。

以下是第一個(gè)步驟的代碼：

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) { // 已經(jīng)初始化過的情況
        // 對(duì)邊界情況的處理：如果hash桶數(shù)組的大小已經(jīng)達(dá)到了最大值MAXINUM_CAPACITY 這里是2的30次方
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } // 擴(kuò)容兩倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold // 這種情況對(duì)照構(gòu)造函數(shù)看
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults // 這種情況對(duì)照構(gòu)造函數(shù)看
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) { // =_= 邏輯好繞
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 到此，newCap是新的hash桶數(shù)組大小，newThr是新的擴(kuò)容閾值
    threshold = newThr;
    // 分配一個(gè)新的hash桶數(shù)組，然后把舊的數(shù)據(jù)遷移過來

    /* ... */
}

邏輯是這樣的，首先有三種情況，代碼寫的看起來很復(fù)雜：

hash桶數(shù)組已經(jīng)初始化過。

擴(kuò)容后是會(huì)溢出，也即達(dá)到了2的30次方。

擴(kuò)容后不會(huì)溢出，這種情況擴(kuò)容兩倍。擴(kuò)容后hash桶數(shù)組的大小依然是2的冪。

hash桶數(shù)組沒有初始化過，但是指定了初始化大小。

hash桶數(shù)組沒有初始化過，也沒有指定初始化大小。

雖然邏輯很明確，但是代碼寫的看起來卻很復(fù)雜。
其原因是HashMap內(nèi)部記錄的字段能表達(dá)的狀態(tài)太多，每種情況都需要考慮周全。

第一階段執(zhí)行完畢后，HashMap內(nèi)部的部分狀態(tài)字段被更新。
最重要的是，newCap這個(gè)變量記錄了擴(kuò)容之后的大小。

final Node[] resize() {
    /* ... */
    // 分配一個(gè)新的hash桶數(shù)組，然后把舊的數(shù)據(jù)遷移過來
    @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null) // 只有一個(gè)元素的情況
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) // 二叉樹的情況
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // preserve order // 鏈表的情況
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do { // 遍歷鏈表
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            // 如果注意到hash桶數(shù)組擴(kuò)容是從2^N 到 2^(N +１) 這一事實(shí)，從二進(jìn)制的角度分析取余運(yùn)算，就不難發(fā)現(xiàn)優(yōu)化思路。
                            // 總之，這個(gè)迭代的代碼是把這條鏈表拆分成兩條，然而不同的處理邏輯。
                            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);
                    // 對(duì)于這兩種不同類型的鏈表，移動(dòng)的方式不一樣
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

從思路上，總結(jié)如下：

分配一個(gè)新的hash桶數(shù)組，這是擴(kuò)容后的數(shù)組。之后需要把之前的節(jié)點(diǎn)遷移過來。

遍歷舊的hash桶數(shù)組，在其中保存有節(jié)點(diǎn)時(shí)，分不同情況處理：

只有一個(gè)節(jié)點(diǎn)的情況，直接將這個(gè)節(jié)點(diǎn)rehash到新的數(shù)組中。

該節(jié)點(diǎn)代表一棵紅黑樹。調(diào)用紅黑樹的相關(guān)方法完成操作。

該節(jié)點(diǎn)代表一個(gè)鏈表。將鏈表節(jié)點(diǎn)rehash到新的數(shù)組中。

先來看下紅黑樹的split函數(shù)：

    final void split(HashMap map, Node[] tab, int index, int bit) {
        /* ... */
        if (loHead != null) {
            if (lc <= UNTREEIFY_THRESHOLD)
                // 只是這里面有一個(gè)邏輯，即如果拆分出的樹太小，就重新轉(zhuǎn)換回鏈表
                tab[index] = loHead.untreeify(map);
            else {
                tab[index] = loHead;
                if (hiHead != null) // (else is already treeified)
                    loHead.treeify(tab);
            }
        }
        /* ... */
    }

紅黑樹的各種操作代碼我是無心看，各種旋轉(zhuǎn)太復(fù)雜了。這里面主要有一個(gè)關(guān)鍵點(diǎn)，在于rehash的時(shí)候，會(huì)將紅黑樹節(jié)點(diǎn)也rehash。
同樣，和鏈表的rehash一樣，也是將紅黑樹拆分成兩條子樹。至于為什么是拆分為兩條后面會(huì)說。
但是，如果拆分出來的子樹太小了，就會(huì)重新將其重構(gòu)回鏈表。

順便說一句，由于刪除操作的邏輯沒有什么新東西之前就沒有分析。我也沒有在其中找到刪除節(jié)點(diǎn)時(shí)，如果紅黑樹太小會(huì)將其重構(gòu)回鏈表的操作。

對(duì)于鏈表的rehash操作，乍一看，這個(gè)邏輯還有些看不懂，從代碼上來看是這樣的邏輯，對(duì)于hash桶數(shù)組中第j個(gè)位置上的一個(gè)鏈表，進(jìn)行遍歷，根據(jù)條件分成兩條：

(e.hash & oldCap) == 0

滿足上述條件的串成一條鏈表loHead，不滿足上述條件的串成一條鏈表hiHead。之后：

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

實(shí)際上，由于HashMap的hash桶數(shù)組的大小一定為2的冪這一性質(zhì)，取余操作能夠被優(yōu)化。前面也說過這一點(diǎn)，這里以大小為8，也即0001000為例子：

設(shè)一個(gè)2的冪次方數(shù)N，如00001000，二進(jìn)制寫法中一定只有一個(gè)1.

任意一個(gè)數(shù)B余N，反映到二進(jìn)制上，就是高于等于1的對(duì)應(yīng)位置0，低于的保留。如00111110 % 00001000 = 00000110，前5位置0，后4位保留。

假如讓這個(gè)數(shù)余2N，不難發(fā)現(xiàn)，反映到二進(jìn)制上，變成了前4位置0，后4為保留。

嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)表達(dá)我實(shí)在懶得寫了，總之通過分析不難得到這個(gè)結(jié)論：

如果數(shù)B的第3位（從低位從0開始數(shù)）為0，那么B % N = B % 2N。

如果數(shù)B的第3位（從低位從0開始數(shù)）為1，那么B % N結(jié)果的第3位給置1等于B % 2N，也即B % N + N = B % 2N

有了以上結(jié)論，對(duì)照上面的代碼，也就不難理解這段rehash代碼的思路了：

(e.hash & oldCap) == 0

這句話是判斷hash值的對(duì)應(yīng)位是否為0，并分成兩條不同的鏈表。

如果為0，則rehash后的位置不變。

如果不為0，則為以前的位置加上舊表的大小。

最后，我比較疑惑的一點(diǎn)是，花了這么大力氣去優(yōu)化，為什么能得到性能或內(nèi)存上的提升？
我們分析下優(yōu)化前后的時(shí)間復(fù)雜度：

如果不優(yōu)化，則是遍歷舊的hash桶數(shù)組，然后遍歷每一個(gè)鏈表，并且把鏈表的每個(gè)節(jié)點(diǎn)rehash到新的hash桶數(shù)組上去。將鏈表插入到新的數(shù)組只需O(1)的時(shí)間，也即整個(gè)操作的時(shí)間復(fù)雜度為O(N)，N為hash表中元素的個(gè)數(shù)。

如果優(yōu)化，則是遍歷舊的hash桶數(shù)組，然后同樣需要遍歷每一個(gè)鏈表，把每一個(gè)節(jié)點(diǎn)分開到兩條不同的子鏈表上去。。。時(shí)間復(fù)雜度仍然是O(N)...

看起來兩種方案都需要遍歷所有的鏈表節(jié)點(diǎn)，難道僅僅是減小一點(diǎn)時(shí)間復(fù)雜度的常數(shù)嗎？

之前說過當(dāng)鏈表長度過大時(shí)會(huì)將其重構(gòu)為紅黑樹，下面來看具體的代碼。

// 8. 把鏈表轉(zhuǎn)換成二叉樹
final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    // 如果hash桶數(shù)組的大小太小還得擴(kuò)容。
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    // 所需要的hash參數(shù)是為了定位是hash桶數(shù)組中的那個(gè)鏈表，可為啥不直接傳index...
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode hd = null, tl = null;
        // 遍歷單鏈表，然后把給它們一個(gè)個(gè)的分配TreeNode節(jié)點(diǎn)
        // 看下面這代碼，這個(gè)TreeNode，記得擁有next和prev字段，看下面的代碼是把它們串成雙鏈表
        do {
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            // 調(diào)用TreeNod.treeify()函數(shù)將這個(gè)已經(jīng)組成雙鏈表的TreeNode節(jié)點(diǎn)重構(gòu)成紅黑樹
            hd.treeify(tab);
    }
}

之前提到過TreeNode擁有next和prev字段，因此它不僅能夠用來組織紅黑樹，還能夠組織雙向鏈表。
這里看到了，這里首先將單鏈表的元素復(fù)制到TreeNode節(jié)點(diǎn)構(gòu)成的雙向鏈表中，然后通過TreeNode的treeify方法將其組織成紅黑樹。至于這個(gè)方法。。。各種旋轉(zhuǎn)，紅黑樹的操作算法本身是很復(fù)雜的，就略過不看了。