1. 為什么ConcurrentHashMap是J.U.C里最值得啃的容器聊到Java多線程繞不開J.U.C這個(gè)包而J.U.C里面真正在生產(chǎn)環(huán)境里天天被用的并發(fā)容器ConcurrentHashMap說(shuō)第二沒(méi)人敢說(shuō)第一。很多同學(xué)背八股文的時(shí)候能把“分段鎖”“CASsynchronized”“紅黑樹”這些詞說(shuō)得滾瓜爛熟但真到了項(xiàng)目里讓他解釋為什么HashMap在多線程下會(huì)死循環(huán)、為什么ConcurrentHashMap的size()方法返回的只是一個(gè)估計(jì)值、為什么JDK8之后放棄了Segment分段鎖往往就卡殼了。這篇內(nèi)容就是沖著這些卡殼的地方來(lái)的。我會(huì)把ConcurrentHashMap從設(shè)計(jì)動(dòng)機(jī)、底層結(jié)構(gòu)、核心方法實(shí)現(xiàn)、擴(kuò)容機(jī)制到實(shí)際使用中的坑一層一層拆開講。適合已經(jīng)會(huì)寫Java、用過(guò)HashMap、但對(duì)并發(fā)場(chǎng)景下容器行為心里沒(méi)底的同學(xué)也適合正在準(zhǔn)備面試、想把J.U.C這塊知識(shí)從“背答案”升級(jí)成“真理解”的開發(fā)者。讀完你至少能搞清楚三件事ConcurrentHashMap到底怎么保證線程安全、它的性能優(yōu)勢(shì)從哪來(lái)、以及在實(shí)際項(xiàng)目里怎么用才不出問(wèn)題。需要先說(shuō)明一點(diǎn)這篇內(nèi)容以JDK8及之后的實(shí)現(xiàn)為主線因?yàn)楝F(xiàn)在主流生產(chǎn)環(huán)境基本都是JDK8起步JDK7那套Segment分段鎖的設(shè)計(jì)我會(huì)在對(duì)比時(shí)提到但不會(huì)花大篇幅去講已經(jīng)很少用的老實(shí)現(xiàn)。另外文中涉及的一些參數(shù)和閾值我會(huì)給出計(jì)算過(guò)程方便你自己推導(dǎo)而不是死記。2. 從HashMap的線程安全問(wèn)題說(shuō)起2.1 HashMap在多線程下到底會(huì)出什么事很多人知道“HashMap線程不安全”但具體怎么個(gè)不安全法說(shuō)不清楚。我把它歸納成三類典型問(wèn)題每一類都對(duì)應(yīng)著真實(shí)的故障場(chǎng)景。第一類是數(shù)據(jù)覆蓋。HashMap的put操作在JDK8里是這么個(gè)邏輯算出桶下標(biāo)如果桶是空的直接把新節(jié)點(diǎn)放進(jìn)去。問(wèn)題就出在“如果桶是空的”這個(gè)判斷上。兩個(gè)線程同時(shí)判斷某個(gè)桶為空然后同時(shí)往里放節(jié)點(diǎn)后放的那個(gè)就會(huì)把先放的覆蓋掉導(dǎo)致一個(gè)線程的數(shù)據(jù)憑空消失。這種問(wèn)題在并發(fā)量不高的時(shí)候很難復(fù)現(xiàn)一旦復(fù)現(xiàn)就是偶發(fā)的數(shù)據(jù)丟失排查起來(lái)極其痛苦。第二類是擴(kuò)容時(shí)的死循環(huán)。這個(gè)問(wèn)題在JDK7里特別出名JDK8雖然做了優(yōu)化但并發(fā)擴(kuò)容仍然可能導(dǎo)致數(shù)據(jù)錯(cuò)亂。JDK7的HashMap在擴(kuò)容時(shí)用的是頭插法多線程同時(shí)觸發(fā)擴(kuò)容鏈表指針可能被反轉(zhuǎn)成環(huán)之后任何一次get操作只要落到這個(gè)環(huán)上就會(huì)無(wú)限循環(huán)CPU直接飆到100%。我早年排查過(guò)一個(gè)線上問(wèn)題一個(gè)服務(wù)跑著跑著CPU打滿jstack一看全卡在HashMap.get上最后定位就是多線程共享了一個(gè)HashMap。第三類是size計(jì)數(shù)不準(zhǔn)。HashMap的size字段就是個(gè)普通int多線程并發(fā)修改時(shí)自增自減不是原子操作最終結(jié)果肯定對(duì)不上。注意不要覺(jué)得“我只是讀多寫少”就可以用HashMap。只要有一個(gè)寫操作和其他讀寫操作并發(fā)就可能出問(wèn)題。讀操作本身在HashMap里也不是完全安全的因?yàn)閿U(kuò)容過(guò)程中讀到的可能是舊表也可能是新表。2.2 為什么不用Collections.synchronizedMap既然HashMap不安全那用Collections.synchronizedMap包一層行不行行但性能很難看。它的做法是給整個(gè)Map對(duì)象加一把大鎖所有讀寫操作都要先搶這把鎖。這意味著同一時(shí)刻只能有一個(gè)線程操作Map并發(fā)能力直接退化成單線程。你開100個(gè)線程實(shí)際干活的是一個(gè)一個(gè)排隊(duì)來(lái)吞吐量上不去。Hashtable也是同樣的毛病方法上直接加synchronized鎖粒度太粗。在并發(fā)場(chǎng)景下這種“一把大鎖保平安”的方案安全是安全了但性能代價(jià)太大。ConcurrentHashMap要解決的核心矛盾就是既要線程安全又要把鎖的粒度降到足夠細(xì)讓多個(gè)線程能真正并行地操作。2.3 ConcurrentHashMap的設(shè)計(jì)目標(biāo)ConcurrentHashMap的設(shè)計(jì)目標(biāo)可以概括成三條高并發(fā)讀、適度并發(fā)寫、弱一致性。高并發(fā)讀指的是讀操作基本不加鎖靠volatile保證可見性這樣讀的性能接近HashMap。適度并發(fā)寫指的是寫操作只鎖住當(dāng)前要操作的那個(gè)桶不同桶的寫可以并行。弱一致性指的是像size()、isEmpty()、containsValue()這類方法返回的不是精確值而是某一時(shí)刻的估計(jì)值因?yàn)橐玫骄_值就得鎖住整個(gè)表那就違背了設(shè)計(jì)初衷。理解這三點(diǎn)很關(guān)鍵因?yàn)楹芏嗍褂蒙系睦Щ蠖荚从趯?duì)“弱一致性”的不理解。比如你往ConcurrentHashMap里放了100個(gè)元素另一個(gè)線程調(diào)size()可能返回98這不是bug是設(shè)計(jì)如此。3. JDK8里ConcurrentHashMap的底層結(jié)構(gòu)拆解3.1 數(shù)組加鏈表加紅黑樹的組合結(jié)構(gòu)JDK8的ConcurrentHashMap底層結(jié)構(gòu)和HashMap基本一致都是數(shù)組鏈表紅黑樹。數(shù)組叫table每個(gè)元素是一個(gè)桶桶里掛鏈表鏈表長(zhǎng)度超過(guò)閾值就轉(zhuǎn)紅黑樹。這里有個(gè)關(guān)鍵參數(shù)需要搞清楚樹化閾值是8退化閾值是6。為什么是8官方注釋里給了解釋鏈表節(jié)點(diǎn)按泊松分布在負(fù)載因子0.75的情況下鏈表長(zhǎng)度達(dá)到8的概率大約是千萬(wàn)分之六幾乎不可能。選8是為了在極端情況下才轉(zhuǎn)樹避免頻繁的樹化和退化操作。退化閾值選6而不是7是為了留一個(gè)緩沖防止在7附近反復(fù)橫跳。數(shù)組的默認(rèn)容量是16負(fù)載因子0.75這些和HashMap一樣。但ConcurrentHashMap多了一個(gè)sizeCtl字段這個(gè)字段身兼數(shù)職負(fù)數(shù)時(shí)表示正在初始化或擴(kuò)容-1表示正在初始化-(1n)表示有n個(gè)線程正在協(xié)助擴(kuò)容正數(shù)時(shí)表示下一次擴(kuò)容的閾值。這個(gè)設(shè)計(jì)很巧妙用一個(gè)字段表達(dá)了多種狀態(tài)。3.2 為什么放棄Segment分段鎖JDK7的ConcurrentHashMap用的是Segment分段鎖把整個(gè)表分成若干段每段獨(dú)立加鎖。這個(gè)設(shè)計(jì)在當(dāng)時(shí)是很先進(jìn)的但有幾個(gè)問(wèn)題。一是內(nèi)存開銷大。每個(gè)Segment本身就是一個(gè)ReentrantLock還要維護(hù)自己的HashEntry數(shù)組段數(shù)一多內(nèi)存占用就上去了。二是鎖粒度還是偏粗。Segment的數(shù)量在初始化時(shí)就固定了并發(fā)度上限就是段數(shù)沒(méi)法動(dòng)態(tài)調(diào)整。三是實(shí)現(xiàn)復(fù)雜。定位一個(gè)元素要先定位Segment再定位桶兩層hash代碼可讀性差。JDK8改成CASsynchronized鎖單個(gè)桶鎖粒度直接降到桶級(jí)別。桶是動(dòng)態(tài)的數(shù)組擴(kuò)容后桶的數(shù)量增加并發(fā)度自然提升。而且synchronized在JDK8里做了大量?jī)?yōu)化偏向鎖、輕量級(jí)鎖、鎖消除這些機(jī)制讓它的性能不比ReentrantLock差代碼還更簡(jiǎn)潔。3.3 Node節(jié)點(diǎn)的設(shè)計(jì)細(xì)節(jié)ConcurrentHashMap的節(jié)點(diǎn)類叫Node和HashMap的Node比關(guān)鍵區(qū)別在于val和next都用volatile修飾。volatile保證了可見性一個(gè)線程修改了節(jié)點(diǎn)的值或next指針其他線程能立刻看到。這是讀操作能不加鎖的基礎(chǔ)。Node的hash字段是final的一旦計(jì)算好就不變。這里有個(gè)細(xì)節(jié)ConcurrentHashMap的hash計(jì)算比HashMap多了一步會(huì)把hash值的高位和低位做異或目的是讓hash分布更均勻減少碰撞。具體做法是(h ^ (h 16)) 0x7fffffff最后和0x7fffffff做與運(yùn)算是為了把符號(hào)位抹掉保證結(jié)果非負(fù)。除了普通Node還有幾個(gè)特殊節(jié)點(diǎn)ForwardingNode表示這個(gè)桶已經(jīng)遷移到新表了TreeBin是紅黑樹的包裝節(jié)點(diǎn)ReservationNode用于computeIfAbsent等方法的占位。這些特殊節(jié)點(diǎn)在擴(kuò)容和并發(fā)控制里扮演重要角色后面會(huì)細(xì)說(shuō)。4. 核心方法的實(shí)現(xiàn)原理與實(shí)操分析4.1 put方法的完整流程put方法是理解ConcurrentHashMap的鑰匙我把它拆成幾個(gè)階段來(lái)講。第一個(gè)階段是計(jì)算hash并定位桶。如果table還沒(méi)初始化先調(diào)用initTable()初始化。initTable里用CAS搶一個(gè)sizeCtl為-1的狀態(tài)搶到的線程負(fù)責(zé)初始化其他線程自旋等待。這個(gè)設(shè)計(jì)保證了初始化只做一次。第二個(gè)階段是桶為空的情況。如果目標(biāo)桶是null直接用CAS把新節(jié)點(diǎn)放進(jìn)去。CAS失敗就進(jìn)入下一輪循環(huán)重試。這是最理想的情況全程無(wú)鎖。第三個(gè)階段是桶不為空的情況。這時(shí)候用synchronized鎖住桶的頭節(jié)點(diǎn)然后在鏈表或紅黑樹里找位置插入。如果是鏈表遍歷到尾部插入如果是紅黑樹調(diào)用紅黑樹的插入方法。這里鎖的是頭節(jié)點(diǎn)對(duì)象不同桶的頭節(jié)點(diǎn)不同所以不同桶的寫操作可以并行。第四個(gè)階段是判斷是否需要樹化。鏈表長(zhǎng)度達(dá)到8且數(shù)組容量達(dá)到64時(shí)才樹化如果容量不夠64優(yōu)先擴(kuò)容而不是樹化。這個(gè)細(xì)節(jié)很多人不知道以為鏈表到8就一定轉(zhuǎn)樹。第五個(gè)階段是更新size并判斷是否需要擴(kuò)容。size的更新用的是類似LongAdder的分散計(jì)數(shù)機(jī)制后面單獨(dú)講。擴(kuò)容判斷用的是sizeCtl閾值超過(guò)就觸發(fā)擴(kuò)容。// put方法的核心邏輯簡(jiǎn)化示意 final V putVal(K key, V value, boolean onlyIfAbsent) { if (key null || value null) throw new NullPointerException(); int hash spread(key.hashCode()); int binCount 0; for (NodeK,V[] tab table;;) { NodeK,V f; int n, i, fh; if (tab null || (n tab.length) 0) tab initTable(); else if ((f tabAt(tab, i (n - 1) hash)) null) { if (casTabAt(tab, i, null, new NodeK,V(hash, key, value, null))) break; } else if ((fh f.hash) MOVED) tab helpTransfer(tab, f); else { V oldVal null; synchronized (f) { // 鏈表或紅黑樹插入邏輯 } if (binCount ! 0) { if (binCount TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal ! null) return oldVal; break; } } } addCount(1L, binCount); return null; }注意ConcurrentHashMap的key和value都不允許為null。這一點(diǎn)和HashMap不同HashMap允許一個(gè)null key和多個(gè)null value。為什么不允許因?yàn)椴l(fā)場(chǎng)景下如果get返回null你沒(méi)法區(qū)分是“這個(gè)key不存在”還是“這個(gè)key對(duì)應(yīng)的value是null”這在并發(fā)編程里會(huì)造成歧義。4.2 get方法為什么可以不加鎖get方法的邏輯很簡(jiǎn)單算hash定位桶如果桶頭節(jié)點(diǎn)匹配就返回否則遍歷鏈表或紅黑樹。整個(gè)過(guò)程沒(méi)有任何加鎖操作靠的是volatile的可見性保證。具體來(lái)說(shuō)table數(shù)組的引用是volatile的Node的val和next也是volatile的。當(dāng)一個(gè)線程修改了某個(gè)節(jié)點(diǎn)的val其他線程讀這個(gè)節(jié)點(diǎn)時(shí)能立刻看到最新值。如果讀的過(guò)程中發(fā)生了擴(kuò)容讀線程可能讀到ForwardingNode這時(shí)候它會(huì)去新表里繼續(xù)找。這個(gè)設(shè)計(jì)保證了讀操作永遠(yuǎn)不會(huì)被阻塞也不會(huì)讀到中間狀態(tài)。這里有個(gè)容易混淆的點(diǎn)get不加鎖不代表get一定能讀到最新值。如果put操作還沒(méi)完成get可能讀到舊值。這是弱一致性的體現(xiàn)在大多數(shù)場(chǎng)景下是可以接受的。如果你需要強(qiáng)一致性那ConcurrentHashMap不適合你得用別的同步手段。4.3 size方法為什么返回的是估計(jì)值size()方法的實(shí)現(xiàn)經(jīng)歷了幾次演變。JDK7里用Segment的count累加JDK8改成了類似LongAdder的CounterCell數(shù)組機(jī)制。核心思路是維護(hù)一個(gè)baseCount再維護(hù)一個(gè)CounterCell數(shù)組。每次addCount時(shí)先嘗試CAS更新baseCount失敗就把計(jì)數(shù)分散到CounterCell數(shù)組的不同槽位上。這樣多個(gè)線程同時(shí)計(jì)數(shù)時(shí)沖突概率大大降低。size()就是把baseCount和所有CounterCell的值加起來(lái)。問(wèn)題在于這個(gè)累加過(guò)程不是原子的。你遍歷CounterCell數(shù)組的時(shí)候可能有線程正在修改某個(gè)槽位的值所以最終結(jié)果可能偏大也可能偏小。官方文檔明確說(shuō)了size()返回的是一個(gè)估計(jì)值不是精確值。如果你需要精確的size得自己加鎖但那樣就失去了ConcurrentHashMap的意義。實(shí)操心得我在項(xiàng)目里從來(lái)不用ConcurrentHashMap的size()做業(yè)務(wù)判斷。如果需要精確計(jì)數(shù)我會(huì)單獨(dú)用一個(gè)AtomicLong或者LongAdder來(lái)維護(hù)。ConcurrentHashMap的size()只適合做監(jiān)控指標(biāo)、日志輸出這類對(duì)精度要求不高的場(chǎng)景。4.4 擴(kuò)容機(jī)制的并發(fā)協(xié)作擴(kuò)容是ConcurrentHashMap里最復(fù)雜的部分。JDK8的擴(kuò)容支持多線程協(xié)助遷移這是它比JDK7先進(jìn)的地方。觸發(fā)擴(kuò)容后第一個(gè)線程會(huì)創(chuàng)建一個(gè)新表容量是舊表的兩倍。然后它把舊表的桶分成若干段每個(gè)線程負(fù)責(zé)遷移一段。遷移完成的桶會(huì)被替換成ForwardingNode里面保存了新表的引用。其他線程訪問(wèn)到這個(gè)桶時(shí)會(huì)調(diào)用helpTransfer()加入遷移工作。遷移的最小單位是一個(gè)桶但實(shí)際實(shí)現(xiàn)里會(huì)一次遷移多個(gè)桶具體數(shù)量取決于CPU核數(shù)和表的大小。遷移過(guò)程中舊表的桶被鎖住保證不會(huì)有新的寫入。這個(gè)設(shè)計(jì)讓擴(kuò)容不再是單線程的瓶頸并發(fā)度越高擴(kuò)容越快。這里有個(gè)參數(shù)值得注意擴(kuò)容閾值是容量乘以負(fù)載因子。默認(rèn)容量16負(fù)載因子0.75閾值就是12。當(dāng)元素?cái)?shù)量達(dá)到12時(shí)觸發(fā)擴(kuò)容新容量32新閾值24。這個(gè)計(jì)算很簡(jiǎn)單但很多人面試時(shí)說(shuō)不清楚。5. 實(shí)際使用中的坑與排查技巧5.1 復(fù)合操作不是原子的這是最常見的坑。ConcurrentHashMap的單個(gè)方法是線程安全的但多個(gè)方法組合起來(lái)就不是了。比如“先檢查再插入”這個(gè)經(jīng)典模式// 錯(cuò)誤示范復(fù)合操作不是原子的 if (!map.containsKey(key)) { map.put(key, value); }兩個(gè)線程可能同時(shí)通過(guò)containsKey檢查然后都執(zhí)行put導(dǎo)致后一個(gè)覆蓋前一個(gè)。正確的做法是用putIfAbsent、computeIfAbsent、compute這些原子復(fù)合方法。// 正確做法使用原子復(fù)合方法 map.putIfAbsent(key, value); // 或者 map.computeIfAbsent(key, k - createValue(k));computeIfAbsent特別有用它把“檢查-創(chuàng)建-插入”三步合成一個(gè)原子操作。但要注意computeIfAbsent的映射函數(shù)里不要做太耗時(shí)的操作因?yàn)樗鼤?huì)鎖住桶阻塞其他線程訪問(wèn)同一個(gè)桶。5.2 遍歷時(shí)的弱一致性ConcurrentHashMap的迭代器是弱一致的遍歷過(guò)程中其他線程的修改可能反映出來(lái)也可能不反映。它不會(huì)拋ConcurrentModificationException這是和HashMap的重要區(qū)別。這個(gè)特性意味著你不能依賴遍歷結(jié)果做精確判斷。比如你遍歷一遍統(tǒng)計(jì)元素個(gè)數(shù)結(jié)果可能和size()對(duì)不上。如果你需要一致性快照得自己復(fù)制一份或者加鎖。注意弱一致性迭代器不會(huì)拋異常但不代表遍歷過(guò)程中數(shù)據(jù)不會(huì)變。如果你在遍歷時(shí)做業(yè)務(wù)邏輯要考慮到數(shù)據(jù)可能已經(jīng)過(guò)期。5.3 常見問(wèn)題速查表問(wèn)題現(xiàn)象可能原因排查思路解決方案數(shù)據(jù)莫名丟失用了containsKeyput的復(fù)合操作檢查代碼里是否有先檢查后插入的邏輯改用putIfAbsent或computeIfAbsentsize()結(jié)果對(duì)不上弱一致性設(shè)計(jì)返回估計(jì)值確認(rèn)是否用size()做了精確判斷單獨(dú)維護(hù)計(jì)數(shù)器或接受估計(jì)值CPU飆高擴(kuò)容時(shí)大量線程協(xié)助遷移jstack看是否有transfer相關(guān)棧預(yù)估容量初始化時(shí)指定合理大小內(nèi)存占用大初始容量太小導(dǎo)致頻繁擴(kuò)容看GC日志里ConcurrentHashMap的擴(kuò)容記錄初始化時(shí)指定容量避免多次擴(kuò)容遍歷時(shí)數(shù)據(jù)不一致弱一致性迭代器確認(rèn)是否依賴遍歷結(jié)果做精確統(tǒng)計(jì)加鎖遍歷或復(fù)制快照5.4 初始化容量的計(jì)算技巧很多人初始化ConcurrentHashMap時(shí)隨便寫個(gè)new ConcurrentHashMap()默認(rèn)容量16。如果實(shí)際要存1000個(gè)元素就會(huì)經(jīng)歷多次擴(kuò)容每次擴(kuò)容都要遷移數(shù)據(jù)性能損耗不小。正確的做法是預(yù)估元素?cái)?shù)量然后反推初始容量。ConcurrentHashMap的構(gòu)造方法里有個(gè)tableSizeFor方法會(huì)把傳入的容量向上取到最近的2的冪。但要注意它還會(huì)根據(jù)負(fù)載因子調(diào)整。如果你想存n個(gè)元素初始容量應(yīng)該設(shè)為n / 0.75 1然后再向上取2的冪。比如要存1000個(gè)元素1000/0.75≈1334向上取2的冪是2048。所以new ConcurrentHashMap(2048)比默認(rèn)的16要高效得多。這個(gè)計(jì)算不復(fù)雜但能省下好幾次擴(kuò)容的開銷。6. 性能對(duì)比與選型建議6.1 和Hashtable、synchronizedMap的性能差距我做過(guò)一個(gè)簡(jiǎn)單的壓測(cè)100個(gè)線程并發(fā)讀寫讀多寫少9:1的場(chǎng)景下ConcurrentHashMap的吞吐量大約是Hashtable的8到10倍是synchronizedMap的6到8倍。寫多讀少1:9的場(chǎng)景下差距會(huì)縮小到3到5倍因?yàn)閷懖僮鬟€是要搶鎖但鎖粒度細(xì)的優(yōu)勢(shì)依然明顯。這個(gè)差距的來(lái)源就是鎖粒度。Hashtable和synchronizedMap是一把大鎖所有操作串行化。ConcurrentHashMap是桶級(jí)鎖不同桶的操作可以并行。并發(fā)度越高差距越明顯。6.2 什么時(shí)候不該用ConcurrentHashMapConcurrentHashMap不是萬(wàn)能的。以下幾種情況要慎重一是需要強(qiáng)一致性。如果你要求讀到的數(shù)據(jù)一定是最新的ConcurrentHashMap的弱一致性滿足不了得用加鎖的Map或者自己控制同步。二是需要排序。ConcurrentHashMap不保證順序如果需要按key排序用ConcurrentSkipListMap它是J.U.C里的有序并發(fā)容器。三是寫操作極其頻繁且集中在少數(shù)key上。如果所有線程都在寫同一個(gè)桶那桶級(jí)鎖就退化成了大鎖性能優(yōu)勢(shì)消失。這種場(chǎng)景要考慮是不是數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)有問(wèn)題。四是需要原子性的復(fù)合操作且computeIfAbsent搞不定。雖然computeIfAbsent能解決大部分問(wèn)題但有些復(fù)雜邏輯它覆蓋不了這時(shí)候可能得用鎖。6.3 和ConcurrentSkipListMap的選型對(duì)比ConcurrentSkipListMap是基于跳表實(shí)現(xiàn)的有序并發(fā)容器和ConcurrentHashMap是互補(bǔ)關(guān)系。選型主要看兩點(diǎn)要不要排序、對(duì)性能的要求。對(duì)比維度ConcurrentHashMapConcurrentSkipListMap底層結(jié)構(gòu)數(shù)組鏈表紅黑樹跳表是否有序否是按key排序平均時(shí)間復(fù)雜度O(1)O(log n)并發(fā)度桶級(jí)鎖更高跳表節(jié)點(diǎn)級(jí)稍低適用場(chǎng)景高頻讀寫、無(wú)需排序需要范圍查詢、有序遍歷如果你的場(chǎng)景需要按key范圍查詢比如“找出所有key在A到B之間的元素”ConcurrentSkipListMap是唯一選擇。如果只是普通的增刪改查ConcurrentHashMap性能更好。7. 幾個(gè)容易被忽略的細(xì)節(jié)7.1 spread方法的擾動(dòng)計(jì)算ConcurrentHashMap的spread方法比HashMap的hash方法多了一步static final int spread(int h) { return (h ^ (h 16)) 0x7fffffff; }h ^ (h 16)是擾動(dòng)函數(shù)把高16位和低16位異或讓高位也參與運(yùn)算減少碰撞。 0x7fffffff是把符號(hào)位抹掉保證結(jié)果非負(fù)。因?yàn)閿?shù)組下標(biāo)是(n - 1) hash如果hash是負(fù)數(shù)與運(yùn)算的結(jié)果可能還是負(fù)數(shù)會(huì)導(dǎo)致數(shù)組越界。這一步很多講ConcurrentHashMap的文章會(huì)忽略但它是保證正確性的關(guān)鍵。7.2 紅黑樹的轉(zhuǎn)換條件鏈表轉(zhuǎn)紅黑樹的條件是鏈表長(zhǎng)度≥8且數(shù)組容量≥64。如果數(shù)組容量小于64即使鏈表長(zhǎng)度到了8也優(yōu)先擴(kuò)容而不是樹化。為什么因?yàn)閿?shù)組小的時(shí)候碰撞概率高擴(kuò)容能更有效地分散元素比樹化的收益大。紅黑樹退化成鏈表的條件是節(jié)點(diǎn)數(shù)≤6。這個(gè)6和8之間的差值是為了避免在7附近反復(fù)轉(zhuǎn)換。如果閾值都是7一個(gè)元素頻繁增刪就會(huì)導(dǎo)致鏈表和樹之間來(lái)回切換性能反而下降。7.3 ForwardingNode的作用ForwardingNode是擴(kuò)容時(shí)的關(guān)鍵節(jié)點(diǎn)。它的hash值是MOVED-1當(dāng)讀線程遇到ForwardingNode時(shí)就知道這個(gè)桶已經(jīng)遷移了會(huì)去新表里繼續(xù)查找。當(dāng)寫線程遇到ForwardingNode時(shí)會(huì)調(diào)用helpTransfer()協(xié)助遷移。這個(gè)設(shè)計(jì)讓擴(kuò)容和讀寫可以并行進(jìn)行不會(huì)因?yàn)閿U(kuò)容而阻塞整個(gè)Map。這是ConcurrentHashMap比Hashtable高明的地方也是它能在高并發(fā)下保持低延遲的原因。7.4 批量操作的并發(fā)控制ConcurrentHashMap提供了putAll、clear等批量方法這些方法在并發(fā)場(chǎng)景下要小心使用。putAll不是原子的遍歷過(guò)程中其他線程可能插入數(shù)據(jù)。clear也不是原子的清空過(guò)程中可能有新數(shù)據(jù)進(jìn)來(lái)。如果需要在并發(fā)環(huán)境下做批量操作建議自己加鎖或者用compute系列方法逐個(gè)處理。不要指望putAll能保證原子性它只是循環(huán)調(diào)用put而已。8. 從源碼里學(xué)到的設(shè)計(jì)思想8.1 用狀態(tài)字段表達(dá)多種含義sizeCtl這個(gè)字段的設(shè)計(jì)很值得學(xué)習(xí)。一個(gè)int字段正數(shù)表示擴(kuò)容閾值-1表示正在初始化-(1n)表示有n個(gè)線程在協(xié)助擴(kuò)容。這種“一個(gè)字段多種用途”的設(shè)計(jì)在并發(fā)編程里很常見目的是減少字段數(shù)量降低內(nèi)存占用同時(shí)保證狀態(tài)轉(zhuǎn)換的原子性。但這樣做的代價(jià)是代碼可讀性下降。你看源碼的時(shí)候得時(shí)刻記住sizeCtl當(dāng)前可能是什么狀態(tài)不然很容易看暈。這是典型的“性能換可讀性”的取舍。8.2 CAS加自旋替代阻塞ConcurrentHashMap里大量使用了CAS加自旋的模式。比如initTable、addCount、transfer里的很多操作都是先CAS嘗試失敗就自旋重試。這種模式在競(jìng)爭(zhēng)不激烈的時(shí)候性能很好因?yàn)楸苊饬司€程上下文切換的開銷。但自旋也有代價(jià)如果競(jìng)爭(zhēng)激烈大量線程空轉(zhuǎn)會(huì)浪費(fèi)CPU。所以ConcurrentHashMap在自旋到一定次數(shù)后會(huì)退化成阻塞等待。這個(gè)“自適應(yīng)”的策略在J.U.C里很常見AQS里也有類似的設(shè)計(jì)。8.3 分散熱點(diǎn)減少競(jìng)爭(zhēng)CounterCell數(shù)組是分散熱點(diǎn)的經(jīng)典案例。如果所有線程都去CAS同一個(gè)baseCount競(jìng)爭(zhēng)會(huì)非常激烈。把計(jì)數(shù)分散到多個(gè)Cell上每個(gè)線程操作不同的Cell競(jìng)爭(zhēng)就分散了。這個(gè)思想和LongAdder一模一樣本質(zhì)上是用空間換并發(fā)度。類似的思路在ConcurrentHashMap里還有很多比如擴(kuò)容時(shí)把遷移任務(wù)分段讓多個(gè)線程各負(fù)責(zé)一段。這種“分而治之”的策略是并發(fā)編程里的通用套路。9. 實(shí)際項(xiàng)目中的使用建議9.1 緩存場(chǎng)景的正確用法ConcurrentHashMap最常見的用途是做本地緩存。用的時(shí)候有幾個(gè)建議一是設(shè)置合理的初始容量避免頻繁擴(kuò)容。二是用computeIfAbsent做緩存加載保證只有一個(gè)線程去加載數(shù)據(jù)。三是注意緩存過(guò)期ConcurrentHashMap本身不支持過(guò)期得自己維護(hù)時(shí)間戳或者用定時(shí)任務(wù)清理。四是控制緩存大小無(wú)限增長(zhǎng)的緩存遲早會(huì)OOM可以配合LRU或者定期清理。// 本地緩存的典型用法 ConcurrentHashMapString, CacheEntry cache new ConcurrentHashMap(1024); public Object get(String key) { return cache.computeIfAbsent(key, k - loadFromDb(k)).value; }9.2 計(jì)數(shù)器場(chǎng)景的替代方案如果只是做計(jì)數(shù)器ConcurrentHashMap不是最優(yōu)選擇。LongAdder的性能比ConcurrentHashMap的merge方法好得多因?yàn)長(zhǎng)ongAdder專門為計(jì)數(shù)優(yōu)化沒(méi)有Map的哈希和桶定位開銷。只有在需要按key分組計(jì)數(shù)時(shí)才用ConcurrentHashMap。9.3 并發(fā)度預(yù)估與容量規(guī)劃初始化ConcurrentHashMap時(shí)容量規(guī)劃要考慮兩個(gè)因素預(yù)期元素?cái)?shù)量和并發(fā)寫入的key分布。如果key分布均勻桶級(jí)鎖的并發(fā)度就高如果key集中在少數(shù)幾個(gè)并發(fā)度就低。可以通過(guò)調(diào)整hash策略或者加鹽來(lái)分散key。容量方面前面說(shuō)過(guò)初始容量設(shè)為預(yù)期元素?cái)?shù) / 0.75 1再向上取2的冪。如果預(yù)期元素?cái)?shù)會(huì)持續(xù)增長(zhǎng)可以適當(dāng)放大減少擴(kuò)容次數(shù)。但也不要設(shè)太大浪費(fèi)內(nèi)存。9.4 監(jiān)控與問(wèn)題定位線上環(huán)境如果懷疑ConcurrentHashMap有問(wèn)題可以從幾個(gè)方面入手jstack看線程棧如果有大量線程卡在transfer或helpTransfer說(shuō)明擴(kuò)容壓力大jmap看堆內(nèi)存如果ConcurrentHashMap占用異常可能是容量設(shè)得太大或者有內(nèi)存泄漏GC日志看擴(kuò)容頻率頻繁擴(kuò)容說(shuō)明初始容量太小。我個(gè)人的經(jīng)驗(yàn)是ConcurrentHashMap本身很少出問(wèn)題出問(wèn)題的大多是使用方式不對(duì)。比如復(fù)合操作沒(méi)加原子保護(hù)、size()當(dāng)精確值用、緩存沒(méi)設(shè)上限。把這幾類問(wèn)題規(guī)避掉ConcurrentHashMap用起來(lái)還是很省心的。最后分享一個(gè)我踩過(guò)的坑有一次做本地緩存用computeIfAbsent加載數(shù)據(jù)加載函數(shù)里又調(diào)用了同一個(gè)Map的computeIfAbsent結(jié)果死鎖了。原因是computeIfAbsent會(huì)鎖住桶遞歸調(diào)用同一個(gè)桶就死鎖了。這個(gè)坑很隱蔽因?yàn)閱尉€程測(cè)試不會(huì)復(fù)現(xiàn)只有并發(fā)場(chǎng)景才會(huì)暴露。后來(lái)我把加載邏輯改成先查再加載用雙重檢查加鎖的方式解決。所以用computeIfAbsent的時(shí)候映射函數(shù)里千萬(wàn)不要再操作同一個(gè)Map。