ConcurrentHashMap可以說是目前使用最多的并發(fā)數(shù)據(jù)結(jié)構(gòu)之一，作為如此核心的基本組件，不僅僅要滿足我們功能的需求，更要滿足性能的需求。而實現(xiàn)一個高性能的線程安全的HashMap也絕非易事。

ConcurrentHashMap作為JDK8的內(nèi)部實現(xiàn)，一個成功的典范，有著諸多可以讓我們學(xué)習(xí)和致敬的地方。

我全局在項目中搜索這個類的時候，發(fā)現(xiàn)大量項目代碼和源碼都用到了，為什么他會這么吃香呢?到底是道德的....呸。

下面我們就來扒一扒，ConcurrentHashMap的內(nèi)部實現(xiàn)，來體會一下它的精妙之處吧!

ConcurrentHashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)

在JDK8中， ConcurrentHashMap的內(nèi)部實現(xiàn)發(fā)生了天翻地覆的變化。這里依據(jù)JDK8，來介紹一下ConcurrentHashMap的內(nèi)部實現(xiàn)。

從靜態(tài)數(shù)據(jù)結(jié)構(gòu)上說，ConcurrentHashMap包含以下內(nèi)容：

int sizeCtl

這是一個多功能的字段，可以用來記錄參與Map擴展的線程數(shù)量，也用來記錄新的table的擴容閾值

CounterCell[] counterCells

用來記錄元素的個數(shù)，這是一個數(shù)組，使用數(shù)組來記錄，是因為避免多線程競爭時，可能產(chǎn)生的沖突。使用了數(shù)組，那么多個線程同時修改數(shù)量時，極有可能實際操作數(shù)組中不同的單元，從而減少競爭。

Node<K,V>[] table

實際存放Map內(nèi)容的地方，一個map實際上就是一個Node數(shù)組，每個Node里包含了key和value的信息。

Node<K,V>[] nextTable

當(dāng)table需要擴充時，會把新的數(shù)據(jù)填充到nextTable中，也就是說nextTable是擴充后的Map。

以上就是ConcurrentHashMap的核心元素，其中最值得注意的便是Node，Node并非想象中如此簡單，下面的圖展示了Node的類族結(jié)構(gòu)：

可以看到，在Map中的Node并非簡單的Node對象，實際上，它有可能是Node對象，也有可能是一個Treebin或者ForwardingNode。

那什么時候是Node，什么時候是TreeBin，什么時候又是一個ForwardingNode呢?

其實在絕大部分場景中，使用的依然是Node，從Node數(shù)據(jù)結(jié)構(gòu)中，不難看出，Node其實是一個鏈表，也就是說，一個正常的Map可能是長這樣的:

上圖中，綠色部分表示Node數(shù)組，里面的元素是Node，也就是鏈表的頭部，當(dāng)兩個元素在數(shù)據(jù)中的位置發(fā)生沖突時，就將它們通過鏈表的形式，放在一個槽位中。

當(dāng)數(shù)組槽位對應(yīng)的是一個鏈表時，在一個鏈表中查找key只能使用簡單的遍歷，這在數(shù)據(jù)不多時，還是可以接受的，當(dāng)沖突數(shù)據(jù)比較多少，這種簡單的遍歷就有點慢了。

因此，在具體實現(xiàn)中，當(dāng)鏈表的長度大于等于8時，會將鏈表樹狀化，也就是變成一顆紅黑樹。如下圖所示，其中一個槽位就變成了一顆樹，這就是TreeBin(在TreeBin中使用TreeNode構(gòu)造整科樹)。

當(dāng)數(shù)組容量快滿時，即超過75%的容量時，數(shù)組還需要進行擴容，在擴容過程中，如果老的數(shù)組已經(jīng)完成了復(fù)制，那么就會將老數(shù)組中的元素使用ForwardingNode對象替代，表示當(dāng)前槽位的數(shù)據(jù)已經(jīng)處理了，不需要再處理了，這樣，當(dāng)有多個線程同時參與擴容時，就不會沖突。

put()方法的實現(xiàn)

現(xiàn)在來看一下作為一個HashMap最為重要的方法put()：

• public V put(K key, V value)

它負(fù)責(zé)將給定的key和value對存入HashMap，它的工作主要有以下幾個步驟：

1. 如果沒有初始化數(shù)組，則嘗試初始化數(shù)組
2. 如果當(dāng)前正在擴容，則參與幫助擴容(調(diào)用helpTransfer()方法)
3. 將給定的key,value 放入對應(yīng)的槽位
4. 統(tǒng)計元素總數(shù)
5. 觸發(fā)擴容操作

根據(jù)以上主要4個步驟，來依次詳細說明一下：

如果沒有初始化數(shù)組，則嘗試初始化數(shù)組

初始化數(shù)據(jù)會生成一個Node數(shù)組:

Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; 

默認(rèn)情況下，n為16。同時設(shè)置sizeCtl為·n - (n >>> 2); 這意味著sizeCtl為n的75%，表示Map的size，也就是說ConcurrentHashMap的負(fù)載因子是0.75。(為了避免沖突，Map的容量是數(shù)組的75%，超過這個閾值，就會擴容)

如果當(dāng)前正在擴容，則參與幫助擴容

else if ((fh = f.hash) == MOVED) 
    tab = helpTransfer(tab, f); 

如果一個節(jié)點的hash是MOVE，則表示這是一個ForwardingNode，也就是當(dāng)前正在擴容中，為了盡快完成擴容，當(dāng)前線程就會參與到擴容的工作中，而不是等待擴容操作完成，如此緊密細致的操作，恰恰是ConcurrentHashMap高性能的原因。

而代碼中的f.hash==MOVE語義上等同于f instanceof ForwardingNode，但是使用整數(shù)相等的判斷的效率要遠遠高于instanceof，所以，這里也是一處對性能的極限優(yōu)化。

將給定的key,value 放入對應(yīng)的槽位

在大部分情況下，應(yīng)該會走到這一步，也就是將key和value放入數(shù)組中。在這個操作中會使用大概如下操作：

Node<K,V> f; 
synchronized (f) { 
     if(所在槽位是一個鏈表) 
         插入鏈表 
     else if(所在槽位是紅黑樹) 
         插入樹 
     if(鏈表長度大于8[TREEIFY_THRESHOLD]) 
         將鏈表樹狀化 
} 

可以看到，這使用了synchronized關(guān)鍵字，鎖住了Node對象。由于在絕大部分情況下，不同線程大概率會操作不同的Node，因此這里的競爭應(yīng)該不會太大。

并且隨著數(shù)組規(guī)模越來越大，競爭的概率會越來越小，因此ConcurrentHashMap有了極好的并行性。

統(tǒng)計元素總數(shù)

為了有一個高性能的size()方法，ConcurrentHashMap使用了單獨的方法來統(tǒng)計元素總數(shù)，元素數(shù)量統(tǒng)計在CounterCell數(shù)組中：

CounterCell[] counterCells; 
@sun.misc.Contended static final class CounterCell { 
    volatile long value; 
    CounterCell(long x) { value = x; } 
} 

CounterCell使用偽共享優(yōu)化，具有很高的讀寫性能。counterCells中所有的成員的value相加，就是整個Map的大小。這里使用數(shù)組，也是為了防止沖突。

如果簡單使用一個變量，那么多線程累加一個計數(shù)器時，難免要有競爭，現(xiàn)在分散到一個數(shù)組中，這種競爭就小了很多，對并發(fā)就更加友好了。

累加的主要邏輯如下：

if (as == null || (m = as.length - 1) < 0 || 
    //不同線程映射到不同的數(shù)組元素，防止沖突 
    (a = as[ThreadLocalRandom.getProbe() & m]) == null || 
    //使用CAS直接增加對應(yīng)的數(shù)據(jù) 
    !(uncontended = 
      U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) 
    //如果有競爭，在這里會重試，如果競爭嚴(yán)重還會將CounterCell[]數(shù)組擴容，以減少競爭 

觸發(fā)擴容操作

最后，ConcurrentHashMap還會檢查是否需要擴容，它會檢查當(dāng)前Map的大小是否超過了閾值，如果超過了，還會進行擴容。

ConcurrentHashMap的擴容過程非常巧妙，它并沒有完全打亂當(dāng)前已有的元素位置，而是在數(shù)組擴容2倍后，將一半的元素移動到新的空間中。

所有的元素根據(jù)高位是否為1分為low節(jié)點和high節(jié)點：

//n是數(shù)組長度，數(shù)組長度是2的冪次方，因此一定是100 1000 10000 100000這種二進制數(shù)字 
//這里將low節(jié)點串一起， high節(jié)點串一起 
if ((ph & n) == 0) 
    ln = new Node<K,V>(ph, pk, pv, ln); 
else 
    hn = new Node<K,V>(ph, pk, pv, hn); 

接著，重新放置這些元素的位置：

//low節(jié)點留在當(dāng)前位置 
setTabAt(nextTab, i, ln); 
//high節(jié)點放到擴容后的新位置，新位置距離老位置n 
setTabAt(nextTab, i + n, hn); 
//擴容完成，用ForwardingNode填充 
setTabAt(tab, i, fwd); 

下圖顯示了 從8擴充到16時的可能得一種擴容情況，注意，新的位置總是在老位置的后面n個槽位(n為原數(shù)組大小)

這樣做的好處是，每個元素的位置不需要重新計算，進行查找時，由于總是會對n-1(一定是一個類似于1111 11111 111111這樣的二進制數(shù))按位與，因此，high類的節(jié)點自然就會出現(xiàn)在+n的位置上。

get()方法的實現(xiàn)

與put()方法相比，get()方法就比較簡單了。步驟如下：

1. 根據(jù)hash值 得到對應(yīng)的槽位 (n - 1) & h
2. 如果當(dāng)前槽位第一個元素key就和請求的一樣，直接返回
3. 否則調(diào)用Node的find()方法查找
4. 對于ForwardingNode 使用的是 ForwardingNode.find()
5. 對于紅黑樹 使用的是TreeBin.find()
6. 對于鏈表型的槽位，依次順序查找對應(yīng)的key

寫在最后

ConcurrentHashMap可以說是并發(fā)設(shè)計的典范，在JDK8中，ConcurrentHashMap可以說是再一次脫胎換骨，全新的架構(gòu)和實現(xiàn)帶來了飛一般的體驗(JDK7中的ConcurrentHashMap還是采用比較骨板的segment實現(xiàn)的)，細細品讀，還是有不少的收獲。

他和HashMap的區(qū)別，優(yōu)劣勢對比，這也是?？嫉目键c，所以大家不管是為了了解、工作還是面試，都應(yīng)該好好的熟悉一下。

多線程系列我會繼續(xù)更新，我是敖丙，你知道的越多，你不知道的越多，我們江湖見。