ConcurrentHashMap面試靈魂拷問，你能扛多久？

來自：blog.csdn.net/zwx900102/article/details/114547968

前言

本文從?ConcurrentHashMap?常見的面試問題引入話題，并逐步揭開其設(shè)計原理，相信讀完本文，對面試中的相關(guān)問題會有很大的幫助。

HashMap 在我們?nèi)粘５拈_發(fā)中使用頻率最高的一個工具類之一，然而使用 HashMap 最大的問題之一就是它是線程不安全的，如果我們想要線程安全應(yīng)該怎么辦呢？這時候就可以選擇使用?ConcurrentHashMap，ConcurrentHashMap?和?HashMap?的功能是基本一樣的，ConcurrentHashMap?是 HashMap 的線程安全版本。

因?ConcurrentHashMap?和 HashMap 在 jdk1.8 版本中排除線程的安全性方面，其他的設(shè)計都很類似，所以有很多相同的設(shè)計思想本文不會做太多重復(fù)介紹。

ConcurrentHashMap 原理

ConcurrentHashMap?是 HashMap 的線程安全版本，其內(nèi)部和 HashMap 一樣，也是采用了數(shù)組 + 鏈表 + 紅黑樹的方式來實現(xiàn)。

如何實現(xiàn)線程的安全性？加鎖。但是這個鎖應(yīng)該怎么加呢？在?HashTable?中，是直接在 put 和 get 方法上加上了?synchronized，理論上來說?ConcurrentHashMap?也可以這么做，但是這么做鎖的粒度太大，會非常影響并發(fā)性能，所以在?ConcurrentHashMap?中并沒有采用這么直接簡單粗暴的方法，其內(nèi)部采用了非常精妙的設(shè)計，大大減少了鎖的競爭，提升了并發(fā)性能。

ConcurrentHashMap?中的初始化和 HashMap 中一樣，而且容量也會調(diào)整為 2 的 N 次冪，在這里不做重復(fù)介紹這么做的原因。

JDK1.8 版本 ConcurrentHashMap 做了什么改進(jìn)

在 JDK1.7 版本中，ConcurrentHashMap?由數(shù)組 + Segment + 分段鎖實現(xiàn)，其內(nèi)部分為一個個段（Segment）數(shù)組，Segment 通過繼承?ReentrantLock?來進(jìn)行加鎖，通過每次鎖住一個 segment 來降低鎖的粒度而且保證了每個 segment 內(nèi)的操作的線程安全性，從而實現(xiàn)全局線程安全。下圖就是 JDK1.7 版本中?ConcurrentHashMap?的結(jié)構(gòu)示意圖：

但是這么做的缺陷就是每次通過 hash 確認(rèn)位置時需要 2 次才能定位到當(dāng)前 key 應(yīng)該落在哪個槽：

• 通過 hash 值和 段數(shù)組長度-1 進(jìn)行位運算確認(rèn)當(dāng)前 key 屬于哪個段，即確認(rèn)其在 segments 數(shù)組的位置。
• 再次通過 hash 值和 table 數(shù)組（即 ConcurrentHashMap 底層存儲數(shù)據(jù)的數(shù)組）長度 - 1進(jìn)行位運算確認(rèn)其所在桶。

為了進(jìn)一步優(yōu)化性能，在 jdk1.8 版本中，對?ConcurrentHashMap?做了優(yōu)化，取消了分段鎖的設(shè)計，取而代之的是通過 cas 操作和?synchronized?關(guān)鍵字來實現(xiàn)優(yōu)化，而擴(kuò)容的時候也利用了一種分而治之的思想來提升擴(kuò)容效率，在 JDK1.8 中?ConcurrentHashMap?的存儲結(jié)構(gòu)和 HashMap 基本一致，如下圖所示：

為什么 key 和 value 不允許為 null

在 HashMap 中，key 和 value 都是可以為 null 的，但是在?ConcurrentHashMap?中卻不允許，這是為什么呢？

作者 Doug Lea 本身對這個問題有過回答，在并發(fā)編程中，null 值容易引來歧義， 假如先調(diào)用?get(key)?返回的結(jié)果是 null，那么我們無法確認(rèn)是因為當(dāng)時這個 key 對應(yīng)的 value 本身放的就是 null，還是說這個 key 值根本不存在，這會引起歧義，如果在非并發(fā)編程中，可以進(jìn)一步通過調(diào)用?containsKey?方法來進(jìn)行判斷，但是并發(fā)編程中無法保證兩個方法之間沒有其他線程來修改 key 值，所以就直接禁止了 null 值的存在。

而且作者 Doug Lea 本身也認(rèn)為，假如允許在集合，如 map 和 set 等存在 null 值的話，即使在非并發(fā)集合中也有一種公開允許程序中存在錯誤的意思，這也是 Doug Lea 和 Josh Bloch（HashMap作者之一） 在設(shè)計問題上少數(shù)不同意見之一，而?ConcurrentHashMap?是 Doug Lea 一個人開發(fā)的，所以就直接禁止了 null 值的存在。

ConcurrentHashMap 如何保證線程的安全性

在 ConcurrentHashMap 中，采用了大量的分而治之的思想來降低鎖的粒度，提升并發(fā)性能。其源碼中大量使用了 cas 操作來保證安全性，而不是和 HashTable 一樣，不論什么方法，直接簡單粗暴的使用 synchronized關(guān)鍵字來實現(xiàn)，接下來的原理分析中，部分和 HashMap 類似之處本文就不在重復(fù)，本文主要從安全性方面來分析 ConcurrentHashMap 的設(shè)計。

如何用 CAS 保證數(shù)組初始化的安全

下面就是初始化的方法：

這里面有一個非常重要的變量 sizeCtl，這個變量對理解整個?ConcurrentHashMap?的原理非常重要。

sizeCtl 有四個含義：

• sizeCtl<-1?表示有 N-1 個線程正在執(zhí)行擴(kuò)容操作，如 -2 就表示有 2-1 個線程正在擴(kuò)容。
• sizeCtl=-1?占位符，表示當(dāng)前正在初始化數(shù)組。
• sizeCtl=0?默認(rèn)狀態(tài)，表示數(shù)組還沒有被初始化。
• sizeCtl>0?記錄下一次需要擴(kuò)容的大小。

知道了這個變量的含義，上面的方法就好理解了，第二個分支采用了 CAS 操作，因為 SIZECTL 默認(rèn)為 0，所以這里如果可以替換成功，則當(dāng)前線程可以執(zhí)行初始化操作，CAS 失敗，說明其他線程搶先一步把 sizeCtl 改為了 -1。擴(kuò)容成功之后會把下一次擴(kuò)容的閾值賦值給 sc，即 sizeClt。

put 操作如何保證數(shù)組元素的可見性

ConcurrentHashMap?中存儲數(shù)據(jù)采用的 Node 數(shù)組是采用了 volatile 來修飾的，但是這只能保證數(shù)組的引用在不同線程之間是可用的，并不能保證數(shù)組內(nèi)部的元素在各個線程之間也是可見的，所以這里我們判定某一個下標(biāo)是否有元素，并不能直接通過下標(biāo)來訪問，那么應(yīng)該如何訪問呢？源碼給你答案：

可以看到，這里是通過 tabAt 方法來獲取元素，而 tableAt 方法實際上就是一個 CAS 操作：

如果發(fā)現(xiàn)當(dāng)前節(jié)點元素為空，也是通過 CAS 操作（casTabAt）來存儲當(dāng)前元素。

如果當(dāng)前節(jié)點元素不為空，則會使用?synchronized?關(guān)鍵字鎖住當(dāng)前節(jié)點，并進(jìn)行對應(yīng)的設(shè)值操作：

精妙的計數(shù)方式

在 HashMap 中，調(diào)用 put 方法之后會通過?++size?的方式來存儲當(dāng)前集合中元素的個數(shù)，但是在并發(fā)模式下，這種操作是不安全的，所以不能通過這種方式，那么是否可以通過 CAS 操作來修改 size 呢？

直接通過 CAS 操作來修改 size 是可行的，但是假如同時有非常多的線程要修改 size 操作，那么只會有一個線程能夠替換成功，其他線程只能不斷的嘗試 CAS，這會影響到?ConcurrentHashMap?集合的性能，所以作者就想到了一個分而治之的思想來完成計數(shù)。

作者定義了一個數(shù)組來計數(shù)，而且這個用來計數(shù)的數(shù)組也能擴(kuò)容，每次線程需要計數(shù)的時候，都通過隨機(jī)的方式獲取一個數(shù)組下標(biāo)的位置進(jìn)行操作，這樣就可以盡可能的降低了鎖的粒度，最后獲取 size 時，則通過遍歷數(shù)組來實現(xiàn)計數(shù)：

//用來計數(shù)的數(shù)組，大小為2的N次冪，默認(rèn)為2
private?transient?volatile?CounterCell[]?counterCells;

@sun.misc.Contended?static?final?class?CounterCell?{//數(shù)組中的對象
????????volatile?long?value;//存儲元素個數(shù)
????????CounterCell(long?x)?{?value?=?x;?}
????}

addCount 計數(shù)方法

接下來我們看看 addCount 方法：

首先會判斷?CounterCell?數(shù)組是不是為空，需要這里的是，這里的 CAS 操作是將?BASECOUNT?和 baseCount 進(jìn)行比較，如果相等，則說明當(dāng)前沒有其他線程過來修改 baseCount（即 CAS 操作成功），此時則不需要使用?CounterCell?數(shù)組，而直接采用 baseCount 來計數(shù)。

假如?CounterCell?為空且 CAS 失敗，那么就會通過調(diào)用?fullAddCount?方法來對?CounterCell?數(shù)組進(jìn)行初始化。

fullAddCount 方法

這個方法也很長，看起來比較復(fù)雜，里面包含了對?CounterCell?數(shù)組的初始化和賦值等操作。

初始化 CounterCell 數(shù)組

我們先不管，直接進(jìn)入初始化的邏輯：

這里面有一個比較重要的變量 cellsBusy，默認(rèn)是 0，表示當(dāng)前沒有線程在初始化或者擴(kuò)容，所以這里判斷如果?cellsBusy==0，而 as 其實在前面就是把全局變量?CounterCell?數(shù)組的賦值，這里之所以再判斷一次就是再確認(rèn)有沒有其他線程修改過全局?jǐn)?shù)組?CounterCell，所以條件滿足的話就會通過 CAS 操作修改?cellsBusy?為 1，表示當(dāng)前自己在初始化了，其他線程就不能同時進(jìn)來初始化操作了。

最后可以看到，默認(rèn)是一個長度為 2 的數(shù)組，也就是采用了 2 個數(shù)組位置進(jìn)行存儲當(dāng)前?ConcurrentHashMap?的元素數(shù)量。

CounterCell 如何賦值

初始化完成之后，如果再次調(diào)用 put 方法，那么就會進(jìn)入?fullAddCount?方法的另一個分支：

這里面首先判斷了?CounterCell?數(shù)組不為空，然后會再次判斷數(shù)組中的元素是不是為空，因為如果元素為空，就需要初始化一個?CounterCell?對象放到數(shù)組，而如果元素不為空，則只需要 CAS 操作替換元素中的數(shù)量即可。

所以這里面的邏輯也很清晰，初始化?CounterCell?對象的時候也需要將?cellBusy?由 0 改成 1。

計數(shù)數(shù)組 CounterCell 也能擴(kuò)容嗎

最后我們再繼續(xù)看其他分支：

主要看上圖紅框中的分支，一旦會進(jìn)入這個分支，就說明前面所有分支都不滿足，即：

• 當(dāng)前?CounterCell?數(shù)組已經(jīng)初始化完成。
• 當(dāng)前通過 hash 計算出來的?CounterCell?數(shù)組下標(biāo)中的元素不為 null。
• 直接通過 CAS 操作修改?CounterCell?數(shù)組中指定下標(biāo)位置中對象的數(shù)量失敗，說明有其他線程在競爭修改同一個數(shù)組下標(biāo)中的元素。
• 當(dāng)前操作不滿足不允許擴(kuò)容的條件。
• 當(dāng)前沒有其他線程創(chuàng)建了新的?CounterCell?數(shù)組，且當(dāng)前?CounterCell?數(shù)組的大小仍然小于 CPU 數(shù)量。

所以接下來就需要對?CounterCell?數(shù)組也進(jìn)行擴(kuò)容，這個擴(kuò)容的方式和?ConcurrentHashMap?的擴(kuò)容一樣，也是將原有容量乘以 2，所以其實?CounterCell?數(shù)組的容量也是滿足 2 的 N 次冪。

ConcurrentHashMap 的擴(kuò)容

接下來我們需要回到 addCount 方法，因為這個方法在添加元素數(shù)量的同時，也會判斷當(dāng)前?ConcurrentHashMap?的大小是否達(dá)到了擴(kuò)容的閾值，如果達(dá)到，需要擴(kuò)容。

擴(kuò)容也能支持并發(fā)嗎

這里可能令大家有點意外的是，ConcurrentHashMap?擴(kuò)容也支持多線程同時進(jìn)行，這又是如何做到的呢？接下來就讓我們回到 addCount 方法一探究竟。

這里 check 是傳進(jìn)來的鏈表長度，>=0?才開始檢查是否需要擴(kuò)容，緊挨之后是一個 while 循環(huán)，主要是滿足兩個條件：

前面我們提到，sizeCtl在初始化的時候會被賦值為下一次擴(kuò)容的大?。〝U(kuò)容之后也會），所以?>=sizeCtl?表示的就是是否達(dá)到擴(kuò)容閾值。

table 不為 null 且當(dāng)前數(shù)組長度小于最大值 2 的 30 次方。

擴(kuò)容戳有什么用

當(dāng)滿足擴(kuò)容條件之后，首先會先調(diào)用一個方法來獲取擴(kuò)容戳，這個擴(kuò)容戳比較有意思，要理解擴(kuò)容戳，必須從二進(jìn)制的角度來分析。resizeStamp?方法就一句話，其中?RESIZE_STAMP_BITS?是一個默認(rèn)值 16。

?static?final?int?resizeStamp(int?n)?{
????????return?Integer.numberOfLeadingZeros(n)?|?(1?<1));
????}

這里面關(guān)鍵就是?Integer.numberOfLeadingZeros(n)?這個方法，這個方法源碼就不貼出來了，實際上這個方法就是做一件事，那就是獲取當(dāng)前數(shù)據(jù)轉(zhuǎn)成二進(jìn)制后的最高非 0 位前的 0 的個數(shù)。

這句話有點拗口，我們舉個例子，就以 16 為準(zhǔn)，16 轉(zhuǎn)成二進(jìn)制是 10000，最高非 0 位是在第 5 位，因為 int 類型是 32 位，所以他前面還有 27 位，而且都是 0，那么這個方法得到的結(jié)果就是 27（1 的前面還有 27 個 0）。

然后?1 << (RESIZE_STAMP_BITS - 1)在當(dāng)前版本就是 1<<15，也就是得到一個二進(jìn)制數(shù)?1000000000000000，這里也是要做一件事，把這個 1 移動到第 16 位。最后這兩個數(shù)通過 | 操作一定得到的結(jié)果就是第 16 位是 1，因為 int 是 32 位，最多也就是 32 個 0，而且因為 n 的默認(rèn)大小是 16（ConcurrentHashMap?默認(rèn)大?。?，所以實際上最多也就是 27（11011），也就是說這個數(shù)最高位的 1 也只是在第五位，執(zhí)行 | 運算最多也就是影響低 5 位的結(jié)果。

注意：這里之所以要保證第 16 位為 1，是為了保證 sizeCtl 變量為負(fù)數(shù)，因為前面我們提到，這個變量為負(fù)數(shù)才代表當(dāng)前有線程在擴(kuò)容，至于這個變量和 sizeCtl 的關(guān)系后面會介紹。

首次擴(kuò)容為什么計數(shù)要 +2 而不是 +1

首次擴(kuò)容一定不會走前面兩個條件，而是走的最后一個紅框內(nèi)條件，這個條件通過 CAS 操作將 rs 左移了 16（RESIZE_STAMP_SHIFT）位，然后加上一個 2，這個代表什么意思呢？為什么是加 2 呢？

要回答這個問題我們先回答另一個問題，上面通過方法獲得的擴(kuò)容戳 rs 究竟有什么用？實際上這個擴(kuò)容戳代表了兩個含義：

• 高 16 位代表當(dāng)前擴(kuò)容的標(biāo)記，可以理解為一個紀(jì)元。
• 低 16 位代表了擴(kuò)容的線程數(shù)。

知道了這兩個條件就好理解了，因為 rs 最終是要賦值給 sizeCtl 的，而 sizeCtl 負(fù)數(shù)才代表擴(kuò)容，而將 rs 左移 16 位就剛好使得最高位為 1，此時低 16 位全部是 0，而因為低 16 位要記錄擴(kuò)容線程數(shù)，所以應(yīng)該 +1，但是這里是 +2，原因是 sizeCtl 中 -1 這個數(shù)值已經(jīng)被使用了，用來代替當(dāng)前有線程準(zhǔn)備擴(kuò)容，所以如果直接 +1 是會和標(biāo)志位發(fā)生沖突。

所以繼續(xù)回到上圖中的第二個紅框，就是正常繼續(xù) +1 了，只有初始化第一次記錄擴(kuò)容線程數(shù)的時候才需要 +2。

擴(kuò)容條件

接下來我們繼續(xù)看上圖中第一個紅框，這里面有 5 個條件，代表是滿足這 5 個條件中的任意一個，則不進(jìn)行擴(kuò)容：

• (sc >>> RESIZE_STAMP_SHIFT) != rs 這個條件實際上有 bug，在 JDK12 中已經(jīng)換掉。
• sc == rs + 1 表示最后一個擴(kuò)容線程正在執(zhí)行首位工作，也代表擴(kuò)容即將結(jié)束。
• sc == rs + MAX_RESIZERS 表示當(dāng)前已經(jīng)達(dá)到最大擴(kuò)容線程數(shù)，所以不能繼續(xù)讓線程加入擴(kuò)容。
• 擴(kuò)容完成之后會把 nextTable（擴(kuò)容的新數(shù)組） 設(shè)為 null。
• transferIndex <= 0 表示當(dāng)前可供擴(kuò)容的下標(biāo)已經(jīng)全部分配完畢，也代表了當(dāng)前線程擴(kuò)容結(jié)束。

多并發(fā)下如何實現(xiàn)擴(kuò)容

在多并發(fā)下如何實現(xiàn)擴(kuò)容才不會沖突呢？可能大家都想到了采用分而治之的思想，在?ConcurrentHashMap?中采用的是分段擴(kuò)容法，即每個線程負(fù)責(zé)一段，默認(rèn)最小是 16，也就是說如果?ConcurrentHashMap?中只有 16 個槽位，那么就只會有一個線程參與擴(kuò)容。如果大于 16 則根據(jù)當(dāng)前 CPU 數(shù)來進(jìn)行分配，最大參與擴(kuò)容線程數(shù)不會超過 CPU 數(shù)。

擴(kuò)容空間和 HashMap 一樣，每次擴(kuò)容都是將原空間大小左移一位，即擴(kuò)大為之前的兩倍。注意這里的?transferIndex?代表的就是推進(jìn)下標(biāo)，默認(rèn)為舊數(shù)組的大小。

擴(kuò)容時的數(shù)據(jù)遷移如何保證安全性

初始化好了新的數(shù)組，接下來就是要準(zhǔn)備確認(rèn)邊界。也就是要確認(rèn)當(dāng)前線程負(fù)責(zé)的槽位，確認(rèn)好之后會從大到小開始往前推進(jìn)，比如線程一負(fù)責(zé) 1-16，那么對應(yīng)的數(shù)組邊界就是 0-15，然后會從最后一位 15 開始遷移數(shù)據(jù)：

這里面有三個變量比較關(guān)鍵：

• fwd 節(jié)點：?這個代表的是占位節(jié)點，最關(guān)鍵的就是這個節(jié)點的 hash 值為 -1，所以一旦發(fā)現(xiàn)某一個節(jié)點中的 hash 值為 -1 就可以知道當(dāng)前節(jié)點已經(jīng)被遷移了。
• advance：?代表是否可以繼續(xù)推進(jìn)下一個槽位，只有當(dāng)前槽位數(shù)據(jù)被遷移完成之后才可以設(shè)置為 true
• finishing：?是否已經(jīng)完成數(shù)據(jù)遷移。

知道了這幾個變量，再看看上面的代碼，第一次一定會進(jìn)入 while 循環(huán)，因為默認(rèn) advance 為 true，第一次進(jìn)入循環(huán)的目的為了確認(rèn)邊界，因為邊界值還沒有確認(rèn)，所以會直接走到最后一個分支，通過 CAS 操作確認(rèn)邊界。

確認(rèn)邊界這里直接表述很難理解，我們通過一個例子來說明：

假設(shè)說最開始的空間為 16，那么擴(kuò)容后的空間就是 32，此時?transferIndex?為舊數(shù)組大小 16，而在第二個 if判斷中，transferIndex?賦值給了 nextIndex，所以?nextIndex?為 1，而 stride 代表的是每個線程負(fù)責(zé)的槽位數(shù)，最小就是 16，所以 stride 也是 16，所以?nextBound= nextIndex > stride ? nextIndex - stride : 0?皆可以得到：nextBound=0?和?i=15?了，也就是當(dāng)前線程負(fù)責(zé) 0-15 的數(shù)組下標(biāo)，且從 0 開始推進(jìn)，確認(rèn)邊界后立刻將 advance 設(shè)置為 false，也就是會跳出 while 循環(huán)，從而執(zhí)行下面的數(shù)據(jù)遷移部分邏輯。

PS：因為?nextBound=0，所以 CAS 操作實際上也是把?transferIndex?變成了 0，表示當(dāng)前擴(kuò)容的數(shù)組下標(biāo)已經(jīng)全部分配完畢，這也是前面不滿足擴(kuò)容的第 5 個條件。

數(shù)據(jù)遷移時，會使用?synchronized?關(guān)鍵字對當(dāng)前節(jié)點進(jìn)行加鎖，也就是說鎖的粒度精確到了每一個節(jié)點，可以說大大提升了效率。加鎖之后的數(shù)據(jù)遷移和 HashMap 基本一致，也是通過區(qū)分高低位兩種情況來完成遷移，在本文就不重復(fù)講述。

當(dāng)前節(jié)點完成數(shù)據(jù)遷移之后，advance 變量會被設(shè)置為 true，也就是說可以繼續(xù)往前推進(jìn)節(jié)點了，所以會重新進(jìn)入上面的 while 循環(huán)的前面兩個分支，把下標(biāo) i 往前推進(jìn)之后再次把 advance 設(shè)置為 false，然后重復(fù)操作，直到下標(biāo)推進(jìn)到 0 完成數(shù)據(jù)遷移。

while 循環(huán)徹底結(jié)束之后，會進(jìn)入到下面這個 if 判斷，紅框中就是當(dāng)前線程自己完成了遷移之后，會將擴(kuò)容線程數(shù)進(jìn)行遞減，遞減之后會再次通過一個條件判斷，這個條件其實就是前面進(jìn)入擴(kuò)容前條件的反推，如果成立說明擴(kuò)容已經(jīng)完成，擴(kuò)容完成之后會將?nextTable?設(shè)置為 null，所以上面不滿足擴(kuò)容的第 4 個條件就是在這里設(shè)置的。

總結(jié)

本文主要講述了?ConcurrentHashMap?中是如何保證安全性的，并且挑選了一些比較經(jīng)典的面試常用問題進(jìn)行分析解答，在整個?ConcurrentHashMap?中，整個思想就是降低鎖的粒度，減少鎖的競爭，所以采用了大量的分而治之的思想，比如多線程同時進(jìn)行擴(kuò)容，以及通過一個數(shù)組來實現(xiàn) size 的計數(shù)等。