最近拜讀了一些Java Map的相關(guān)源碼，不得不驚嘆于JDK開發(fā)者們的鬼斧神工。他山之石可以攻玉，這些巧妙的設(shè)計(jì)思想非常有借鑒價(jià)值，可謂是最佳實(shí)踐。然而，大多數(shù)有關(guān)Java Map原理的科普類文章都是專注于“點(diǎn)”，并沒有連成“線”，甚至形成“網(wǎng)狀結(jié)構(gòu)”。因此，本文基于個(gè)人理解，對(duì)所閱讀的部分源碼進(jìn)行了分類與總結(jié)，歸納出Map中的幾個(gè)核心特性，包括：自動(dòng)擴(kuò)容、初始化與懶加載、哈希計(jì)算、位運(yùn)算與并發(fā)，并結(jié)合源碼進(jìn)行深入講解，希望看完本文的你也能從中獲取到些許收獲(本文默認(rèn)采用JDK1.8中的HashMap)。

一 自動(dòng)擴(kuò)容

最小可用原則，容量超過一定閾值便自動(dòng)進(jìn)行擴(kuò)容。

擴(kuò)容是通過resize方法來實(shí)現(xiàn)的。擴(kuò)容發(fā)生在putVal方法的最后，即寫入元素之后才會(huì)判斷是否需要擴(kuò)容操作，當(dāng)自增后的size大于之前所計(jì)算好的閾值threshold，即執(zhí)行resize操作。

??

通過位運(yùn)算<<1進(jìn)行容量擴(kuò)充，即擴(kuò)容1倍，同時(shí)新的閾值newThr也擴(kuò)容為老閾值的1倍。

??

擴(kuò)容時(shí)，總共存在三種情況：

• 哈希桶數(shù)組中某個(gè)位置只有1個(gè)元素，即不存在哈希沖突時(shí)，則直接將該元素copy至新哈希桶數(shù)組的對(duì)應(yīng)位置即可。
• 哈希桶數(shù)組中某個(gè)位置的節(jié)點(diǎn)為樹節(jié)點(diǎn)時(shí)，則執(zhí)行紅黑樹的擴(kuò)容操作。
• 哈希桶數(shù)組中某個(gè)位置的節(jié)點(diǎn)為普通節(jié)點(diǎn)時(shí)，則執(zhí)行鏈表擴(kuò)容操作，在JDK1.8中，為了避免之前版本中并發(fā)擴(kuò)容所導(dǎo)致的死鏈問題，引入了高低位鏈表輔助進(jìn)行擴(kuò)容操作。

??

在日常的開發(fā)過程中，會(huì)遇到一些bad case，比如：

HashMap hashMap = new HashMap(2); 
 hashMap.put("1", 1); 
 hashMap.put("2", 2); 
 hashMap.put("3", 3);

當(dāng)hashMap設(shè)置最后一個(gè)元素3的時(shí)候，會(huì)發(fā)現(xiàn)當(dāng)前的哈希桶數(shù)組大小已經(jīng)達(dá)到擴(kuò)容閾值2*0.75=1.5，緊接著會(huì)執(zhí)行一次擴(kuò)容操作，因此，此類的代碼每次運(yùn)行的時(shí)候都會(huì)進(jìn)行一次擴(kuò)容操作，效率低下。在日常開發(fā)過程中，一定要充分評(píng)估好HashMap的大小，盡可能保證擴(kuò)容的閾值大于存儲(chǔ)元素的數(shù)量，減少其擴(kuò)容次數(shù)。

二 初始化與懶加載

初始化的時(shí)候只會(huì)設(shè)置默認(rèn)的負(fù)載因子，并不會(huì)進(jìn)行其他初始化的操作，在首次使用的時(shí)候才會(huì)進(jìn)行初始化。

當(dāng)new一個(gè)新的HashMap的時(shí)候，不會(huì)立即對(duì)哈希數(shù)組進(jìn)行初始化，而是在首次put元素的時(shí)候，通過resize()方法進(jìn)行初始化。

??

resize()中會(huì)設(shè)置默認(rèn)的初始化容量DEFAULT_INITIAL_CAPACITY為16，擴(kuò)容的閾值為0.75*16 = 12，即哈希桶數(shù)組中元素達(dá)到12個(gè)便進(jìn)行擴(kuò)容操作。

最后創(chuàng)建容量為16的Node數(shù)組，并賦值給成員變量哈希桶table，即完成了HashMap的初始化操作。

??

三 哈希計(jì)算

哈希表以哈希命名，足以說明哈希計(jì)算在該數(shù)據(jù)結(jié)構(gòu)中的重要程度。而在實(shí)現(xiàn)中，JDK并沒有直接使用Object的native方法返回的hashCode作為最終的哈希值，而是進(jìn)行了二次加工。

以下分別為HashMap與ConcurrentHashMap計(jì)算hash值的方法，核心的計(jì)算邏輯相同，都是使用key對(duì)應(yīng)的hashCode與其hashCode右移16位的結(jié)果進(jìn)行異或操作。此處，將高16位與低16位進(jìn)行異或的操作稱之為擾動(dòng)函數(shù)，目的是將高位的特征融入到低位之中，降低哈希沖突的概率。

??

舉個(gè)例子來理解下擾動(dòng)函數(shù)的作用：

hashCode(key1) = 0000 0000 0000 1111 0000 0000 0000 0010 
 hashCode(key2) = 0000 0000 0000 0000 0000 0000 0000 0010

若HashMap容量為4，在不使用擾動(dòng)函數(shù)的情況下，key1與key2的hashCode注定會(huì)沖突(后兩位相同，均為01)。

經(jīng)過擾動(dòng)函數(shù)處理后，可見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

這種增益會(huì)隨著HashMap容量的減少而增加?！禔n introduction to optimising a hashing strategy》文章中隨機(jī)選取了哈希值不同的352個(gè)字符串，當(dāng)HashMap的容量為2^9時(shí)，使用擾動(dòng)函數(shù)可以減少10%的碰撞，可見擾動(dòng)函數(shù)的必要性。

此外，ConcurrentHashMap中經(jīng)過擾亂函數(shù)處理之后，需要與HASH_BITS做與運(yùn)算，HASH_BITS為0x7ffffff，即只有最高位為0，這樣運(yùn)算的結(jié)果使hashCode永遠(yuǎn)為正數(shù)。在ConcurrentHashMap中，預(yù)定義了幾個(gè)特殊節(jié)點(diǎn)的hashCode，如：MOVED、TREEBIN、RESERVED，它們的hashCode均定義為負(fù)值。因此，將普通節(jié)點(diǎn)的hashCode限定為正數(shù)，也就是為了防止與這些特殊節(jié)點(diǎn)的hashCode產(chǎn)生沖突。

1 哈希沖突

通過哈希運(yùn)算，可以將不同的輸入值映射到指定的區(qū)間范圍內(nèi)，隨之而來的是哈希沖突問題。考慮一個(gè)極端的case，假設(shè)所有的輸入元素經(jīng)過哈希運(yùn)算之后，都映射到同一個(gè)哈希桶中，那么查詢的復(fù)雜度將不再是O(1)，而是O(n)，相當(dāng)于線性表的順序遍歷。因此，哈希沖突是影響哈希計(jì)算性能的重要因素之一。哈希沖突如何解決呢?主要從兩個(gè)方面考慮，一方面是避免沖突，另一方面是在沖突時(shí)合理地解決沖突，盡可能提高查詢效率。前者在上面的章節(jié)中已經(jīng)進(jìn)行介紹，即通過擾動(dòng)函數(shù)來增加hashCode的隨機(jī)性，避免沖突。針對(duì)后者，HashMap中給出了兩種方案：拉鏈表與紅黑樹。

拉鏈表

在JDK1.8之前，HashMap中是采用拉鏈表的方法來解決沖突，即當(dāng)計(jì)算出的hashCode對(duì)應(yīng)的桶上已經(jīng)存在元素，但兩者key不同時(shí)，會(huì)基于桶中已存在的元素拉出一條鏈表，將新元素鏈到已存在元素的前面。當(dāng)查詢存在沖突的哈希桶時(shí)，會(huì)順序遍歷沖突鏈上的元素。同一key的判斷邏輯如下圖所示，先判斷hash值是否相同，再比較key的地址或值是否相同。

??

(1)死鏈

在JDK1.8之前，HashMap在并發(fā)場(chǎng)景下擴(kuò)容時(shí)存在一個(gè)bug，形成死鏈，導(dǎo)致get該位置元素的時(shí)候，會(huì)死循環(huán)，使CPU利用率高居不下。這也說明了HashMap不適于用在高并發(fā)的場(chǎng)景，高并發(fā)應(yīng)該優(yōu)先考慮JUC中的ConcurrentHashMap。然而，精益求精的JDK開發(fā)者們并沒有選擇繞過問題，而是選擇直面問題并解決它。在JDK1.8之中，引入了高低位鏈表(雙端鏈表)。

什么是高低位鏈表呢?在擴(kuò)容時(shí)，哈希桶數(shù)組buckets會(huì)擴(kuò)容一倍，以容量為8的HashMap為例，原有容量8擴(kuò)容至16，將[0, 7]稱為低位，[8, 15]稱為高位，低位對(duì)應(yīng)loHead、loTail，高位對(duì)應(yīng)hiHead、hiTail。

擴(kuò)容時(shí)會(huì)依次遍歷舊buckets數(shù)組的每一個(gè)位置上面的元素：

• 若不存在沖突，則重新進(jìn)行hash取模，并copy到新buckets數(shù)組中的對(duì)應(yīng)位置。
• 若存在沖突元素，則采用高低位鏈表進(jìn)行處理。通過e.hash & oldCap來判斷取模后是落在高位還是低位。舉個(gè)例子：假設(shè)當(dāng)前元素hashCode為0001(忽略高位)，其運(yùn)算結(jié)果等于0，說明擴(kuò)容后結(jié)果不變，取模后還是落在低位[0, 7]，即0001 & 1000 = 0000，還是原位置，再用低位鏈表將這類的元素鏈接起來。假設(shè)當(dāng)前元素的hashCode為1001， 其運(yùn)算結(jié)果不為0，即1001 & 1000 = 1000 ，擴(kuò)容后會(huì)落在高位，新的位置剛好是舊數(shù)組索引(1) + 舊數(shù)據(jù)長(zhǎng)度(8) = 9，再用高位鏈表將這些元素鏈接起來。最后，將高低位鏈表的頭節(jié)點(diǎn)分別放在擴(kuò)容后數(shù)組newTab的指定位置上，即完成了擴(kuò)容操作。這種實(shí)現(xiàn)降低了對(duì)共享資源newTab的訪問頻次，先組織沖突節(jié)點(diǎn)，最后再放入newTab的指定位置。避免了JDK1.8之前每遍歷一個(gè)元素就放入newTab中，從而導(dǎo)致并發(fā)擴(kuò)容下的死鏈問題。

??

紅黑樹

在JDK1.8之中，HashMap引入了紅黑樹來處理哈希沖突問題，而不再是拉鏈表。那么為什么要引入紅黑樹來替代鏈表呢?雖然鏈表的插入性能是O(1)，但查詢性能確是O(n)，當(dāng)哈希沖突元素非常多時(shí)，這種查詢性能是難以接受的。因此，在JDK1.8中，如果沖突鏈上的元素?cái)?shù)量大于8，并且哈希桶數(shù)組的長(zhǎng)度大于64時(shí)，會(huì)使用紅黑樹代替鏈表來解決哈希沖突，此時(shí)的節(jié)點(diǎn)會(huì)被封裝成TreeNode而不再是Node(TreeNode其實(shí)繼承了Node，以利用多態(tài)特性)，使查詢具備O(logn)的性能。

這里簡(jiǎn)單地回顧一下紅黑樹，它是一種平衡的二叉樹搜索樹，類似地還有AVL樹。兩者核心的區(qū)別是AVL樹追求“絕對(duì)平衡”，在插入、刪除節(jié)點(diǎn)時(shí)，成本要高于紅黑樹，但也因此擁有了更好的查詢性能，適用于讀多寫少的場(chǎng)景。然而，對(duì)于HashMap而言，讀寫操作其實(shí)難分伯仲，因此選擇紅黑樹也算是在讀寫性能上的一種折中。

四 位運(yùn)算

1 確定哈希桶數(shù)組大小

找到大于等于給定值的最小2的整數(shù)次冪。

tableSizeFor根據(jù)輸入容量大小cap來計(jì)算最終哈希桶數(shù)組的容量大小，找到大于等于給定值cap的最小2的整數(shù)次冪。乍眼一看，這一行一行的位運(yùn)算讓人云里霧里，莫不如采用類似找規(guī)律的方式來探索其中的奧秘。

??

當(dāng)cap為3時(shí)，計(jì)算過程如下：

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

當(dāng)cap為5時(shí)，計(jì)算過程如下：

cap = 5 
 n = 4 
 n |= n >>> 1    0100 | 0010 = 0110  n = 6 
 n |= n >>> 2    0110 | 0001 = 0111  n = 7 
 …. 
 n = n + 1 = 8

因此，計(jì)算的意義在于找到大于等于cap的最小2的整數(shù)次冪。整個(gè)過程是找到cap對(duì)應(yīng)二進(jìn)制中最高位的1，然后每次以2倍的步長(zhǎng)(依次移位1、2、4、8、16)復(fù)制最高位1到后面的所有低位，把最高位1后面的所有位全部置為1，最后進(jìn)行+1，即完成了進(jìn)位。

類似二進(jìn)制位的變化過程如下：

0100 1010 
 0111 1111 
 1000 0000

找到輸入cap的最小2的整數(shù)次冪作為最終容量可以理解為最小可用原則，盡可能地少占用空間，但是為什么必須要2的整數(shù)次冪呢?答案是，為了提高計(jì)算與存儲(chǔ)效率，使每個(gè)元素對(duì)應(yīng)hash值能夠準(zhǔn)確落入哈希桶數(shù)組給定的范圍區(qū)間內(nèi)。確定數(shù)組下標(biāo)采用的算法是 hash & (n - 1)，n即為哈希桶數(shù)組的大小。由于其總是2的整數(shù)次冪，這意味著n-1的二進(jìn)制形式永遠(yuǎn)都是0000111111的形式，即從最低位開始，連續(xù)出現(xiàn)多個(gè)1，該二進(jìn)制與任何值進(jìn)行&運(yùn)算都會(huì)使該值映射到指定區(qū)間[0, n-1]。比如：當(dāng)n=8時(shí)，n-1對(duì)應(yīng)的二進(jìn)制為0111，任何與0111進(jìn)行&運(yùn)算都會(huì)落入[0,7]的范圍內(nèi)，即落入給定的8個(gè)哈希桶中，存儲(chǔ)空間利用率100%。舉個(gè)反例，當(dāng)n=7，n-1對(duì)應(yīng)的二進(jìn)制為0110，任何與0110進(jìn)行&運(yùn)算會(huì)落入到第0、6、4、2個(gè)哈希桶，而不是[0,6]的區(qū)間范圍內(nèi)，少了1、3、5三個(gè)哈希桶，這導(dǎo)致存儲(chǔ)空間利用率只有不到60%，同時(shí)也增加了哈希碰撞的幾率。

2 ASHIFT偏移量計(jì)算

獲取給定值的最高有效位數(shù)(移位除了能夠進(jìn)行乘除運(yùn)算，還能用于保留高、低位操作，右移保留高位，左移保留低位)。

ConcurrentHashMap中的ABASE+ASHIFT是用來計(jì)算哈希數(shù)組中某個(gè)元素在實(shí)際內(nèi)存中的初始位置，ASHIFT采取的計(jì)算方式是31與scale前導(dǎo)0的數(shù)量做差，也就是scale的實(shí)際位數(shù)-1。scale就是哈希桶數(shù)組Node[]中每個(gè)元素的大小，通過((long)i << ASHIFT) + ABASE)進(jìn)行計(jì)算，便可得到數(shù)組中第i個(gè)元素的起始內(nèi)存地址。

??

我們繼續(xù)看下前導(dǎo)0的數(shù)量是怎么計(jì)算出來的，numberOfLeadingZeros是Integer的靜態(tài)方法，還是沿用找規(guī)律的方式一探究竟。

??

假設(shè) 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，并且已經(jīng)將信息記錄至n中，因此可以舍棄高8位，即 i <<= 8。此時(shí)，

i = 0000 0100 0000 0000 0000 0000 0000 0000

類似地，i >>> 28 也等于0，說明28位到31位全為0，n = 9 + 4 = 13，舍棄高4位。此時(shí)，

i = 0100 0000 0000 0000 0000 0000 0000 0000

繼續(xù)運(yùn)算，

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個(gè)前導(dǎo)0。n -= i >>> 31是檢查最高位31位是否是1，因?yàn)閚初始化為1，如果最高位是1，則不存在前置0，即n = n - 1 = 0。

總結(jié)一下，以上的操作其實(shí)是基于二分法的思想來定位二進(jìn)制中1的最高位，先看高16位，若為0，說明1存在于低16位;反之存在高16位。由此將搜索范圍由32位(確切的說是31位)減少至16位，進(jìn)而再一分為二，校驗(yàn)高8位與低8位，以此類推。

計(jì)算過程中校驗(yàn)的位數(shù)依次為16、8、4、2、1，加起來剛好為31。為什么是31不是32呢?因?yàn)榍爸?的數(shù)量為32的情況下i只能為0，在前面的if條件中已經(jīng)進(jìn)行過濾。這樣一來，非0值的情況下，前置0只能出現(xiàn)在高31位，因此只需要校驗(yàn)高31位即可。最終，用總位數(shù)減去計(jì)算出來的前導(dǎo)0的數(shù)量，即可得出二進(jìn)制的最高有效位數(shù)。代碼中使用的是31 - Integer.numberOfLeadingZeros(scale)，而不是總位數(shù)32，這是為了能夠得到哈希桶數(shù)組中第i個(gè)元素的起始內(nèi)存地址，方便進(jìn)行CAS等操作。

五 并發(fā)

1 悲觀鎖

全表鎖

HashTable中采用了全表鎖，即所有操作均上鎖，串行執(zhí)行，如下圖中的put方法所示，采用synchronized關(guān)鍵字修飾。這樣雖然保證了線程安全，但是在多核處理器時(shí)代也極大地影響了計(jì)算性能，這也致使HashTable逐漸淡出開發(fā)者們的視野。

??

分段鎖

針對(duì)HashTable中鎖粒度過粗的問題，在JDK1.8之前，ConcurrentHashMap引入了分段鎖機(jī)制。整體的存儲(chǔ)結(jié)構(gòu)如下圖所示，在原有結(jié)構(gòu)的基礎(chǔ)上拆分出多個(gè)segment，每個(gè)segment下再掛載原來的entry(上文中經(jīng)常提到的哈希桶數(shù)組)，每次操作只需要鎖定元素所在的segment，不需要鎖定整個(gè)表。因此，鎖定的范圍更小，并發(fā)度也會(huì)得到提升。

??

2 樂觀鎖

Synchronized+CAS

雖然引入了分段鎖的機(jī)制，即可以保證線程安全，又可以解決鎖粒度過粗導(dǎo)致的性能低下問題，但是對(duì)于追求極致性能的工程師來說，這還不是性能的天花板。因此，在JDK1.8中，ConcurrentHashMap摒棄了分段鎖，使用了樂觀鎖的實(shí)現(xiàn)方式。放棄分段鎖的原因主要有以下幾點(diǎn)：

• 使用segment之后，會(huì)增加ConcurrentHashMap的存儲(chǔ)空間。
• 當(dāng)單個(gè)segment過大時(shí)，并發(fā)性能會(huì)急劇下降。

ConcurrentHashMap在JDK1.8中的實(shí)現(xiàn)廢棄了之前的segment結(jié)構(gòu)，沿用了與HashMap中的類似的Node數(shù)組結(jié)構(gòu)。

??

ConcurrentHashMap中的樂觀鎖是采用synchronized+CAS進(jìn)行實(shí)現(xiàn)的。這里主要看下put的相關(guān)代碼。

當(dāng)put的元素在哈希桶數(shù)組中不存在時(shí)，則直接CAS進(jìn)行寫操作。

??

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

在獲取哈希桶數(shù)組中指定位置的元素時(shí)為什么不能直接get而是要使用getObjectVolatile呢?因?yàn)樵贘VM的內(nèi)存模型中，每個(gè)線程有自己的工作內(nèi)存，也就是棧中的局部變量表，它是主存的一份copy。因此，線程1對(duì)某個(gè)共享資源進(jìn)行了更新操作，并寫入到主存，而線程2的工作內(nèi)存之中可能還是舊值，臟數(shù)據(jù)便產(chǎn)生了。Java中的volatile是用來解決上述問題，保證可見性，任意線程對(duì)volatile關(guān)鍵字修飾的變量進(jìn)行更新時(shí)，會(huì)使其它線程中該變量的副本失效，需要從主存中獲取最新值。雖然ConcurrentHashMap中的Node數(shù)組是由volatile修飾的，可以保證可見性，但是Node數(shù)組中元素是不具備可見性的。因此，在獲取數(shù)據(jù)時(shí)通過Unsafe的方法直接到主存中拿，保證獲取的數(shù)據(jù)是最新的。

??

繼續(xù)往下看put方法的邏輯，當(dāng)put的元素在哈希桶數(shù)組中存在，并且不處于擴(kuò)容狀態(tài)時(shí)，則使用synchronized鎖定哈希桶數(shù)組中第i個(gè)位置中的第一個(gè)元素f(頭節(jié)點(diǎn)2)，接著進(jìn)行double check，類似于DCL單例模式的思想。校驗(yàn)通過后，會(huì)遍歷當(dāng)前沖突鏈上的元素，并選擇合適的位置進(jìn)行put操作。此外，ConcurrentHashMap也沿用了HashMap中解決哈希沖突的方案，鏈表+紅黑樹。這里只有在發(fā)生哈希沖突的情況下才使用synchronized鎖定頭節(jié)點(diǎn)，其實(shí)是比分段鎖更細(xì)粒度的鎖實(shí)現(xiàn)，只在特定場(chǎng)景下鎖定其中一個(gè)哈希桶，降低鎖的影響范圍。

??

Java Map針對(duì)并發(fā)場(chǎng)景解決方案的演進(jìn)方向可以歸結(jié)為，從悲觀鎖到樂觀鎖，從粗粒度鎖到細(xì)粒度鎖，這也可以作為我們?cè)谌粘２l(fā)編程中的指導(dǎo)方針。

3 并發(fā)求和

CounterCell是JDK1.8中引入用來并發(fā)求和的利器，而在這之前采用的是【嘗試無鎖求和】+【沖突時(shí)加鎖重試】的策略?？聪翪ounterCell的注釋，它是改編自LongAdder和Striped64。我們先看下求和操作，其實(shí)就是取baseCount作為初始值，然后遍歷CounterCell數(shù)組中的每一個(gè)cell，將各個(gè)cell的值進(jìn)行累加。這里額外說明下@sun.misc.Contender注解的作用，它是Java8中引入用來解決緩存行偽共享問題的。什么是偽共享呢?簡(jiǎn)單說下，考慮到CPU與主存之間速度的巨大差異，在CPU中引入了L1、L2、L3多級(jí)緩存，緩存中的存儲(chǔ)單位是緩存行，緩存行大小為2的整數(shù)次冪字節(jié)，32-256個(gè)字節(jié)不等，最常見的是64字節(jié)。因此，這將導(dǎo)致不足64字節(jié)的變量會(huì)共享同一個(gè)緩存行，其中一個(gè)變量失效會(huì)影響到同一個(gè)緩存行中的其他變量，致使性能下降，這就是偽共享問題?？紤]到不同CPU的緩存行單位的差異性，Java8中便通過該注解將這種差異性屏蔽，根據(jù)實(shí)際緩存行大小來進(jìn)行填充，使被修飾的變量能夠獨(dú)占一個(gè)緩存行。

??

??

再來看下CounterCell是如何實(shí)現(xiàn)計(jì)數(shù)的，每當(dāng)map中的容量有變化時(shí)會(huì)調(diào)用addCount進(jìn)行計(jì)數(shù)，核心邏輯如下：

• 當(dāng)counterCells不為空，或counterCells為空且對(duì)baseCount進(jìn)行CAS操作失敗時(shí)進(jìn)入到后續(xù)計(jì)數(shù)處理邏輯，否則對(duì)baseCount進(jìn)行CAS操作成功，直接返回。
• 后續(xù)計(jì)數(shù)處理邏輯中會(huì)調(diào)用核心計(jì)數(shù)方法fullAddCount，但需要滿足以下4個(gè)條件中的任意一個(gè)：1、counterCells為空;2、counterCells的size為0;3、counterCells對(duì)應(yīng)位置上的counterCell為空;4、CAS更新counterCells對(duì)應(yīng)位置上的counterCell失敗。這些條件背后的語義是，當(dāng)前情況下，計(jì)數(shù)已經(jīng)或曾經(jīng)出現(xiàn)過并發(fā)沖突，需要優(yōu)先借助于CounterCell來解決。若counterCells與對(duì)應(yīng)位置上的元素已經(jīng)初始化(條件4)，則先嘗試CAS進(jìn)行更新，若失敗則調(diào)用fullAddCount繼續(xù)處理。若counterCells與對(duì)應(yīng)位置上的元素未初始化完成(條件1、2、3)，也要調(diào)用AddCount進(jìn)行后續(xù)處理。
• 這里確定cell下標(biāo)時(shí)采用了ThreadLocalRandom.getProbe()作為哈希值，這個(gè)方法返回的是當(dāng)前Thread中threadLocalRandomProbe字段的值。而且當(dāng)哈希值沖突時(shí)，還可以通過advanceProbe方法來更換哈希值。這與HashMap中的哈希值計(jì)算邏輯不同，因?yàn)镠ashMap中要保證同一個(gè)key進(jìn)行多次哈希計(jì)算的哈希值相同并且能定位到對(duì)應(yīng)的value，即便兩個(gè)key的哈希值沖突也不能隨便更換哈希值，只能采用鏈表或紅黑樹處理沖突。然而在計(jì)數(shù)場(chǎng)景，我們并不需要維護(hù)key-value的關(guān)系，只需要在counterCells中找到一個(gè)合適的位置放入計(jì)數(shù)cell，位置的差異對(duì)最終的求和結(jié)果是沒有影響的，因此當(dāng)沖突時(shí)可以基于隨機(jī)策略更換一個(gè)哈希值來避免沖突。

??

接著，我們來看下核心計(jì)算邏輯fullAddCount，代碼還是比較多的，核心流程是通過一個(gè)死循環(huán)來實(shí)現(xiàn)的，循環(huán)體中包含了3個(gè)處理分支，為了方便講解我將它們依次定義A、B、C。

• A：表示counterCells已經(jīng)初始化完成，因此可以嘗試更新或創(chuàng)建對(duì)應(yīng)位置的CounterCell。
• B：表示counterCells未初始化完成，且無沖突(拿到cellsBusy鎖)，則加鎖初始化counterCells，初始容量為2。
• C：表示counterCells未初始化完成，且有沖突(未能拿到cellsBusy鎖)，則CAS更新baseCount，baseCount在求和時(shí)也會(huì)被算入到最終結(jié)果中，這也相當(dāng)于是一種兜底策略，既然counterCells正在被其他線程鎖定，那當(dāng)前線程也沒必要再等待了，直接嘗試使用baseCount進(jìn)行累加。

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

• a1：對(duì)應(yīng)位置的CounterCell未創(chuàng)建，采用鎖+Double Check的策略嘗試創(chuàng)建CounterCell，失敗的話則continue進(jìn)行重試。這里面采用的鎖是cellsBusy，它保證創(chuàng)建CounterCell并放入counterCells時(shí)一定是串行執(zhí)行，避免重復(fù)創(chuàng)建，其實(shí)就是使用了DCL單例模式的策略。在CounterCells的創(chuàng)建、擴(kuò)容中都需要使用該鎖。
• a2：沖突檢測(cè)，變量wasUncontended是調(diào)用方addCount中傳入的，表示前置的CAS更新cell失敗，有沖突，需要更換哈希值【a7】后繼續(xù)重試。
• a3：對(duì)應(yīng)位置的CounterCell不為空，直接CAS進(jìn)行更新。
• a4：

• 沖突檢測(cè)，當(dāng)counterCells的引用值不等于當(dāng)前線程對(duì)應(yīng)的引用值時(shí)，說明有其他線程更改了counterCells的引用，出現(xiàn)沖突，則將collide設(shè)為false，下次迭代時(shí)可進(jìn)行擴(kuò)容。
• 容量限制，counterCells容量的最大值為大于等于NCPU(實(shí)際機(jī)器CPU核心的數(shù)量)的最小2的整數(shù)次冪，當(dāng)達(dá)到容量限制時(shí)后面的擴(kuò)容分支便永遠(yuǎn)不會(huì)執(zhí)行。這里限制的意義在于，真實(shí)并發(fā)度是由CPU核心來決定，當(dāng)counterCells容量與CPU核心數(shù)量相等時(shí)，理想情況下就算所有CPU核心在同時(shí)運(yùn)行不同的計(jì)數(shù)線程時(shí)，都不應(yīng)該出現(xiàn)沖突，每個(gè)線程選擇各自的cell進(jìn)行處理即可。如果出現(xiàn)沖突，一定是哈希值的問題，因此采取的措施是重新計(jì)算哈希值a7，而不是通過擴(kuò)容來解決。時(shí)間換空間，避免不必要的存儲(chǔ)空間浪費(fèi)，非常贊的想法~

• a5：更新擴(kuò)容標(biāo)志位，下次迭代時(shí)將會(huì)進(jìn)行擴(kuò)容。
• a6：進(jìn)行加鎖擴(kuò)容，每次擴(kuò)容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; 
         } 
         // 用來控制擴(kuò)容操作 
         boolean collide = false;                // True if last slot nonempty 
         for (;;) { 
             CounterCell[] as; CounterCell a; int n; long v; 
             // 【A】counterCells已經(jīng)初始化完畢 
             if ((as = counterCells) != null && (n = as.length) > 0) { 
                 // 【a1】對(duì)應(yīng)位置的CounterCell未創(chuàng)建 
                 if ((a = as[(n - 1) & h]) == null) { 
                     // cellsBusy其實(shí)是一個(gè)鎖，cellsBusy=0時(shí)表示無沖突 
                     if (cellsBusy == 0) {            // Try to attach new Cell 
                         // 創(chuàng)建新的CounterCell 
                         CounterCell r = new CounterCell(x); // Optimistic create 
                         // Double Check，加鎖（通過CAS將cellsBusy設(shè)置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) { 
                                     // 將新創(chuàng)建的CounterCell放入counterCells中 
                                     rs[j] = r; 
                                     created = true; 
                                 } 
                             } finally { 
                                 // 解鎖，這里為什么不用CAS？因?yàn)楫?dāng)前流程中需要在獲取鎖的前提下進(jìn)行，即串行執(zhí)行，因此不存在并發(fā)更新問題，只需要正常更新即可 
                                 cellsBusy = 0; 
                             } 
                             if (created) 
                                 break; 
                             // 創(chuàng)建失敗則重試 
                             continue;           // Slot is now non-empty 
                         } 
                     } 
                     // cellsBusy不為0，說明被其他線程爭(zhēng)搶到了鎖，還不能考慮擴(kuò)容 
                     collide = false; 
                 } 
                 //【a2】沖突檢測(cè) 
                 else if (!wasUncontended)       // CAS already known to fail 
                     // 調(diào)用方addCount中CAS更新cell失敗，有沖突，則繼續(xù)嘗試CAS 
                     wasUncontended = true;      // Continue after rehash 
  
                 //【a3】對(duì)應(yīng)位置的CounterCell不為空，直接CAS進(jìn)行更新 
                 else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) 
                     break; 
                 //【a4】容量限制 
                 else if (counterCells != as || n >= NCPU) 
                     // 說明counterCells容量的最大值為大于NCPU（實(shí)際機(jī)器CPU核心的數(shù)量）最小2的整數(shù)次冪。 
                     // 這里限制的意義在于，并發(fā)度是由CPU核心來決定，當(dāng)counterCells容量與CPU核心數(shù)量相等時(shí)，理論上講就算所有CPU核心都在同時(shí)運(yùn)行不同的計(jì)數(shù)線程時(shí)，都不應(yīng)該出現(xiàn)沖突，每個(gè)線程選擇各自的cell進(jìn)行處理即可。如果出現(xiàn)沖突，一定是哈希值的問題，因此采取的措施是重新計(jì)算哈希值（h = ThreadLocalRandom.advanceProbe(h)），而不是通過擴(kuò)容來解決 
  
                     // 當(dāng)n大于NCPU時(shí)后面的分支就不會(huì)走到了 
                     collide = false;            // At max size or stale 
                 // 【a5】更新擴(kuò)容標(biāo)志位 
                 else if (!collide) 
                     // 說明映射到cell位置不為空，并且嘗試進(jìn)行CAS更新時(shí)失敗了，則說明有競(jìng)爭(zhēng)，將collide設(shè)置為true，下次迭代時(shí)執(zhí)行后面的擴(kuò)容操作，降低競(jìng)爭(zhēng)度 
                     // 有競(jìng)爭(zhēng)時(shí)，執(zhí)行rehash+擴(kuò)容，當(dāng)容量大于CPU核心時(shí)則停止擴(kuò)容只進(jìn)行rehash 
                     collide = true; 
                 // 【a6】加鎖擴(kuò)容 
                 else if (cellsBusy == 0 && 
                          U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) { 
                     // 加鎖擴(kuò)容 
                     try { 
                         if (counterCells == as) {// Expand table unless stale 
                             // 擴(kuò)容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的設(shè)計(jì)很巧妙，它的背后其實(shí)就是JDK1.8中的LongAdder。核心思想是：在并發(fā)較低的場(chǎng)景下直接采用baseCount累加，否則結(jié)合counterCells，將不同的線程散列到不同的cell中進(jìn)行計(jì)算，盡可能地確保訪問資源的隔離，減少?zèng)_突。LongAdder相比較于AtomicLong中無腦CAS的策略，在高并發(fā)的場(chǎng)景下，能夠減少CAS重試的次數(shù)，提高計(jì)算效率。

六 結(jié)語

以上可能只是Java Map源碼中的冰山一角，但是基本包括了大部分的核心特性，涵蓋了我們?nèi)粘ｉ_發(fā)中的大部分場(chǎng)景。讀源碼跟讀書一樣，仿佛跨越了歷史長(zhǎng)河與作者進(jìn)行近距離對(duì)話，揣摩他的心思，學(xué)習(xí)他的思想并加以傳承。信息加工轉(zhuǎn)化為知識(shí)并運(yùn)用的過程是痛苦的，但是痛并快樂著。