面試 ConcurrentHashMap ，看這一篇就夠了！

mghio2021-07-02 17:49:18

文章標(biāo)簽面試 ConcurrentHashMa文章分類代碼人生閱讀數(shù)201

ConcurrentHashMap  在 JDK1.7 和 JDK1.8  的實現(xiàn)方式是不同的。

JDK1.7 中的 ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HashEntry 數(shù)組結(jié)構(gòu)組成，即 ConcurrentHashMap 把哈希桶數(shù)組切分成小數(shù)組（Segment ），每個小數(shù)組有 n 個 HashEntry 組成。

如下圖所示，首先將數(shù)據(jù)分為一段一段的存儲，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個線程占用鎖訪問其中一段數(shù)據(jù)時，其他段的數(shù)據(jù)也能被其他線程訪問，實現(xiàn)了真正的并發(fā)訪問。

Segment 是 ConcurrentHashMap 的一個內(nèi)部類，主要的組成如下：

Segment 繼承了 ReentrantLock，所以 Segment 是一種可重入鎖，扮演鎖的角色。Segment 默認(rèn)為 16，也就是并發(fā)度為 16。

存放元素的 HashEntry，也是一個靜態(tài)內(nèi)部類，主要的組成如下：

其中，用 volatile 修飾了 HashEntry 的數(shù)據(jù) value 和 下一個節(jié)點 next，保證了多線程環(huán)境下數(shù)據(jù)獲取時的可見性！

在數(shù)據(jù)結(jié)構(gòu)上， JDK1.8  中的ConcurrentHashMap  選擇了與 HashMap 相同的Node數(shù)組+鏈表+紅黑樹結(jié)構(gòu)；在鎖的實現(xiàn)上，拋棄了原有的 Segment 分段鎖，采用CAS + synchronized實現(xiàn)更加細(xì)粒度的鎖。

將鎖的級別控制在了更細(xì)粒度的哈希桶數(shù)組元素級別，也就是說只需要鎖住這個鏈表頭節(jié)點（紅黑樹的根節(jié)點），就不會影響其他的哈希桶數(shù)組元素的讀寫，大大提高了并發(fā)度。

在 JDK1.6 中，對 synchronized 鎖的實現(xiàn)引入了大量的優(yōu)化，并且 synchronized 有多種鎖狀態(tài)，會從無鎖 -> 偏向鎖 -> 輕量級鎖 -> 重量級鎖一步步轉(zhuǎn)換。

減少內(nèi)存開銷 。假設(shè)使用可重入鎖來獲得同步支持，那么每個節(jié)點都需要通過繼承 AQS 來獲得同步支持。但并不是每個節(jié)點都需要獲得同步支持的，只有鏈表的頭節(jié)點（紅黑樹的根節(jié)點）需要同步，這無疑帶來了巨大內(nèi)存浪費。

先來看JDK1.7

先定位到相應(yīng)的 Segment ，然后再進(jìn)行 put 操作。

源代碼如下：

首先會嘗試獲取鎖，如果獲取失敗肯定就有其他線程存在競爭，則利用 scanAndLockForPut() 自旋獲取鎖。

嘗試自旋獲取鎖。

如果重試的次數(shù)達(dá)到了 MAX_SCAN_RETRIES 則改為阻塞鎖獲取，保證能獲取成功。

大致可以分為以下步驟：

根據(jù) key 計算出 hash 值；

判斷是否需要進(jìn)行初始化；

定位到 Node，拿到首節(jié)點 f，判斷首節(jié)點 f：

如果為  null  ，則通過 CAS 的方式嘗試添加；

如果為 f.hash = MOVED = -1 ，說明其他線程在擴(kuò)容，參與一起擴(kuò)容；

如果都不滿足 ，synchronized 鎖住 f 節(jié)點，判斷是鏈表還是紅黑樹，遍歷插入；

當(dāng)在鏈表長度達(dá)到 8 的時候，數(shù)組擴(kuò)容或者將鏈表轉(zhuǎn)換為紅黑樹。

源代碼如下：

首先，根據(jù) key 計算出 hash 值定位到具體的 Segment ，再根據(jù) hash 值獲取定位 HashEntry 對象，并對 HashEntry 對象進(jìn)行鏈表遍歷，找到對應(yīng)元素。

由于 HashEntry 涉及到的共享變量都使用 volatile 修飾，volatile 可以保證內(nèi)存可見性，所以每次獲取時都是最新值。

源代碼如下：

大致可以分為以下步驟：

根據(jù) key 計算出 hash 值，判斷數(shù)組是否為空；

如果是首節(jié)點，就直接返回；

如果是紅黑樹結(jié)構(gòu)，就從紅黑樹里面查詢；

如果是鏈表結(jié)構(gòu)，循環(huán)遍歷判斷。

源代碼如下：

get 方法不需要加鎖。因為 Node 的元素 value 和指針 next 是用 volatile 修飾的，在多線程環(huán)境下線程A修改節(jié)點的 value 或者新增節(jié)點的時候是對線程B可見的。

這也是它比其他并發(fā)集合比如 Hashtable、用 Collections.synchronizedMap()包裝的 HashMap 效率高的原因之一。

沒有關(guān)系。哈希桶數(shù)組table用 volatile 修飾主要是保證在數(shù)組擴(kuò)容的時候保證可見性。

我們先來說value 為什么不能為 null。因為 ConcurrentHashMap 是用于多線程的 ，如果ConcurrentHashMap.get(key)得到了 null ，這就無法判斷，是映射的value是 null ，還是沒有找到對應(yīng)的key而為 null ，就有了二義性。

而用于單線程狀態(tài)的 HashMap 卻可以用containsKey(key) 去判斷到底是否包含了這個 null 。

我們用反證法來推理：

假設(shè) ConcurrentHashMap 允許存放值為 null 的 value，這時有A、B兩個線程，線程A調(diào)用ConcurrentHashMap.get(key)方法，返回為 null ，我們不知道這個 null 是沒有映射的 null ，還是存的值就是 null 。

假設(shè)此時，返回為 null 的真實情況是沒有找到對應(yīng)的 key。那么，我們可以用 ConcurrentHashMap.containsKey(key)來驗證我們的假設(shè)是否成立，我們期望的結(jié)果是返回 false 。

但是在我們調(diào)用 ConcurrentHashMap.get(key)方法之后，containsKey方法之前，線程B執(zhí)行了ConcurrentHashMap.put(key, null)的操作。那么我們調(diào)用containsKey方法返回的就是 true 了，這就與我們的假設(shè)的真實情況不符合了，這就有了二義性。

至于 ConcurrentHashMap 中的 key 為什么也不能為 null 的問題，源碼就是這樣寫的，哈哈。如果面試官不滿意，就回答因為作者Doug不喜歡 null ，所以在設(shè)計之初就不允許了 null 的 key 存在。想要深入了解的小伙伴，可以看這篇文章這道面試題我真不知道面試官想要的回答是什么

并發(fā)度可以理解為程序運(yùn)行時能夠同時更新 ConccurentHashMap且不產(chǎn)生鎖競爭的最大線程數(shù)。在JDK1.7中，實際上就是ConcurrentHashMap中的分段鎖個數(shù)，即Segment[]的數(shù)組長度，默認(rèn)是16，這個值可以在構(gòu)造函數(shù)中設(shè)置。

如果自己設(shè)置了并發(fā)度，ConcurrentHashMap 會使用大于等于該值的最小的2的冪指數(shù)作為實際并發(fā)度，也就是比如你設(shè)置的值是17，那么實際并發(fā)度是32。

如果并發(fā)度設(shè)置的過小，會帶來嚴(yán)重的鎖競爭問題；如果并發(fā)度設(shè)置的過大，原本位于同一個Segment內(nèi)的訪問會擴(kuò)散到不同的Segment中，CPU cache命中率會下降，從而引起程序性能下降。

在JDK1.8中，已經(jīng)摒棄了Segment的概念，選擇了Node數(shù)組+鏈表+紅黑樹結(jié)構(gòu)，并發(fā)度大小依賴于數(shù)組的大小。

與 HashMap 迭代器是強(qiáng)一致性不同，ConcurrentHashMap 迭代器是弱一致性。

ConcurrentHashMap 的迭代器創(chuàng)建后，就會按照哈希表結(jié)構(gòu)遍歷每個元素，但在遍歷過程中，內(nèi)部元素可能會發(fā)生變化，如果變化發(fā)生在已遍歷過的部分，迭代器就不會反映出來，而如果變化發(fā)生在未遍歷過的部分，迭代器就會發(fā)現(xiàn)并反映出來，這就是弱一致性。

這樣迭代器線程可以使用原來老的數(shù)據(jù)，而寫線程也可以并發(fā)的完成改變，更重要的，這保證了多個線程并發(fā)執(zhí)行的連續(xù)性和擴(kuò)展性，是性能提升的關(guān)鍵。想要深入了解的小伙伴，可以看這篇文章：http:///ConcurrentHashMap-weakly-consistent/

數(shù)據(jù)結(jié)構(gòu)：取消了 Segment 分段鎖的數(shù)據(jù)結(jié)構(gòu)，取而代之的是數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)。

保證線程安全機(jī)制：JDK1.7 采用 Segment 的分段鎖機(jī)制實現(xiàn)線程安全，其中 Segment 繼承自 ReentrantLock 。JDK1.8 采用CAS+synchronized保證線程安全。

鎖的粒度：JDK1.7 是對需要進(jìn)行數(shù)據(jù)操作的 Segment 加鎖，JDK1.8 調(diào)整為對每個數(shù)組元素加鎖（Node）。

鏈表轉(zhuǎn)化為紅黑樹：定位節(jié)點的 hash 算法簡化會帶來弊端，hash 沖突加劇，因此在鏈表節(jié)點數(shù)量大于 8（且數(shù)據(jù)總量大于等于 64）時，會將鏈表轉(zhuǎn)化為紅黑樹進(jìn)行存儲。

查詢時間復(fù)雜度：從 JDK1.7的遍歷鏈表O(n)， JDK1.8 變成遍歷紅黑樹O(logN)。

ConcurrentHashMap 的效率要高于 Hashtable，因為 Hashtable 給整個哈希表加了一把大鎖從而實現(xiàn)線程安全。而ConcurrentHashMap 的鎖粒度更低，在 JDK1.7 中采用分段鎖實現(xiàn)線程安全，在 JDK1.8 中采用CAS+synchronized實現(xiàn)線程安全。

Hashtable 是使用 synchronized來實現(xiàn)線程安全的，給整個哈希表加了一把大鎖，多線程訪問時候，只要有一個線程訪問或操作該對象，那其他線程只能阻塞等待需要的鎖被釋放，在競爭激烈的多線程場景中性能就會非常差！

還可以使用Collections.synchronizedMap方法，對方法進(jìn)行加同步鎖。

如果傳入的是 HashMap 對象，其實也是對 HashMap 做的方法做了一層包裝，里面使用對象鎖來保證多線程場景下，線程安全，本質(zhì)也是對 HashMap 進(jìn)行全表鎖。在競爭激烈的多線程環(huán)境下性能依然也非常差，不推薦使用！