如何進(jìn)行ConcurrentHashMap內(nèi)部實(shí)現(xiàn)

如何進(jìn)行ConcurrentHashMap內(nèi)部實(shí)現(xiàn)，針對(duì)這個(gè)問題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡(jiǎn)單易行的方法。

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

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

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

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

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

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

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

int sizeCtl

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

CounterCell[] counterCells

用來記錄元素的個(gè)數(shù)，這是一個(gè)數(shù)組，使用數(shù)組來記錄，是因?yàn)楸苊舛嗑€程競(jìng)爭(zhēng)時(shí)，可能產(chǎn)生的沖突。使用了數(shù)組，那么多個(gè)線程同時(shí)修改數(shù)量時(shí)，極有可能實(shí)際操作數(shù)組中不同的單元，從而減少競(jìng)爭(zhēng)。

Node<K,V>[] table

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

Node<K,V>[] nextTable

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

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

可以看到，在Map中的Node并非簡(jiǎn)單的Node對(duì)象，實(shí)際上，它有可能是Node對(duì)象，也有可能是一個(gè)Treebin或者ForwardingNode。

那什么時(shí)候是Node，什么時(shí)候是TreeBin，什么時(shí)候又是一個(gè)ForwardingNode呢?

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

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

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

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

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

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

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

• public V put(K key, V value)

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

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

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

3. 如果當(dāng)前正在擴(kuò)容，則參與幫助擴(kuò)容(調(diào)用helpTransfer()方法)

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

5. 統(tǒng)計(jì)元素總數(shù)

6. 觸發(fā)擴(kuò)容操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了有一個(gè)高性能的size()方法，ConcurrentHashMap使用了單獨(dú)的方法來統(tǒng)計(jì)元素總數(shù)，元素?cái)?shù)量統(tǒng)計(jì)在CounterCell數(shù)組中：

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

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

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

累加的主要邏輯如下：

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

觸發(fā)擴(kuò)容操作

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

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

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

//n是數(shù)組長(zhǎng)度，數(shù)組長(zhǎng)度是2的冪次方，因此一定是100 1000 10000 100000這種二進(jìn)制數(shù)字 //這里將low節(jié)點(diǎn)串一起， high節(jié)點(diǎn)串一起 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é)點(diǎn)留在當(dāng)前位置 setTabAt(nextTab, i, ln); //high節(jié)點(diǎn)放到擴(kuò)容后的新位置，新位置距離老位置n setTabAt(nextTab, i + n, hn); //擴(kuò)容完成，用ForwardingNode填充 setTabAt(tab, i, fwd);

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

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

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

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

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 根據(jù)hash值 得到對(duì)應(yīng)的槽位 (n - 1) & h

3. 如果當(dāng)前槽位第一個(gè)元素key就和請(qǐng)求的一樣，直接返回

4. 否則調(diào)用Node的find()方法查找

5. 對(duì)于ForwardingNode 使用的是 ForwardingNode.find()

6. 對(duì)于紅黑樹 使用的是TreeBin.find()

7. 對(duì)于鏈表型的槽位，依次順序查找對(duì)應(yīng)的key

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

關(guān)于如何進(jìn)行ConcurrentHashMap內(nèi)部實(shí)現(xiàn)問題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。