// 在鏈表長(zhǎng)度大于等于8時(shí)，嘗試將鏈表轉(zhuǎn)為紅黑樹
private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    // 數(shù)組不能為空
    if (tab != null) {
        // 數(shù)組的長(zhǎng)度n，是否小于64
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            // 如果數(shù)組長(zhǎng)度小于64，不能將鏈表轉(zhuǎn)為紅黑樹，先嘗試擴(kuò)容操作
            // 這里的擴(kuò)容傳入的數(shù)據(jù)是當(dāng)前數(shù)據(jù)的2倍
            tryPresize(n << 1);
        // 省略部分代碼……
    }
}

private final void tryPresize(int size) {
    // 如果當(dāng)前傳過來的size大于最大值MAXIMUM_CAPACITY >>> 1，則取 MAXIMUM_CAPACITY 
    // 反之取 tableSizeFor(size + (size >>> 1) + 1)= size的1.5倍 + 1
    // tableSizeFor：這個(gè)方法我們之前也講過,找size的最近二次冪
    // 這個(gè)地方的c
    int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1);
    int sc;
    // 當(dāng)前的sizeCtl大于等于0,證明不屬于異常狀態(tài)
    // static final int MOVED     = -1; // 代表當(dāng)前hash位置的數(shù)據(jù)正在擴(kuò)容！
    // static final int TREEBIN   = -2; // 代表當(dāng)前hash位置下掛載的是一個(gè)紅黑樹
    // static final int RESERVED  = -3; // 預(yù)留當(dāng)前索引位置……
    while ((sc = sizeCtl) >= 0) {
        Node<K,V>[] tab = table; int n;
        // 如果當(dāng)前的數(shù)組為空,走初始化的邏輯
        // 有人可能會(huì)好奇,這里怎么會(huì)為空呢？
        // 大家可以去看下putAll的源碼(放在下面),源碼里面第一句調(diào)用的就是tryPresize的方法
        if (tab == null || (n = tab.length) == 0) {
            // 進(jìn)來執(zhí)行初始化
            // sc是初始化長(zhǎng)度，初始化長(zhǎng)度如果比計(jì)算出來的c要大的話，直接使用sc，如果沒有sc大，
            // 說明sc無法容納下putAll中傳入的map，使用更大的數(shù)組長(zhǎng)度
            n = (sc > c) ? sc : c;
            // 還是老配方,CAS將SIZECTL嘗試從sc變成-1
            if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    // Step1:判斷引用
                    // Step2:創(chuàng)建數(shù)組
                    // Step3:修改sizeCtl數(shù)值
                    if (table == tab) {
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
            }
        }
        // 如果計(jì)算出來的長(zhǎng)度c如果小于等于sc，直接退出循環(huán)結(jié)束方法
        // 數(shù)組長(zhǎng)度大于等于最大長(zhǎng)度了，直接退出循環(huán)結(jié)束方法
        // 不需要擴(kuò)容
        else if (c <= sc || n >= MAXIMUM_CAPACITY)
            break;
        // 省略部分代碼
    }
}
// putAll方法
public void putAll(Map<? extends K, ? extends V> m) {
    // 直接走擴(kuò)容的邏輯
    tryPresize(m.size());
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        putVal(e.getKey(), e.getValue(), false);
}

private final void tryPresize(int size) {
    int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
        tableSizeFor(size + (size >>> 1) + 1);
    int sc;
    while ((sc = sizeCtl) >= 0) {
        Node<K,V>[] tab = table;
        // 當(dāng)前數(shù)組的長(zhǎng)度
        int n; 
        // 判斷引用是否一致
        if (tab == table) {
            // 計(jì)算擴(kuò)容標(biāo)識(shí)戳，根據(jù)當(dāng)前數(shù)組的長(zhǎng)度計(jì)算一個(gè)16位的擴(kuò)容戳
            // 1、保證后面的SIZECTL賦值是負(fù)數(shù)
            // 2、記錄當(dāng)前從什么長(zhǎng)度開始擴(kuò)容
            int rs = resizeStamp(n);
            // 這里存在bug
            // 由于我們上面(sc = sizeCtl) >= 0的判斷,sc只能大于0
            // 這里永遠(yuǎn)大于等于0
            if (sc < 0) {
                // 協(xié)助擴(kuò)容的代碼
            }
            // 代表當(dāng)前沒有線程進(jìn)行擴(kuò)容，我是第一個(gè)擴(kuò)容的
            else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
        }
    }
}
// 計(jì)算擴(kuò)容標(biāo)識(shí)戳
static final int resizeStamp(int n) {
    return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}

private final void tryPresize(int size) {
    // sc默認(rèn)為sizeCtl
    while ((sc = sizeCtl) >= 0) {
        else if (tab == table) {
            // rs：擴(kuò)容戳  00000000 00000000 10000000 00011010
            int rs = resizeStamp(n);
            if (sc < 0) {
                // 說明有線程正在擴(kuò)容，過來幫助擴(kuò)容
                // 我們之前第一個(gè)線程擴(kuò)容的時(shí)候,將sizeCtl設(shè)置成：10000000 00011010 00000000 00000010
                // 所以：sc = 10000000 00011010 00000000 00000010
                Node<K,V>[] nt;
                // 依然有BUG
                // 當(dāng)前線程擴(kuò)容時(shí)，老數(shù)組長(zhǎng)度是否和我當(dāng)前線程擴(kuò)容時(shí)的老數(shù)組長(zhǎng)度一致
                // 00000000 00000000 10000000 00011010
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs  
                    // 10000000 00011010 00000000 00000010 
                    // 00000000 00000000 10000000 00011010
                    // 這兩個(gè)判斷都是有問題的，核心問題就應(yīng)該先將rs左移16位，再追加當(dāng)前值。
                    // 這兩個(gè)判斷是BUG
                    // 判斷當(dāng)前擴(kuò)容是否已經(jīng)即將結(jié)束
                    || sc == rs + 1   // sc == rs << 16 + 1 BUG
                    // 判斷當(dāng)前擴(kuò)容的線程是否達(dá)到了最大限度
                    || sc == rs + MAX_RESIZERS   // sc == rs << 16 + MAX_RESIZERS BUG
                    // 擴(kuò)容已經(jīng)結(jié)束了。
                    || (nt = nextTable) == null 
                    // 記錄遷移的索引位置，從高位往低位遷移，也代表擴(kuò)容即將結(jié)束。
                    || transferIndex <= 0)
                    break;
                // 如果線程需要協(xié)助擴(kuò)容，首先就是對(duì)sizeCtl進(jìn)行+1操作，代表當(dāng)前要進(jìn)來一個(gè)線程協(xié)助擴(kuò)容
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    // 上面的判斷沒進(jìn)去的話，nt就代表新數(shù)組
                    transfer(tab, nt);
            }
            // 是第一個(gè)來擴(kuò)容的線程
            // 基于CAS將sizeCtl修改為:10000000 00011010 00000000 00000010 
            // 將擴(kuò)容戳左移16位之后，符號(hào)位是1，就代碼這個(gè)值為負(fù)數(shù)
            // 低16位在表示當(dāng)前正在擴(kuò)容的線程有多少個(gè):低16位為2,代表當(dāng)前有一個(gè)線程正在擴(kuò)容
            // 為什么低16位值為2時(shí)，代表有一個(gè)線程正在擴(kuò)容
            // 每一個(gè)線程擴(kuò)容完畢后，會(huì)對(duì)低16位進(jìn)行-1操作，當(dāng)最后一個(gè)線程擴(kuò)容完畢后，減1的結(jié)果還是-1，
            // 當(dāng)值為-1時(shí)，要對(duì)老數(shù)組進(jìn)行一波掃描，查看是否有遺漏的數(shù)據(jù)沒有遷移到新數(shù)組
            else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))
                // 調(diào)用transfer方法，并且將第二個(gè)參數(shù)設(shè)置為null，就代表是第一次來擴(kuò)容！
                transfer(tab, null);
        }
    }
}

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    // 數(shù)組長(zhǎng)度	
    int n = tab.length; 
    // 每個(gè)線程一次性遷移多少數(shù)據(jù)到新數(shù)組
    int stride; 		
    // 基于CPU的線程數(shù)來計(jì)算：NCPU = Runtime.getRuntime().availableProcessors()
    // MIN_TRANSFER_STRIDE = 16
    // NCPU = 4
    // 舉個(gè)例子：N = 1024 - 512 - 256 - 128 / 4 = 32
    // 如果算出來每個(gè)線程的長(zhǎng)度小于16的話,直接使用16
    // 如果大于16的話,則使用N
    // 如果線程數(shù)只有1的話，直接就是原數(shù)組長(zhǎng)度
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE){
        stride = MIN_TRANSFER_STRIDE;
    }
}

// 以32位長(zhǎng)度數(shù)組擴(kuò)容到64位為例子
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    // 數(shù)組長(zhǎng)度	
    int n = tab.length; 
    // 每個(gè)線程一次性遷移多少數(shù)據(jù)到新數(shù)組
    int stride; 	
    // 第一個(gè)進(jìn)來擴(kuò)容的線程需要把新數(shù)組構(gòu)建出來
    if (nextTab == null) {            
        try {
            // 將原數(shù)組長(zhǎng)度左移一位創(chuàng)建新數(shù)組
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
            // 賦值操作
            nextTab = nt;
        } catch (Throwable ex) {      
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        // 將成員變量的新數(shù)組賦值volatile修飾
        nextTable = nextTab;
        // 遷移數(shù)據(jù)時(shí)用到的標(biāo)識(shí)volatile修飾
        transferIndex = n;
    }
    // 新數(shù)組長(zhǎng)度
    int nextn = nextTab.length;
    // 老數(shù)組遷移完數(shù)據(jù)后，做的標(biāo)識(shí)
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    // 遷移數(shù)據(jù)時(shí)，需要用到的標(biāo)識(shí)
    boolean advance = true;
    boolean finishing = false; 
}

// 以32位長(zhǎng)度數(shù)組擴(kuò)容到64位為例子
// 數(shù)組長(zhǎng)度	
int n = tab.length; 
// 每個(gè)線程一次性遷移多少數(shù)據(jù)到新數(shù)組
int stride;
// 遷移數(shù)據(jù)時(shí)用到的標(biāo)識(shí)volatile修飾
transferIndex = n;
// 新數(shù)組長(zhǎng)度
int nextn = nextTab.length;
// 老數(shù)組遷移完數(shù)據(jù)后，做的標(biāo)識(shí)
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// advance：true，代表當(dāng)前線程需要接收任務(wù)，然后再執(zhí)行遷移
// 如果為false，代表已經(jīng)接收完任務(wù)
boolean advance = true;
// 標(biāo)識(shí)遷移是否結(jié)束
boolean finishing = false;
// 開始循環(huán)
for (int i = 0, bound = 0;;) {
    Node<K,V> f; 
    int fh;
    while (advance) {
        int nextIndex;
        int nextBound;
        // 第一次：這里肯定進(jìn)不去
        // 主要判斷當(dāng)前任務(wù)是否執(zhí)行完畢
        if (--i >= bound || finishing)
            advance = false;
        // 第一次：這里肯定也進(jìn)不去
        // 判斷transferIndex是否小于等于0，代表沒有任務(wù)可領(lǐng)取，結(jié)束了。
        // 在線程領(lǐng)取任務(wù)會(huì)，會(huì)對(duì)transferIndex進(jìn)行修改，修改為transferIndex - stride
        // 在任務(wù)都領(lǐng)取完之后，transferIndex肯定是小于等于0的，代表沒有遷移數(shù)據(jù)的任務(wù)可以領(lǐng)取
        else if ((nextIndex = transferIndex) <= 0) {
            i = -1;
            advance = false;
        }
       	// nextIndex=32
        // stride=16
        // nextIndex > stride ? nextIndex - stride : 0：當(dāng)前的nextIndex是否大于每個(gè)線程切割的
        // 是：nextIndex - stride/否：0
        // 將TRANSFERINDEX從nextIndex變成16
        else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,
                                     nextBound = (nextIndex > stride ?nextIndex - stride : 0))) {
            // 對(duì)bound賦值(16)
            bound = nextBound;
            // 對(duì)i賦值(31)
            i = nextIndex - 1;
            // 賦值,代表當(dāng)前領(lǐng)取任務(wù)結(jié)束
            // 該線程當(dāng)前領(lǐng)取的任務(wù)是(16~31)
            advance = false;
        }
    }
}

// 判斷擴(kuò)容是否已經(jīng)結(jié)束！
// i < 0：當(dāng)前線程沒有接收到任務(wù)！
// i >= n: 遷移的索引位置，不可能大于數(shù)組的長(zhǎng)度，不會(huì)成立
// i + n >= nextn：因?yàn)閕最大值就是數(shù)組索引的最大值，不會(huì)成立
if (i < 0 || i >= n || i + n >= nextn) {
    int sc;
    // 第一次到這里：必定是false
    // 如果再次到這里的時(shí)候,最后一個(gè)擴(kuò)容的線程也掃描完了
    if (finishing) {
        nextTable = null;
        table = nextTab;
        // 重新更改當(dāng)前的sizeCtl的數(shù)值：0.75N
        sizeCtl = (n << 1) - (n >>> 1);
        return;
    }
    // 到這里代表當(dāng)前線程已經(jīng)不需要去擴(kuò)容了
    // 那么它要把當(dāng)前并發(fā)擴(kuò)容的線程數(shù)減一
    // SIZECTL ----> sc - 1
    if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
        // 判斷當(dāng)前這個(gè)線程是不是最后一個(gè)擴(kuò)容線程
        if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
            // 如果不是的話,直接返回就好了
            return;
        // 如果是的話,當(dāng)前線程還需要將舊數(shù)據(jù)全部掃描一遍,校驗(yàn)一下是不是都遷移完了
        finishing = advance = true;
        // 將當(dāng)前的i重新變成原數(shù)組的長(zhǎng)度
        // 重新進(jìn)行一輪校驗(yàn)
        i = n; // recheck before commit 
    }
}

    // 如果當(dāng)前的i位置上沒有數(shù)據(jù),直接不需要遷移
	else if ((f = tabAt(tab, i)) == null)
        // 將原來i位置上CAS標(biāo)記成fwd
        // fwd的Hash為Move
        advance = casTabAt(tab, i, null, fwd);
	// // 拿到當(dāng)前i位置的hash值，如果為MOVED，證明數(shù)據(jù)已經(jīng)遷移過了。
    else if ((fh = f.hash) == MOVED)
        // 那么直接返回即可，主要是最后一個(gè)擴(kuò)容線程掃描的時(shí)候使用
        advance = true; // already processed
    else {
        // 鎖住
        synchronized (f) {
            // 再次校驗(yàn)
            if (tabAt(tab, i) == f) {
                // ln：null  - lowNode
                Node<K,V> ln;
                 // hn：null  - highNode
                Node<K,V> hn;
                // 如果當(dāng)前的fh是正常的
                if (fh >= 0) {
                    // 求當(dāng)前的runBit
                    // 這里只會(huì)有兩個(gè)結(jié)果：0 或者 n
                    int runBit = fh & n;
                    // 用當(dāng)前l(fā)astRun指向f
                    Node<K,V> lastRun = f;
                    // 進(jìn)行鏈表的遍歷
                    for (Node<K,V> p = f.next; p != null; p = p.next) {
                        // 求每一個(gè)鏈表的p.hash & n
                        int b = p.hash & n;
                        // 如果當(dāng)前的b不等于上一個(gè)節(jié)點(diǎn)
                        // 需要更新下runBit的數(shù)據(jù)和lastRun的指針
                        if (b != runBit) {
                            runBit = b;
                            lastRun = p;
                        }
                    }
                    // 如果最后runBit=0的話
                    // lastRun賦值給ln
                    if (runBit == 0) {
                        ln = lastRun;
                        hn = null;
                    }
                    // 如果最后runBit=0的話
                    // lastRun賦值給hn
                    else {
                        hn = lastRun;
                        ln = null;
                    }
                    // 從數(shù)組頭節(jié)點(diǎn)開始一直遍歷到lastRun位置
                    for (Node<K,V> p = f; p != lastRun; p = p.next) {
                        // hash/key/value
                        int ph = p.hash; K pk = p.key; V pv = p.val;
                        // 如果當(dāng)前的是0,則掛到ln下面
                        if ((ph & n) == 0)
                            ln = new Node<K,V>(ph, pk, pv, ln);
                        // 如果當(dāng)前的是1,則掛到hn下面
                        else
                            hn = new Node<K,V>(ph, pk, pv, hn);
                    }
                    // 將新數(shù)組i位置設(shè)置成ln
                    setTabAt(nextTab, i, ln);
                    // 將新數(shù)組i+N位置設(shè)置成hn
                    setTabAt(nextTab, i + n, hn);
                    // 將原來數(shù)組的i位置設(shè)置成fwd,代表遷移完畢
                    setTabAt(tab, i, fwd);
                    // 將advance設(shè)置成true,保證進(jìn)行上面的while循環(huán)
                    // 執(zhí)行上面的i--,進(jìn)行下一節(jié)點(diǎn)的遷移計(jì)劃
                    advance = true;
                }
            }
        }
    }
}

int runBit = fh & n;
for (Node<K,V> p = f.next; p != null; p = p.next) {
    // 求每一個(gè)鏈表的p.hash & n
    int b = p.hash & n;
    // 如果當(dāng)前的b不等于上一個(gè)節(jié)點(diǎn)
    // 需要更新下runBit的數(shù)據(jù)和lastRun的指針
    if (b != runBit) {
        runBit = b;
        lastRun = p;
    }
}

// 如果當(dāng)前的hash是正在擴(kuò)容
if ((fh = f.hash) == MOVED){
     // 進(jìn)行協(xié)作式擴(kuò)容
    tab = helpTransfer(tab, f);
}
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; 
    int sc;
    // 第一個(gè)判斷：老數(shù)組不為null
    // 第二個(gè)判斷：新數(shù)組不為null  （將新數(shù)組賦值給nextTab）
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        // 拿到擴(kuò)容戳
        int rs = resizeStamp(tab.length);
        // 第一個(gè)判斷：fwd中的新數(shù)組，和當(dāng)前正在擴(kuò)容的新數(shù)組是否相等。    
        // 相等：可以協(xié)助擴(kuò)容。不相等：要么擴(kuò)容結(jié)束，要么開啟了新的擴(kuò)容
        // 第二個(gè)判斷：老數(shù)組是否改變了。     相等：可以協(xié)助擴(kuò)容。不相等：擴(kuò)容結(jié)束了
        // 第三個(gè)判斷：如果正在擴(kuò)容，sizeCtl肯定為負(fù)數(shù)，并且給sc賦值
        while (nextTab == nextTable && table == tab &&
               (sc = sizeCtl) < 0) {
            // 判斷擴(kuò)容戳是否一致
            // 看下transferIndex是否小于0,如果小于的話，說明擴(kuò)容的任務(wù)已經(jīng)被領(lǐng)完了
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            // 如果還有任務(wù)的話,CAS將當(dāng)前的SIZECTL加一，協(xié)助擴(kuò)容
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                // 協(xié)助擴(kuò)容的代碼,上面剛剛分析過
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}