前言

我是fancy，一個(gè)年紀(jì)輕輕bug量就累計(jì)到3200個(gè)的程序員，同事們都夸我一個(gè)人養(yǎng)活了整個(gè)測(cè)試組。

最近迷上了并發(fā)編程。并發(fā)這玩意怎么說(shuō)呢，就是你平時(shí)工作用不到，一用就用在面試上。這不，又卷起了并發(fā)容器。

那說(shuō)起并發(fā)容器，你一定也知道那幾個(gè)，CopyOnWriteArrayList、并發(fā)隊(duì)列BlockingQueue，等等。但是作為面試的典中典，聊到并發(fā)容器就無(wú)法繞開(kāi)ConcurrentHashMap。

由于篇幅原因，這篇文章不會(huì)具體解釋那些較為基礎(chǔ)的問(wèn)題，比如為什么散列表數(shù)組的長(zhǎng)度一定要是2的n次方等。將更多圍繞并發(fā)這個(gè)話(huà)題。如有需要，之后會(huì)另外講解。

所以本文我們就來(lái)深入聊聊這個(gè)大廠(chǎng)面試青睞的對(duì)象，八股文里的蘭博基尼：ConcurrentHashMap。

以下的技術(shù)點(diǎn)都基于JDK1.8~

基礎(chǔ)回顧

我們都知道，從JDK1.8起，ConcurrentHashMap底層的數(shù)據(jù)結(jié)構(gòu)就已經(jīng)從原來(lái)的Segment分段鎖變?yōu)榱藬?shù)組 + 鏈表 + 紅黑樹(shù)的形態(tài)。

它是一款并發(fā)容器，一款裝數(shù)據(jù)的容器在并發(fā)環(huán)境下鐵定就會(huì)有各種各樣的問(wèn)題。你在單線(xiàn)程環(huán)境下玩單機(jī)，并發(fā)環(huán)境下就會(huì)有別的線(xiàn)程和你搶數(shù)據(jù)，搶桶位。因此編寫(xiě)JUC包的大神Doug Lea也都為這些場(chǎng)景一一做了適配，可以說(shuō)是絕對(duì)的并發(fā)安全，至少運(yùn)行了這么多年了也沒(méi)遇到什么bug。

紅黑樹(shù)

紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)

JDK1.8這里的紅黑樹(shù)，準(zhǔn)確的來(lái)說(shuō)是一個(gè)TreeBin代理類(lèi)，它作為紅黑樹(shù)的具體實(shí)現(xiàn)起存儲(chǔ)作用，而TreeNode是封裝紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)，所以你可以理解TreeBin就是封裝TreeNode的一個(gè)容器。

紅黑樹(shù)在ConcurrentHashMap里面的體現(xiàn)是一個(gè)雙向鏈表：

紅黑樹(shù)插入數(shù)據(jù)

在這里，紅黑樹(shù)維護(hù)一個(gè)字段dir。

在插入數(shù)據(jù)的時(shí)候會(huì)獲取節(jié)點(diǎn)的hash值，從而與當(dāng)前節(jié)點(diǎn)p的hash值比較，若插入節(jié)點(diǎn)的hash小于當(dāng)前節(jié)點(diǎn)，則dir的值為-1，否則為1：

所以，當(dāng)dir的值為-1時(shí)，就代表插入節(jié)點(diǎn)需要插入到當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)或者繼續(xù)往左子樹(shù)上查找，相反如果dir值為1則向右查找，這里的規(guī)則和二叉查找樹(shù)的規(guī)則是一樣的。

多線(xiàn)程競(jìng)爭(zhēng)下的讀寫(xiě)操作

由于讀操作本身就是天然線(xiàn)程安全的。所以多個(gè)線(xiàn)程對(duì)同一個(gè)桶位同時(shí)讀并不會(huì)有什么問(wèn)題。

但若是相互競(jìng)爭(zhēng)的寫(xiě)操作，就是通過(guò)Synchronized鎖的方式來(lái)保證某個(gè)桶位同一時(shí)刻只有一個(gè)線(xiàn)程能獲取到資源。

通過(guò)源碼可以看到，put()方法的核心是putVal():

putVal()很長(zhǎng)，它主要是通過(guò)Synchronized去鎖住每一個(gè)節(jié)點(diǎn)保證并發(fā)的安全性。

在這里最為重要的兩點(diǎn)

一是判斷你put進(jìn)去的這個(gè)元素，是處于鏈表還是處于紅黑樹(shù)上；

二就是判斷當(dāng)前插入的key是否與鏈表或者紅黑樹(shù)上的某個(gè)元素一致。如果當(dāng)前插入key與鏈表當(dāng)中所有元素的key都不一致時(shí)，那么當(dāng)前的插入操作就追加到鏈表的末尾。否則就替換掉key對(duì)應(yīng)的value。

擴(kuò)容原理

在知道擴(kuò)容原理之前，得知道什么情況會(huì)導(dǎo)致擴(kuò)容。

因此需要知道的兩個(gè)重要字段：

• MIN_TREEIFY_CAPACITY ： 數(shù)組初始長(zhǎng)度，默認(rèn)為64
• TREEIFY_THRESHOLD ： 樹(shù)化閾值，指定桶位鏈表長(zhǎng)度達(dá)到8的話(huà)，就可能發(fā)生樹(shù)化操作

線(xiàn)程往桶里面新增每一個(gè)元素，都會(huì)對(duì)鏈表的長(zhǎng)度進(jìn)行判斷，只有元素個(gè)數(shù)大于閾值MIN_TREEIFY_CAPACITY并且鏈表長(zhǎng)度大于8，才會(huì)調(diào)用treeifyBin()把鏈表轉(zhuǎn)化為紅黑樹(shù)，否則就會(huì)進(jìn)行擴(kuò)容操作。

這里的擴(kuò)容，指的就是擴(kuò)大數(shù)組的桶個(gè)數(shù)，從而裝下更多的元素。

除此之外，擴(kuò)容還維護(hù)了另一重要的字段，sizeCtl：

通過(guò)翻譯，我們可以知道這個(gè)字段有三種狀態(tài)：

• sizeCtl < 0：若為-1則起標(biāo)記作用，告知其它線(xiàn)程此時(shí)正在初始化；若為其它的值表示當(dāng)前table正在擴(kuò)容
• sizeCtl = 0：表示創(chuàng)建table數(shù)組時(shí)還未進(jìn)行擴(kuò)容，沒(méi)有指定的初始容量
• sizeCtl > 0：表示當(dāng)table初始化后下次擴(kuò)容的觸發(fā)條件

字段的值可以轉(zhuǎn)化為32位的二進(jìn)制數(shù)值，它的高16位表示擴(kuò)容標(biāo)識(shí)戳，用來(lái)標(biāo)識(shí)擴(kuò)容的范圍，如從長(zhǎng)度16擴(kuò)容到32；低16位表示當(dāng)前參與擴(kuò)容的線(xiàn)程數(shù)量。

擴(kuò)容操作會(huì)新建一個(gè)長(zhǎng)度更大的數(shù)組，然后將老數(shù)組上的元素全部遷移到新的數(shù)組去。

擴(kuò)容的本質(zhì)目的是為了減少桶位鏈表的長(zhǎng)度，提高查詢(xún)效率。因?yàn)殒湵淼牟樵?xún)復(fù)雜度是O(n)，如果鏈表過(guò)長(zhǎng)就會(huì)影響查詢(xún)效率。

假設(shè)桶位的長(zhǎng)度從16擴(kuò)容到32，說(shuō)明桶位變多了，那遷移到新數(shù)組后就需要有元素去到新的桶位。這就需要通過(guò)一些算法將老數(shù)組和新數(shù)組的元素位置做一個(gè)映射。因?yàn)閿U(kuò)容后元素有的需要遷移到新的位置，有的還是處于和老數(shù)組一樣的位置，只不過(guò)是換了一個(gè)數(shù)組。

如何計(jì)算出這個(gè)元素遷移后要呆在哪個(gè)桶位呢？這里使用了一個(gè)按位與的算法。就是將這個(gè)桶位key的hash值 & (擴(kuò)容前數(shù)組長(zhǎng)度 - 1)，若生成的值等于0則不需要遷移，否則就要進(jìn)行遷移。并且維護(hù)兩個(gè)變量ln和hn代表是否需要進(jìn)行位置遷移。然后采用尾插法將元素插入。這就是LastRun機(jī)制。

注：尾插法指的就是后面插入的元素都處于前一個(gè)元素的后面

這里簡(jiǎn)單普通的擴(kuò)容是沒(méi)什么問(wèn)題的，大多數(shù)場(chǎng)景都和HashMap的擴(kuò)容是一樣的。

問(wèn)題就在于當(dāng)前是處于并發(fā)環(huán)境的，而擴(kuò)容也需要時(shí)間。

正在擴(kuò)容 && 有多個(gè)線(xiàn)程正在競(jìng)爭(zhēng)

所以，比較復(fù)雜的場(chǎng)景來(lái)了。若是桶位正在擴(kuò)容，且有多個(gè)線(xiàn)程正在競(jìng)爭(zhēng)讀寫(xiě)咋辦？厚禮謝

沒(méi)關(guān)系，我們依然分情況來(lái)討論。

擴(kuò)容期間的讀操作

如果擴(kuò)容期間，有線(xiàn)程進(jìn)行元素的讀取，比如你去get()某個(gè)key的value，那讀不讀的到呢？

答案是可以。但是前提是你這個(gè)節(jié)點(diǎn)已經(jīng)遷移結(jié)束，如果你是一個(gè)正在擴(kuò)容遷移的節(jié)點(diǎn)，那就訪(fǎng)問(wèn)不到。

具體的操作，就是去調(diào)用find()。

當(dāng)一個(gè)桶位要進(jìn)行數(shù)據(jù)遷移，就會(huì)往這個(gè)桶位上放置一個(gè)ForwardingNode節(jié)點(diǎn)。除此之外還需要去標(biāo)識(shí)這個(gè)節(jié)點(diǎn)是正在遷移還是已經(jīng)遷移結(jié)束了的；

在這里我們統(tǒng)稱(chēng)遷移前的桶位節(jié)點(diǎn)叫老節(jié)點(diǎn)，遷移后的桶位節(jié)點(diǎn)叫新節(jié)點(diǎn)。當(dāng)其中某一個(gè)節(jié)點(diǎn)遷移完成后，就會(huì)在老節(jié)點(diǎn)上添加一個(gè)fwd引用，它指向新節(jié)點(diǎn)的地址。

所以當(dāng)某個(gè)線(xiàn)程訪(fǎng)問(wèn)了這個(gè)節(jié)點(diǎn)，看到它上面存在fwd引用，就說(shuō)明當(dāng)前table正在擴(kuò)容，那么就會(huì)根據(jù)這個(gè)引用上的newtable字段去新數(shù)組的對(duì)應(yīng)桶位上找到數(shù)據(jù)然后返回。

擴(kuò)容期間的寫(xiě)操作

寫(xiě)操作相較于讀操作會(huì)更加復(fù)雜一點(diǎn)，原因就是讀操作只需要獲取對(duì)應(yīng)數(shù)據(jù)返回就行了，而寫(xiě)操作還要修改數(shù)據(jù)，所以當(dāng)一個(gè)寫(xiě)線(xiàn)程來(lái)修改數(shù)據(jù)剛好碰到容器處于擴(kuò)容期間，那么它還要協(xié)助容器進(jìn)行擴(kuò)容。

具體的擴(kuò)容操作依然還要分情況，假如訪(fǎng)問(wèn)的桶位數(shù)據(jù)還沒(méi)有被遷移走的話(huà)，那就直接競(jìng)爭(zhēng)鎖，然后在老節(jié)點(diǎn)上進(jìn)行操作就行。

但是假如線(xiàn)程修改的節(jié)點(diǎn)正好是一個(gè)fwd節(jié)點(diǎn)，說(shuō)明當(dāng)前節(jié)點(diǎn)正處于擴(kuò)容操作，那么為了節(jié)約線(xiàn)程數(shù)并且快速完成任務(wù)，當(dāng)前線(xiàn)程就會(huì)進(jìn)行協(xié)助擴(kuò)容。如果有多個(gè)線(xiàn)程進(jìn)行同時(shí)寫(xiě)，那么它們都會(huì)調(diào)用helpTransfer()進(jìn)行協(xié)助擴(kuò)容。

這里協(xié)助擴(kuò)容的方式就是拿到一個(gè)擴(kuò)容標(biāo)識(shí)戳，這個(gè)標(biāo)識(shí)戳的作用就是用來(lái)標(biāo)識(shí)擴(kuò)大的容量大小。因?yàn)槊總€(gè)線(xiàn)程都是獨(dú)立的嘛，互不通信，但是它們要做的事情是相同的，就是將桶位擴(kuò)大相同的值，所以它們就必須拿到這個(gè)相同的標(biāo)識(shí)戳，只有標(biāo)識(shí)戳一致才會(huì)進(jìn)行擴(kuò)容。

假設(shè)一個(gè)容器從16個(gè)桶位擴(kuò)容到32個(gè)桶位，有線(xiàn)程A、B兩個(gè)線(xiàn)程。

若A觸發(fā)了擴(kuò)容的機(jī)制，那么線(xiàn)程A就會(huì)進(jìn)行擴(kuò)容，此時(shí)線(xiàn)程B也來(lái)進(jìn)行寫(xiě)操作，發(fā)現(xiàn)正在擴(kuò)容就會(huì)進(jìn)入到協(xié)助擴(kuò)容的步驟中去。

所以線(xiàn)程A和線(xiàn)程B共同負(fù)責(zé)桶位的擴(kuò)容。

一個(gè)線(xiàn)程負(fù)責(zé)擴(kuò)容的桶位個(gè)數(shù)，是根據(jù)CPU核心數(shù)來(lái)算的。最少是16個(gè)，也就是一個(gè)線(xiàn)程最少要負(fù)責(zé)16個(gè)元素的擴(kuò)容：

我們?cè)谏厦嬗刑徇^(guò)，sizeCtl轉(zhuǎn)化為32位后，它的低16位是表示當(dāng)前參與擴(kuò)容的線(xiàn)程數(shù)量。所以當(dāng)A線(xiàn)程觸發(fā)了擴(kuò)容之后，它就會(huì)將sizeCtl低16位的最后一位值+1，表示擴(kuò)容線(xiàn)程多了一位，當(dāng)它退出擴(kuò)容時(shí)又會(huì)將最后一位的值-1，表示擴(kuò)容線(xiàn)程少了一位，就這樣各個(gè)線(xiàn)程共同維護(hù)這個(gè)字段。

所以你一定會(huì)好奇了：那我要是最后一個(gè)退出擴(kuò)容的線(xiàn)程要怎么維護(hù)啊？是的，最后一個(gè)線(xiàn)程還有一些別的事情要做。當(dāng)某一個(gè)線(xiàn)程完成任務(wù)后去判斷sizeCtl的值得時(shí)候，發(fā)現(xiàn)它的低16位只剩下最后一位是1，再減下去就是0了，那就代表它是最后一個(gè)退出擴(kuò)容的線(xiàn)程。此時(shí)它還需要去檢查一遍老的table數(shù)組，判斷是否還有遺漏的slot沒(méi)有遷移。具體的操作就是去輪詢(xún)檢查是否還留有fwd節(jié)點(diǎn)，如果沒(méi)有的話(huà)代表遷移完成，如果有的話(huà)還需要繼續(xù)將它遷移到新的桶位：

由于源碼非常長(zhǎng)，所以我們就不貼全部源碼了，通過(guò)流程圖的方式來(lái)幫助大家理解這個(gè)擴(kuò)容期間的操作：

總結(jié)

有的童鞋在看Juc這一塊的時(shí)候會(huì)去背誦源碼，將方法的調(diào)用鏈都講的頭頭是道，我認(rèn)為沒(méi)有必要，相反面試官可能會(huì)覺(jué)得你過(guò)于抽象，背的這么清楚。并發(fā)的核心在于如何用手段去解決可能遇到的安全問(wèn)題，并且讓它更高效點(diǎn)，面試的目的也是為了體現(xiàn)你思維能力。

以上就是java并發(fā)容器ConcurrentHashMap深入分析的詳細(xì)內(nèi)容，更多關(guān)于ConcurrentHashMap并發(fā)容器的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論