作者 | 子澐
來源 |
阿裡技術公衆号最近拜讀了一些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 0010
hashCode(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 1101
hashCode(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.hash & oldCap來判斷取模後是落在高位還是低位。舉個例子：假設目前元素hashCode為0001（忽略高位），其運算結果等于0，說明擴容後結果不變，取模後還是落在低位[0, 7]，即0001 & 1000 = 0000，還是原位置，再用低位連結清單将這類的元素連結起來。假設目前元素的hashCode為1001， 其運算結果不為0，即1001 & 1000 = 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 = 3
n = 2
n |= n >>> 1 010 | 001 = 011 n = 3
n |= n >>> 2 011 | 000 = 011 n = 3
n |= n >>> 4 011 | 000 = 011 n = 3
….
n = n + 1 = 4 當cap為5時，計算過程如下：
cap = 5
n = 4
n |= n >>> 1 0100 | 0010 = 0110 n = 6
n |= n >>> 2 0110 | 0001 = 0111 n = 7
….
n = n + 1 = 8 是以，計算的意義在于找到大于等于cap的最小2的整數次幂。整個過程是找到cap對應二進制中最高位的1，然後每次以2倍的步長（依次移位1、2、4、8、16）複制最高位1到後面的所有低位，把最高位1後面的所有位全部置為1，最後進行+1，即完成了進位。
類似二進制位的變化過程如下：
0100 1010
0111 1111
1000 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)i << ASHIFT) + ABASE)進行計算，便可得到數組中第i個元素的起始記憶體位址。
我們繼續看下前導0的數量是怎麼計算出來的，numberOfLeadingZeros是Integer的靜态方法，還是沿用找規律的方式一探究竟。
假設 i = 0000 0000 0000 0100 0000 0000 0000 0000，n = 1
i >>> 16 0000 0000 0000 0000 0000 0000 0000 0100 不為0
i >>> 24 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 類似地，i >>> 28 也等于0，說明28位到31位全為0，n = 9 + 4 = 13，舍棄高4位。此時，
i = 0100 0000 0000 0000 0000 0000 0000 0000 繼續運算，
i >>> 30 0000 0000 0000 0000 0000 0000 0000 0001 不為0
i >>> 31 0000 0000 0000 0000 0000 0000 0000 0000 等于0 最終可得出n = 13，即有13個前導0。n -= i >>> 31是檢查最高位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 == 0 &&
U.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) > 0 &&
rs[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 == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
// 加鎖擴容
try {
if (counterCells == as) {// Expand table unless stale
// 擴容1倍
CounterCell[] rs = new CounterCell[n << 1];
for (int i = 0; i < n; ++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 == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try { // Initialize table
if (counterCells == as) {
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = 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源碼中的冰山一角，但是基本包括了大部分的核心特性，涵蓋了我們日常開發中的大部分場景。讀源碼跟讀書一樣，仿佛跨越了曆史長河與作者進行近距離對話，揣摩他的心思，學習他的思想并加以傳承。資訊加工轉化為知識并運用的過程是痛苦的，但是痛并快樂着。