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

mghio2021-07-02 17:49:18

文章標簽面試 ConcurrentHashMa文章分類代碼人生閱讀數201

ConcurrentHashMap  在 JDK1.7 和 JDK1.8  的實現方式是不同的。

JDK1.7 中的 ConcurrentHashMap 是由 Segment 數組結構和 HashEntry 數組結構組成，即 ConcurrentHashMap 把哈希桶數組切分成小數組（Segment ），每個小數組有 n 個 HashEntry 組成。

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

Segment 是 ConcurrentHashMap 的一個內部類，主要的組成如下：

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

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

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

在數據結構上， JDK1.8  中的ConcurrentHashMap  選擇了與 HashMap 相同的Node數組+鏈表+紅黑樹結構；在鎖的實現上，拋棄了原有的 Segment 分段鎖，采用CAS + synchronized實現更加細粒度的鎖。

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

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

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

先來看JDK1.7

先定位到相應的 Segment ，然后再進行 put 操作。

源代碼如下：

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

嘗試自旋獲取鎖。

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

大致可以分為以下步驟：

根據 key 計算出 hash 值；

判斷是否需要進行初始化；

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

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

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

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

當在鏈表長度達到 8 的時候，數組擴容或者將鏈表轉換為紅黑樹。

源代碼如下：

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

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

源代碼如下：

大致可以分為以下步驟：

根據 key 計算出 hash 值，判斷數組是否為空；

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

如果是紅黑樹結構，就從紅黑樹里面查詢；

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

源代碼如下：

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

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

沒有關系。哈希桶數組table用 volatile 修飾主要是保證在數組擴容的時候保證可見性。

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

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

我們用反證法來推理：

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

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

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

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

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

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

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

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

與 HashMap 迭代器是強一致性不同，ConcurrentHashMap 迭代器是弱一致性。

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

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

數據結構：取消了 Segment 分段鎖的數據結構，取而代之的是數組+鏈表+紅黑樹的結構。

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

鎖的粒度：JDK1.7 是對需要進行數據操作的 Segment 加鎖，JDK1.8 調整為對每個數組元素加鎖（Node）。

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

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

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

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

還可以使用Collections.synchronizedMap方法，對方法進行加同步鎖。

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