ConcurrentHashMap的初步使用及場景
CHM的使用
ConcurrentHashMap是J.U.C包里面提供的一個線程安全并且高效的HashMap，所以ConcurrentHashMap在并發(fā)編程的場景中使用的頻率比較高，那么這一節(jié)課我們就從ConcurrentHashMap的使用上以及源碼層面來分析ConcurrentHashMap到底是如何實現(xiàn)安全性的
api使用
ConcurrentHashMap是Map的派生類，所以api基本和Hashmap是類似，主要就是put、get這些方法，接下來基于ConcurrentHashMap的put和get這兩個方法作為切入點來分析ConcurrentHashMap的源碼實現(xiàn)
ConcurrentHashMap的源碼分析
先要做一個說明，這節(jié)課分析的ConcurrentHashMap是基于Jdk1.8的版本。
JDK1.7和Jdk1.8版本的變化
ConcurrentHashMap和HashMap的實現(xiàn)原理是差不多的，但是因為ConcurrentHashMap需要支持并發(fā)操作，所以在實現(xiàn)上要比hashmap稍微復(fù)雜一些。
在JDK1.7的實現(xiàn)上，ConrruentHashMap由一個個Segment組成，簡單來說，ConcurrentHashMap是一個Segment數(shù)組，它通過繼承ReentrantLock來進行加鎖，通過每次鎖住一個segment來保證每個segment內(nèi)的操作的線程安全性從而實現(xiàn)全局線程安全。整個結(jié)構(gòu)圖如下
當(dāng)每個操作分布在不同的segment上的時候，默認情況下，理論上可以同時支持16個線程的并發(fā)寫入。
相比于1.7版本，它做了兩個改進
- 取消了segment分段設(shè)計，直接使用Node數(shù)組來保存數(shù)據(jù)，并且采用Node數(shù)組元素作為鎖來實現(xiàn)每一行數(shù)據(jù)進行加鎖來進一步減少并發(fā)沖突的概率
- 將原本數(shù)組+單向鏈表的數(shù)據(jù)結(jié)構(gòu)變更為了數(shù)組+單向鏈表+紅黑樹的結(jié)構(gòu)。為什么要引入紅黑樹呢？在正常情況下，key hash之后如果能夠很均勻的分散在數(shù)組中，那么table數(shù)組中的每個隊列的長度主要為0或者1.但是實際情況下，還是會存在一些隊列長度過長的情況。如果還采用單向列表方式，那么查詢某個節(jié)點的時間復(fù)雜度就變?yōu)镺(n); 因此對于隊列長度超過8的列表，JDK1.8采用了紅黑樹的結(jié)構(gòu)，那么查詢的時間復(fù)雜度就會降低到O(logN),可以提升查找的性能；
這個結(jié)構(gòu)和JDK1.8版本中的Hashmap的實現(xiàn)結(jié)構(gòu)基本一致，但是為了保證線程安全性，ConcurrentHashMap的實現(xiàn)會稍微復(fù)雜一下。接下來我們從源碼層面來了解一下它的原理.
我們基于put和get方法來分析它的實現(xiàn)即可
put方法第一階段
假如在上面這段代碼中存在兩個線程，在不加鎖的情況下：線程A成功執(zhí)行casTabAt操作后，隨后的線程B可以通過tabAt方法立刻看到table[i]的改變。原因如下：線程A的casTabAt操作，具有volatile讀寫相同的內(nèi)存語義，根據(jù)volatile的happens-before規(guī)則：線程A的casTabAt操作，一定對線程B的tabAt操作可見
initTable
數(shù)組初始化方法，這個方法比較簡單，就是初始化一個合適大小的數(shù)組
sizeCtl這個要單獨說一下，如果沒搞懂這個屬性的意義，可能會被搞暈
這個標(biāo)志是在Node數(shù)組初始化或者擴容的時候的一個控制位標(biāo)識，負數(shù)代表正在進行初始化或者擴容操作
-1 代表正在初始化
-N 代表有N-1有二個線程正在進行擴容操作，這里不是簡單的理解成n個線程，sizeCtl就是-N,這塊后續(xù)在講擴容的時候會說明
0標(biāo)識Node數(shù)組還沒有被初始化，正數(shù)代表初始化或者下一次擴容的大小
tabAt
該方法獲取對象中offset偏移地址對應(yīng)的對象field的值。實際上這段代碼的含義等價于tab[i], 但是為什么不直接使用tab[i]來計算呢？
getObjectVolatile，一旦看到volatile關(guān)鍵字，就表示可見性。因為對volatile寫操作happen-before于volatile讀操作，因此其他線程對table的修改均對get讀取可見；
雖然table數(shù)組本身是增加了volatile屬性，但是“volatile的數(shù)組只針對數(shù)組的引用具有volatile的語義，而不是它的元素”。 所以如果有其他線程對這個數(shù)組的元素進行寫操作，那么當(dāng)前線程來讀的時候不一定能讀到最新的值。
出于性能考慮，Doug Lea直接通過Unsafe類來對table進行操作。
圖解分析
put方法第二階段
在putVal方法執(zhí)行完成以后，會通過addCount來增加ConcurrentHashMap中的元素個數(shù)，并且還會可能觸發(fā)擴容操作。這里會有兩個非常經(jīng)典的設(shè)計
- 高并發(fā)下的擴容
- 如何保證addCount的數(shù)據(jù)安全性以及性能
addCount
在putVal最后調(diào)用addCount的時候，傳遞了兩個參數(shù)，分別是1和binCount(鏈表長度)，看看addCount方法里面做了什么操作
x表示這次需要在表中增加的元素個數(shù)，check參數(shù)表示是否需要進行擴容檢查，大于等于0都需要進行檢查
CounterCells解釋
ConcurrentHashMap是采用CounterCell數(shù)組來記錄元素個數(shù)的，像一般的集合記錄集合大小，直接定義一個size的成員變量即可，當(dāng)出現(xiàn)改變的時候只要更新這個變量就行。為什么ConcurrentHashMap要用這種形式來處理呢？
問題還是處在并發(fā)上，ConcurrentHashMap是并發(fā)集合，如果用一個成員變量來統(tǒng)計元素個數(shù)的話，為了保證并發(fā)情況下共享變量的的難全興，勢必會需要通過加鎖或者自旋來實現(xiàn)，如果競爭比較激烈的情況下，size的設(shè)置上會出現(xiàn)比較大的沖突反而影響了性能，所以在ConcurrentHashMap采用了分片的方法來記錄大小，具體什么意思，我們來分析下
fullAddCount源碼分析
fullAddCount主要是用來初始化CounterCell，來記錄元素個數(shù)，里面包含擴容，初始化等操作
初始化CounterCells數(shù)組
CounterCells初始化圖解
初始化長度為2的數(shù)組，然后隨機得到指定的一個數(shù)組下標(biāo)，將需要新增的值加入到對應(yīng)下標(biāo)位置處
transfer擴容階段
判斷是否需要擴容，也就是當(dāng)更新后的鍵值對總數(shù)baseCount >= 閾值sizeCtl時，進行rehash，這里面會有兩個邏輯。
- 如果當(dāng)前正在處于擴容階段，則當(dāng)前線程會加入并且協(xié)助擴容
- 如果當(dāng)前沒有在擴容，則直接觸發(fā)擴容操作
resizeStamp
這塊邏輯要理解起來，也有一點復(fù)雜。
resizeStamp用來生成一個和擴容有關(guān)的擴容戳，具體有什么作用呢？我們基于它的實現(xiàn)來做一個分析
transfer
擴容是ConcurrentHashMap的精華之一，擴容操作的核心在于數(shù)據(jù)的轉(zhuǎn)移，在單線程環(huán)境下數(shù)據(jù)的轉(zhuǎn)移很簡單，無非就是把舊數(shù)組中的數(shù)據(jù)遷移到新的數(shù)組。但是這在多線程環(huán)境下，在擴容的時候其他線程也可能正在添加元素，這時又觸發(fā)了擴容怎么辦？可能大家想到的第一個解決方案是加互斥鎖，把轉(zhuǎn)移過程鎖住，雖然是可行的解決方案，但是會帶來較大的性能開銷。因為互斥鎖會導(dǎo)致所有訪問臨界區(qū)的線程陷入到阻塞狀態(tài)，持有鎖的線程耗時越長，其他競爭線程就會一直被阻塞，導(dǎo)致吞吐量較低。而且還可能導(dǎo)致死鎖。
而ConcurrentHashMap并沒有直接加鎖，而是采用CAS實現(xiàn)無鎖的并發(fā)同步策略，最精華的部分是它可以利用多線程來進行協(xié)同擴容
簡單來說，它把Node數(shù)組當(dāng)作多個線程之間共享的任務(wù)隊列，然后通過維護一個指針來劃分每個線程鎖負責(zé)的區(qū)間，每個線程通過區(qū)間逆向遍歷來實現(xiàn)擴容，一個已經(jīng)遷移完的bucket會被替換為一個ForwardingNode節(jié)點，標(biāo)記當(dāng)前bucket已經(jīng)被其他線程遷移完了。接下來分析一下它的源碼實現(xiàn)
1、fwd:這個類是個標(biāo)識類，用于指向新表用的，其他線程遇到這個類會主動跳過這個類，因為這個類要么就是擴容遷移正在進行，要么就是已經(jīng)完成擴容遷移，也就是這個類要保證線程安全，再進行操作。
2、advance:這個變量是用于提示代碼是否進行推進處理，也就是當(dāng)前桶處理完，處理下一個桶的標(biāo)識
3、finishing:這個變量用于提示擴容是否結(jié)束用的
擴容過程圖解
ConcurrentHashMap支持并發(fā)擴容，實現(xiàn)方式是，把Node數(shù)組進行拆分，讓每個線程處理自己的區(qū)域，假設(shè)table數(shù)組總長度是64，默認情況下，那么每個線程可以分到16個bucket。
然后每個線程處理的范圍，按照倒序來做遷移
通過for自循環(huán)處理每個槽位中的鏈表元素，默認advace為真，通過CAS設(shè)置transferIndex屬性值，并初始化i和bound值，i指當(dāng)前處理的槽位序號，bound指需要處理的槽位邊界，先處理槽位31的節(jié)點； （bound,i） =(16,31) 從31的位置往前推動。
假設(shè)這個時候ThreadA在進行transfer，那么邏輯圖表示如下
在當(dāng)前假設(shè)條件下，槽位15中沒有節(jié)點，則通過CAS插入在第二步中初始化的ForwardingNode節(jié)點，用于告訴其它線程該槽位已經(jīng)處理過了；
sizeCtl擴容退出機制
在擴容操作transfer的第2414行，代碼如下
高低位原理分析
ConcurrentHashMap在做鏈表遷移時，會用高低位來實現(xiàn)，這里有兩個問題要分析一下
如何實現(xiàn)高低位鏈表的區(qū)分 假如我們有這樣一個隊列
第14個槽位插入新節(jié)點之后，鏈表元素個數(shù)已經(jīng)達到了8，且數(shù)組長度為16，優(yōu)先通過擴容來緩解鏈表過長的問題，擴容這塊的圖解稍后再分析，先分析高低位擴容的原理
假如當(dāng)前線程正在處理槽位為14的節(jié)點，它是一個鏈表結(jié)構(gòu)，在代碼中，首先定義兩個變量節(jié)點ln和hn，實際就是lowNode和HighNode，分別保存hash值的第x位為0和不等于0的節(jié)點
通過fn&n可以把這個鏈表中的元素分為兩類，A類是hash值的第X位為0，B類是hash值的第x位為不等于0（至于為什么要這么區(qū)分，稍后分析），并且通過lastRun記錄最后要處理的節(jié)點。最終要達到的目的是，A類的鏈表保持位置不動，B類的鏈表為14+16(擴容增加的長度)=30
我們把14槽位的鏈表單獨伶出來，我們用藍色表示 fn&n=0的節(jié)點，假如鏈表的分類是這樣
接著，通過CAS操作，把hn鏈放在i+n也就是14+16的位置，ln鏈保持原來的位置不動。并且設(shè)置當(dāng)前節(jié)點為fwd，表示已經(jīng)被當(dāng)前線程遷移完了
遷移完成以后的數(shù)據(jù)分布如下
為什么要做高低位的劃分
要想了解這么設(shè)計的目的，我們需要從ConcurrentHashMap的根據(jù)下標(biāo)獲取對象的算法來看，在putVal方法中1018行
擴容結(jié)束以后的退出機制
如果線程擴容結(jié)束，那么需要退出，就會執(zhí)行transfer方法的如下代碼
put方法第三階段
如果對應(yīng)的節(jié)點存在，判斷這個節(jié)點的hash是不是等于MOVED(-1)，說明當(dāng)前節(jié)點是ForwardingNode節(jié)點，
意味著有其他線程正在進行擴容，那么當(dāng)前現(xiàn)在直接幫助它進行擴容，因此調(diào)用helpTransfer方法
put方法第四階段
這個方法的主要作用是，如果被添加的節(jié)點的位置已經(jīng)存在節(jié)點的時候，需要以鏈表的方式加入到節(jié)點中
如果當(dāng)前節(jié)點已經(jīng)是一顆紅黑樹，那么就會按照紅黑樹的規(guī)則將當(dāng)前節(jié)點加入到紅黑樹中
put方法第五個階段
判斷鏈表的長度是否已經(jīng)達到臨界值8. 如果達到了臨界值，這個時候會根據(jù)當(dāng)前數(shù)組的長度來決定是擴容還是將鏈表轉(zhuǎn)化為紅黑樹。也就是說如果當(dāng)前數(shù)組的長度小于64，就會先擴容。否則，會把當(dāng)前鏈表轉(zhuǎn)化為紅黑樹
treeifyBin
在putVal的最后部分，有一個判斷，如果鏈表長度大于8，那么就會觸發(fā)擴容或者紅黑樹的轉(zhuǎn)化操作。
tryPresize
tryPresize里面部分代碼和addCount的部分代碼類似，看起來會稍微簡單一些
文章中涉及到的技術(shù)點我都分享在Java架構(gòu)社區(qū) 142019080 里，錄制成視頻供大家免費下載，希望可以幫助在這個行業(yè)發(fā)展的朋友和童鞋們，在論壇博客等地方少花些時間找資料，把有限的時間，真正花在學(xué)習(xí)上，所以我把這些資料，分享出來。相信對于已經(jīng)工作和遇到技術(shù)瓶頸或者寫博客碼友，在這份資料中一定都有你需要的內(nèi)容。
