ConcurrentHashMap 并發之美

一、前言

她如暴風雨中的一葉扁舟，在高并發的大風大浪下疾馳而過，眼看就要被湮滅，卻又在絕境中絕處逢生

撰寫一套即穩定、高效、且支持并發的代碼，不說難如登天，卻也絕非易事，

一直有小伙伴向我咨詢關于ConcurrentHashMap（后文簡寫為CHM）的問題，常常抱怨說：其他原始碼懂就是懂了，不懂就是不懂，唯獨CHM總給人一種似懂非懂的感覺，感覺抓住了精髓，卻又若即若離，其實，之所以有這種感覺，并不難理解，因為本質上CHM是一套支持高并發的代碼，同一個方法、同一個回傳值，在不同的執行緒或不同并發場景都需要完美運行，之所以感覺似懂非懂，可能是因為只抓住了某一類場景，區別于其他原始碼，我們讀CHM時，也一定讓自己學會分身，

本文在介紹CHM原理時，會更多的以分身的角度去看她，我會盡量拋棄逐行讀原始碼的方式，并抱著為CHM找bug的心態去讀她（不存在完美的代碼，CHM也不例外）

二、概述

本文介紹的CHM版本基于JDK1.8，原始碼洋洋灑灑共有6000+行代碼，本文著重介紹put（初始化、累加器、擴容）、get方法

建議沒有讀過原始碼的同學先看一遍原始碼，然后帶著問題來讀，這樣更容易讀懂并吃透她

三、整體介紹

3.1、模型介紹

我們首先把1.8版本的CHM資料結構介紹下，讓大家對她有個宏觀認識

• 說明：此示意圖僅為展示CHM資料結構，并非真實場景，例如資料個數如果超過陣列長度的3/4，會自動進行擴容；還有某節點下hash沖突嚴重，導致鏈表樹化的時，陣列長度至少要擴容至64

名詞約定

分桶： 如上圖所示，CHM的Node陣列長度為16，我們把每一個陣列元素及其相關節點稱為一個分桶，可見一個分桶的資料結構可以是鏈表形式的，也可以是紅黑樹或者null

結構簡述

在沒有指定引數的情況下，CHM 會默認創建一個長度為 16 的 Node 陣列，隨著資料 put 進來，CHM 通過 key 計算其 hash(正數) 值，然后對資料長度取模，確認其將要插入的分桶后通過尾插法將新資料插入鏈表尾部，當鏈表長度超過8，CHM 會將其轉換為紅黑樹，為之后的查詢、插入等提速，紅黑樹的資料結構為 TreeBin，hash值固定為-2；當因發生節點洗掉導致紅黑樹總長度低于6時，便重新轉換為鏈表，一旦數量超過 Node 陣列長度的 3/4，CHM 便會發生擴容，

class Node<K,V> implements Map.Entry<K,V> {
   final int hash;	// hash值，正常節點的hash值都為正數
   final K key;	// map的key值
   volatile V val;	// map的value值
   volatile Node<K,V> next;	// 當前節點的下一個，如沒有則為null
}

以上是 CHM 的操作梗概，很多細節都沒展開來說，大家先有個宏觀概念即可，另紅黑樹的操作本文不會展開來說，因本文主要側重點為并發，而操作紅黑樹時一般都掛有synchronized鎖，那多執行緒并發的場景便不會涉及，讀者如果有興趣可自行google、百度；或者參考本人的github工程[email protected]:xijiu/share.git，里面有關于紅黑樹、B樹、B+樹等詳細用例，值得一提的是用例會直接在控制臺列印樹資訊，方便除錯、學習

3.2、宏觀認識

put方法的流程如下圖所示，其中涉及幾個關鍵步驟：table初始化、擴容、資料寫入、總數累加，其實整體來看的話，流程很簡單，沒有初始化時，執行初始化，需要擴容時，幫助擴容，然后將資料寫入，最后記錄map總數，接下來我們逐個分析

注：本文中，橙色線表示執行時不加任何鎖；藍色表示CAS操作；綠色表示synchronized鎖

3.3、初始化

變數說明

table 成員變數，volatile修飾，定義為 Node<K,V>[] table，初始默認值為null；Node的資料結構簡單明晰，為map存盤資料的主要資料結構，讀者可自行參看jdk原始碼，此處不再贅述

sizeCtl int 型別的成員變數，volatile修飾，保證記憶體可見性，主要用來標記map擴容的閾值；例如map新創建時，table的長度為16，那么siteCtl=leng*3/4=12，即達到該閾值后，map就需要進行擴容；siteCtl 的初始默認值為 0，不過在table初始化或者擴容時，sizeCtl 會復用

• -1 table初始化時，會將其通過CAS操作置為-1，用來標記初始化加鎖成功
• ≈ -2147024894 很大的一個負數，逼近int最小值，擴容時用到，主要用來標記參與擴容執行緒數量以及控制最大擴容并發執行緒，具體計算公式為((Integer.numberOfLeadingZeros(n) | (1 << 15)) << 16) + 2，其低4位及高4位都有設計理念，在講到擴容部分時會詳細介紹

質疑

Ⅰ、問：最后直接將 sizeCtl 修改為12時，是否存在漏洞？設想場景：當執行緒 A 執行到此處，并完成了對 table 的初始化操作，但還未對 sizeCtl 進行賦值，新的請求進來后，發現table不為null，那么便執行賦值操作（初始化執行緒還未執行完畢），在后續的擴容判斷時，sizeCtl 的值一直為-1，導致CHM例外

答：其實這個問題質量很高，的確存在描述的情況，不過即便真的出現，也不會導致CHM例外，在擴容階段有個關鍵判斷(sc >>> RESIZE_STAMP_SHIFT) != rs會將擴容操作攔截，在講到擴容部分時，會詳細說明，所以在初始化執行緒 A 已經完成對table的初始化，但還未執行 sizeCtl 初始化就被hang住后，其他執行緒是可以正常插入資料，但卻不會觸發擴容，直到執行緒 A 執行完畢 （注：上述分析的案例發生的概率極低，但即便是再小的幾率也會有可能觸發，此處可見 Doug 老爺子編碼之嚴謹）

3.4、資料插入

變數說明

Node 及 hashCode 其實節點型別與hashCode一一對應

• 1、null，即table新建后，還沒有內容加入分桶
• 2、List Node，hashCode >= 0；即桶內的鏈表長度沒有超過8
• 3、Tree Node，hashCode == -2；紅黑樹
• 4、FWD Node，hashCode == -1；標記轉移節點
• 5、ReservationNode，hashCode == -3；在computeIfAbsent()等方法使用到，本文不再展開

質疑

Ⅰ、問：[點1] 如果當前分桶 f 如果為空，那么會新建 Node 節點并將其插入，如果2個執行緒同時進入，不會導致資料丟失嗎？

答：不會，因為CAS操作確保了賦值成功時，f 節點必須為null，如果2個執行緒同時進入當前操作，一定會有一個失敗，進而重試，此處有一個小點，即 CAS 失敗后，程式重新輪訓，new Node的操作豈不是白白浪費了空間？的確是這樣，不過也不太好避免；除非是為其添加重量級synchronized鎖，在鎖內開辟空間，不過這樣又會影響性能，類似場景的操作后文還會涉及

Ⅱ、問：[點1] 如果在執行當前操作時，map發生了擴容，而成員變數 table 已經指向了新陣列；而此處會將新建的 node 節點賦值給老的 table，豈不是導致了當前資料的丟失？

答：不會，同樣還是CAS的功勞，擴容時如果發現 f 節點為null，會通過CAS操作將其修改為 ForwardingNode 節點，不管是當前操作還是擴容，失敗的話都會觸發重試

Ⅲ、問：[點2] 如果在進行賦值操作時，map觸發了擴容，成員變數table已經指向了新的陣列，那此處添加的新節點豈不是要丟失？

答：不會，因為在擴容時，也需要對分桶加鎖，也就是在分桶粒度看的話，添加新節點與擴容是互斥的關系，正在進行添加操作的程序中，當前分桶的擴容是無法進行的

Ⅳ、問：[點2] 無論是List Node還是Tree Node，雖然有synchronized加持，但在進行最終賦值操作時，都沒有CAS控制，會不會導致最終資料的不一致？

答：不會，其實要回答這個問題，首先要分析Node涉及寫操作的變更場景，如下：a、正常向分桶添加、修改資料；b、擴容；c、table初始化；d、節點洗掉，而table初始化一定發生在當前操作之前，否則當前執行緒會先執行初始化操作，其他a、b、d在操作伊始都會對桶添加同步鎖synchronized，保證了修改操作的同步執行

3.5、累加器

整體思想

相信很多同學直觀感受是：不就做個多執行緒計數器累加么，至于搞這么復雜？直接使用AtomicInteger不香嗎？其實此處作者為了提速還是用心了良苦，累加器的核心思想與LongAdder是一致的，其本質還是想盡力避免沖突，從而提高吞吐，與擴容不同，在并發比較大的場景下，累加器很快就能達到stable狀態，原因是counterCells陣列的長度超過了CPU核數時，便不會繼續增長，

為什么使用LongAdder而不是AtomicInteger？首先兩者實作累加的機理是不一致的，AtomicInteger只有一個并發點，好處是每次累加完，都可以拿到最新的數值；弊端是多CPU下，沖突嚴重，LongAdder則根據使用場景動態增加并發點，帶來的最大收益便是提高了寫入的吞吐，但因為沖突點變多，每次統計最新值時，煞費周章，兩者談不上好壞，或誰取代誰，都要視你的應用場景而定，而CHM的size()方法的更偏向寫多讀少，故采用LongAdder的處理方式，本節后有關于兩者的對比實驗

變數說明

baseCount 定義為private volatile long baseCount; CHM的成員變數，累加時如果出現沖突，會將壓力打散

counterCells 定義為private volatile long baseCount; CHM的成員變數，map的總數便是由baseCount及counterCells聯合存盤的，定義為：

@sun.misc.Contended （解決快取行偽共享問題）
static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = https://www.cnblogs.com/xijiu/archive/2021/01/04/x; }
}

質疑

Ⅰ、問：[點1] 既然要進行CAS控制，可以不要cellBusy == 0及counterCells == as這2個判斷嗎？

答：可以，因為在CAS加鎖成功后，還會進行double check，查看counterCells是否已經被初始化，但是直接進行CAS加鎖操作會影響效率，試想如果counterCells已經被另外一個執行緒初始化完畢，如果有這2個判斷，就可以直接跳出本次回圈，否則還要進行CAS搶鎖

Ⅱ、問：[點2] 會有counterCells != as的場景嗎？

答：會，例如2個執行緒都發現counterCells == null，都進來初始化，具體場景可參見上述流程圖

Ⅲ、問：[點3] 如果執行cas期間發生counterCells擴容咋辦？

答：其實累加器的擴容不同于map中table陣列的擴容，table的擴容是會新建Node物件，而累加器的擴容則不會新建物件，而是直接復用已創建的CounterCell物件，且陣列的下標都不會發生變化，所以即便是在執行CAS期間發生了擴容，也不會影響整體計數的準確性

Ⅳ、問：[點4] Doug 老爺子是不是寫漏了？居然在CAS鎖外直接創建物件，如果CAS失敗，這個new操作豈不是無謂之舉，影響性能？

答：其實看到這里第一反應就是不夠嚴謹，在加鎖前執行這個操作容易造成 r 的無謂犧牲；但再一仔細琢磨，作者此舉是有深意的，主要為以下二點：1、new操作跟分支判斷等陳述句是很耗時的操作，放在鎖外，可減少當前執行緒對鎖的占用；2、counterCells陣列不同于table陣列，其最大值max介于
CPU <= max < 2*CPU，在并發較大的情況下，很快就能達到stable狀態，不會一直上漲，所以這塊為了性能的提升，還是煞費苦心的

Ⅴ、問：[點5] 所有進入累加主邏輯的執行緒，在累加結束后，全部都直接回傳了，也就是不再參與后續的擴容邏輯，如果恰好本次累加后，整體長度達到閾值而又不擴容，豈不是造成CHM過載？

答：又是一個精妙的細節！的確是這樣，也就是CHM不嚴格保證在長度達到閾值后，馬上進行擴容，為什么這樣設計呢？其實主要還是為了避免頻繁的呼叫sumCount()方法，因為計算總長度的方法采用的是LongAdder分散法，每次統計長度相對來說是比較耗時的，而能進入累加主邏輯的話，表明現在并發比較大，在大并發下每個進入的流量都計算長度是得不償失的，所以此處犧牲了及時進行CHM擴容的代價，換取了累加的高性能；而其他協助擴容的執行緒僅是判斷分桶 f hashChode == -1才會協助擴容，同樣也不會呼叫sumCount()方法

附

LongAdder與AtomicLong寫入性能對比，將目標值從1多執行緒累加至10億，分別統計2個并發類的耗時，本來打算將CHM中計數器累加部分的代碼摳出來做性能對比，但其本質上是LongAdder的思想，所以我們直接抓其精要

注：僅測驗寫入性能，單位(ms)，測驗用例 [email protected]:xijiu/share.git

3.6、擴容

整體思想

多執行緒協助擴容是CHM最難最重要的部分，同時也是存在bug的部分

具體實作思路我們可先打個比方：好比我們有100塊磚頭需要從A搬至B，但是每人每次只能搬運10塊，路途花費5分鐘，假如某人完成一次任務后，發現A地還有剩余磚塊，那么他還將持續作業，直至A地沒有剩余磚塊，他的作業才算結束，每個人進入場地前首選需要領取一張作業許可證，而管理員手中共有20張許可證，即最多允許20人同時作業，當有人開始歸還許可證時，并不代表所有的磚塊已經從A搬運至了B，因為雖然此時A地已經沒有磚頭，但并不代表所有的磚頭都已搬運至B，可能有些磚頭正在路上，所以只有最后一張許可證歸還時，才表示所有的作業已經做完

而體現在CHM上的話，則是由transferIndex欄位控制，例如map中table的長度為16，步幅為4，transferIndex的初始值為16，每個執行緒進入后對其進行CAS加鎖操作(transferIndex = transferIndex - 4)，如果加鎖成功話，當前執行緒便獲取了轉移此4個節點的唯一權限，轉移完畢后，如 transferIndex > 0，當前執行緒還會嘗試對transferIndex進行加鎖并轉移，直至transferIndex == 0；所以本例中transferIndex存在的5個狀態：16、12、8、4、0

• 鏈表轉移
  

  如上圖所示，對節點6進行擴容，分桶內的資料只會對應新table中的2個分桶，即桶6跟桶22，然后分別將之前的資料拷貝一份，并形成2個list，然后掛在新table的對應分桶下，此處為什么要新建而不是直接參考？主要是為了保證get方法的吞吐，即便是在擴容階段，get也不受影響

• 紅黑樹轉移
  

  其主要思想與鏈表轉移類似，唯一不同是，紅黑樹拆分后可能變成2個紅黑樹、或者1個樹1個鏈表、或者2個鏈表

質疑

Ⅰ、問：[點1] 第一個進入擴容的執行緒，在搶到鎖至為nextTable賦值是有一點gap的，假設某個后續執行緒在執行時，正好處于這個gap，那nextTable == null就會成立，這樣豈不是會導致當前執行緒誤以為擴容已經結束，然后直接回傳了么？這是否是一個bug？

答：的確是問題描述的這種情況，不過是否是bug值得商榷，因為首先協助擴容并不是功能上強依賴的，即便是只有一個執行緒在擴容，其他執行緒一直在等待也不會對整體功能有影響；其次這個gap存在的時間相比較整個擴容來說還是比較短的，如果某個執行緒正好處于這個gap對整體性能的影響可控

Ⅱ、問：[點1] (sc >>> 16) != rs這個運算式什么時候會成立？直觀看代碼，好像(sc >>> 16)恒等于 rs 呀？

答：好問題，其實要回答這個問題還要看結合后續的擴容邏輯來看，在擴容結束后，最后一個執行緒會給成員變數賦新值，賦值的順序為：

nextTable = null;
table = nextTab;
sizeCtl = n * 2 * 0.75;

可見，他們無法做到原子操作，而是有先后順序；設想當程式已經為table賦了新值，而sizeCtl還未被賦值時（此時sizeCtl為一個很大的負數），某個執行緒處理新資料添加并判斷是否要擴容時，便命中了此判斷，因為此時sizeCtl的高16位標記的還是舊的table長度，所以此判斷還是非常嚴謹的，讓我不禁想到了不朽名著《紅樓夢》的“草蛇灰線，伏脈千里”啊，嘆嘆！

Ⅲ、問：[點2] 此運算式在什么場景下會成立？前面會對 transferIndex 進行CAS加鎖，按理說這個運算式永遠不會成立？

答：僅當前的邏輯，此運算式確實永遠不會成立，可是最后一個負責擴容的執行緒會對所有的節點進行一遍double check，來確保所有的節點的hash值都為-1，即所有節點都完成轉移

Ⅳ、問：[點2] 既然每個執行緒都按照嚴格的加鎖順序將CHM已經轉移完畢，為什么最后一個執行緒還要執行double check？

答：如果你讀原始碼也注意到了這點，那么恭喜你，你發現了CHM的另一個bug！的確，最后一個執行緒再次double check是完全沒有必要的，doug 本人已經實錘，是前一個版本遺留的，會在下個版本中刪去；其實我本人讀到這兒時，糾結了很長時間，一直不明白作者此舉用意，心想是不是背景關系有些漏讀的資訊，導致浪費了不少時間哈，此優化具體可參看： http://cs.oswego.edu/pipermail/concurrency-interest/2020-July/017171.html

Ⅴ、問：[點1] 流程圖中標注在計算最大執行緒時存在bug，為什么CHM真正跑起來時從來沒有遇到過？

答：CHM這個控制最大參與擴容并發執行緒樹的bug，原始碼是

if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
	sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
   	transferIndex <= 0)

此處其實為想獲取正常參與擴容的執行緒數，應修改為sc == (rs << 16) + 1 || sc == (rs << 16) + MAX_RESIZERS，之所以我們實際生產程序中很少碰到，是因為首先需要執行緒數達到MAX_RESIZERS65536個，才有可能出問題，此bug地址 https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8214427

3.7、get方法

get方法相對簡單，先上原始碼

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    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;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

其實也就是直接獲取值，是鏈表或紅黑樹，就直接尋找，如果分桶為空，也就直接回傳空；能做到這么瀟灑，還是得力于volatile關鍵字以及CHM在擴容時對資料進行復制新建

四、總結

文中的流程圖算是比較重要的資訊，CHM的功能、并發、知識點全都涵蓋在里面，建議讀者一邊看圖一邊參照原始碼，這樣更能加深印象，也更容易吃透CHM

本來想做個知識點總結的，結果發現赫赫有名的CHM僅僅用到了CAS、volatile、回圈以及分支判斷，讓我們不禁對 doug 肅然起敬，他留給我們的東西太美了

標籤：其他

上一篇：Github上目標檢測專案： mmdetection專案初接觸，安裝學習程序記錄。

下一篇：Mybatis使用的9種設計模式，這些你都知道嗎？真是太有用了