本文轉(zhuǎn)載自微信公眾號「yes的練級攻略」，作者是Yes呀。轉(zhuǎn)載本文請聯(lián)系yes的練級攻略公眾號。

你好，我是yes。

上篇講了??集合類的相關面試點??已經(jīng)包含 HashMap 了，這篇就來盤盤 ConcurrentHashMap。

我們都知道 HashMap 是非線程安全的，然后還有個 HashTable ，這玩意雖說是線程安全，但所有方法用的是同一把鎖，并發(fā)度太低，性能不好。

所以，如要在并發(fā)場景下使用 Map ，那就推薦用 ConcurrentHashMap。

而談到 ConcurrentHashMap，經(jīng)常會被問到 JDK1.8 相對于 1.7 版本做哪些優(yōu)化，所以我們先來看下 1.7 的是實現(xiàn)。

ConcurrentHashMap 1.7

其實大體的哈希表實現(xiàn)跟 HashMap 沒有本質(zhì)的區(qū)別，都是經(jīng)過 key 的 hash 定位到一個下標，然后獲取元素，如果沖突了就用鏈表相連。

差別就在于引入了一個 Segments 數(shù)組，我們來看下大致的結(jié)構(gòu)。

原理就是先通過 key 的 hash 判斷得到 Segment 數(shù)組的下標，然后將這個 Segment 上鎖，然后再次通過 key 的 hash 得到 Segment 里 HashEntry 數(shù)組的下標，下面這步其實就是 HashMap 一致了，所以我說差別就是引入了一個 Segments 數(shù)組。

因此可以簡化的這樣理解：每個 Segment 數(shù)組存放的就是一個單獨的 HashMap。

可以看到，圖上我們有 6 個 Segment ，那么等于有六把鎖，因此共可以有六個線程同時操作這個 ConcurrentHashMap，并發(fā)度就是 6，相比于直接將 put 方法上鎖，并發(fā)度就提高了，這就是分段鎖。

具體上鎖的方式來源于 Segment ，這個類實際繼承了 ReentrantLock，因此它自身具備加鎖的功能。

可以看出，1.7 的分段鎖已經(jīng)有了細化鎖粒度的概念，它的一個缺陷是 Segment 數(shù)組一旦初始化了之后不會擴容，只有 HashEntry 數(shù)組會擴容，這就導致并發(fā)度過于死板，不能隨著數(shù)據(jù)的增加而提高并發(fā)度。

ConcurrentHashMap 1.8

1.8 ConcurrentHashMap 做了更細粒度的鎖控制，可以理解為 1.8 HashMap 的數(shù)組的每個位置都是一把鎖，這樣擴容了鎖也會變多，并發(fā)度也會增加。

思想的轉(zhuǎn)變就是把粒度更加細化，我不分段了，我直接把 Node 數(shù)組的每個節(jié)點分別上一把鎖，這樣并發(fā)度不就更高了嗎?

并且 1.8 也不借助于 ReentrantLock 了，直接用 synchronized，這也側(cè)面證明，都 1.8 了 synchronized 優(yōu)化后的速度已經(jīng)不下于 ReentrantLock 了。

具體實現(xiàn)思路也簡單，當塞入一個值的時候，先計算 key 的 hash 后的下標，如果計算到的下標還未有 Node ，那么就通過 cas 塞入新的 Node。如果已經(jīng)有 node 則通過 synchronized 將這個 node 上鎖，這樣別的線程就無法訪問這個 node 及其之后的所有節(jié)點。

然后判斷 key 是否相等，相等則是替換 value ，反之則是新增一個 node，這個操作和 HashMap 是一樣的。

1.8 的擴容也是有點意思的，它允許協(xié)助擴容，也就是多線程擴容。

當 put 的時候，發(fā)現(xiàn)當前 node hash 值是 -1，則表明當前的節(jié)點正在擴容，則會觸發(fā)協(xié)助擴容機制

這個要詳細說起來還真的有點麻煩，而且不太好說清，代碼有點大，我就說個大概。

其實大家大致理解下就夠了：

擴容無非就是搬遷 Node，假設當前數(shù)組長度為 32，那就可以分著搬遷，31-16 這幾個下標的 Node 都由線程A來搬遷，然后線程 B 來搬遷 15-0 這幾個下標的 Node。

簡單說就是會維護一個 transferIndex 變量，來的線程死循環(huán) cas 爭搶下標，如果下標已經(jīng)分配完了，那自然就不需要搬遷了，如果 cas 搶到了要搬運的下標，那就去幫忙搬就好了，就是這么個事兒。

還有 1.8 的 size 方法和 1.7 也不一樣1.7 有個嘗試的思想，當調(diào)用 size 方法的時候不會加鎖，而是先嘗試三次不加鎖獲取 sum。

如果三次總數(shù)一樣，說明當前數(shù)量沒有變化，那就直接返回了。如果總數(shù)不一樣，那說明此時有線程在增刪 map，于是加鎖計算，這時候其他線程就操作不了 map 了。

  if (retries++ == RETRIES_BEFORE_LOCK) {
       for (int j = 0; j < segments.length; ++j)
           ensureSegment(j).lock(); // force creation
   }
   ...再累加數(shù)量

而 1.8 不一樣，它就是直接計算返回結(jié)果，具體采用的是類似 LongAdder 的思想，累加不再是基于一個成員變量，而是搞了一個數(shù)組，每個線程在自己對應的下標地方進行累加，等最后的時候把數(shù)組里面的數(shù)據(jù)統(tǒng)一一下，就是最終的值了。

所以這是一個分解的思想，分而治之。

在 put 的時候，就會通過 addCount 方法維護 counterCells 的數(shù)量，當然 remove 的時候也會調(diào)用此方法。

總而言之，就是平日的操作會維護 map 里面的節(jié)點數(shù)量，會先通過 CAS 修改 baseCount ，如果成功就直接返回，如果失敗說明此時有線程在競爭，那么就通過 hash 選擇一個 CounterCell 對象就行修改，最終 size 的結(jié)果就是 baseCount + 所有 CounterCell 。

這種通過 counterCell 數(shù)組來減少并發(fā)下場景下對單個成員變量的競爭壓力，提高了并發(fā)度，提升了性能，這也就是 LongAdder 的思想。

這里還有個能問的就是 @sun.misc.Contended 注解了，這個和偽共享有關系，具體可以看看我之前寫的這篇文章：

??填之前的坑，偽共享解析??

ConcurrentHashMap#get需要加鎖嗎?不需要加鎖。

保證 put 的時候線程安全之后，get 的時候只需要保證可見性即可，而可見性不需要加鎖。

具體是通過Unsafe#getXXXVolatile 和用 volatile 來修飾節(jié)點的 val 和 next 指針來實現(xiàn)的。

為什么 ConcurrentHashMap 不支持 key 或者 value 為 null ?

首先， key 為什么也不能為 null ?我不知道，沒想明白，可能是作者 lea 佬不喜歡 null 值。

那 value 為什么不能為 null ?

因為在多線程情況下， null 值會產(chǎn)生二義性，因為你不清楚 map 里到底是不存在在這個 key ，還是說被put(key，null)。

這里可能有人會說，那 HashMap 不一樣有這個問題?HashMap 可以通過 containsKey 來判斷是否存在這個 key，而多線程使用的 ConcurrentHashMap 就不能夠。

比如你 get(key) 得到了null，此時map里面沒有這個 key 的，但是你不知道，所以你想調(diào)用 containsKey 看看，而恰巧在你調(diào)用之前，別的線程 put 了這個 key ，這樣你 containsKey 就發(fā)現(xiàn)有這個 key，這是不是就發(fā)生“誤會”了。

最后

對 ConcurrentHashMap 的了解到這份上差不多了，再多的可以看看源碼，里面還是有很多值得學習的地方。

集合類的面試題到這就差不多了，后面寫 Spring 的面試題。

還有我的面試倉庫，上面已經(jīng)有很多面試題啦，求個 star!點擊閱讀原文，也可訪問~

??https://github.com/yessimida/interview-of-legends??

我是yes，我們下篇見~