Java Map 中那些巧妙的設計

最近拜讀了一些Java Map的相關原始碼，不得不驚歎於JDK開發者們的鬼斧神工。他山之石可以攻玉，這些巧妙的設計思想非常有借鑑價值，可謂是最佳實踐。然而，大多數有關Java Map原理的科普類文章都是專注於“點”，並沒有連成“線”，甚至形成“網狀結構”。因此，本文基於個人理解，對所閱讀的部分原始碼進行了分類與總結，歸納出Map中的幾個核心特性，包括：自動擴容、初始化與懶載入、雜湊計算、位運算與併發，並結合原始碼進行深入講解，希望看完本文的你也能從中獲取到些許收穫（本文預設採用JDK1。8中的HashMap）。

一 自動擴容

最小可用原則，容量超過一定閾值便自動進行擴容。

擴容是透過resize方法來實現的。擴容發生在putVal方法的最後，即寫入元素之後才會判斷是否需要擴容操作，當自增後的size大於之前所計算好的閾值threshold，即執行resize操作。

透過位運算1進行容量擴充，即擴容1倍，同時新的閾值newThr也擴容為老閾值的1倍。

擴容時，總共存在三種情況：

雜湊桶陣列中某個位置只有1個元素，即不存在雜湊衝突時，則直接將該元素copy至新雜湊桶陣列的對應位置即可。

雜湊桶陣列中某個位置的節點為樹節點時，則執行紅黑樹的擴容操作。

雜湊桶陣列中某個位置的節點為普通節點時，則執行連結串列擴容操作，在JDK1。8中，為了避免之前版本中併發擴容所導致的死鏈問題，引入了高低位連結串列輔助進行擴容操作。

在日常的開發過程中，會遇到一些bad case，比如：

HashMap hashMap = new HashMap（2）；hashMap。put（“1”， 1）；hashMap。put（“2”， 2）；hashMap。put（“3”， 3）；

當hashMap設定最後一個元素3的時候，會發現當前的雜湊桶陣列大小已經達到擴容閾值2*0。75=1。5，緊接著會執行一次擴容操作，因此，此類的程式碼每次執行的時候都會進行一次擴容操作，效率低下。在日常開發過程中，一定要充分評估好HashMap的大小，儘可能保證擴容的閾值大於儲存元素的數量，減少其擴容次數。

二 初始化與懶載入

初始化的時候只會設定預設的負載因子，並不會進行其他初始化的操作，在首次使用的時候才會進行初始化。

當new一個新的HashMap的時候，不會立即對雜湊陣列進行初始化，而是在首次put元素的時候，透過resize（）方法進行初始化。

resize（）中會設定預設的初始化容量DEFAULT_INITIAL_CAPACITY為16，擴容的閾值為0。75*16 = 12，即雜湊桶陣列中元素達到12個便進行擴容操作。

最後建立容量為16的Node陣列，並賦值給成員變數雜湊桶table，即完成了HashMap的初始化操作。

三 雜湊計算

雜湊表以雜湊命名，足以說明雜湊計算在該資料結構中的重要程度。而在實現中，JDK並沒有直接使用Object的native方法返回的hashCode作為最終的雜湊值，而是進行了二次加工。

以下分別為HashMap與ConcurrentHashMap計算hash值的方法，核心的計算邏輯相同，都是使用key對應的hashCode與其hashCode右移16位的結果進行異或操作。此處，將高16位與低16位進行異或的操作稱之為擾動函式，目的是將高位的特徵融入到低位之中，降低雜湊衝突的機率。

舉個例子來理解下擾動函式的作用：

hashCode（key1） = 0000 0000 0000 1111 0000 0000 0000 0010hashCode（key2） = 0000 0000 0000 0000 0000 0000 0000 0010

若HashMap容量為4，在不使用擾動函式的情況下，key1與key2的hashCode註定會衝突（後兩位相同，均為01）。

經過擾動函式處理後，可見key1與key2 hashcode的後兩位不同，上述的雜湊衝突也就避免了。

hashCode（key1） ^ （hashCode（key1）16）0000 0000 0000 1111 0000 0000 0000 1101hashCode（key2） ^ （hashCode（key2）16）0000 0000 0000 0000 0000 0000 0000 0010

這種增益會隨著HashMap容量的減少而增加。《An introduction to optimising a hashing strategy》文章中隨機選取了雜湊值不同的352個字串，當HashMap的容量為2^9時，使用擾動函式可以減少10%的碰撞，可見擾動函式的必要性。

此外，ConcurrentHashMap中經過擾亂函式處理之後，需要與HASH_BITS做與運算，HASH_BITS為0x7ffffff，即只有最高位為0，這樣運算的結果使hashCode永遠為正數。在ConcurrentHashMap中，預定義了幾個特殊節點的hashCode，如：MOVED、TREEBIN、RESERVED，它們的hashCode均定義為負值。因此，將普通節點的hashCode限定為正數，也就是為了防止與這些特殊節點的hashCode產生衝突。

1 雜湊衝突

透過雜湊運算，可以將不同的輸入值對映到指定的區間範圍內，隨之而來的是雜湊衝突問題。考慮一個極端的case，假設所有的輸入元素經過雜湊運算之後，都對映到同一個雜湊桶中，那麼查詢的複雜度將不再是O（1），而是O（n），相當於線性表的順序遍歷。因此，雜湊衝突是影響雜湊計算效能的重要因素之一。雜湊衝突如何解決呢？主要從兩個方面考慮，一方面是避免衝突，另一方面是在衝突時合理地解決衝突，儘可能提高查詢效率。前者在上面的章節中已經進行介紹，即透過擾動函式來增加hashCode的隨機性，避免衝突。針對後者，HashMap中給出了兩種方案：拉鍊表與紅黑樹。

拉鍊表

在JDK1。8之前，HashMap中是採用拉鍊表的方法來解決衝突，即當計算出的hashCode對應的桶上已經存在元素，但兩者key不同時，會基於桶中已存在的元素拉出一條連結串列，將新元素鏈到已存在元素的前面。當查詢存在衝突的雜湊桶時，會順序遍歷衝突鏈上的元素。同一key的判斷邏輯如下圖所示，先判斷hash值是否相同，再比較key的地址或值是否相同。

（1）死鏈

在JDK1。8之前，HashMap在併發場景下擴容時存在一個bug，形成死鏈，導致get該位置元素的時候，會死迴圈，使CPU利用率高居不下。這也說明了HashMap不適於用在高併發的場景，高併發應該優先考慮JUC中的ConcurrentHashMap。然而，精益求精的JDK開發者們並沒有選擇繞過問題，而是選擇直面問題並解決它。在JDK1。8之中，引入了高低位連結串列（雙端連結串列）。

什麼是高低位連結串列呢？在擴容時，雜湊桶陣列buckets會擴容一倍，以容量為8的HashMap為例，原有容量8擴容至16，將［0， 7］稱為低位，［8， 15］稱為高位，低位對應loHead、loTail，高位對應hiHead、hiTail。

擴容時會依次遍歷舊buckets陣列的每一個位置上面的元素：

若不存在衝突，則重新進行hash取模，並copy到新buckets陣列中的對應位置。

若存在衝突元素，則採用高低位連結串列進行處理。透過e。hasholdCap來判斷取模後是落在高位還是低位。舉個例子：假設當前元素hashCode為0001（忽略高位），其運算結果等於0，說明擴容後結果不變，取模後還是落在低位［0， 7］，即00011000 = 0000，還是原位置，再用低位連結串列將這類的元素連結起來。假設當前元素的hashCode為1001， 其運算結果不為0，即10011000 = 1000 ，擴容後會落在高位，新的位置剛好是舊陣列索引（1） + 舊資料長度（8） = 9，再用高位連結串列將這些元素連結起來。最後，將高低位連結串列的頭節點分別放在擴容後陣列newTab的指定位置上，即完成了擴容操作。這種實現降低了對共享資源newTab的訪問頻次，先組織衝突節點，最後再放入newTab的指定位置。避免了JDK1。8之前每遍歷一個元素就放入newTab中，從而導致併發擴容下的死鏈問題。

紅黑樹

在JDK1。8之中，HashMap引入了紅黑樹來處理雜湊衝突問題，而不再是拉鍊表。那麼為什麼要引入紅黑樹來替代連結串列呢？雖然連結串列的插入效能是O（1），但查詢效能確是O（n），當雜湊衝突元素非常多時，這種查詢效能是難以接受的。因此，在JDK1。8中，如果衝突鏈上的元素數量大於8，並且雜湊桶陣列的長度大於64時，會使用紅黑樹代替連結串列來解決雜湊衝突，此時的節點會被封裝成TreeNode而不再是Node（TreeNode其實繼承了Node，以利用多型特性），使查詢具備O（logn）的效能。

這裡簡單地回顧一下紅黑樹，它是一種平衡的二叉樹搜尋樹，類似地還有AVL樹。兩者核心的區別是AVL樹追求“絕對平衡”，在插入、刪除節點時，成本要高於紅黑樹，但也因此擁有了更好的查詢效能，適用於讀多寫少的場景。然而，對於HashMap而言，讀寫操作其實難分伯仲，因此選擇紅黑樹也算是在讀寫效能上的一種折中。

四 位運算

1 確定雜湊桶陣列大小

找到大於等於給定值的最小2的整數次冪。

tableSizeFor根據輸入容量大小cap來計算最終雜湊桶陣列的容量大小，找到大於等於給定值cap的最小2的整數次冪。乍眼一看，這一行一行的位運算讓人云裡霧裡，莫不如採用類似找規律的方式來探索其中的奧秘。

當cap為3時，計算過程如下：

cap = 3n = 2n |= n1 010 | 001 = 011 n = 3n |= n2 011 | 000 = 011 n = 3n |= n4 011 | 000 = 011 n = 3…。n = n + 1 = 4

當cap為5時，計算過程如下：

cap = 5n = 4n |= n1 0100 | 0010 = 0110 n = 6n |= n2 0110 | 0001 = 0111 n = 7…。n = n + 1 = 8

因此，計算的意義在於找到大於等於cap的最小2的整數次冪。整個過程是找到cap對應二進位制中最高位的1，然後每次以2倍的步長（依次移位1、2、4、8、16）複製最高位1到後面的所有低位，把最高位1後面的所有位全部置為1，最後進行+1，即完成了進位。

類似二進位制位的變化過程如下：

0100 10100111 11111000 0000

找到輸入cap的最小2的整數次冪作為最終容量可以理解為最小可用原則，儘可能地少佔用空間，但是為什麼必須要2的整數次冪呢？答案是，為了提高計算與儲存效率，使每個元素對應hash值能夠準確落入雜湊桶陣列給定的範圍區間內。確定陣列下標採用的演算法是 hash（n - 1），n即為雜湊桶陣列的大小。由於其總是2的整數次冪，這意味著n-1的二進位制形式永遠都是0000111111的形式，即從最低位開始，連續出現多個1，該二進位制與任何值進行運算都會使該值對映到指定區間［0， n-1］。比如：當n=8時，n-1對應的二進位制為0111，任何與0111進行運算都會落入［0，7］的範圍內，即落入給定的8個雜湊桶中，儲存空間利用率100%。舉個反例，當n=7，n-1對應的二進位制為0110，任何與0110進行運算會落入到第0、6、4、2個雜湊桶，而不是［0，6］的區間範圍內，少了1、3、5三個雜湊桶，這導致儲存空間利用率只有不到60%，同時也增加了雜湊碰撞的機率。

2 ASHIFT偏移量計算

獲取給定值的最高有效位數（移位除了能夠進行乘除運算，還能用於保留高、低位操作，右移保留高位，左移保留低位）。

ConcurrentHashMap中的ABASE+ASHIFT是用來計算雜湊陣列中某個元素在實際記憶體中的初始位置，ASHIFT採取的計算方式是31與scale前導0的數量做差，也就是scale的實際位數-1。scale就是雜湊桶陣列Node［］中每個元素的大小，透過（（long）iASHIFT） + ABASE）進行計算，便可得到陣列中第i個元素的起始記憶體地址。

我們繼續看下前導0的數量是怎麼計算出來的，numberOfLeadingZeros是Integer的靜態方法，還是沿用找規律的方式一探究竟。

假設 i = 0000 0000 0000 0100 0000 0000 0000 0000，n = 1

i16 0000 0000 0000 0000 0000 0000 0000 0100 不為0i24 0000 0000 0000 0000 0000 0000 0000 0000 等於0

右移了24位等於0，說明24位到31位之間肯定全為0，即n = 1 + 8 = 9，由於高8位全為0，並且已經將資訊記錄至n中，因此可以捨棄高8位，即 i= 8。此時，

i = 0000 0100 0000 0000 0000 0000 0000 0000

類似地，i28 也等於0，說明28位到31位全為0，n = 9 + 4 = 13，捨棄高4位。此時，

i = 0100 0000 0000 0000 0000 0000 0000 0000

繼續運算，

i30 0000 0000 0000 0000 0000 0000 0000 0001 不為0i31 0000 0000 0000 0000 0000 0000 0000 0000 等於0

最終可得出n = 13，即有13個前導0。n -= i31是檢查最高位31位是否是1，因為n初始化為1，如果最高位是1，則不存在前置0，即n = n - 1 = 0。

總結一下，以上的操作其實是基於二分法的思想來定位二進位制中1的最高位，先看高16位，若為0，說明1存在於低16位；反之存在高16位。由此將搜尋範圍由32位（確切的說是31位）減少至16位，進而再一分為二，校驗高8位與低8位，以此類推。

計算過程中校驗的位數依次為16、8、4、2、1，加起來剛好為31。為什麼是31不是32呢？因為前置0的數量為32的情況下i只能為0，在前面的if條件中已經進行過濾。這樣一來，非0值的情況下，前置0只能出現在高31位，因此只需要校驗高31位即可。最終，用總位數減去計算出來的前導0的數量，即可得出二進位制的最高有效位數。程式碼中使用的是31 - Integer。numberOfLeadingZeros（scale），而不是總位數32，這是為了能夠得到雜湊桶陣列中第i個元素的起始記憶體地址，方便進行CAS等操作。

五 併發

1 悲觀鎖

全表鎖

HashTable中採用了全表鎖，即所有操作均上鎖，序列執行，如下圖中的put方法所示，採用synchronized關鍵字修飾。這樣雖然保證了執行緒安全，但是在多核處理器時代也極大地影響了計算效能，這也致使HashTable逐漸淡出開發者們的視野。

分段鎖

針對HashTable中鎖粒度過粗的問題，在JDK1。8之前，ConcurrentHashMap引入了分段鎖機制。整體的儲存結構如下圖所示，在原有結構的基礎上拆分出多個segment，每個segment下再掛載原來的entry（上文中經常提到的雜湊桶陣列），每次操作只需要鎖定元素所在的segment，不需要鎖定整個表。因此，鎖定的範圍更小，併發度也會得到提升。

2 樂觀鎖

Synchronized+CAS

雖然引入了分段鎖的機制，即可以保證執行緒安全，又可以解決鎖粒度過粗導致的效能低下問題，但是對於追求極致效能的工程師來說，這還不是效能的天花板。因此，在JDK1。8中，ConcurrentHashMap摒棄了分段鎖，使用了樂觀鎖的實現方式。放棄分段鎖的原因主要有以下幾點：

使用segment之後，會增加ConcurrentHashMap的儲存空間。

當單個segment過大時，併發效能會急劇下降。

ConcurrentHashMap在JDK1。8中的實現廢棄了之前的segment結構，沿用了與HashMap中的類似的Node陣列結構。

ConcurrentHashMap中的樂觀鎖是採用synchronized+CAS進行實現的。這裡主要看下put的相關程式碼。

當put的元素在雜湊桶陣列中不存在時，則直接CAS進行寫操作。

這裡涉及到了兩個重要的操作，tabAt與casTabAt。可以看出，這裡面都使用了Unsafe類的方法。Unsafe這個類在日常的開發過程中比較罕見。我們通常對Java語言的認知是：Java語言是安全的，所有操作都基於JVM，在安全可控的範圍內進行。然而，Unsafe這個類會打破這個邊界，使Java擁有C的能力，可以操作任意記憶體地址，是一把雙刃劍。這裡使用到了前文中所提到的ASHIFT，來計算出指定元素的起始記憶體地址，再透過getObjectVolatile與compareAndSwapObject分別進行取值與CAS操作。

在獲取雜湊桶陣列中指定位置的元素時為什麼不能直接get而是要使用getObjectVolatile呢？因為在JVM的記憶體模型中，每個執行緒有自己的工作記憶體，也就是棧中的區域性變量表，它是主存的一份copy。因此，執行緒1對某個共享資源進行了更新操作，並寫入到主存，而執行緒2的工作記憶體之中可能還是舊值，髒資料便產生了。Java中的volatile是用來解決上述問題，保證可見性，任意執行緒對volatile關鍵字修飾的變數進行更新時，會使其它執行緒中該變數的副本失效，需要從主存中獲取最新值。雖然ConcurrentHashMap中的Node陣列是由volatile修飾的，可以保證可見性，但是Node陣列中元素是不具備可見性的。因此，在獲取資料時透過Unsafe的方法直接到主存中拿，保證獲取的資料是最新的。

繼續往下看put方法的邏輯，當put的元素在雜湊桶陣列中存在，並且不處於擴容狀態時，則使用synchronized鎖定雜湊桶陣列中第i個位置中的第一個元素f（頭節點2），接著進行double check，類似於DCL單例模式的思想。校驗通過後，會遍歷當前衝突鏈上的元素，並選擇合適的位置進行put操作。此外，ConcurrentHashMap也沿用了HashMap中解決雜湊衝突的方案，連結串列+紅黑樹。這裡只有在發生雜湊衝突的情況下才使用synchronized鎖定頭節點，其實是比分段鎖更細粒度的鎖實現，只在特定場景下鎖定其中一個雜湊桶，降低鎖的影響範圍。

Java Map針對併發場景解決方案的演進方向可以歸結為，從悲觀鎖到樂觀鎖，從粗粒度鎖到細粒度鎖，這也可以作為我們在日常併發程式設計中的指導方針。

3 併發求和

CounterCell是JDK1。8中引入用來併發求和的利器，而在這之前採用的是【嘗試無鎖求和】+【衝突時加鎖重試】的策略。看下CounterCell的註釋，它是改編自LongAdder和Striped64。我們先看下求和操作，其實就是取baseCount作為初始值，然後遍歷CounterCell陣列中的每一個cell，將各個cell的值進行累加。這裡額外說明下@sun。misc。Contender註解的作用，它是Java8中引入用來解決快取行偽共享問題的。什麼是偽共享呢？簡單說下，考慮到CPU與主存之間速度的巨大差異，在CPU中引入了L1、L2、L3多級快取，快取中的儲存單位是快取行，快取行大小為2的整數次冪位元組，32-256個位元組不等，最常見的是64位元組。因此，這將導致不足64位元組的變數會共享同一個快取行，其中一個變數失效會影響到同一個快取行中的其他變數，致使效能下降，這就是偽共享問題。考慮到不同CPU的快取行單位的差異性，Java8中便透過該註解將這種差異性遮蔽，根據實際快取行大小來進行填充，使被修飾的變數能夠獨佔一個快取行。

再來看下CounterCell是如何實現計數的，每當map中的容量有變化時會呼叫addCount進行計數，核心邏輯如下：

當counterCells不為空，或counterCells為空且對baseCount進行CAS操作失敗時進入到後續計數處理邏輯，否則對baseCount進行CAS操作成功，直接返回。

後續計數處理邏輯中會呼叫核心計數方法fullAddCount，但需要滿足以下4個條件中的任意一個：1、counterCells為空；2、counterCells的size為0；3、counterCells對應位置上的counterCell為空；4、CAS更新counterCells對應位置上的counterCell失敗。這些條件背後的語義是，當前情況下，計數已經或曾經出現過併發衝突，需要優先借助於CounterCell來解決。若counterCells與對應位置上的元素已經初始化（條件4），則先嚐試CAS進行更新，若失敗則呼叫fullAddCount繼續處理。若counterCells與對應位置上的元素未初始化完成（條件1、2、3），也要呼叫AddCount進行後續處理。

這裡確定cell下標時採用了ThreadLocalRandom。getProbe（）作為雜湊值，這個方法返回的是當前Thread中threadLocalRandomProbe欄位的值。而且當雜湊值衝突時，還可以透過advanceProbe方法來更換雜湊值。這與HashMap中的雜湊值計算邏輯不同，因為HashMap中要保證同一個key進行多次雜湊計算的雜湊值相同並且能定位到對應的value，即便兩個key的雜湊值衝突也不能隨便更換雜湊值，只能採用連結串列或紅黑樹處理衝突。然而在計數場景，我們並不需要維護key-value的關係，只需要在counterCells中找到一個合適的位置放入計數cell，位置的差異對最終的求和結果是沒有影響的，因此當衝突時可以基於隨機策略更換一個雜湊值來避免衝突。

接著，我們來看下核心計算邏輯fullAddCount，程式碼還是比較多的，核心流程是透過一個死迴圈來實現的，迴圈體中包含了3個處理分支，為了方便講解我將它們依次定義A、B、C。

A：表示counterCells已經初始化完成，因此可以嘗試更新或建立對應位置的CounterCell。

B：表示counterCells未初始化完成，且無衝突（拿到cellsBusy鎖），則加鎖初始化counterCells，初始容量為2。

C：表示counterCells未初始化完成，且有衝突（未能拿到cellsBusy鎖），則CAS更新baseCount，baseCount在求和時也會被算入到最終結果中，這也相當於是一種兜底策略，既然counterCells正在被其他執行緒鎖定，那當前執行緒也沒必要再等待了，直接嘗試使用baseCount進行累加。

其中，A分支中涉及到的操作又可以拆分為以下幾點：

a1：對應位置的CounterCell未建立，採用鎖+Double Check的策略嘗試建立CounterCell，失敗的話則continue進行重試。這裡面採用的鎖是cellsBusy，它保證建立CounterCell並放入counterCells時一定是序列執行，避免重複建立，其實就是使用了DCL單例模式的策略。在CounterCells的建立、擴容中都需要使用該鎖。

a2：衝突檢測，變數wasUncontended是呼叫方addCount中傳入的，表示前置的CAS更新cell失敗，有衝突，需要更換雜湊值【a7】後繼續重試。

a3：對應位置的CounterCell不為空，直接CAS進行更新。

a4：衝突檢測，當counterCells的引用值不等於當前執行緒對應的引用值時，說明有其他執行緒更改了counterCells的引用，出現衝突，則將collide設為false，下次迭代時可進行擴容。容量限制，counterCells容量的最大值為大於等於NCPU（實際機器CPU核心的數量）的最小2的整數次冪，當達到容量限制時後面的擴容分支便永遠不會執行。這裡限制的意義在於，真實併發度是由CPU核心來決定，當counterCells容量與CPU核心數量相等時，理想情況下就算所有CPU核心在同時執行不同的計數執行緒時，都不應該出現衝突，每個執行緒選擇各自的cell進行處理即可。如果出現衝突，一定是雜湊值的問題，因此採取的措施是重新計算雜湊值a7，而不是透過擴容來解決。時間換空間，避免不必要的儲存空間浪費，非常讚的想法~

a5：更新擴容標誌位，下次迭代時將會進行擴容。

a6：進行加鎖擴容，每次擴容1倍。

a7：更換雜湊值。

private final void fullAddCount（long x， boolean wasUncontended） { int h； // 初始化probe if （（h = ThreadLocalRandom。getProbe（）） == 0） { ThreadLocalRandom。localInit（）； // force initialization h = ThreadLocalRandom。getProbe（）； wasUncontended = true； } // 用來控制擴容操作 boolean collide = false； // True if last slot nonempty for （；；） { CounterCell［］ as； CounterCell a； int n； long v； // 【A】counterCells已經初始化完畢 if （（as = counterCells） ！= null（n = as。length）0） { // 【a1】對應位置的CounterCell未建立 if （（a = as［（n - 1）h］） == null） { // cellsBusy其實是一個鎖，cellsBusy=0時表示無衝突 if （cellsBusy == 0） { // Try to attach new Cell // 建立新的CounterCell CounterCell r = new CounterCell（x）； // Optimistic create // Double Check，加鎖（透過CAS將cellsBusy設定1） if （cellsBusy == 0U。compareAndSwapInt（this， CELLSBUSY， 0， 1）） { boolean created = false； try { // Recheck under lock CounterCell［］ rs； int m， j； // Double Check if （（rs = counterCells） ！= null（m = rs。length）0rs［j = （m - 1）h］ == null） { // 將新建立的CounterCell放入counterCells中 rs［j］ = r； created = true； } } finally { // 解鎖，這裡為什麼不用CAS？因為當前流程中需要在獲取鎖的前提下進行，即序列執行，因此不存在併發更新問題，只需要正常更新即可 cellsBusy = 0； } if （created） break； // 建立失敗則重試 continue； // Slot is now non-empty } } // cellsBusy不為0，說明被其他執行緒爭搶到了鎖，還不能考慮擴容 collide = false； } //【a2】衝突檢測 else if （！wasUncontended） // CAS already known to fail // 呼叫方addCount中CAS更新cell失敗，有衝突，則繼續嘗試CAS wasUncontended = true； // Continue after rehash //【a3】對應位置的CounterCell不為空，直接CAS進行更新 else if （U。compareAndSwapLong（a， CELLVALUE， v = a。value， v + x）） break； //【a4】容量限制 else if （counterCells ！= as || n= NCPU） // 說明counterCells容量的最大值為大於NCPU（實際機器CPU核心的數量）最小2的整數次冪。 // 這裡限制的意義在於，併發度是由CPU核心來決定，當counterCells容量與CPU核心數量相等時，理論上講就算所有CPU核心都在同時執行不同的計數執行緒時，都不應該出現衝突，每個執行緒選擇各自的cell進行處理即可。如果出現衝突，一定是雜湊值的問題，因此採取的措施是重新計算雜湊值（h = ThreadLocalRandom。advanceProbe（h）），而不是透過擴容來解決 // 當n大於NCPU時後面的分支就不會走到了 collide = false； // At max size or stale // 【a5】更新擴容標誌位 else if （！collide） // 說明對映到cell位置不為空，並且嘗試進行CAS更新時失敗了，則說明有競爭，將collide設定為true，下次迭代時執行後面的擴容操作，降低競爭度 // 有競爭時，執行rehash+擴容，當容量大於CPU核心時則停止擴容只進行rehash collide = true； // 【a6】加鎖擴容 else if （cellsBusy == 0U。compareAndSwapInt（this， CELLSBUSY， 0， 1）） { // 加鎖擴容 try { if （counterCells == as） {// Expand table unless stale // 擴容1倍 CounterCell［］ rs = new CounterCell［n1］； for （int i = 0； in； ++i） rs［i］ = as［i］； counterCells = rs； } } finally { cellsBusy = 0； } collide = false； continue； // Retry with expanded table } //【a7】更換雜湊值 h = ThreadLocalRandom。advanceProbe（h）； } // 【B】counterCells未初始化完成，且無衝突，則加鎖初始化counterCells else if （cellsBusy == 0counterCells == asU。compareAndSwapInt（this， CELLSBUSY， 0， 1）） { boolean init = false； try { // Initialize table if （counterCells == as） { CounterCell［］ rs = new CounterCell［2］； rs［h1］ = new CounterCell（x）； counterCells = rs； init = true； } } finally { cellsBusy = 0； } if （init） break； } // 【C】counterCells未初始化完成，且有衝突，則CAS更新baseCount else if （U。compareAndSwapLong（this， BASECOUNT， v = baseCount， v + x）） break； // Fall back on using base }

CounterCell的設計很巧妙，它的背後其實就是JDK1。8中的LongAdder。核心思想是：在併發較低的場景下直接採用baseCount累加，否則結合counterCells，將不同的執行緒雜湊到不同的cell中進行計算，儘可能地確保訪問資源的隔離，減少衝突。LongAdder相比較於AtomicLong中無腦CAS的策略，在高併發的場景下，能夠減少CAS重試的次數，提高計算效率。

六 結語

以上可能只是Java Map原始碼中的冰山一角，但是基本包括了大部分的核心特性，涵蓋了我們日常開發中的大部分場景。讀原始碼跟讀書一樣，彷彿跨越了歷史長河與作者進行近距離對話，揣摩他的心思，學習他的思想並加以傳承。資訊加工轉化為知識並運用的過程是痛苦的，但是痛並快樂著。

作者 | 子澐