Java並行原始碼分析ConcurrentHashMap執行緒集合

/** 陣列最大容量大小(1073741824) */
private static final int MAXIMUM_CAPACITY = 1 << 30;
/** 預設的初始容量大小 */
private static final int DEFAULT_CAPACITY = 16;
/** 預設的並行等級 */
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
/** 負載因子 */
private static final float LOAD_FACTOR = 0.75f;
/** 連結串列轉換為紅黑樹的閾值 */
static final int TREEIFY_THRESHOLD = 8;
/** 紅黑樹轉換為連結串列的閾值 */
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * 最小樹化閾值
 * 當連結串列中的節點數量大於等於8時,如果陣列的長度小於最小樹化閾值則不會將連結串列轉換為紅黑樹,而是對陣列進行擴容
 * 將連結串列中的節點分散到別的索引節點中去,只有當陣列的長度大於等於最小樹化閾值則會將連結串列轉換為紅黑樹
 */
static final int MIN_TREEIFY_CAPACITY = 64;
/** 擴容時,每個cpu最少需要負責的區域長度 */
private static final int MIN_TRANSFER_STRIDE = 16;
/** 擴容時生成標記的二進位制所在位置 */
private static int RESIZE_STAMP_BITS = 16;
/** 擴容時記錄擴容容量的標記的二進位制所在位置 */
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
//節點正在移動
static final int MOVED = -1;
//節點已被樹化
static final int TREEBIN = -2;
static final int RESERVED = -3; // hash for transient reservations
//32位元二進位制中正數最大的值,主要用於對key的hash值進行二次運算
static final int HASH_BITS = 0x7fffffff;
/** 當前機器的cpu數量 */
static final int NCPU = Runtime.getRuntime().availableProcessors();
/**
 * 存放元素的陣列物件
 * 只有在第一次新增元素的時候進行初始化
 * 如果沒有指定陣列容量則使用預設的容量16進行初始化
 * 陣列容量為2的次方,如果指定的陣列容量不是2的次方則會進行計算獲取到大於指定容量並是2的次方的數
 */
transient volatile Node<K, V>[] table;
/** 擴容後的新陣列,如果該陣列不為空則說明當前有其它執行緒正在進行擴容 */
private transient volatile Node<K, V>[] nextTable;
/** 基本計數器值,在沒有執行緒爭用的時候才會使用 */
private transient volatile long baseCount;
/**
 * -1時則說明陣列物件正在初始化
 * 如果陣列未被初始化時該值為陣列初始化時的大小
 * 如果陣列已被初始化該值為陣列擴容的閾值
 * -N:低16位元二進位制轉換為十進位制數M,M-1則是當前正在擴容的執行緒數量
 */
private transient volatile int sizeCtl;
/**
 * 擴容時需要轉移舊陣列中的剩餘的索引位置長度
 * 每個執行緒最少負責16個索引位置上的節點轉移
 */
private transient volatile int transferIndex;
/**
 * 計數器陣列的鎖標識
 * 用與初始化計數器陣列以及擴容和建立計數器物件的時候使用
 */
private transient volatile int cellsBusy;
/** 計數器陣列 */
private transient volatile CounterCell[] counterCells;

/**
 * 建立一個預設容量為16的陣列物件
 * 該構造方法中並沒有執行任何操作
 * 並沒有建立預設容量的陣列物件
 * 只有在第一次新增元素的時候才會初始化陣列物件
 */
public ConcurrentHashMap() {
}
/**
 * 建立一個指定初始容量的陣列物件
 * @param initialCapacity 指定的初始容量
 */
public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();
    //校驗指定的初始容量大小是否大於等於最大容量大小的一半
    //如果大於等於最大容量大小的一半則在後續第一次新增元素的時候使用最大容量大小建立陣列
    //如果小於最大容量大小的一半則根據指定容量來計算最接近指定容量大小並大於指定容量的2的次方
    //此處有一個疑問,指定容量大小如果等於最大容量大小的一半則說明指定容量大小是2的29次方,為什麼不使用指定容量大小,而是使用最大的容量大小?
    //從tableSizeFor方法也能看出,如果指定的初始容量大小本來就是2的次方的話並不會使用指定的初始容量大小來建立陣列物件
    //而是使用大於指定初始容量大小的2的次方來建立陣列物件,比如指定的初始容量大小為16,那就會使用32來建立陣列物件
    //在HashMap中如果指定的初始容量大小本來就是2的次方的話則會使用指定的初始容量大小來建立陣列物件
    //並不會像ConcurrentHashMap一樣會取比當前指定的2的次方的初始容量大小大的2的次方的容量大小來建立陣列物件
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
            MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    //將計算後的容量大小賦值給sizeCtl等待初始化
    this.sizeCtl = cap;
}
/**
 * 根據指定的集合中的元素來建立新的陣列物件
 * @param m the map
 */
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
    //使用預設的初始容量大小等待初始化
    this.sizeCtl = DEFAULT_CAPACITY;
    //初始化新的陣列物件並將指定集合中的元素新增到新的陣列物件中
    putAll(m);
}
/**
 * 根據指定的初始容量大小和指定的負載因子來建立新的陣列物件
 */
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
    this(initialCapacity, loadFactor, 1);
}
/**
 * 根據指定的初始容量大小和指定的負載因子和並行數來建立新的陣列物件
 */
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
    if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    if (initialCapacity < concurrencyLevel)
        //初始容量大小小於並行數則使用並行數來建立陣列物件
        initialCapacity = concurrencyLevel;
    //通過計算獲取到擴容的閾值
    long size = (long) (1.0 + (long) initialCapacity / loadFactor);
    //如果閾值大於等於最大容量大小則使用最大容量大小來建立新的陣列物件
    //如果閾值小於最大容量大小則使用閾值來計算獲取到大於閾值並是2的次方的值
    //使用計算後的值來建立新的陣列物件
    int cap = (size >= (long) MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int) size);
    //將計算後的容量大小賦值給sizeCtl等待初始化
    this.sizeCtl = cap;
}

public V put(K key, V value) {
    return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null)
        //key和value不能為空
        throw new NullPointerException();
    //將key的hash值的高16位元二進位制參加運算獲取到新的hash值
    int hash = spread(key.hashCode());
    //指定索引位置上節點的數量
    int binCount = 0;
    for (Node<K, V>[] tab = table; ; ) {
        //陣列中指定索引的節點
        Node<K, V> f;
        //n 陣列長度
        //i key所在的陣列索引位置
        //fh 指定索引的節點的hash值
        int n, i, fh;
        //校驗陣列是否已經初始化
        if (tab == null || (n = tab.length) == 0)
            //陣列未初始化則初始化陣列
            //並返回初始化完成的陣列物件
            tab = initTable();
        //通過陣列索引長度與key的hash值進行與運算獲取到指定索引位置上的元素節點,並校驗元素節點是否為空
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //指定索引位置上的節點不存在則使用傳遞進來的key和value建立新的節點
            //並將新的節點放置到指定索引位置上
            if (casTabAt(tab, i, null,new Node<K, V>(hash, key, value, null)))
                //節點新增成功則退出迴圈
                break;
        //校驗索引位置上的節點是否正在移動
        } else if ((fh = f.hash) == MOVED)
            //如果索引位置上的節點正在移動則幫忙移動節點到新的陣列中
            //協助擴容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            //使用鎖鎖住指定索引位置上的節點
            //這樣其它執行緒就不能對該索引位置上的節點進行操作
            //其它執行緒可以對其它索引位置上的節點進行操作
            synchronized (f) {
                //校驗指定索引位置上的節點是否被更改
                if (tabAt(tab, i) == f) {
                    //校驗節點的hash值是否大於等於0
                    //如果節點的hash值大於等於0則說明該索引位置上只有一個節點或節點是一個連結串列節點
                    if (fh >= 0) {
                        binCount = 1;
                        //從指定索引位置上的節點開始遍歷
                        for (Node<K, V> e = f; ; ++binCount) {
                            K ek;
                            //校驗遍歷到的節點的hash值以及key是否與傳遞的key和計算的hash值相同
                            //如果相同則根據onlyIfAbsent引數來決定是否需要使用新的value替換舊的value
                            if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
                                //獲取舊的value
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    //使用新的value替換舊的value
                                    e.val = value;
                                break;
                            }
                            //遍歷到的節點的hash值以及key不相同
                            //則判斷當前遍歷到的節點是否是連結串列上的最後一個節點
                            //如果不是最後一個節點則繼續遍歷
                            //如果是最後一個節點則為key和value建立一個新的節點
                            //並將原尾節點的next指標指向新建立的節點
                            Node<K, V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K, V>(hash, key, value, null);
                                break;
                            }
                        }
                     //校驗節點是否是一個紅黑樹節點
                    } else if (f instanceof TreeBin) {
                        Node<K, V> p;
                        binCount = 2;
                        //將指定的key和value封裝成一個樹節點並新增到紅黑樹中
                        //如果紅黑樹中已經存在相同key的節點則根據onlyIfAbsent引數來決定是否使用新的value替換紅黑樹中的節點的value
                        if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key,value)) != null) {
                            //獲取節點中的舊值
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                //替換節點中的value
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                //校驗索引位置上的節點的數量是否到達樹化的閾值
                //如果該索引位置上的節點本來就是樹節點則不會繼續樹化
                //只有當索引位置上的節點是連結串列節點並且節點的數量大於等於8的時候才會樹化
                if (binCount >= TREEIFY_THRESHOLD)
                    //索引位置上的節點數量已經到達樹化的閾值
                    //則將該索引位置上的所有節點轉換為樹節點
                    treeifyBin(tab, i);
                if (oldVal != null)
                    //返回被替換的舊值
                    return oldVal;
                break;
            }
        }
    }
    //更新集合中元素節點的數量,並校驗是否需要擴容
    addCount(1L, binCount);
    return null;
}

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

private final Node<K, V>[] initTable() {
    Node<K, V>[] tab;
    int sc;
    //校驗陣列是否未被初始化
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            //陣列長度小於0則說明其它執行緒正在準備初始化陣列
            //當前執行緒則需要讓出cpu讓其它執行緒初始化陣列
            Thread.yield();
        //通過cas操作將sizeCtl修改成-1,告知其它執行緒當前執行緒正在準備初始化陣列
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    //如果指定了初始容量則使用指定的初始容量來建立陣列
                    //如果沒有指定則使用預設的初始容量大小16來建立陣列
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    //初始化陣列
                    @SuppressWarnings("unchecked")
                    Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n];
                    //將初始化的陣列物件賦值給當前集合中的陣列物件
                    //並賦值給tab,下一次迴圈校驗則會發現tab不為空則會退出迴圈並退出當前方法
                    table = tab = nt;
                    //計算陣列擴容的閾值
                    sc = n - (n >>> 2);
                }
            } finally {
                //如果try中的程式碼塊執行失敗時sizeCtl則是原先陣列的長度
                //執行成功時sizeCtl則是擴容的閾值
                sizeCtl = sc;
            }
            break;
        }
    }
    //陣列已被初始化返回陣列
    return tab;
}

static {
    try {
        U = sun.misc.Unsafe.getUnsafe();
        Class<?> k = ConcurrentHashMap.class;
        SIZECTL = U.objectFieldOffset
                (k.getDeclaredField("sizeCtl"));
        TRANSFERINDEX = U.objectFieldOffset
                (k.getDeclaredField("transferIndex"));
        BASECOUNT = U.objectFieldOffset
                (k.getDeclaredField("baseCount"));
        CELLSBUSY = U.objectFieldOffset
                (k.getDeclaredField("cellsBusy"));
        Class<?> ck = CounterCell.class;
        CELLVALUE = U.objectFieldOffset
                (ck.getDeclaredField("value"));
        Class<?> ak = Node[].class;
        //獲取陣列中第一個元素在記憶體中開始的偏移量
        ABASE = U.arrayBaseOffset(ak);
        //獲取陣列中元素在記憶體中的增量地址
        int scale = U.arrayIndexScale(ak);
        if ((scale & (scale - 1)) != 0)
            throw new Error("data type scale not a power of two");
        //獲取增量地址在32位元二進位制情況下高位連續包含0的個數
        //使用31減去包含0的個數獲取到需要位移的次數
        ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
    } catch (Exception e) {
        throw new Error(e);
    }

static final <K, V> Node<K, V> tabAt(Node<K, V>[] tab, int i) {
    //根據指定的索引位置計算該索引中的節點在記憶體中的偏移量
    //並從tab陣列中根據索引所在的記憶體的偏移量獲取節點
    return (Node<K, V>) U.getObjectVolatile(tab, ((long) i << ASHIFT) + ABASE);
}

static final <K, V> boolean casTabAt(Node<K, V>[] tab, int i,Node<K, V> c, Node<K, V> v) {
    //根據指定的索引位置計算該索引中的節點在記憶體中的偏移量
    //並根據偏移量獲取節點,並將獲取到的節點與傳遞的節點c進行比較
    //如果兩個節點相同則使用節點v進行替換
    return U.compareAndSwapObject(tab, ((long) i << ASHIFT) + ABASE, c, v);
}

final Node<K, V>[] helpTransfer(Node<K, V>[] tab, Node<K, V> f) {
    Node<K, V>[] nextTab;
    int sc;
    //f instanceof ForwardingNode 當前節點正在轉移
    //nextTab = ((ForwardingNode<K, V>) f).nextTable) != null 擴容的新陣列是否不為空
    //如果條件都為true則說明有執行緒正在擴容中,當前執行緒則需要協助擴容
    if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode<K, V>) f).nextTable) != null) {
        //擴容標記
        int rs = resizeStamp(tab.length);
        while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {
            //(sc >>> RESIZE_STAMP_SHIFT) != rs 校驗擴容標識是否一致,不一致則說明不是同一個陣列
            //sc == rs + 1 應該是sc == (rs << 16) + 1 校驗擴容是否完成
            //sc == rs + MAX_RESIZERS 應該是sc == (rs << 16) + MAX_RESIZERS 校驗擴容的執行緒的數量是否到達最大
            //transferIndex <= 0 舊陣列中還有多少沒有轉移的索引節點長度,如果小於等於0則說明已經轉移完成則不需要協助
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            //擴容執行緒加1
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                //協助擴容
                transfer(tab, nextTab);
                break;
            }
        }
        //擴容完成則返回新的陣列,對新的陣列進行操作
        return nextTab;
    }
    //當前節點還未被轉移或新的陣列還沒有被初始化則對舊陣列進行操作
    return table;
}

final TreeNode<K, V> putTreeVal(int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    for (TreeNode<K, V> p = root; ; ) {
        int dir, ph;
        K pk;
        if (p == null) {
            first = root = new TreeNode<K, V>(h, k, v, null, null);
            break;
        } else if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
            return p;
        else if ((kc == null &&
                (kc = comparableClassFor(k)) == null) ||
                (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K, V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                        (q = ch.findTreeNode(h, k, kc)) != null) ||
                        ((ch = p.right) != null &&
                                (q = ch.findTreeNode(h, k, kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k, pk);
        }
        TreeNode<K, V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            TreeNode<K, V> x, f = first;
            first = x = new TreeNode<K, V>(h, k, v, f, xp);
            if (f != null)
                //將新新增的樹節點設定為連結串列的頭節點
                f.prev = x;
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            if (!xp.red)
                x.red = true;
            else {
                //獲取寫鎖,如果獲取寫鎖失敗則會將當前執行緒掛起進行等待
                //如果有執行緒正在讀,那當前寫的執行緒就要掛起進行等待
                //當讀的執行緒執行完成之後就會去喚醒掛起的執行緒
                //如果說當前執行緒在寫,有執行緒準備讀
                //那讀執行緒並不會去讀取紅黑樹中的節點
                //而是讀取連結串列的節點,因為TreeBin物件中包含了紅黑樹的根節點並且也包含了連結串列的頭節點
                //如果發生寫寫的問題呢?
                //其實並不會發生寫寫的問題,因為當前整個方法都被外部的synchronized鎖住了
                lockRoot();
                try {
                    //平衡紅黑樹中的節點
                    root = balanceInsertion(root, x);
                } finally {
                    //釋放鎖
                    unlockRoot();
                }
            }
            break;
        }
    }
    assert checkInvariants(root);
    return null;
}

//鎖狀態
volatile int lockState;
//寫鎖
static final int WRITER = 1; // set while holding write lock
//等待
static final int WAITER = 2; // set when waiting for write lock
//讀鎖
static final int READER = 4; // increment value for setting read lock

private final void lockRoot() {
    //嘗試加寫鎖
    if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
        //加寫鎖失敗則嘗試將執行緒掛起進行等待
        contendedLock();
}

private final void contendedLock() {
    boolean waiting = false;
    for (int s; ; ) {
        /**
         * ~WAITER = 1111 1111 1111 1111 1111 1111 1111 1101
         * ((s = lockState) & ~WAITER) == 0 等於0則說明當前沒有執行緒對當前TreeBin物件下的紅黑樹進行加鎖
         * 不等於則說明有執行緒對TreeBin物件下的紅黑樹加鎖
         */
        if (((s = lockState) & ~WAITER) == 0) {
            //沒有執行緒對TreeBin物件下的紅黑樹加鎖
            //當前執行緒則可以對TreeBin物件下的紅黑樹嘗試加鎖
            if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                if (waiting)
                    //將等待執行緒清空
                    waiter = null;
                return;
            }
        //(s & WAITER) == 0 執行當前判斷語句的時候則說明有執行緒對紅黑樹加了鎖
        //如果(s & WAITER)等於0則說明沒有執行緒在等待加鎖
        //此時當前執行緒就可以進行等待
        } else if ((s & WAITER) == 0) {
            //將鎖狀態的32位元二進位制中的第2位設定為1
            //代表當前有一個執行緒正在等待加鎖
            if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
                waiting = true;
                //將TreeBin中的等待執行緒設定為當前執行緒
                waiter = Thread.currentThread();
            }
        } else if (waiting)
            //當前執行緒已經設定成了等待狀態了,此時就需要將執行緒掛起
            LockSupport.park(this);
    }
}

if (binCount != 0) {
    //校驗索引位置上的節點的數量是否到達樹化的閾值
    //如果該索引位置上的節點本來就是樹節點則不會繼續樹化
    //只有當索引位置上的節點是連結串列節點並且節點的數量大於等於8的時候才會樹化
    if (binCount >= TREEIFY_THRESHOLD)
        //索引位置上的節點數量已經到達樹化的閾值
        //則將該索引位置上的所有節點轉換為樹節點
        treeifyBin(tab, i);
    if (oldVal != null)
        //返回被替換的舊值
        return oldVal;
    break;
}

private final void treeifyBin(Node<K, V>[] tab, int index) {
    //指定索引位置上的節點
    Node<K, V> b;
    //n 陣列長度
    int n, sc;
    if (tab != null) {
        //校驗陣列的長度是否小於最小的樹化閾值
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
            /**
             * 陣列長度小於最小的樹化閾值
             * 此時並不會將陣列中的連結串列節點轉換為樹節點
             * 只會將陣列進行擴容
             *
             * 如果仔細檢視tryPresize方法你會發現該方法中也對n進行了左移1位
             * 當前tryPresize傳參的時候就已經對n進行了左移1位,然後在方法裡面又對n進行了左移1位
             * 這樣是不是就對陣列進行了4倍擴容,並不是我們想的那樣2倍擴容呢?
             * 其實不是的,在tryPresize方法裡面並沒有使用2次位移後的n來擴容
             * 而是使用最開始的陣列長度n來計算進行擴容
             */
            tryPresize(n << 1);
            //獲取指定索引位置上的元素節點並校驗元素節點是否不為空
            //如果元素節點不為空則校驗該節點的hash值是大於等於0
            //如果hash值大於等於0則說明該節點需要轉換為樹節點
            //如果hash值小於0則說明該節點正在移動或已經被樹化了
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            //使用鎖鎖住指定索引位置上的節點
            //在新增元素的時候也會對指定索引位置上的節點加鎖
            //如果兩個索引位置都是相同的索引位置的時候,如果新增元素的執行緒先加了鎖
            //那執行到當前方法的執行緒則會等待新增元素的執行緒釋放鎖
            //當新增元素的執行緒釋放了鎖之後,當前方法的執行緒則會獲取鎖將索引位置上所有的節點都樹化,包括新新增的元素節點
            //如果是執行到當前方法的執行緒獲取到了鎖,那新增元素的執行緒則會等待
            //當指定索引位置上的所有節點都樹化了之後並釋放了鎖
            //新增元素的執行緒則會去獲取鎖,此時新增元素的執行緒會發現當前索引位置上的節點已經是樹節點
            //則會將元素節點新增到紅黑樹中並使紅黑樹平衡
            synchronized (b) {
                //校驗在獲取鎖的時候指定索引位置上的節點是否被更改
                if (tabAt(tab, index) == b) {
                    //hd 頭節點
                    //tl 當前遍歷到的節點的上一個節點
                    TreeNode<K, V> hd = null, tl = null;
                    //從指定索引位置上的節點開始遍歷,依次將連結串列上的所有節點轉換為樹節點
                    for (Node<K, V> e = b; e != null; e = e.next) {
                        //將普通節點轉換為樹節點
                        TreeNode<K, V> p = new TreeNode<K, V>(e.hash, e.key, e.val, null, null);
                        //校驗當前遍歷的節點是否是連結串列中的頭節點
                        //如果是頭節點則將該節點設定為了樹節點的頭節點
                        //如果不是頭節點則將當前轉換的樹節點與上一個樹節點進行關聯
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    //建立一個TreeBin物件並將樹化的節點轉換為紅黑樹
                    //TreeBin物件中保留著紅黑樹的根節點以及連結串列的頭節點
                    //再呼叫setTabAt方法將TreeBin物件新增到指定的索引位置上
                    //在HashMap中並沒有建立一個TreeBin物件來存放紅黑樹的根節點
                    //而是直接將紅黑樹的根節點放置到指定的索引位置上
                    setTabAt(tab, index, new TreeBin<K, V>(hd));
                }
            }
        }
    }
}

TreeBin(TreeNode<K, V> b) {
    //給當前TreeBin物件設定一個樹化標識
    super(TREEBIN, null, null, null);
    //樹化的頭節點的設定為連結串列的頭節點
    this.first = b;
    //根節點
    TreeNode<K, V> r = null;
    //從樹化的頭節點開始遍歷將節點轉換為紅黑樹中的節點,直到沒有下一個節點
    for (TreeNode<K, V> x = b, next; x != null; x = next) {
        //下一個節點
        next = (TreeNode<K, V>) x.next;
        //初始化每個樹節點的左右子節點
        x.left = x.right = null;
        if (r == null) {
            //根節點為空則將當前遍歷到的節點設定為根節點
            //並將該節點的顏色設定為黑色
            x.parent = null;
            x.red = false;
            r = x;
        } else {
            //待新增到紅黑樹中的節點的key
            K k = x.key;
            //待新增到紅黑樹中的節點的hash值
            int h = x.hash;
            Class<?> kc = null;
            //從紅黑樹的根節點開始遍歷來校驗節點放置的位置
            for (TreeNode<K, V> p = r; ; ) {
                //dir 節點新增到紅黑樹中的位置
                //ph 被遍歷到的紅黑樹中的節點的key
                int dir, ph;
                //被遍歷到的紅黑樹中的節點的key
                K pk = p.key;
                if ((ph = p.hash) > h)
                    //被遍歷到的紅黑樹中的節點的hash值大於待新增到紅黑樹中的節點的hash值
                    //則需要將節點新增到紅黑樹中的左子節點
                    dir = -1;
                else if (ph < h)
                    //被遍歷到的紅黑樹中的節點的hash值小於待新增到紅黑樹中的節點的hash值
                    //則需要將節點新增到紅黑樹中的右子節點
                    dir = 1;
                else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
                TreeNode<K, V> xp = p;
                //校驗待新增到紅黑樹中的節點所放置的位置是否有節點存在
                //如果有節點存在則重新走回圈與子節點繼續比較直到沒有了子節點
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    //放置待新增到紅黑樹中的節點的位置沒有了節點
                    //則會將節點新增到紅黑樹中
                    //將待新增節點的父節點的指標指向當前遍歷到的紅黑樹中的節點
                    x.parent = xp;
                    if (dir <= 0)
                        //將待新增的節點放置到被遍歷到的節點的左子節點
                        xp.left = x;
                    else
                        //將待新增的節點放置到被遍歷到的節點的右子節點
                        xp.right = x;
                    //紅黑樹中新增了新的節點,可能讓紅黑樹不在平衡
                    //所以需要將紅黑樹中的節點進行平衡
                    r = balanceInsertion(r, x);
                    break;
                }
            }
        }
    }
    //TreeBin物件記錄根節點
    this.root = r;
    assert checkInvariants(root);
}

/**
 * 新增元素節點或刪除元素節點的時候需要將計數器中的值修改
 * 如果在單執行緒的情況下直接對基本計數器值修改
 * 如果在多執行緒的情況下對基本計數器修改失敗的話並且計數器陣列為空
 * 則需要初始化計數器陣列,並使用執行緒生成亂數與計數器陣列的長度進行運算獲取到指定的索引位置
 * 並將指定索引位置上的計數器物件進行初始化並將check值儲存在計數器物件中的value
 * 如果計數器陣列不為空,但是指定的索引位置上的計數器物件為空
 * 則初始化計數器物件並將check值儲存在計數器物件中的value
 * 如果計數器物件也不為空則直接將check值累加到計數器物件中的value
 * 在將check值儲存之後則會校驗當前集合中的陣列是否需要擴容
 * 如果需要擴容則會呼叫transfer方法來進行擴容
 */
private final void addCount(long x, int check) {
    //計數器陣列
    CounterCell[] as;
    //b 基本計數器值
    long b, s;
    //計數器陣列counterCells不為空則說明之前已經發生過多執行緒對基本計數器baseCount進行操作
    //計數器陣列counterCells為空則說明之前一直在單執行緒的情況下對基本計數器baseCount進行操作
    //如果計數器陣列為空則會嘗試對基本計數器baseCount進行操作,如果對baseCount操作失敗則說明當前處於多執行緒的情況下
    //此時就需要初始化counterCells
    if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a;
        long v;
        int m;
        boolean uncontended = true;
        //as == null || (m = as.length - 1) < 0 校驗計數器陣列是否初始化,如果沒有初始化則呼叫fullAddCount方法進行初始化
        //(a = as[ThreadLocalRandom.getProbe() & m]) == null 當前計數器陣列不為空的時候則使用執行緒生成的亂數
        //與計數器陣列的長度進行與運算獲取到指定索引位置上的計數器物件,並校驗計數器物件是否為空
        //如果計數器物件為空則呼叫fullAddCount方法對指定索引位置上的計數器物件進行初始化
        //!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) 計數器陣列不為空並且運算獲取到的指定索引位置上的計數器物件也不為空
        //此時就可以對計數器物件進行操作,如果操作失敗則說明有其它執行緒獲取到了這個索引位置上的計數器物件並對這個計數器進行操作中
        //此時就需要呼叫fullAddCount方法選擇其它索引位置上的計數器物件進行操作
        if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            //對計數器陣列以及計數器陣列中的計數器物件進行初始化
            //一個執行緒對計數器物件操作失敗則會更換其它索引上的計數器物件進行操作
            //如果這個執行緒多次對計數器物件操作失敗並且當前計數器陣列的長度小於cpu的數量
            //此時就會嘗試進行擴容,然後對擴容之後的陣列中的計數器物件進行操作
            //如果說計數器陣列的長度不小於cpu的數量則不會進行擴容
            //只會一直更換計數器物件進行操作,直到操作成功
            fullAddCount(x, uncontended);
            return;
        }
        //校驗check是否小於等於1
        //check=-1的情況下則說明刪除了指定索引位置上的元素節點
        //check=0的情況下則說明指定索引位置上沒有元素節點,直接將指定的key和value封裝成一個節點放置到指定的索引位置上
        //check=1的情況在put方法下則說明指定索引位置上有元素節點,但是隻是對索引位置上的元素節點中的value進行了替換
        //在其它方法中check=1可能表示在指定的索引位置上新增了1個元素節點
        //如果是這三種情況的話則不會去嘗試進行擴容
        //如果執行到了當前判斷語句的話則說明並沒有執行上面的fullAddCount方法
        //而是通過上面判斷語句中的cas操作對指定索引位置上的計數器物件的值操作成功
        //但是在check=1的情況下的put方法只是將原本的元素節點中的value替換了
        //如果此時還要對計數器物件中的value加1,那不就會造成1個元素節點變成了2個元素節點?
        //其實並不會的,如果check=1的情況下put方法並不會走到當前的方法中
        if (check <= 1)
            return;
        //將計數器陣列中所有的計數器物件值以及基本的計數器值合併獲取到當前集合中的元素節點的數量
        s = sumCount();
    }
    //校驗check是否大於等於0
    //大於等於0則說明新增了新的元素節點
    //此時就需要來校驗是否需要進行擴容
    //check一共分為5種情況,有三種已經在上面說過,現在來看一下剩下的兩種情況
    //check=2的情況下代表在紅黑樹種新增了一個樹節點,也有可能是在一個連結串列節點中新增了一個節點
    //check>2的情況下代表在連結串列節點中新增了一個節點
    if (check >= 0) {
        Node<K, V>[] tab, nt;
        int n, sc;
        //當前陣列中的元素節點的數量已經到達擴容的閾值並且陣列的長度小於陣列最大容量大小
        //此時會嘗試將陣列進行擴容,如果擴容失敗則會一直進行嘗試,直到擴容成功
        while (s >= (long) (sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) {
            //獲取擴容時的標記
            int rs = resizeStamp(n);
            if (sc < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0)
                    break;
                //擴容執行緒加1
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    //協助擴容
                    transfer(tab, nt);
            //將sizeCtl修改成一個很大的負數,告知其它執行緒現在有執行緒正在擴容
            //為什麼要+2而不是+1?+1代表當前擴容的執行緒數量+1,而+2可能是標識開啟擴容
            } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
                //擴容
                transfer(tab, null);
            //重新計算集合中元素節點的數量
            s = sumCount();
        }
    }
}

private final void fullAddCount(long x, boolean wasUncontended) {
    int h;
    //使用當前執行緒生成亂數,如果亂數為0則說明ThreadLocalRandom中的一些引數還未被初始化
    //此時就需要進行初始化並重新獲取亂數
    if ((h = ThreadLocalRandom.getProbe()) == 0) {
        ThreadLocalRandom.localInit();
        h = ThreadLocalRandom.getProbe();
        wasUncontended = true;
    }
    boolean collide = false;
    for (; ; ) {
        //計數器陣列
        CounterCell[] as;
        //計數器物件
        CounterCell a;
        //計數器陣列長度
        int n;
        //計數器物件中的value
        long v;
        //校驗計數器陣列是否已初始化
        if ((as = counterCells) != null && (n = as.length) > 0) {
            //校驗當前執行緒生成的亂數與計數器陣列索引長度運算後獲取到的指定索引位置上的計數器物件是否為空
            if ((a = as[(n - 1) & h]) == null) {
                //校驗計數器陣列的鎖狀態是否為0
                //如果不為0則說明有其它執行緒正在對計數器陣列進行擴容或對計數器陣列中的計數器物件進行初始化
                if (cellsBusy == 0) {
                    //建立一個計數器物件,並將值新增到計數器物件中
                    CounterCell r = new CounterCell(x);
                    //加鎖,防止多個執行緒同時對通一個索引位置上的計數器物件進行初始化
                    if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                        boolean created = false;
                        try {
                            CounterCell[] rs;
                            int m, j;
                            //校驗一下運算後的索引位置上的計數器物件是否為空
                            //如果不為空則說明已經被其它執行緒初始化了,當前執行緒就不需要再去初始化
                            if ((rs = counterCells) != null && (m = rs.length) > 0 && rs[j = (m - 1) & h] == null) {
                                //將建立好的計數器物件新增到運算後的指定索引位置上
                                rs[j] = r;
                                //初始化成功
                                created = true;
                            }
                        } finally {
                            //修改計數器陣列鎖標識
                            cellsBusy = 0;
                        }
                        if (created)
                            //初始化成功則退出
                            break;
                        //初始化失敗,說明已經有其它執行緒初始化了計數器物件,此時就需要重新走回圈選擇初始化成功的計數器物件進行操作
                        continue;
                    }
                }
                //其它執行緒正在對計數器陣列進行擴容或初始化指定索引位置上的計數器物件
                collide = false;
            } else if (!wasUncontended)
                //wasUncontended為false則說明有其它執行緒正在對指定索引位置上的計數器物件進行操作
                //此時當前執行緒則需要獲取其它索引位置上的計數器物件進行操作
                wasUncontended = true;
            //嘗試對指定索引位置上的計數器物件進行操作
            else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
                //執行成功則退出
                break;
            //校驗當前是否有執行緒對計數器陣列進行了擴容,將計數器陣列中的計數器物件移動到了新的計數器陣列中
            //如果已經將計數器物件移動到了新的計數器陣列中,那重新選擇新的計數器陣列中的計數器物件來進行操作
            //如果沒有執行緒對計數器陣列進行擴容,那比較一下當前計數器陣列的長度是否大於等於cpu的數量
            //如果大於等於cpu的數量則不會進行擴容,只會重新選擇計數器陣列中的計數器物件來操作
            //如果計數器陣列的長度小於cpu的數量那就會對計數器陣列進行2倍的擴容
            else if (counterCells != as || n >= NCPU)
                //此處將collide修改為false可能是想再次嘗試一下是否能對計數器陣列中的計數器物件進行操作
                //如果能操作則不進行擴容,這樣能減少擴容帶來的效能問題
                collide = false;
            else if (!collide)
                collide = true;
            //多次獲取計數器陣列中的計數器物件而不能操作,並計數器陣列的長度小於cpu的數量
            //導致部分的cpu沒有被使用到,此時就需要對計數器陣列進行擴容,充分的使用cpu
            //對計數器陣列加鎖
            else if (cellsBusy == 0 && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                try {
                    //校驗計數器陣列是否變更,防止其它執行緒已經對計數器陣列進行了擴容
                    if (counterCells == as) {
                        //初始化一個新的計數器陣列,大小是原來的2倍
                        CounterCell[] rs = new CounterCell[n << 1];
                        //迴圈將原來的計數器陣列中的計數器物件移動到擴容後的計數器陣列中
                        for (int i = 0; i < n; ++i)
                            rs[i] = as[i];
                        //更新當前集合中的計數器陣列
                        counterCells = rs;
                    }
                } finally {
                    //修改計數器陣列鎖標識
                    cellsBusy = 0;
                }
                collide = false;
                //使用擴容後的計數器陣列進行操作
                continue;
            }
            //計數器物件正在被其它執行緒操作,此時需要重新生成亂數,獲取別的索引位置上的計數器物件來進行操作
            h = ThreadLocalRandom.advanceProbe(h);
        //計數器陣列未被初始化,此時就需要校驗一下當前是否有其它執行緒正在初始化計數器陣列
        //如果沒有,那當前執行緒就需要將計數器陣列初始化的標識設定為1,代表當前有執行緒正在初始化計數器陣列
        } else if (cellsBusy == 0 && counterCells == as && U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
            boolean init = false;
            try {
                if (counterCells == as) {
                    //建立計數器陣列,計數器陣列的長度為2的次方
                    CounterCell[] rs = new CounterCell[2];
                    //建立一個計數器物件,並將值新增到計數器物件中
                    //並使用執行緒生成的亂數與計數器陣列索引長度進行運算獲取到指定的索引位置
                    //並將計數器物件放置到指定的索引位置上
                    rs[h & 1] = new CounterCell(x);
                    //更新當前集合中的計數器陣列
                    counterCells = rs;
                    //初始化完成
                    init = true;
                }
            } finally {
                //修改計數器陣列鎖標識
                cellsBusy = 0;
            }
            if (init)
                //計數器陣列初始化完成則退出
                break;
        //計數器陣列正在被其它執行緒初始化或已經被其它執行緒初始化完成
        //此時嘗試對基本的計數器值進行操作
        //如果失敗則說明有其它執行緒也在對基本計數器值進行操作
        //那就要重新走回圈,來看計數器陣列是否被初始化完成,如果被初始化完成那就對計數器陣列中的計數器物件進行操作
        //如果還沒有初始化完成則會繼續嘗試對基本的計數器值進行操作
        } else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
            break;
    }
}

private final void transfer(Node<K, V>[] tab, Node<K, V>[] nextTab) {
    //n 陣列長度
    //stride 每個cpu需要負責轉移的索引長度
    int n = tab.length, stride;
    //使用陣列長度來計算每個cpu需要負責的長度
    //每個cpu最少需要負責16的長度
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE;
    //nextTab為空則說明當前沒有其它執行緒在初始化
    //不為空則說明當前有其它執行緒正在初始化,當前執行緒則需要幫助初始化的執行緒將舊陣列中的元素節點轉移到新的陣列中
    if (nextTab == null) {
        try {
            //建立新的陣列,容量是舊陣列的2倍
            @SuppressWarnings("unchecked")
            Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {
            //出現異常時則說明擴容失敗,容量大小已經超出MAXIMUM_CAPACITY引數指定的最大的陣列容量
            //因為MAXIMUM_CAPACITY引數指定的容量大小是int型別中正整數最大的2的次方
            //當陣列的長度已經到達MAXIMUM_CAPACITY引數指定的容量大小時,如果再進行2倍的擴容就會導致陣列的長度變成負數
            //此時就會導致擴容失敗,將int型別中最大的正整數設定成擴容的閾值來停止本次擴容
            //如果陣列的長度已到達陣列最大的容量大小那就不會進行擴容了
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        //擴容後的陣列,當其它擴容的執行緒發現nextTable不為空時則不會重複擴容
        nextTable = nextTab;
        //擴容後,預設需要轉移整個舊陣列
        transferIndex = n;
    }
    //獲取擴容後的陣列長度
    int nextn = nextTab.length;
    //建立一個轉移的節點
    ForwardingNode<K, V> fwd = new ForwardingNode<K, V>(nextTab);
    //是否繼續轉移
    boolean advance = true;
    //標識擴容之後舊陣列中的節點是否全部完成轉移
    boolean finishing = false;
    for (int i = 0, bound = 0; ; ) {
        Node<K, V> f;
        int fh;
        while (advance) {
            //nextIndex 當前執行緒開始轉移的長度位置
            //nextBound 當前執行緒負責轉移的索引位置邊界,如果到達這個邊界則說明當前執行緒已經完成了所負責的索引長度的節點
            //轉移舊陣列中的元素節點是從陣列的尾部向陣列的頭部開始轉移
            int nextIndex, nextBound;
            //每次轉移完一個索引位置上的節點的時候都會校驗一下下一次轉移的索引位置是否已經超出邊界
            //或舊陣列中的元素節點都已經全部轉移完成
            //如果下一次轉移的索引位置超出邊界,但是剩下需要轉移的節點沒有被其它執行緒協助轉移
            //那麼當前執行緒則繼續選擇部分的索引長度來轉移
            if (--i >= bound || finishing)
                advance = false;
            //校驗剩餘需要轉移的索引長度是否為0,如果為0則說明舊陣列中沒有需要轉移的元素節點了
            else if ((nextIndex = transferIndex) <= 0) {
                //將轉移的節點的索引位置設定為-1,後續會根據該條件退出擴容方法
                i = -1;
                advance = false;
            //根據開始轉移的長度位置與每個執行緒需要轉移的長度進行比較
            //如果開始轉移的長度位置大於每個執行緒需要轉移的長度,那就使用開始轉移的長度位置減去每個執行緒需要轉移的長度
            //獲取到當前執行緒需要負責轉移的索引位置邊界
            //如果開始轉移的長度位置小於等於每個執行緒需要轉移的長度,那就說明當前需要轉移的長度不需要其它執行緒協助
            //當前執行緒則會將剩下需要轉移的節點轉移到新的陣列中
            } else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
                //將計算後的索引邊界賦予bound,用於執行緒每次轉移之後進行校驗
                //如果已經到達了邊界說明執行緒已經完成了所負責的索引長度的節點轉移
                //執行緒不再執行節點的轉移
                bound = nextBound;
                //開始轉移的長度位置-1,獲取到開始轉移的節點的索引位置
                i = nextIndex - 1;
                advance = false;
            }
        }
        //i < 0 小於0則說明當前執行緒所負責轉移的節點已經完成並且沒有其它需要轉移的節點了
        //i >= n
        //i + n >= nextn
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            //當前finishing為true時則說明舊陣列中的所有節點都已經轉移
            //此時就需要將新陣列設定為當前集合使用的陣列並計算下一次的擴容閾值
            if (finishing) {
                //將擴容的陣列置為空,代表當前沒有執行緒正在進行擴容操作
                nextTable = null;
                //將擴容後的新陣列設定為當前集合正在使用的陣列
                table = nextTab;
                //計算下一次擴容的閾值
                sizeCtl = (n << 1) - (n >>> 1);
                //擴容完成,退出
                return;
            }
            //finishing為false則會走到當前語句,則說明當前執行緒並不知道舊陣列中的元素節點有沒有轉移完成
            //但是當前執行緒所負責轉移的索引節點已經完成,此時就需要將並行擴容中的執行緒數量減1
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                //擴容標記左移16位元獲取到執行緒數量的標記
                //使用sc-2獲取到當前還剩下的執行緒數量的標記
                //如果兩個相等則說明當前執行緒是最後一個擴容結束的執行緒
                //此時就需要當前執行緒執行收尾操作,需要從舊陣列中的尾部開始向頭部節點遍歷來檢查是否所有的元素節點都轉移了
                //如果都轉移了,則將擴容後的新陣列設定為當前集合正在使用的陣列,並且計算下一次擴容的閾值
                //如果還有元素節點沒有轉移,當前執行緒則會將剩下的元素節點進行轉移
                //如果兩個不相等則說明當前執行緒不是最後一個擴容結束的執行緒
                //當前執行緒已經完成了所負責的索引位置的元素節點,並且舊陣列中沒有其他需要轉移的節點了,當前執行緒直接退出擴容
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                //當前執行緒是最後一個結束擴容的執行緒,此時就需要檢查舊陣列中是否所有的元素節點都轉移了
                finishing = advance = true;
                //從舊陣列的尾部開始檢查
                i = n;
            }
        } else if ((f = tabAt(tab, i)) == null)
            //如果指定索引位置上的節點為空則直接將舊陣列中該索引位置上的節點設定成一個正在轉移的節點進行佔位
            //當有新的執行緒要對該索引位置的節點操作的時候則會發現該索引位置上的節點是一個正在轉移的節點
            //則不會對該索引位置上的節點進行操作而是先協助擴容執行緒進行轉移
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED)
            //指定索引位置上的節點已經被其它執行緒處理過
            advance = true;
        else {
            //加鎖,防止其它執行緒對當前需要移動的節點進行操作
            synchronized (f) {
                //校驗節點是否變更
                if (tabAt(tab, i) == f) {
                    //ln 低位節點,該節點放置到新陣列中的索引位置與在舊陣列中的索引位置相同
                    //hn 高位節點,該節點放置到新陣列中的索引位置是在舊陣列中的索引位置加上舊陣列的長度
                    Node<K, V> ln, hn;
                    //校驗節點的hash值是否大於等於0
                    //如果節點的hash值大於等於0則說明該索引位置上只有一個節點或節點是一個連結串列節點
                    if (fh >= 0) {
                        //使用節點的hash值與舊陣列的長度進行與運算
                        //與運算後的結果分為0和1,0則將該節點放置到低位,1則將節點放置高位
                        int runBit = fh & n;
                        //避免後續轉移節點的時候沒有必要的迴圈以及建立節點
                        Node<K, V> lastRun = f;
                        //遍歷整個連結串列來決定從那個節點開始以及後續的節點都是沒有必要遍歷和建立的
                        //而是直接使用指標指向舊陣列中的節點,當擴容完成之後舊陣列以及舊陣列中部分沒有被指標參照的節點則會被回收
                        for (Node<K, V> p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        //沒有必要回圈和建立的節點應該放置到新陣列中的低為還是高位
                        if (runBit == 0) {
                            //低位
                            ln = lastRun;
                            hn = null;
                        } else {
                            //高位
                            hn = lastRun;
                            ln = null;
                        }
                        //從頭節點開始遍歷將需要重新建立的節點進行建立並新增到高位或低位
                        //在新增到高位或低位的時候,新建立的節點使用的是頭插法
                        //如果有節點不需要重新建立,那不需要重新建立的節點則會放到高位或低位節點的尾部
                        //在上面的時候如果不需要重新建立的節點其實就已經放在了ln或hn中
                        //當有節點重新建立了的時候,則ln或hn設定為新建立的節點的下一個節點
                        //其實整體來說就是頭插法,如果說整個連結串列或部分連續的連結串列節點不需要重新建立的時候還是保持在舊陣列中一樣的順序
                        for (Node<K, V> p = f; p != lastRun; p = p.next) {
                            int ph = p.hash;
                            K pk = p.key;
                            V pv = p.val;
                            if ((ph & n) == 0)
                                //低位
                                ln = new Node<K, V>(ph, pk, pv, ln);
                            else
                                //高位
                                hn = new Node<K, V>(ph, pk, pv, hn);
                        }
                        //將低位節點連結串列新增到新陣列中所在的索引位置與舊陣列所在的索引位置相同
                        setTabAt(nextTab, i, ln);
                        //將高位節點連結串列新增到新陣列中所在的索引位置是在舊陣列中所在的索引位置加上舊陣列的長度
                        setTabAt(nextTab, i + n, hn);
                        //將舊陣列中的索引位置上的節點設定為一個已經轉移的節點
                        setTabAt(tab, i, fwd);
                        //繼續推進下一次節點轉移
                        advance = true;
                    //節點是一個紅黑樹節點
                    } else if (f instanceof TreeBin) {
                        TreeBin<K, V> t = (TreeBin<K, V>) f;
                        //低位頭節點和尾節點
                        TreeNode<K, V> lo = null, loTail = null;
                        //高位頭節點和尾節點
                        TreeNode<K, V> hi = null, hiTail = null;
                        //低位節點和高位節點的數量
                        int lc = 0, hc = 0;
                        //從TreeBin物件中記錄的連結串列的頭節點開始遍歷將每一個節點分為低位節點和高位節點
                        for (Node<K, V> e = t.first; e != null; e = e.next) {
                            int h = e.hash;
                            //構造新的樹節點
                            TreeNode<K, V> p = new TreeNode<K, V>(h, e.key, e.val, null, null);
                            if ((h & n) == 0) {
                                //將構造的樹節點的上一個節點指標指向原低位尾節點
                                //如果原低尾節點為空則說明當前樹節點是第一個節點
                                //那就將當前樹節點設定為低位頭節點
                                if ((p.prev = loTail) == null)
                                    lo = p;
                                else
                                    //原低位尾節點不為空則將原尾節點的下一個節點指標指向當前樹節點
                                    loTail.next = p;
                                //將新構造的樹節點設定為低位尾節點
                                loTail = p;
                                //低位節點的數量自增
                                ++lc;
                            } else {
                                if ((p.prev = hiTail) == null)
                                    hi = p;
                                else
                                    hiTail.next = p;
                                hiTail = p;
                                ++hc;
                            }
                        }
                        //拆分後的高低位節點的數量是否小於等於紅黑樹轉連結串列的閾值
                        //如果小於等於則呼叫untreeify方法將樹節點轉換為連結串列節點
                        //如果高位節點數量或低位節點數量大於閾值則會校驗對方節點的數量是否不等於0
                        //如果說對方的節點數量等於0則說明節點並沒有拆分為高位或低位節點
                        //那就使用原本的TreeBin物件進行轉移
                        //如果對方的節點數量大於0則說明已經拆分為了高低位節點
                        //此時就需要將高低位節點轉換為紅黑樹並封裝成一個TreeBin物件
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin<K, V>(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin<K, V>(hi) : t;
                        //將低位節點TreeBin物件新增到新陣列中所在的索引位置與舊陣列所在的索引位置相同
                        setTabAt(nextTab, i, ln);
                        //將高位節點TreeBin新增到新陣列中所在的索引位置是在舊陣列中所在的索引位置加上舊陣列的長度
                        setTabAt(nextTab, i + n, hn);
                        //將舊陣列中的索引位置上的節點設定為一個已經轉移的節點
                        setTabAt(tab, i, fwd);
                        //繼續推進下一次節點轉移
                        advance = true;
                    }
                }
            }
        }
    }
}

int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
    stride = MIN_TRANSFER_STRIDE;
if (nextTab == null) {
    try {
        @SuppressWarnings("unchecked")
        Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n << 1];
        nextTab = nt;
    } catch (Throwable ex) {
        sizeCtl = Integer.MAX_VALUE;
        return;
    }
    nextTable = nextTab;
    transferIndex = n;
}

ForwardingNode<K, V> fwd = new ForwardingNode<K, V>(nextTab);
ForwardingNode(Node<K,V>[] tab) {
    super(MOVED, null, null, null);
    this.nextTable = tab;
}

while (advance) {
    int nextIndex, nextBound;
    if (--i >= bound || finishing)
        advance = false;
    else if ((nextIndex = transferIndex) <= 0) {
        i = -1;
        advance = false;
    } else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
        bound = nextBound;
        i = nextIndex - 1;
        advance = false;
    }
}

if (i < 0 || i >= n || i + n >= nextn) {
    int sc;
    if (finishing) {
        nextTable = null;
        table = nextTab;
        sizeCtl = (n << 1) - (n >>> 1);
        return;
    }
    if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
        if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
            return;
        finishing = advance = true;
        i = n;
    }
}

else if ((f = tabAt(tab, i)) == null)
    advance = casTabAt(tab, i, null, fwd);

else if ((fh = f.hash) == MOVED)
    advance = true;

synchronized (f) {
    if (tabAt(tab, i) == f) {
        Node<K, V> ln, hn;
        if (fh >= 0) {
            int runBit = fh & n;
            Node<K, V> lastRun = f;
            for (Node<K, V> p = f.next; p != null; p = p.next) {
                int b = p.hash & n;
                if (b != runBit) {
                    runBit = b;
                    lastRun = p;
                }
            }
            if (runBit == 0) {
                ln = lastRun;
                hn = null;
            } else {
                hn = lastRun;
                ln = null;
            }
            for (Node<K, V> p = f; p != lastRun; p = p.next) {
                int ph = p.hash;
                K pk = p.key;
                V pv = p.val;
                if ((ph & n) == 0)
                    ln = new Node<K, V>(ph, pk, pv, ln);
                else
                    hn = new Node<K, V>(ph, pk, pv, hn);
            }
            setTabAt(nextTab, i, ln);
            setTabAt(nextTab, i + n, hn);
            setTabAt(tab, i, fwd);
            advance = true;
        } else if (f instanceof TreeBin) {
            TreeBin<K, V> t = (TreeBin<K, V>) f;
            TreeNode<K, V> lo = null, loTail = null;
            TreeNode<K, V> hi = null, hiTail = null;
            int lc = 0, hc = 0;
            for (Node<K, V> e = t.first; e != null; e = e.next) {
                int h = e.hash;
                TreeNode<K, V> p = new TreeNode<K, V>(h, e.key, e.val, null, null);
                if ((h & n) == 0) {
                    if ((p.prev = loTail) == null)
                        lo = p;
                    else
                        loTail.next = p;
                    loTail = p;
                    ++lc;
                } else {
                    if ((p.prev = hiTail) == null)
                        hi = p;
                    else
                        hiTail.next = p;
                    hiTail = p;
                    ++hc;
                }
            }
            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin<K, V>(lo) : t;
            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin<K, V>(hi) : t;
            setTabAt(nextTab, i, ln);
            setTabAt(nextTab, i + n, hn);
            setTabAt(tab, i, fwd);
            advance = true;
        }
    }
}