1. 為什么ConcurrentHashMap是J.U.C里最值得啃的容器聊到Java多線程繞不開J.U.C這個(gè)包而J.U.C里面真正在生產(chǎn)環(huán)境里天天被用的并發(fā)容器ConcurrentHashMap說第二沒人敢說第一。很多同學(xué)背八股文的時(shí)候能把“分段鎖”“CASsynchronized”“紅黑樹”這些詞說得滾瓜爛熟但真到了項(xiàng)目里讓他解釋為什么HashMap在多線程下會(huì)死循環(huán)、為什么ConcurrentHashMap的size()方法返回的只是一個(gè)估計(jì)值、為什么JDK8之后放棄了Segment分段鎖往往就卡殼了。這篇內(nèi)容就是沖著這些卡殼的地方來的。我會(huì)把ConcurrentHashMap從設(shè)計(jì)動(dòng)機(jī)、底層結(jié)構(gòu)、核心方法實(shí)現(xiàn)、擴(kuò)容機(jī)制到實(shí)際使用中的坑一層一層拆開講。適合已經(jīng)會(huì)寫Java、用過HashMap、但對(duì)并發(fā)場(chǎng)景下容器行為心里沒底的同學(xué)也適合正在準(zhǔn)備面試、想把J.U.C這塊知識(shí)從“背答案”升級(jí)成“真理解”的開發(fā)者。讀完你至少能搞清楚三件事ConcurrentHashMap到底怎么保證線程安全、它的性能優(yōu)勢(shì)從哪來、以及在實(shí)際項(xiàng)目里怎么用才不出問題。需要先說明一點(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ì)算過程方便你自己推導(dǎo)而不是死記。2. 從HashMap的線程安全問題說起2.1 HashMap在多線程下到底會(huì)出什么事很多人知道“HashMap線程不安全”但具體怎么個(gè)不安全法說不清楚。我把它歸納成三類典型問題每一類都對(duì)應(yīng)著真實(shí)的故障場(chǎng)景。第一類是數(shù)據(jù)覆蓋。HashMap的put操作在JDK8里是這么個(gè)邏輯算出桶下標(biāo)如果桶是空的直接把新節(jié)點(diǎn)放進(jìn)去。問題就出在“如果桶是空的”這個(gè)判斷上。兩個(gè)線程同時(shí)判斷某個(gè)桶為空然后同時(shí)往里放節(jié)點(diǎn)后放的那個(gè)就會(huì)把先放的覆蓋掉導(dǎo)致一個(gè)線程的數(shù)據(jù)憑空消失。這種問題在并發(fā)量不高的時(shí)候很難復(fù)現(xiàn)一旦復(fù)現(xiàn)就是偶發(fā)的數(shù)據(jù)丟失排查起來極其痛苦。第二類是擴(kuò)容時(shí)的死循環(huán)。這個(gè)問題在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ì)無限循環(huán)CPU直接飆到100%。我早年排查過一個(gè)線上問題一個(gè)服務(wù)跑著跑著CPU打滿jstack一看全卡在HashMap.get上最后定位就是多線程共享了一個(gè)HashMap。第三類是size計(jì)數(shù)不準(zhǔn)。HashMap的size字段就是個(gè)普通int多線程并發(fā)修改時(shí)自增自減不是原子操作最終結(jié)果肯定對(duì)不上。注意不要覺得“我只是讀多寫少”就可以用HashMap。只要有一個(gè)寫操作和其他讀寫操作并發(fā)就可能出問題。讀操作本身在HashMap里也不是完全安全的因?yàn)閿U(kuò)容過程中讀到的可能是舊表也可能是新表。2.2 為什么不用Collections.synchronizedMap既然HashMap不安全那用Collections.synchronizedMap包一層行不行行但性能很難看。它的做法是給整個(gè)Map對(duì)象加一把大鎖所有讀寫操作都要先搶這把鎖。這意味著同一時(shí)刻只能有一個(gè)線程操作Map并發(fā)能力直接退化成單線程。你開100個(gè)線程實(shí)際干活的是一個(gè)一個(gè)排隊(duì)來吞吐量上不去。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)度超過閾值就轉(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è)問題。一是內(nèi)存開銷大。每個(gè)Segment本身就是一個(gè)ReentrantLock還要維護(hù)自己的HashEntry數(shù)組段數(shù)一多內(nèi)存占用就上去了。二是鎖粒度還是偏粗。Segment的數(shù)量在初始化時(shí)就固定了并發(fā)度上限就是段數(shù)沒法動(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ì)說。4. 核心方法的實(shí)現(xiàn)原理與實(shí)操分析4.1 put方法的完整流程put方法是理解ConcurrentHashMap的鑰匙我把它拆成幾個(gè)階段來講。第一個(gè)階段是計(jì)算hash并定位桶。如果table還沒初始化先調(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)重試。這是最理想的情況全程無鎖。第三個(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閾值超過就觸發(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你沒法區(qū)分是“這個(gè)key不存在”還是“這個(gè)key對(duì)應(yīng)的value是null”這在并發(fā)編程里會(huì)造成歧義。4.2 get方法為什么可以不加鎖get方法的邏輯很簡(jiǎn)單算hash定位桶如果桶頭節(jié)點(diǎn)匹配就返回否則遍歷鏈表或紅黑樹。整個(gè)過程沒有任何加鎖操作靠的是volatile的可見性保證。具體來說table數(shù)組的引用是volatile的Node的val和next也是volatile的。當(dāng)一個(gè)線程修改了某個(gè)節(jié)點(diǎn)的val其他線程讀這個(gè)節(jié)點(diǎn)時(shí)能立刻看到最新值。如果讀的過程中發(fā)生了擴(kuò)容讀線程可能讀到ForwardingNode這時(shí)候它會(huì)去新表里繼續(xù)找。這個(gè)設(shè)計(jì)保證了讀操作永遠(yuǎn)不會(huì)被阻塞也不會(huì)讀到中間狀態(tài)。這里有個(gè)容易混淆的點(diǎn)get不加鎖不代表get一定能讀到最新值。如果put操作還沒完成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的值加起來。問題在于這個(gè)累加過程不是原子的。你遍歷CounterCell數(shù)組的時(shí)候可能有線程正在修改某個(gè)槽位的值所以最終結(jié)果可能偏大也可能偏小。官方文檔明確說了size()返回的是一個(gè)估計(jì)值不是精確值。如果你需要精確的size得自己加鎖但那樣就失去了ConcurrentHashMap的意義。實(shí)操心得我在項(xiàng)目里從來不用ConcurrentHashMap的size()做業(yè)務(wù)判斷。如果需要精確計(jì)數(shù)我會(huì)單獨(dú)用一個(gè)AtomicLong或者LongAdder來維護(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里面保存了新表的引用。其他線程訪問到這個(gè)桶時(shí)會(huì)調(diào)用helpTransfer()加入遷移工作。遷移的最小單位是一個(gè)桶但實(shí)際實(shí)現(xiàn)里會(huì)一次遷移多個(gè)桶具體數(shù)量取決于CPU核數(shù)和表的大小。遷移過程中舊表的桶被鎖住保證不會(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í)說不清楚。5. 實(shí)際使用中的坑與排查技巧5.1 復(fù)合操作不是原子的這是最常見的坑。ConcurrentHashMap的單個(gè)方法是線程安全的但多個(gè)方法組合起來就不是了。比如“先檢查再插入”這個(gè)經(jīng)典模式// 錯(cuò)誤示范復(fù)合操作不是原子的 if (!map.containsKey(key)) { map.put(key, value); }兩個(gè)線程可能同時(shí)通過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ì)鎖住桶阻塞其他線程訪問同一個(gè)桶。5.2 遍歷時(shí)的弱一致性ConcurrentHashMap的迭代器是弱一致的遍歷過程中其他線程的修改可能反映出來也可能不反映。它不會(huì)拋ConcurrentModificationException這是和HashMap的重要區(qū)別。這個(gè)特性意味著你不能依賴遍歷結(jié)果做精確判斷。比如你遍歷一遍統(tǒng)計(jì)元素個(gè)數(shù)結(jié)果可能和size()對(duì)不上。如果你需要一致性快照得自己復(fù)制一份或者加鎖。注意弱一致性迭代器不會(huì)拋異常但不代表遍歷過程中數(shù)據(jù)不會(huì)變。如果你在遍歷時(shí)做業(yè)務(wù)邏輯要考慮到數(shù)據(jù)可能已經(jīng)過期。5.3 常見問題速查表問題現(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的性能差距我做過一個(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è)差距的來源就是鎖粒度。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ì)有問題。四是需要原子性的復(fù)合操作且computeIfAbsent搞不定。雖然computeIfAbsent能解決大部分問題但有些復(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)景高頻讀寫、無需排序需要范圍查詢、有序遍歷如果你的場(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)致鏈表和樹之間來回切換性能反而下降。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不是原子的遍歷過程中其他線程可能插入數(shù)據(jù)。clear也不是原子的清空過程中可能有新數(shù)據(jù)進(jìn)來。如果需要在并發(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ù)。三是注意緩存過期ConcurrentHashMap本身不支持過期得自己維護(hù)時(shí)間戳或者用定時(shí)任務(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)化沒有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ā)度就低?？梢酝ㄟ^調(diào)整hash策略或者加鹽來分散key。容量方面前面說過初始容量設(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)控與問題定位線上環(huán)境如果懷疑ConcurrentHashMap有問題可以從幾個(gè)方面入手jstack看線程棧如果有大量線程卡在transfer或helpTransfer說明擴(kuò)容壓力大jmap看堆內(nèi)存如果ConcurrentHashMap占用異?？赡苁侨萘吭O(shè)得太大或者有內(nèi)存泄漏GC日志看擴(kuò)容頻率頻繁擴(kuò)容說明初始容量太小。我個(gè)人的經(jīng)驗(yàn)是ConcurrentHashMap本身很少出問題出問題的大多是使用方式不對(duì)。比如復(fù)合操作沒加原子保護(hù)、size()當(dāng)精確值用、緩存沒設(shè)上限。把這幾類問題規(guī)避掉ConcurrentHashMap用起來還是很省心的。最后分享一個(gè)我踩過的坑有一次做本地緩存用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ì)暴露。后來我把加載邏輯改成先查再加載用雙重檢查加鎖的方式解決。所以用computeIfAbsent的時(shí)候映射函數(shù)里千萬(wàn)不要再操作同一個(gè)Map。