ConcurrentHashMap 是一個支持并發(fā)檢索和并發(fā)更新的線程安全的HashMap（但不允許空key或value）胚宦。不管是在實際工作或者是面試中填大，ConcurrentHashMap 都是在整個JUC集合框架里出現(xiàn)頻率最高的一個類纵顾，所以，對ConcurrentHashMap有一個深入的認(rèn)識對我們自身還是非常重要的栋盹。本章我們來從源碼層面詳細(xì)分析 ConcurrentHashMap 的實現(xiàn)（基于JDK 8）施逾，希望對大家有所幫助。

1. 概述

ConcurrentHashMap 在JDK 7之前是通過Lock和Segment（分段鎖）實現(xiàn)并發(fā)安全例获，JDK 8之后改為CAS+synchronized來保證并發(fā)安全（為了序列化兼容汉额，JDK 8的代碼中還是保留了Segment的部分代碼）。由于筆者沒有過多研究過JDK 7的源碼榨汤，所以我們后面的分析主要針對JDK 8蠕搜。

首先來看一下ConcurrentHashMap、HashMap和HashTable的區(qū)別：

HashMap 是非線程安全的哈希表收壕，常用于單線程程序中妓灌。
Hashtable 是線程安全的哈希表，由于是通過內(nèi)置鎖 synchronized 來保證線程安全蜜宪，在資源爭用比較高的環(huán)境下虫埂，Hashtable 的效率比較低。
ConcurrentHashMap 是一個支持并發(fā)操作的線程安全的HashMap圃验，但是他不允許存儲空key或value掉伏。使用CAS+synchronized來保證并發(fā)安全，在并發(fā)訪問時不需要阻塞線程澳窑，所以效率是比Hashtable 要高的斧散。

2. 數(shù)據(jù)結(jié)構(gòu)

ConcurrentHashMap數(shù)據(jù)結(jié)構(gòu)

ConcurrentHashMap 是通過Node來存儲K-V的，從上圖可以看出摊聋，它的內(nèi)部有很多Node節(jié)點（在內(nèi)部封裝了一個Node數(shù)組-table）鸡捐，不同的節(jié)點有不同的作用。下面我們來詳細(xì)看一下這幾個Node節(jié)點類：

Node

Node<K, V>： 保存k-v麻裁、k的hash值和鏈表的 next 節(jié)點引用箍镜，其中 V 和 next 用volatile修飾瞻鹏，保證多線程環(huán)境下的可見性。
TreeNode<K, V>： 紅黑樹節(jié)點類,當(dāng)鏈表長度>=8且數(shù)組長度>=64時鹿寨，Node 會轉(zhuǎn)為 TreeNode新博，但它不是直接轉(zhuǎn)為紅黑樹，而是把這些 TreeNode 節(jié)點放入TreeBin 對象中脚草，由 TreeBin 完成紅黑樹的封裝赫悄。
TreeBin<K, V>： 封裝了 TreeNode，紅黑樹的根節(jié)點馏慨，也就是說在 ConcurrentHashMap 中紅黑樹存儲的是 TreeBin 對象埂淮。
ForwardingNode<K, V>： 在節(jié)點轉(zhuǎn)移時用于連接兩個 table（table和nextTable）的節(jié)點類。包含一個 nextTable 指針写隶，用于指向下一個table倔撞。而且這個節(jié)點的 k-v 和 next 指針全部為 null，hash 值為-1慕趴。只有在擴(kuò)容時發(fā)揮作用痪蝇，作為一個占位節(jié)點放在 table 中表示當(dāng)前節(jié)點已經(jīng)被移動。
ReservationNode<K,V>： 在computeIfAbsent和compute方法計算時當(dāng)做一個占位節(jié)點冕房，表示當(dāng)前節(jié)點已經(jīng)被占用躏啰，在compute或computeIfAbsent的 function 計算完成后插入元素。hash值為-3耙册。

2.1 核心參數(shù)

//最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;
//初始容量
private static final int DEFAULT_CAPACITY = 16;
//數(shù)組最大容量
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//默認(rèn)并發(fā)度给僵，兼容1.7及之前版本
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//加載/擴(kuò)容因子，實際使用n - (n >>> 2)
private static final float LOAD_FACTOR = 0.75f;
//鏈表轉(zhuǎn)紅黑樹的節(jié)點數(shù)閥值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹轉(zhuǎn)鏈表的節(jié)點數(shù)閥值
static final int UNTREEIFY_THRESHOLD = 6;
//當(dāng)數(shù)組長度還未超過64,優(yōu)先數(shù)組的擴(kuò)容,否則將鏈表轉(zhuǎn)為紅黑樹
static final int MIN_TREEIFY_CAPACITY = 64;
//擴(kuò)容時任務(wù)的最小轉(zhuǎn)移節(jié)點數(shù)
private static final int MIN_TRANSFER_STRIDE = 16;
//sizeCtl中記錄stamp的位數(shù)
private static int RESIZE_STAMP_BITS = 16;
//幫助擴(kuò)容的最大線程數(shù)
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
//size在sizeCtl中的偏移量
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

//存放Node元素的數(shù)組,在第一次插入數(shù)據(jù)時初始化
transient volatile Node<K,V>[] table;
//一個過渡的table表,只有在擴(kuò)容的時候才會使用
private transient volatile Node<K,V>[] nextTable;
//基礎(chǔ)計數(shù)器值(size = baseCount + CounterCell[i].value)
private transient volatile long baseCount;
//控制table初始化和擴(kuò)容操作
private transient volatile int sizeCtl;
//節(jié)點轉(zhuǎn)移時下一個需要轉(zhuǎn)移的table索引
private transient volatile int transferIndex;
//元素變化時用于控制自旋
private transient volatile int cellsBusy;
// 保存table中的每個節(jié)點的元素個數(shù) 2的冪次方
// size = baseCount + CounterCell[i].value
private transient volatile CounterCell[] counterCells;

table：Node數(shù)組详拙，在第一次插入元素的時候初始化帝际，默認(rèn)初始大小為16，用來存儲Node節(jié)點數(shù)據(jù)饶辙，擴(kuò)容時大小總是2的冪次方蹲诀。

nextTable：默認(rèn)為null，擴(kuò)容時生成的新的數(shù)組畸悬，其大小為原數(shù)組的兩倍侧甫。

sizeCtl ：默認(rèn)為0，用來控制table的初始化和擴(kuò)容操作蹋宦，在不同的情況下有不同的涵義：

-1 代表table正在初始化
-N 表示有N-1個線程正在進(jìn)行擴(kuò)容操作
初始化數(shù)組或擴(kuò)容完成后,將sizeCtl的值設(shè)為0.75*n
在擴(kuò)容操作在進(jìn)行節(jié)點轉(zhuǎn)移前，sizeCtl改為(hash << RESIZE_STAMP_SHIFT) + 2咒锻，這個值為負(fù)數(shù)冷冗，并且每有一個線程參與擴(kuò)容操作sizeCtl就加1

transferIndex：擴(kuò)容時用到，初始時為table.length惑艇，表示從索引 0 到transferIndex的節(jié)點還未轉(zhuǎn)移蒿辙。

counterCells： ConcurrentHashMap的特定計數(shù)器拇泛，實現(xiàn)方法跟LongAdder類似。這個計數(shù)器的機(jī)制避免了在更新時的資源爭用思灌，但是如果并發(fā)讀取太頻繁會導(dǎo)致緩存超負(fù)荷俺叭，為了避免讀取太頻繁，只有在添加了兩個以上節(jié)點時才可以嘗試擴(kuò)容操作泰偿。在統(tǒng)一hash分配的前提下熄守，發(fā)生這種情況的概率在13%左右，也就是說只有大約1/8的put操作才會檢查擴(kuò)容（并且在擴(kuò)容后會更少）耗跛。

hash計算公式：hash = (key.hashCode ^ (key.hashCode >>> 16)) & HASH_BITS
索引計算公式：(table.length-1)&hash

3. 源碼解析

3.1 put(K, V)

public V put(K key, V value) {
    return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    //計算hash值
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {//自旋
        //f:索引節(jié)點; n:tab.length; i:新節(jié)點索引 (n - 1) & hash; fh:f.hash
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            //初始化
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//索引i節(jié)點為空裕照，直接插入
            //cas插入節(jié)點,成功則跳出循環(huán)
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        //當(dāng)前節(jié)點處于移動狀態(tài)-其他線程正在進(jìn)行節(jié)點轉(zhuǎn)移操作
        else if ((fh = f.hash) == MOVED)
            //幫助轉(zhuǎn)移
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {//check stable
                    //f.hash>=0,說明f是鏈表的頭結(jié)點
                    if (fh >= 0) {
                        binCount = 1;//記錄鏈表節(jié)點數(shù)，用于后面是否轉(zhuǎn)換為紅黑樹做判斷
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            //key相同 修改
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            //到這里說明已經(jīng)是鏈表尾调塌，把當(dāng)前值作為新的節(jié)點插入到隊尾
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    //紅黑樹節(jié)點操作
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                //如果鏈表中節(jié)點數(shù)binCount >= TREEIFY_THRESHOLD(默認(rèn)是8)晋南，則把鏈表轉(zhuǎn)化為紅黑樹結(jié)構(gòu)
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    //更新新元素個數(shù)
    addCount(1L, binCount);
    return null;
}

說明：在 ConcurrentHashMap 中，put 方法幾乎涵蓋了所有內(nèi)部的函數(shù)操作羔砾。所以负间，我們將從put函數(shù)開始逐步向下分析。
首先說一下put的流程姜凄，后面再詳細(xì)分析每一個流程的具體實現(xiàn)（閱讀時請結(jié)合源碼）：

計算當(dāng)前key的hash值唉擂，根據(jù)hash值計算索引 i （i=(table.length - 1) & hash）；
如果當(dāng)前table為null檀葛，說明是第一次進(jìn)行put操作玩祟，調(diào)用initTable()初始化table；
如果索引 i 位置的節(jié)點 f 為空屿聋，則直接把當(dāng)前值作為新的節(jié)點直接插入到索引 i 位置空扎；
如果節(jié)點 f 的hash為-1（f.hash == MOVED(-1)），說明當(dāng)前節(jié)點處于移動狀態(tài)（或者說是其他線程正在對 f 節(jié)點進(jìn)行轉(zhuǎn)移/擴(kuò)容操作）润讥，此時調(diào)用helpTransfer(tab, f)幫助轉(zhuǎn)移/擴(kuò)容转锈；
如果不屬于上述條件，說明已經(jīng)有元素存儲到索引 i 處（即發(fā)生了哈希碰撞）楚殿，此時需要對索引 i 處的節(jié)點 f 進(jìn)行 put or update 操作撮慨，首先使用內(nèi)置鎖 synchronized 對節(jié)點 f 進(jìn)行加鎖：

如果f.hash>=0，說明 i 位置是一個鏈表脆粥，并且節(jié)點 f 是這個鏈表的頭節(jié)點砌溺，則對 f 節(jié)點進(jìn)行遍歷，此時分兩種情況：
- 如果鏈表中某個節(jié)點e的key與當(dāng)前key的hash相同变隔，則對這個節(jié)點e的value進(jìn)行修改操作规伐。
- 如果遍歷到鏈表尾都沒有找到與當(dāng)前key相同的節(jié)點，則把當(dāng)前K-V作為一個新的節(jié)點插入到這個鏈表尾部匣缘。
如果節(jié)點 f 是TreeBin節(jié)點(f instanceof TreeBin)猖闪，說明索引 i 位置的節(jié)點是一個紅黑樹鲜棠，則調(diào)用putTreeVal方法找到一個已存在的節(jié)點進(jìn)行修改，或者是把當(dāng)前K-V放入一個新的節(jié)點（put or update）培慌。

完成插入后豁陆，如果索引 i 處是一個鏈表，并且在插入新的節(jié)點后節(jié)點數(shù)>8吵护，則調(diào)用treeifyBin把鏈表轉(zhuǎn)換為紅黑樹盒音。
最后，調(diào)用addCount更新元素數(shù)量

3.1.1 initTable()

/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)//其他線程正在進(jìn)行初始化或轉(zhuǎn)移操作何址，讓出CPU執(zhí)行時間片里逆，繼續(xù)自旋
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {//CAS設(shè)置sizectl為-1 表示當(dāng)前線程正在進(jìn)行初始化
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);//0.75*n 設(shè)置擴(kuò)容閾值
                }
            } finally {
                sizeCtl = sc;//初始化sizeCtl=0.75*n
            }
            break;
        }
    }
    return tab;
}

說明：初始化操作，ConcurrentHashMap的初始化在第一次插入數(shù)據(jù)的時候(判斷table是否為null)用爪，注意初始化操作為單線程操作（如果有其他線程正在進(jìn)行初始化原押，則調(diào)用Thread.yield()讓出CPU時間片，自旋等待table初始完成）偎血。

3.1.2 helpTransfer(Node<K,V>[], Node<K,V>)

//幫助其他線程進(jìn)行轉(zhuǎn)移操作
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    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) {
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)//不需要幫助轉(zhuǎn)移诸衔，跳出
                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {//CAS更新幫助轉(zhuǎn)移的線程數(shù)
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

說明： 如果索引到的節(jié)點的 hash 為-1，說明當(dāng)前節(jié)點處于移動狀態(tài)（或者說是其他線程正在對 f 節(jié)點進(jìn)行轉(zhuǎn)移操作颇玷。這里主要是靠 ForwardingNode 節(jié)點來檢測笨农，在transfer方法中，被轉(zhuǎn)移后的節(jié)點會改為ForwardingNode帖渠，它是一個占位節(jié)點谒亦，并且hash=MOVED（-1），也就是說空郊，我們可以通過判斷hash是否為MOVED來確定當(dāng)前節(jié)點的狀態(tài)）份招，此時調(diào)用helpTransfer(tab, f)幫助轉(zhuǎn)移，主要操作就是更新幫助轉(zhuǎn)移的線程數(shù)（sizeCtl+1）狞甚，然后調(diào)用transfer方法進(jìn)行轉(zhuǎn)移操作锁摔，transfer后面我們會詳細(xì)分析。

3.1.3 treeifyBin(Node<K,V>[] , index)

private final void treeifyBin(Node<K,V>[] tab, int index) {
        Node<K,V> b; int n, sc;
        if (tab != null) {
            //當(dāng)數(shù)組長度還未超過64,優(yōu)先數(shù)組的擴(kuò)容,否則將鏈表轉(zhuǎn)為紅黑樹
            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                //兩倍擴(kuò)容
                tryPresize(n << 1);
            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                synchronized (b) {
                    if (tabAt(tab, index) == b) {//check stable
                        //hd：節(jié)點頭
                        TreeNode<K,V> hd = null, tl = null;
                        //遍歷轉(zhuǎn)換節(jié)點
                        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;
                        }
                        setTabAt(tab, index, new TreeBin<K,V>(hd));
                    }
                }
            }
        }
    }

說明： 在put操作完成后哼审，如果當(dāng)前節(jié)點為一個鏈表谐腰，并且鏈表長度>=TREEIFY_THRESHOLD(8)，此時就需要調(diào)用treeifyBin方法來把當(dāng)前鏈表轉(zhuǎn)為一個紅黑樹涩盾。treeifyBin主要進(jìn)行兩步操作：

如果當(dāng)前table長度還未超過MIN_TREEIFY_CAPACITY(64)十气，則優(yōu)先對數(shù)組進(jìn)行擴(kuò)容操作，容量為原來的2倍(n<<1)旁赊。
否則就對當(dāng)前節(jié)點進(jìn)行轉(zhuǎn)換操作（注意這個操作是單線程完成的）桦踊。遍歷鏈表節(jié)點，把Node轉(zhuǎn)換為TreeNode终畅，然后在通過TreeBin來構(gòu)造紅黑樹（紅黑樹的構(gòu)造這里就不在詳細(xì)介紹了）籍胯。

3.1.4 tryPresize(int size)

private final void tryPresize(int size) {
    int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
        tableSizeFor(size + (size >>> 1) + 1);//計算一個近似size的2的冪次方數(shù)
    int sc;
    while ((sc = sizeCtl) >= 0) {
        Node<K,V>[] tab = table; int n;
        //未初始化
        if (tab == null || (n = tab.length) == 0) {
            n = (sc > c) ? sc : c;
            if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if (table == tab) {
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
            }
        }
        //已達(dá)到最大容量
        else if (c <= sc || n >= MAXIMUM_CAPACITY)
            break;
        else if (tab == table) {
            int rs = resizeStamp(n);
            //正在進(jìn)行擴(kuò)容操作
            if (sc < 0) {
                Node<K,V>[] nt;
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
        }
    }
}

說明： 當(dāng)table容量不足時，需要對其進(jìn)行兩倍擴(kuò)容离福。tryPresize方法很簡單杖狼，主要就是用來檢查擴(kuò)容前的必要條件（比如是否超過最大容量），真正的擴(kuò)容其實也可以叫“節(jié)點轉(zhuǎn)移”妖爷，主要是通過transfer方法完成蝶涩。

3.1.5 transfer(Node<K,V> tab, Node<K,V> nextTab)

//轉(zhuǎn)移或復(fù)制節(jié)點到新的table
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    //轉(zhuǎn)移幅度( tab.length/(NCPU*8) )，最小為16
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    if (nextTab == null) {            // initiating
        try {
            //根據(jù)當(dāng)前數(shù)組長度,新建一個兩倍長度的數(shù)組nextTab
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;//初始為table的最后一個索引
    }
    int nextn = nextTab.length;
    //初始化ForwardingNode節(jié)點,持有nextTab的引用,在處理完每個節(jié)點之后當(dāng)做占位節(jié)點絮识，表示該槽位已經(jīng)處理過了
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true;//節(jié)點是否已經(jīng)處理
    boolean finishing = false; // to ensure sweep before committing nextTab
    //自旋移動每個節(jié)點绿聘，從transferIndex開始移動stride個節(jié)點到新的table。
    //i：當(dāng)前處理的Node索引次舌；bound：需要處理節(jié)點的索引邊界
    for (int i = 0, bound = 0;;) {
        //f:當(dāng)前處理i位置的node; fh:f.hash
        Node<K,V> f; int fh;
        //通過while循環(huán)獲取本次需要移動的節(jié)點索引i
        while (advance) {
            //nextIndex:下一個要處理的節(jié)點索引; nextBound:下一個需要處理的節(jié)點的索引邊界
            int nextIndex, nextBound;
            if (--i >= bound || finishing)//通過--i控制下一個需要移動的節(jié)點
                advance = false;
            //節(jié)點已全部轉(zhuǎn)移
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            //transferIndex（初值為最后一個節(jié)點的索引）熄攘，表示從transferIndex開始后面所有的節(jié)點都已分配，
            //每次線程領(lǐng)取擴(kuò)容任務(wù)后彼念，需要更新transferIndex的值(transferIndex-stride)挪圾。
            //CAS修改transferIndex，并更新索引邊界
            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) {//已完成轉(zhuǎn)移逐沙，更新相關(guān)屬性
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);//1.5*n 擴(kuò)容閾值設(shè)置為原來容量的1.5倍  依然相當(dāng)于現(xiàn)在容量的0.75倍
                return;
            }
            //當(dāng)前線程已經(jīng)完成轉(zhuǎn)移哲思，但可能還有其他線程正在進(jìn)行轉(zhuǎn)移操作
            //每個線程完成自己的擴(kuò)容操作后就對sizeCtl-1
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                //判斷是否全部任務(wù)已經(jīng)完成,sizeCtl初始值=(rs << RESIZE_STAMP_SHIFT) + 2)
                //這里判斷如果還有其他線程正在操作，直接返回吩案，否則的話重新初始化i對原tab進(jìn)行一遍檢查然后再提交
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                finishing = advance = true;
                i = n; // recheck before commit
            }
        }
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);//i位置節(jié)點為空棚赔，替換為ForwardingNode節(jié)點，用于通知其他線程該位置已經(jīng)處理
        else if ((fh = f.hash) == MOVED)//節(jié)點已經(jīng)被其他線程處理過徘郭，繼續(xù)處理下一個節(jié)點
            advance = true; // already processed
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {//check stable
                    //處理當(dāng)前拿到的節(jié)點,構(gòu)建兩個node:ln/hn靠益。ln:原位置; hn:i+n位置
                    Node<K,V> ln, hn;

                    if (fh >= 0) {//當(dāng)前為鏈表節(jié)點（fh>=0）
                        //使用fn&n把原鏈表中的元素分成兩份（fn&n = n or 0）
                        //在表擴(kuò)容2倍后，索引i可能發(fā)生改變崎岂，如果原table長度n=2^x捆毫，如果hash的x位為1，此時需要加上x位的值冲甘，也就是i+n绩卤；
                        //如果x位為0，索引i不變
                        int runBit = fh & n; // n or 0
                        //最后一個與頭節(jié)點f索引不同的節(jié)點
                        Node<K,V> lastRun = f;
                        //從索引i的節(jié)點開始向后查找最后一個有效節(jié)點
                        for (Node<K,V> p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;//n or 0
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        } else {
                            hn = lastRun;
                            ln = null;
                        }
                        //把f鏈表分解為兩個鏈表
                        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);
                            //i+n位置
                            else
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        //nextTab的i位置插入一個鏈表
                        setTabAt(nextTab, i, ln);
                        //nextTab的i+n位置插入一個鏈表
                        setTabAt(nextTab, i + n, hn);
                        //在table的i位置上插入forwardNode節(jié)點  表示已經(jīng)處理過該節(jié)點
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    /**
                     * 如果該節(jié)點是紅黑樹結(jié)構(gòu)江醇，則構(gòu)造樹節(jié)點lo和hi濒憋，遍歷紅黑樹中的節(jié)點，同樣是根據(jù)hash&tab.length算法陶夜，
                     * 把節(jié)點分為兩類凛驮，分別插入索引i和(i+n)位置。
                     */
                    else if (f instanceof TreeBin) {
                        //轉(zhuǎn)為根結(jié)點
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> lo = null, loTail = null;//低位(i)節(jié)點和低位尾節(jié)點
                        TreeNode<K,V> hi = null, hiTail = null;//高位(i+n)節(jié)點和高位尾節(jié)點
                        int lc = 0, hc = 0;
                        //從首個節(jié)點向后遍歷
                        for (Node<K,V> e = t.first; e != null; e = e.next) {
                            int h = e.hash;
                            //構(gòu)建樹節(jié)點
                            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;
                            }
                            //i+n位置
                            else {
                                if ((p.prev = hiTail) == null)
                                    hi = p;
                                else
                                    hiTail.next = p;
                                hiTail = p;
                                ++hc;
                            }
                        }
                        //如果擴(kuò)容后已經(jīng)不再需要tree的結(jié)構(gòu) 反向轉(zhuǎn)換為鏈表結(jié)構(gòu)
                        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;
                    }
                }
            }
        }
    }
}

說明： transfer方法是table擴(kuò)容的核心實現(xiàn)条辟。由于 ConcurrentHashMap 的擴(kuò)容是新建一個table黔夭，所以主要問題就是如何把舊table的元素轉(zhuǎn)移到新的table上宏胯。所以，擴(kuò)容問題就演變成了“節(jié)點轉(zhuǎn)移”問題本姥。首先總結(jié)一下需要轉(zhuǎn)移節(jié)點（調(diào)用transfer）的幾個條件：

對table進(jìn)行擴(kuò)容時
在更新元素數(shù)目時(addCount方法)肩袍，元素總數(shù)>=sizeCtl（sizeCtl=0.75n，達(dá)到擴(kuò)容閥值）婚惫，此時也需要擴(kuò)容
在put操作時氛赐，發(fā)現(xiàn)索引節(jié)點正在轉(zhuǎn)移(hash==MOVED)，此時需要幫助轉(zhuǎn)移

在進(jìn)行節(jié)點轉(zhuǎn)移之前先舷，首先要做的就是重新初始化sizeCtl的值（sizeCtl = (hash << RESIZE_STAMP_SHIFT) + 2）艰管，這個值是一個負(fù)值，用于標(biāo)識當(dāng)前table正在進(jìn)行轉(zhuǎn)移操作蒋川，并且每有一個線程參與轉(zhuǎn)移牲芋，sizeCtl就加1。transfer執(zhí)行步驟如下（請結(jié)合源碼注釋閱讀）：

計算轉(zhuǎn)移幅度stride（或者說是當(dāng)前線程需要轉(zhuǎn)移的節(jié)點數(shù)）尔破，最小為16街图；
創(chuàng)建一個相當(dāng)于當(dāng)前 table 兩倍容量的 Node 數(shù)組，轉(zhuǎn)移完成后用作新的 table懒构；
從transferIndex（初始為table.length餐济，也就是 table 的最后一個節(jié)點）開始，依次向前處理stride個節(jié)點胆剧。前面介紹過絮姆，table 的每個節(jié)點都可能是一個鏈表結(jié)構(gòu)，因為在 put 的時候是根據(jù)(table.length-1)&hash計算出的索引秩霍，當(dāng)插入新值時篙悯，如果通過 key 計算出的索引已經(jīng)存在節(jié)點，那么這個新值就放在這個索引位節(jié)點的尾部(Node.next)铃绒。所以鸽照，在進(jìn)行節(jié)點轉(zhuǎn)移后，由于 table.length 變?yōu)樵瓉淼膬杀兜咝韵鄳?yīng)的索引也會改變矮燎，這時候就需要對鏈表進(jìn)行分割，我們來看一下這個分割算法：

假設(shè)當(dāng)前處理的節(jié)點 table[i]=f赔癌，并且它是一個鏈表結(jié)構(gòu)诞外，原table容量為 n=2^x，索引計算公式為i=(n - 1)&hash灾票。在表擴(kuò)張后峡谊，由于容量 n 變?yōu)?2^x+1 = 2*2^x，所以索引計算就變?yōu)?code>i=(2n - 1)&hash。如果 hash 的 x 位為0既们，則 hash&(2^x-1)=hash濒析，此時 hash&(2^x-1) == hash&(2^x+1-1)，索引位 i 不變贤壁；如果 hash 的 x 位為1悼枢，則 hash&2^x=2^x == n埠忘，在擴(kuò)容后 x 變?yōu)?x+1脾拆，此時的索引需要加上 x 位的值，即 _i=hash&(2^x-1) + hash&2^x莹妒，也就是 i+n名船。舉個栗子：設(shè) n=100000 (2⁵)，x=5旨怠，hash 為100101（x位是1）渠驼。n-1=011111，那么i=hash&(n-1)=000101鉴腻；擴(kuò)容后容量變?yōu)閙=1000000(2⁶)迷扇，m-1=0111111，那么 i 就變成了 hash&(m-1)=100101爽哎，也就是說新的索引位_i = i+n蜓席。
如果當(dāng)前節(jié)點為紅黑樹結(jié)構(gòu)，也是利用這個算法進(jìn)行分割课锌，不同的是厨内，在分割完成之后，如果這兩個新的樹節(jié)點<=6渺贤，則調(diào)用untreeify方法把樹結(jié)構(gòu)轉(zhuǎn)為鏈表結(jié)構(gòu)雏胃。

最后把操作過的節(jié)點都設(shè)為 ForwardingNode 節(jié)點（hash= MOVED，這樣別的線程就可以檢測到）志鞍。

transfer操作完成后瞭亮，table的結(jié)構(gòu)變化如下：

擴(kuò)容之后的table變化

3.1.6 addCount(long,int)

private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {//counterCells為null，CAS更新baseCount
        CounterCell a; long v; int m;
        boolean uncontended = true;
        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended =
              U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);//在線程爭用資源時固棚，使用fullAddCount計算更新元素數(shù)
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();//計算元素總數(shù)统翩，用于后面的擴(kuò)容操作
    }
    if (check >= 0) {
        //檢查擴(kuò)容
        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);
            //其他線程在進(jìn)行擴(kuò)容操作
            if (sc < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
            s = sumCount();
        }
    }
}

說明： put操作全部完成后，別忘了更新元素數(shù)量玻孟。addCount用來更新 ConcurrentHashMap 的元素數(shù)唆缴，根據(jù)所傳參數(shù)check決定是否檢查擴(kuò)容，如果需要黍翎，調(diào)用transfer方法進(jìn)行擴(kuò)容/節(jié)點轉(zhuǎn)移面徽。這里面有一個看起來比較復(fù)雜的方法fullAddCount，作用是在線程爭用資源時，使用它來計算更新元素數(shù)趟紊。這個方法的實現(xiàn)類似于LongAdder的add（LongAdder在上面有簡單介紹）氮双，源碼在此就不再詳細(xì)分析了，有興趣的同學(xué)可以研究下霎匈。

4. 總結(jié)

到此戴差，ConcurrentHashMap的分析就告一段落了☆踔觯總的來說源碼比較復(fù)雜暖释，真正理解它還是需要一些耐心的。重點是它的數(shù)據(jù)結(jié)構(gòu)和擴(kuò)容的實現(xiàn)墨吓。
ConcurrentHashMap 源碼分析到此結(jié)束球匕，希望對大家有所幫助，如您發(fā)現(xiàn)文章中有不妥的地方帖烘，請留言指正亮曹，謝謝。

JUC源碼分析-集合篇（一）：ConcurrentHashMap