面試必問的JDK 8 ConcurrentHashMap實現原理：數據結構、get操作與put操作

職位：Java軟件工程師

這是本人的署名原創文章，未經許可不支持轉載，請勿抄襲。本公眾號的所有文章均為本人原創。為了更容易理解和記憶，今後所有文章將以圖解為主、代碼為輔，忽略不太重要的細節，但是保留關鍵性的技術細節。如果您感興趣，歡迎關注！

ConcurrentHashMap相信大家都已經知道怎麼使用，並且它的源碼可以算是JDK 併發包中最長最複雜的了。雖然目前網絡上已經有很多分析ConcurrentHashMap實現原理的文章，但大多數都是貼代碼，看起來很費勁，也沒有把實現原理真正講清楚。本文將深度解析ConcurrentHashMap實現原理，讓人一看就明白。請注意，本文分析的是JDK 8中的ConcurrentHashMap。不要相信那些一文就懂JDK 1.7 和JDK 1.8的文章，因為細節很豐富，一篇文章怎麼能覆蓋？就算這樣的文章寫出來了，也是篇幅超長，難以學會。

說明：下文所述的bin、槽位、位置等詞語均指代ConcurrentHashMap中的最外層的table數組中的某個元素。

ConcurrentHashMap內部數據結構：基本形態

當hash值衝突較少且當前沒有resize操作的時候，ConcurrentHashMap的內部數據結構跟HashMap非常接近，是一個拉鍊表，即binned(bucketed) hash table。這個拉鍊表的最外層是一個數組（長度必須是2的n次冪），每個數組元素保存一個單鏈表的表頭。

注意，上圖所示拉鍊表結構是最簡單的情況。為了保證線程安全性，對這個結構的讀寫操作都需要使用volatile、atomic或CAS操作。向這個table的每個空bin（bin指的是數組中的每個元素）插入第一個Node是用CAS操作完成，其次，每個bin中的第一個Node結點作為一個synchronized鎖，保護後面的insert, update, remove操作的線程安全性。可見，如果key-value mapping的hash值都被映射到同一個bin，則插入、刪除、修改操作都需要加鎖，而且這個鎖是每個bin鏈表中的頭結點，且使用的是synchronize鎖。

說到這裡，不得不糾正某些人的錯誤觀點。有一些人反對使用ConcurrentHashMap（包括我公司裡的某些人），而且自認為他們瞭解ConcurrentHashMap。因為上面提到的這個特徵，他們就片面認為"向ConcurrentHashMap插入數據有鎖操作，所以會影響性能"，這是隻知其一、不知其二。實際上，如果key的hash函數的隨機化程度足夠，鎖的問題其實並不大。因為根據JDK官方的統計，hash表中每個bin的結點個數近似服從泊松分佈（Poisson distribution），即鏈表長度的概率大概是

兩個線程競爭ConcurrentHashMap中同一個鎖的概率是1/8n（n是數組長度，初值等於16）。所以，一開始的競爭概率約0.78%。如果擴容以後，這個概率將會更小。這樣小的概率，就害怕到不敢使用嗎？除非故意設計成讓hash值衝突。

假如hash值真的衝突了，現在JDK8也有應對策略，即下文所介紹內容。

ConcurrentHashMap內部數據結構：紅黑樹形態

當拉鍊表數組（table）中的某個bin元素個數太多、鏈表長度太長之後（前面說過了，這種情況的發生概率只有0.78%），並且hash表的Key實現了Comparable接口，原來的單鏈表結構被轉換成紅黑樹，如下圖所示：

需要注意，並非當bin中鏈表長度足夠長就馬上轉換成紅黑樹，還需要等table數組的長度也到達某個閾值才會轉換成樹。如果某個bin的長度太長，但是table數組長度較短，則只會先觸發resize擴容。另外，順便說一下，JDK 8的HashMap針對bin中的單鏈表過長的問題，也是將它轉換為紅黑樹來處理的。

ConcurrentHashMap內部數據結構：轉移節點形態

當有resize操作在進行中的時候，已經轉移到新數組的bin原來的位置被放進一個ForwardingNode結點。這保證了有resize操作正在進行中的時候，不會阻塞對ConcurrentHashMap的讀操作。例如，如果有一個調用get操作的線程，它的key的hash碼映射到了一個ForwardingNode，那麼它會從這個ForwadingNode結點中的nextTable字段找到新數組的引用，然後再找到新數組nextTable的對應bin。

另外，數組table除了可以存放Node, TreeBin和ForwadingNode之外，還可以存放一種特殊類型的結點ReservationNode，它主要是用來幫助實現Java 8的新增API ConcurrentHashMap.comptuteIfAbsent的，不影響我們分析ConcurrentHashMap的主體實現，今後將會撰文解析。

ConcurrentHashMap的get操作

你可能以為get操作需要實現線程安全性，所以它的實現會很複雜吧？其實，JDK 8中的ConcurrentHashMap的get操作非常簡單。相關變量都加上了volatile修飾，所以get操作自身幾乎無需考慮線程安全性和變量可見性，只需要注意原子性。這裡的原子性指的是，get操作中的被多個線程共享的table變量及節點屬性等可能也在被其他線程修改，所以需要一開始就把它們保存到局部變量，然後再使用，這樣就不必擔心有其他線程修改了。get操作的主體邏輯用偽代碼說明如下（個人認為比流程圖或直接貼代碼清晰）：

解釋一下，"簡單處理"指的是對key的原始hashCode進行一些簡單的位變換（解決hashCode高比特位沒有使用的問題），"h & (n – 1)"中的n是table的長度，因為n一定是2的冪，那麼n-1剛好是掩碼，用來與h進行位運算後剛好是table的下標。table[idx]的hash值小於0表示這個節點不是單鏈表（Node），而是其他類型的節點，比如ForwadingNode（需要到新table中繼續查找）、TreeBin（用紅黑樹算法搜索）或ReservationNode（直接返回null）。

ConcurrentHashMap的put操作

put操作既需要到ConcurrentHashMap中查詢有沒有對應的key，還需要寫入key-value，並且保證多線程寫入的線程安全性，並且還會參與到可能正在進行中的resize操作。那麼如何實現呢？我們用偽代碼描述如下（如果需要了解非常細節的地方，還需查看源碼，若只想明白原理，看偽代碼足矣）：

理解上述put操作過程要注意，只有在執行到break之後才會跳出循環，沒有遇到break則會重試。JDK代碼的重試功能幾乎全部是用死循環來實現的。

從以上執行過程可以看出，put操作的線程安全性是利用"分類討論"方法保證的。或者說，分情況處理，即只有在需要的時候才加鎖、不需要的時候不加鎖，而JDK 7則是每次在一個segment中寫入都要加鎖。分成的情況：

1. 如果位置上是空的（null），那麼用cas操作來保證線程安全性。
2. 如果這個位置是ForwardingNode，則執行一部分transfer工作，然後在新table中重試。
3. 如果這個位置是單鏈表或紅黑樹，那麼才進行加鎖。

這裡之所以用synchronized鎖，而不用ReentrantLock是因為JVM對於synchronized有許多優化，在沒有競爭的時候，synchronized性能優於ReentrantLock顯式鎖（例如鎖消除、偏向鎖、自旋等優化措施）。關於ConcurrentHashMap的分析尚未全部覆蓋，其擴容、計數器優化、遍歷優化等內容且看下回分解。如果您感興趣，歡迎關注。