ConCurrentHashMap是一個(gè)支持高并發(fā)集合删咱，常用的集合之一撵幽，在jdk1.8中ConCurrentHashMap的結(jié)構(gòu)和操作和HashMap都很類似：

• 數(shù)據(jù)結(jié)構(gòu)基于數(shù)組+鏈表/紅黑樹壁榕。
• get通過計(jì)算hash值后取模數(shù)組長(zhǎng)度確認(rèn)索引來查詢?cè)亍?/li>
• put方法也是先找索引位置席镀，然后不存在就直接添加卧檐，存在相同key就替換切蟋。
• 擴(kuò)容都是創(chuàng)建新的table數(shù)組秸妥，原來的數(shù)據(jù)轉(zhuǎn)移到新的table數(shù)組中滚停。

唯一不同的是，HashMap不支持并發(fā)操作粥惧，ConCurrentHashMap是支持并發(fā)操作的键畴。所以ConCurrentHashMap的設(shè)計(jì)也比HashMap也復(fù)雜的多，通過閱讀ConCurrentHashMap的源碼突雪，也更加了解一些并發(fā)的操作,比如：

• volatile 線程可見性
• CAS 樂觀鎖
• synchronized 同步鎖/悲觀鎖

詳見HashMap相關(guān)文章：

詳解HashMap源碼解析（上）

詳解HashMap源碼解析（下）

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

ConCurrentHashMap是由數(shù)組+鏈表/紅黑樹組成的：

image.png

其中左側(cè)部分是一個(gè)哈希表,通過hash算法確定元素在數(shù)組的下標(biāo):

transient volatile Node<K,V>[] table;

鏈表是為了解決hash沖突,當(dāng)發(fā)生沖突的時(shí)候镰吵。采用鏈表法,將元素添加到鏈表的尾部檩禾。其中Node節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)：

 static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;

    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }
}

Node節(jié)點(diǎn)包含：

• hash hash值
• key 值
• value 值
• next next指針

主要屬性字段

// 最大容量
int MAXIMUM_CAPACITY = 1 << 30;

// 初始化容量
int DEFAULT_CAPACITY = 16

// 控制數(shù)組初始化或者擴(kuò)容，為負(fù)數(shù)時(shí)疤祭，表示數(shù)組正在初始化或者擴(kuò)容盼产。-1表示正在初始化。其他情況-n表示n線程正在擴(kuò)容勺馆。
private transient volatile int sizeCtl;

// 裝載因子
float LOAD_FACTOR = 0.75f

// 鏈表長(zhǎng)度為 8 轉(zhuǎn)成紅黑樹
int TREEIFY_THRESHOLD = 8

// 紅黑樹長(zhǎng)度小于6退化成鏈表
int UNTREEIFY_THRESHOLD = 6;

獲取數(shù)據(jù)get

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // 計(jì)算hash值
    int h = spread(key.hashCode());
    // 判斷 tab 不為空并且 tab對(duì)應(yīng)的下標(biāo)不為空 
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // eh < 0 表示遇到擴(kuò)容
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        // 遍歷鏈表戏售，直到遍歷key相等的值    
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

• 獲取數(shù)據(jù)流程：
  • 調(diào)用spread獲取hash值,通過(n - 1) & h取余獲取數(shù)組下標(biāo)的數(shù)據(jù)。
  • 首節(jié)點(diǎn)符合就返回?cái)?shù)據(jù)草穆。
  • eh<0表示遇到了擴(kuò)容灌灾，會(huì)調(diào)用正在擴(kuò)容節(jié)點(diǎn)ForwardingNode的find方法，查找該節(jié)點(diǎn)悲柱，匹配就返回锋喜。
  • 遍歷鏈表，匹配到數(shù)據(jù)就返回豌鸡。
  • 以上都不符合嘿般，返回null。

get如何實(shí)現(xiàn)線程安全

get方法里面沒有使用到鎖涯冠，那是如何實(shí)現(xiàn)線程安全炉奴。主要使用到了volatile。

• volatile

一個(gè)線程對(duì)共享變量的修改蛇更，另外一個(gè)線程能夠立刻看到瞻赶，我們稱為可見性。

cpu運(yùn)行速度比內(nèi)存速度快很多派任，為了均衡和內(nèi)存之間的速度差異砸逊，增加了cpu緩存,如果在cpu緩存中存在cpu需要數(shù)據(jù)，說明命中了cpu緩存掌逛，就不經(jīng)過訪問內(nèi)存痹兜。如果不存在，則要先把內(nèi)存的數(shù)據(jù)載入到cpu緩存中颤诀，在返回給cpu處理器字旭。

在多核cpu的服務(wù)器中，每個(gè)cpu都有自己的緩存崖叫，cpu之間的緩存是不共享的遗淳。 當(dāng)多個(gè)線程在不同的cpu上執(zhí)行時(shí)，比如下圖中心傀，線程A操作的是cpu-1上的緩存屈暗，線程B操作的是cpu-2上的緩存，這個(gè)時(shí)候，線程A對(duì)變量V的操作對(duì)于線程B是不可見的养叛。

image.png

但是一個(gè)變量被volatile聲明种呐，它的意思是：

告訴編譯器，對(duì)這個(gè)變量的讀寫弃甥，不能使用cpu緩存爽室，必須從內(nèi)存中讀取或者寫入。

上面的變量V被volatile聲明淆攻，線程A在cup-1中修改了數(shù)據(jù)阔墩，會(huì)直接寫到內(nèi)存中，不會(huì)寫入到cpu緩存中瓶珊。而線程B無法從cpu緩存讀取變量啸箫，需要從主內(nèi)存拉取數(shù)據(jù)。

• 總結(jié):
  • 使用volatile關(guān)鍵字的變量會(huì)將修改的變量強(qiáng)制寫入內(nèi)存中伞芹。
  • 其他線程讀取變量時(shí)忘苛，會(huì)直接從內(nèi)存中讀取變量。

volatile在get應(yīng)用

• table哈希表

transient volatile Node<K,V>[] table;

使用volatile聲明數(shù)組唱较，表示引用地址是volatile而不是數(shù)組元素是volatile扎唾。

既然不是數(shù)組元素被修飾成volatile，那實(shí)現(xiàn)線程安全在看Node節(jié)點(diǎn)绊汹。

• Node節(jié)點(diǎn)

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}

其中val和next都用了volatile修飾稽屏，在多線程環(huán)境下扮宠，線程A修改節(jié)點(diǎn)val或者新增節(jié)點(diǎn)對(duì)別人線程是可見的西乖。
所以get方法使用無鎖操作是可以保證線程安全。

既然volatile修飾數(shù)組對(duì)get操作沒有效果坛增，那加在volatile上有什么目的呢获雕？

是為了數(shù)組在擴(kuò)容的時(shí)候?qū)ζ渌€程具有可見性。

• jdk 1.8 的get操作不使用鎖收捣，主要有兩個(gè)方面：
  • Node節(jié)點(diǎn)的val和next都用volatile修飾届案，保證線程修改或者新增節(jié)點(diǎn)對(duì)別人線程是可見的。
  • volatile修飾table數(shù)組罢艾，保證數(shù)組在擴(kuò)容時(shí)其它線程是具有可見性的楣颠。

添加數(shù)據(jù)put

put(K key, V value)直接調(diào)用putVal(key, value, false)方法。

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

putVal()方法：

final V putVal(K key, V value, boolean onlyIfAbsent) {
        // key或者value為空咐蚯，報(bào)空指針錯(cuò)誤
        if (key == null || value == null) throw new NullPointerException();
        // 計(jì)算hash值
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                // tab為空或者長(zhǎng)度為0童漩，初始化table
                tab = initTable();
            // 使用volatile查找索引下的數(shù)據(jù)
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                // 索引位置沒有數(shù)據(jù)，使用cas添加數(shù)據(jù)
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            // MOVED表示數(shù)組正在進(jìn)行數(shù)組擴(kuò)容春锋，當(dāng)前進(jìn)行也參加到數(shù)組復(fù)制
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                // 數(shù)組不在擴(kuò)容和也有值矫膨，說明數(shù)據(jù)下標(biāo)處有值
                // 鏈表中有數(shù)據(jù)，使用synchronized同步鎖
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        // 為鏈表
                        if (fh >= 0) {
                            binCount = 1;
                            // 遍歷鏈表
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                // hash 以及key相同，替換value值
                                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;
                                // 遍歷到鏈表尾侧馅，添加鏈表節(jié)點(diǎn)
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        // 紅黑樹危尿，TreeBin哈希值固定為-2
                        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) {
                    // 鏈表轉(zhuǎn)紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

• 添加數(shù)據(jù)流程：
  • 判斷key或者value為null都會(huì)報(bào)空指針錯(cuò)誤。
  • 計(jì)算hash值,然后開啟沒有終止條件的循環(huán)馁痴。
  • 如果table數(shù)組為null,初始化數(shù)組谊娇。
  • 數(shù)組table不為空，通過volatile找到數(shù)組對(duì)應(yīng)下標(biāo)是否為空弥搞，為空就使用CAS添加頭結(jié)點(diǎn)邮绿。
  • 節(jié)點(diǎn)的hash=-1表示數(shù)組正在擴(kuò)容，一起進(jìn)行擴(kuò)容操作攀例。
  • 以上不符合船逮，說明索引處有值，使用synchronized鎖住當(dāng)前位置的節(jié)點(diǎn)粤铭，防止被其他線程修改挖胃。
    • 如果是鏈表，遍歷鏈表梆惯，匹配到相同的key替換value值酱鸭。如果鏈表找不到，就添加到鏈表尾部垛吗。
    • 如果是紅黑樹凹髓，就添加到紅黑樹中。
  • 節(jié)點(diǎn)的鏈表個(gè)數(shù)大于8,鏈表就轉(zhuǎn)成紅黑樹怯屉。

ConcurrentHashMap鍵值對(duì)為什么都不能為null,而HashMap就可以蔚舀？

通過get獲取數(shù)據(jù)時(shí)，如果獲取的數(shù)據(jù)是null锨络，就無法判斷赌躺，是put時(shí)的value為null，還是找個(gè)key就沒做過映射羡儿。HashMap是非并發(fā)的礼患，可以通過contains(key)判斷，而支持并發(fā)的ConcurrentHashMap在調(diào)用contains方法和get方法的時(shí)候掠归，map可能已經(jīng)不同了缅叠。參考

如果數(shù)組table為空調(diào)用initTable初始化數(shù)組：

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    // table 為 null
    while ((tab = table) == null || tab.length == 0) {
       
        if ((sc = sizeCtl) < 0)
         // sizeCtl<0表示其它線程正在初始化數(shù)組數(shù)組，當(dāng)前線程需要讓出CPU
            Thread.yield(); // lost initialization race; just spin
        // 調(diào)用CAS初始化table表    
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            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);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

initTable判斷sizeCtl值虏冻，如果sizeCtl為-1表示有其他線程正在初始化數(shù)組肤粱，當(dāng)前線程調(diào)用Thread.yield讓出CPU。而正在初始化數(shù)組的線程通過Unsafe.compareAndSwapInt方法將sizeCtl改成-1兄旬。

initTable最外層一直使用while循環(huán)狼犯，而非if條件判斷余寥，就是確保數(shù)組可以初始化成功。

數(shù)組初始化成功之后悯森，再執(zhí)行添加的操作宋舷，調(diào)用tableAt通過volatile的方式找到(n-1)&hash處的bin節(jié)點(diǎn)。

• 如果為空瓢姻，使用CAS添加節(jié)點(diǎn)祝蝠。
• 不為空，需要使用synchronized鎖幻碱，索引對(duì)應(yīng)的bin節(jié)點(diǎn)绎狭，進(jìn)行添加或者更新操作。

Insertion (via put or its variants) of the first node in an
empty bin is performed by just CASing it to the bin. This is
by far the most common case for put operations under most
key/hash distributions. Other update operations (insert,
delete, and replace) require locks. We do not want to waste
the space required to associate a distinct lock object with
each bin, so instead use the first node of a bin list itself as
a lock. Locking support for these locks relies on builtin
"synchronized" monitors.

如果f的hash值為-1褥傍，說明當(dāng)前f是ForwaringNode節(jié)點(diǎn)儡嘶，意味著有其它線程正在擴(kuò)容，則一起進(jìn)行擴(kuò)容操作恍风。

完成添加或者更新操作之后蹦狂，才執(zhí)行break終止最外層沒有終止條件的for循環(huán)，確保數(shù)據(jù)可以添加成功朋贬。

最后執(zhí)行addCount方法凯楔。

private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    // 利用CAS更新baseCoount
    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        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);
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();
    }
    // check >= 0,需要檢查是否需要進(jìn)行擴(kuò)容操作
    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;
                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();
        }
    }
}

擴(kuò)容transfer

什么時(shí)候會(huì)擴(kuò)容

*插入一個(gè)新的節(jié)點(diǎn)：

• 新增節(jié)點(diǎn)，所在的鏈表元素個(gè)數(shù)達(dá)到閾值8锦募，則會(huì)調(diào)用treeifyBin把鏈表轉(zhuǎn)成紅黑樹摆屯，在轉(zhuǎn)成之前，會(huì)判斷數(shù)組長(zhǎng)度小于MIN_TREEIFY_CAPACITY,默認(rèn)是64,觸發(fā)擴(kuò)容糠亩。
• 調(diào)用put方法虐骑，在結(jié)尾addCount方法記錄元素個(gè)數(shù)，并檢查是否進(jìn)行擴(kuò)容削解，數(shù)組元素達(dá)到閾值時(shí)富弦，觸發(fā)擴(kuò)容沟娱。

不使用加鎖的氛驮，支持多線程擴(kuò)容。利用并發(fā)處理減少擴(kuò)容帶來性能的影響济似。

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    if (nextTab == null) {            // initiating
        try {
            @SuppressWarnings("unchecked")
            // 創(chuàng)建nextTab矫废，容量為原來容量的兩倍
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            // 擴(kuò)容是拋出異常，將閾值設(shè)置成最大砰蠢，表示不再擴(kuò)容蓖扑。
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;
    }
    int nextn = nextTab.length;
    // 創(chuàng)建 ForwardingNode 節(jié)點(diǎn)，作為標(biāo)記位台舱，表明當(dāng)前位置已經(jīng)做過桶處理
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    // advance = true 表明該節(jié)點(diǎn)已經(jīng)處理過了
    boolean advance = true;
    boolean finishing = false; // to ensure sweep before committing nextTab
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        // 控制 --i律杠，遍歷原h(huán)ash表中的節(jié)點(diǎn)
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            // 用CAS計(jì)算得到的transferIndex
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        // 將原數(shù)組中的節(jié)點(diǎn)賦值到新的數(shù)組中潭流，nextTab賦值給table，清空nextTable柜去。
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            // 所有節(jié)點(diǎn)完成復(fù)制工作灰嫉，
            if (finishing) {
                nextTable = null;
                table = nextTab;
                // 設(shè)置新的閾值為原來的1.5倍
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            // 利用CAS方法更新擴(kuò)容的閾值，sizeCtl減一嗓奢，說明新加入一個(gè)線程參與到擴(kuò)容中
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                finishing = advance = true;
                i = n; // recheck before commit
            }
        }
        // 遍歷的節(jié)點(diǎn)為null讼撒，則放入到ForwardingNode指針節(jié)點(diǎn)
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        // f.hash==-1表示遍歷到ForwardingNode節(jié)點(diǎn)，說明該節(jié)點(diǎn)已經(jīng)處理過了    
        else if ((fh = f.hash) == MOVED)
            advance = true; // already processed
        else {
            // 節(jié)點(diǎn)加鎖
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    Node<K,V> ln, hn;
                    // fh>=0股耽，表示為鏈表節(jié)點(diǎn)
                    if (fh >= 0) {
                        // 構(gòu)建兩個(gè)鏈表根盒，一個(gè)是原鏈表，另一個(gè)是原鏈表的反序鏈表
                        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);
                        }
                        // 在nextTable i 位置處插入鏈表
                        setTabAt(nextTab, i, ln);
                        // 在nextTable i+n 位置處插入鏈表
                        setTabAt(nextTab, i + n, hn);
                        // 在table i的位置處插上ForwardingNode物蝙，表示該節(jié)點(diǎn)已經(jīng)處理過
                        setTabAt(tab, i, fwd);
                        // 可以執(zhí)行 --i的操作炎滞，再次遍歷節(jié)點(diǎn)
                        advance = true;
                    }
                    // TreeBin紅黑樹，按照紅黑樹處理诬乞，處理邏輯和鏈表類似
                    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;
                            }
                        }
                        // 擴(kuò)容后樹節(jié)點(diǎn)的個(gè)數(shù)<=6,紅黑樹轉(zhuǎn)成鏈表
                        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;
                    }
                }
            }
        }
    }
}

擴(kuò)容過程有的復(fù)雜厂榛，主要涉及到多線程的并發(fā)擴(kuò)容，ForwardingNode的作用就是支持?jǐn)U容操作丽惭，將已經(jīng)處理過的節(jié)點(diǎn)和空節(jié)點(diǎn)置為ForwardingNode击奶，并發(fā)處理時(shí)多個(gè)線程處理ForwardingNode表示已經(jīng)處理過了，就往后遍歷责掏。

總結(jié)

• ConcurrentHashMap是基于數(shù)組+鏈表/紅黑樹的數(shù)據(jù)結(jié)構(gòu)柜砾，添加、刪除换衬、更新都是先通過計(jì)算key的hash值確定數(shù)據(jù)的索引值痰驱，這和HashMap是類似的，只不過ConcurrentHashMap針對(duì)并發(fā)做了更多的處理瞳浦。

• get方法獲取數(shù)據(jù)担映，先計(jì)算hash值再再和數(shù)組長(zhǎng)度取余操作獲取索引位置。

  • 通過volatile關(guān)鍵字找到table保證多線程環(huán)境下叫潦，數(shù)組擴(kuò)容具有可見性,而Node節(jié)點(diǎn)中val和next指針都使用volatile修飾保證數(shù)據(jù)修改后別的線程是可見的蝇完。這就保證了ConcurrentHashMap的線程安全性。
  • 如果遇到數(shù)組擴(kuò)容矗蕊，就參與到擴(kuò)容中短蜕。
  • 首節(jié)點(diǎn)值匹配到數(shù)據(jù)就直接返回?cái)?shù)據(jù)绷蹲，否則就遍歷鏈表或者紅黑樹或渤，直到匹配到數(shù)據(jù)。

• put方法添加或者更新數(shù)據(jù)唾戚。

  • 如果key或value為空卿操，就報(bào)錯(cuò)警检。這是因?yàn)樵谡{(diào)用get方法獲取數(shù)據(jù)為null,無法判斷是獲取的數(shù)據(jù)為null孙援，還是對(duì)應(yīng)的key就不存在映射,HashMap可以通過contains(key)判斷，而ConcurrentHashMap在多線程環(huán)境下調(diào)用contains和get方法的時(shí)候扇雕，map可能就不同了赃磨。
  • 如果table數(shù)組為空，先初始化數(shù)組洼裤，先通過sizeCtl控制并發(fā)邻辉，如果小于0表示有別的線程正在初始化數(shù)組，就讓出CPU,否則使用CAS將sizeCtl設(shè)置成-1腮鞍。
  • 初始化數(shù)組之后值骇，如果節(jié)點(diǎn)為空，使用CAS添加節(jié)點(diǎn)移国。
  • 不為空吱瘩，就鎖住該節(jié)點(diǎn)，進(jìn)行添加或者更新操作迹缀。

• transfer擴(kuò)容

  • 在新增一個(gè)節(jié)點(diǎn)時(shí)使碾，鏈表個(gè)數(shù)達(dá)到閾值8，會(huì)將鏈表轉(zhuǎn)成紅黑樹祝懂，在轉(zhuǎn)成之前票摇，會(huì)先判斷數(shù)組長(zhǎng)度小于64,會(huì)觸發(fā)擴(kuò)容。還有集合個(gè)數(shù)達(dá)到閾值時(shí)也會(huì)觸發(fā)擴(kuò)容砚蓬。
  • 擴(kuò)容數(shù)組的長(zhǎng)度是原來數(shù)組的兩倍矢门。
  • 為了支持多線程擴(kuò)容創(chuàng)建ForwardingNode節(jié)點(diǎn)作為標(biāo)記位，如果遍歷到該節(jié)點(diǎn)灰蛙，說明已經(jīng)做過處理祟剔。
  • 遍歷賦值原來的數(shù)據(jù)給新的數(shù)組。

參考

為什么ConcurrentHashMap的讀操作不需要加鎖

Java并發(fā)——ConcurrentHashMap(JDK 1.8）