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

mghio2021-07-02 17:49:18

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

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

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

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

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

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

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

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

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

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

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

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

先來(lái)看JDK1.7

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

源代碼如下：

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

嘗試自旋獲取鎖。

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

大致可以分為以下步驟：

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

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

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

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

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

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

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

源代碼如下：

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

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

源代碼如下：

大致可以分為以下步驟：

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

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

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

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

源代碼如下：

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

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

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

我們先來(lái)說(shuō)value 為什么不能為 null。因?yàn)?ConcurrentHashMap 是用于多線程的 ，如果ConcurrentHashMap.get(key)得到了 null ，這就無(wú)法判斷，是映射的value是 null ，還是沒(méi)有找到對(duì)應(yīng)的key而為 null ，就有了二義性。

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

我們用反證法來(lái)推理：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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