之前被問的 ConcurrentHashMap 面試題，我匯總一下！
本文轉(zhuǎn)載自微信公眾號(hào)「yes的練級(jí)攻略」，作者是Yes呀。轉(zhuǎn)載本文請(qǐng)聯(lián)系yes的練級(jí)攻略公眾號(hào)。
你好，我是yes。
上篇講了??集合類的相關(guān)面試點(diǎn)??已經(jīng)包含 HashMap 了，這篇就來盤盤 ConcurrentHashMap。
我們都知道 HashMap 是非線程安全的，然后還有個(gè) HashTable ，這玩意雖說是線程安全，但所有方法用的是同一把鎖，并發(fā)度太低，性能不好。
所以，如要在并發(fā)場(chǎng)景下使用 Map ，那就推薦用 ConcurrentHashMap。
而談到 ConcurrentHashMap，經(jīng)常會(huì)被問到 JDK1.8 相對(duì)于 1.7 版本做哪些優(yōu)化，所以我們先來看下 1.7 的是實(shí)現(xiàn)。
ConcurrentHashMap 1.7
其實(shí)大體的哈希表實(shí)現(xiàn)跟 HashMap 沒有本質(zhì)的區(qū)別，都是經(jīng)過 key 的 hash 定位到一個(gè)下標(biāo)，然后獲取元素，如果沖突了就用鏈表相連。
差別就在于引入了一個(gè) Segments 數(shù)組，我們來看下大致的結(jié)構(gòu)。
原理就是先通過 key 的 hash 判斷得到 Segment 數(shù)組的下標(biāo)，然后將這個(gè) Segment 上鎖，然后再次通過 key 的 hash 得到 Segment 里 HashEntry 數(shù)組的下標(biāo)，下面這步其實(shí)就是 HashMap 一致了，所以我說差別就是引入了一個(gè) Segments 數(shù)組。
因此可以簡(jiǎn)化的這樣理解：每個(gè) Segment 數(shù)組存放的就是一個(gè)單獨(dú)的 HashMap。
可以看到，圖上我們有 6 個(gè) Segment ，那么等于有六把鎖，因此共可以有六個(gè)線程同時(shí)操作這個(gè) ConcurrentHashMap，并發(fā)度就是 6，相比于直接將 put 方法上鎖，并發(fā)度就提高了，這就是分段鎖。
具體上鎖的方式來源于 Segment ，這個(gè)類實(shí)際繼承了 ReentrantLock，因此它自身具備加鎖的功能。
可以看出，1.7 的分段鎖已經(jīng)有了細(xì)化鎖粒度的概念，它的一個(gè)缺陷是 Segment 數(shù)組一旦初始化了之后不會(huì)擴(kuò)容，只有 HashEntry 數(shù)組會(huì)擴(kuò)容，這就導(dǎo)致并發(fā)度過于死板，不能隨著數(shù)據(jù)的增加而提高并發(fā)度。
ConcurrentHashMap 1.8
1.8 ConcurrentHashMap 做了更細(xì)粒度的鎖控制，可以理解為 1.8 HashMap 的數(shù)組的每個(gè)位置都是一把鎖，這樣擴(kuò)容了鎖也會(huì)變多，并發(fā)度也會(huì)增加。
思想的轉(zhuǎn)變就是把粒度更加細(xì)化，我不分段了，我直接把 Node 數(shù)組的每個(gè)節(jié)點(diǎn)分別上一把鎖，這樣并發(fā)度不就更高了嗎?
并且 1.8 也不借助于 ReentrantLock 了，直接用 synchronized，這也側(cè)面證明，都 1.8 了 synchronized 優(yōu)化后的速度已經(jīng)不下于 ReentrantLock 了。
具體實(shí)現(xiàn)思路也簡(jiǎn)單，當(dāng)塞入一個(gè)值的時(shí)候，先計(jì)算 key 的 hash 后的下標(biāo)，如果計(jì)算到的下標(biāo)還未有 Node ，那么就通過 cas 塞入新的 Node。如果已經(jīng)有 node 則通過 synchronized 將這個(gè) node 上鎖，這樣別的線程就無法訪問這個(gè) node 及其之后的所有節(jié)點(diǎn)。
然后判斷 key 是否相等，相等則是替換 value ，反之則是新增一個(gè) node，這個(gè)操作和 HashMap 是一樣的。
1.8 的擴(kuò)容也是有點(diǎn)意思的，它允許協(xié)助擴(kuò)容，也就是多線程擴(kuò)容。
當(dāng) put 的時(shí)候，發(fā)現(xiàn)當(dāng)前 node hash 值是 -1，則表明當(dāng)前的節(jié)點(diǎn)正在擴(kuò)容，則會(huì)觸發(fā)協(xié)助擴(kuò)容機(jī)制
這個(gè)要詳細(xì)說起來還真的有點(diǎn)麻煩，而且不太好說清，代碼有點(diǎn)大，我就說個(gè)大概。
其實(shí)大家大致理解下就夠了：
擴(kuò)容無非就是搬遷 Node，假設(shè)當(dāng)前數(shù)組長(zhǎng)度為 32，那就可以分著搬遷，31-16 這幾個(gè)下標(biāo)的 Node 都由線程A來搬遷，然后線程 B 來搬遷 15-0 這幾個(gè)下標(biāo)的 Node。
簡(jiǎn)單說就是會(huì)維護(hù)一個(gè) transferIndex 變量，來的線程死循環(huán) cas 爭(zhēng)搶下標(biāo)，如果下標(biāo)已經(jīng)分配完了，那自然就不需要搬遷了，如果 cas 搶到了要搬運(yùn)的下標(biāo)，那就去幫忙搬就好了，就是這么個(gè)事兒。
還有 1.8 的 size 方法和 1.7 也不一樣1.7 有個(gè)嘗試的思想，當(dāng)調(diào)用 size 方法的時(shí)候不會(huì)加鎖，而是先嘗試三次不加鎖獲取 sum。
如果三次總數(shù)一樣，說明當(dāng)前數(shù)量沒有變化，那就直接返回了。如果總數(shù)不一樣，那說明此時(shí)有線程在增刪 map，于是加鎖計(jì)算，這時(shí)候其他線程就操作不了 map 了。
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
...再累加數(shù)量
而 1.8 不一樣，它就是直接計(jì)算返回結(jié)果，具體采用的是類似 LongAdder 的思想，累加不再是基于一個(gè)成員變量，而是搞了一個(gè)數(shù)組，每個(gè)線程在自己對(duì)應(yīng)的下標(biāo)地方進(jìn)行累加，等最后的時(shí)候把數(shù)組里面的數(shù)據(jù)統(tǒng)一一下，就是最終的值了。
所以這是一個(gè)分解的思想，分而治之。
在 put 的時(shí)候，就會(huì)通過 addCount 方法維護(hù) counterCells 的數(shù)量，當(dāng)然 remove 的時(shí)候也會(huì)調(diào)用此方法。
總而言之，就是平日的操作會(huì)維護(hù) map 里面的節(jié)點(diǎn)數(shù)量，會(huì)先通過 CAS 修改 baseCount ，如果成功就直接返回，如果失敗說明此時(shí)有線程在競(jìng)爭(zhēng)，那么就通過 hash 選擇一個(gè) CounterCell 對(duì)象就行修改，最終 size 的結(jié)果就是 baseCount + 所有 CounterCell 。
這種通過 counterCell 數(shù)組來減少并發(fā)下場(chǎng)景下對(duì)單個(gè)成員變量的競(jìng)爭(zhēng)壓力，提高了并發(fā)度，提升了性能，這也就是 LongAdder 的思想。
這里還有個(gè)能問的就是 @sun.misc.Contended 注解了，這個(gè)和偽共享有關(guān)系，具體可以看看我之前寫的這篇文章：
ConcurrentHashMap#get需要加鎖嗎?不需要加鎖。
保證 put 的時(shí)候線程安全之后，get 的時(shí)候只需要保證可見性即可，而可見性不需要加鎖。
具體是通過Unsafe#getXXXVolatile 和用 volatile 來修飾節(jié)點(diǎn)的 val 和 next 指針來實(shí)現(xiàn)的。
為什么 ConcurrentHashMap 不支持 key 或者 value 為 null ?
首先， key 為什么也不能為 null ?我不知道，沒想明白，可能是作者 lea 佬不喜歡 null 值。
那 value 為什么不能為 null ?
因?yàn)樵诙嗑€程情況下， null 值會(huì)產(chǎn)生二義性，因?yàn)槟悴磺宄?map 里到底是不存在在這個(gè) key ，還是說被put(key，null)。
這里可能有人會(huì)說，那 HashMap 不一樣有這個(gè)問題?HashMap 可以通過 containsKey 來判斷是否存在這個(gè) key，而多線程使用的 ConcurrentHashMap 就不能夠。
比如你 get(key) 得到了null，此時(shí)map里面沒有這個(gè) key 的，但是你不知道，所以你想調(diào)用 containsKey 看看，而恰巧在你調(diào)用之前，別的線程 put 了這個(gè) key ，這樣你 containsKey 就發(fā)現(xiàn)有這個(gè) key，這是不是就發(fā)生“誤會(huì)”了。
最后
對(duì) ConcurrentHashMap 的了解到這份上差不多了，再多的可以看看源碼，里面還是有很多值得學(xué)習(xí)的地方。
集合類的面試題到這就差不多了，后面寫 Spring 的面試題。
還有我的面試倉庫，上面已經(jīng)有很多面試題啦，求個(gè) star!點(diǎn)擊閱讀原文，也可訪問~
??https://github.com/yessimida/interview-of-legends??
我是yes，我們下篇見~
