由于HashMap在并發(fā)中會出現(xiàn)一些問題，所以JDK中提供了并發(fā)容器ConcurrentHashMap。有關(guān)HashMap并發(fā)中的問題和原理，強(qiáng)烈建議查看這篇文章進(jìn)行復(fù)習(xí)。

ConcurrentHashMap使用分段鎖技術(shù)吧史，將整個數(shù)據(jù)結(jié)構(gòu)分段（默認(rèn)為16段）進(jìn)行存儲，然后給每一段數(shù)據(jù)配一把鎖（繼承ReentrantLock）唠雕，當(dāng)一個線程占用鎖訪問其中一個段的數(shù)據(jù)的時候贸营，其他段的數(shù)據(jù)仍然能被其他線程訪問，能夠?qū)崿F(xiàn)真正的并發(fā)訪問岩睁。下圖為JDK7的數(shù)據(jù)結(jié)構(gòu)钞脂。

ConcurrentHashMap使用分段鎖技術(shù)

JDK7的操作

JDK7的put過程

1. 首先對key進(jìn)行第1次hash，通過hash值確定segment的位置
2. 然后在segment內(nèi)進(jìn)行操作捕儒，獲取鎖
3. 獲取當(dāng)前segment的HashEntry數(shù)組后對key進(jìn)行第2次hash冰啃，通過hash值確定在HashEntry數(shù)組的索引位置
4. 通過繼承ReentrantLock的tryLock方法嘗試去獲取鎖，如果獲取成功就直接插入相應(yīng)的位置刘莹，如果已經(jīng)有線程獲取該Segment的鎖阎毅，那當(dāng)前線程會以自旋的方式去繼續(xù)的調(diào)用tryLock方法去獲取鎖，超過指定次數(shù)就掛起点弯，等待喚醒
5. 然后對當(dāng)前索引的HashEntry鏈進(jìn)行遍歷扇调，如果有重復(fù)的key，則替換抢肛；如果沒有重復(fù)的狼钮，則插入到鏈頭
6. 釋放鎖

get操作和put操作類似，也是要兩次hash捡絮。但是get操作的concurrenthashmap不需要加鎖燃领，原因是將存儲元素都標(biāo)記了volatile。要是不明白volatile锦援，歡迎復(fù)習(xí)這篇博客

JDK7的size過程

1. size操作就是遍歷了兩次所有的Segments，每次記錄Segment的modCount值剥悟，然后將兩次的modCount進(jìn)行比較灵寺，如果相同曼库，則表示期間沒有發(fā)生過寫入操作，就將原先遍歷的結(jié)果返回略板。
2. 如果經(jīng)判斷發(fā)現(xiàn)兩次統(tǒng)計(jì)出的modCount并不一致毁枯，要重新啟用全部segment加鎖的方式來進(jìn)行count的獲取和統(tǒng)計(jì)了，這樣在此期間每個segement都被鎖住叮称，無法進(jìn)行其他操作种玛，統(tǒng)計(jì)出的count自然很準(zhǔn)確。

在寫操作put瓤檐，remove赂韵，擴(kuò)容的時候，會對Segment加鎖挠蛉，只影響當(dāng)前Segment祭示，其他的Segment還是可以并發(fā)的

JDK8的優(yōu)化總結(jié)

JDK8的ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)已經(jīng)接近對應(yīng)版本的HashMap，了解Hashmap的結(jié)構(gòu)谴古，就基本了解了Concurrenthashmap了质涛，只是增加了同步的操作來控制并發(fā)。從JDK7版本的ReentrantLock+Segment+HashEntry掰担，到JDK8版本中synchronized+CAS+HashEntry+紅黑樹汇陆。

JDK8的ConcurrentHashMap

1. 數(shù)據(jù)結(jié)構(gòu)：取消了Segment分段鎖的數(shù)據(jù)結(jié)構(gòu)，取而代之的是Node數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)带饱，從而實(shí)現(xiàn)了對每一行數(shù)據(jù)進(jìn)行加鎖毡代，進(jìn)一步減少并發(fā)沖突的概率。

Node類成員變量Node的元素val和指針next都標(biāo)注volatile纠炮，目的是在多線程環(huán)境下線程A修改結(jié)點(diǎn)的val或者新增節(jié)點(diǎn)的時候是對線程B可見的月趟。

ConcurrentHashMap有成員變量transient volatile Node<K,V>[] table，目的是為了使Node數(shù)組在擴(kuò)容的時候?qū)ζ渌€程具有可見性而加的volatile恢口。（例如：volatile int array[10]是指array的地址是volatile的而不是數(shù)組元素的值是volatile的.）

2. 保證線程安全機(jī)制：JDK7采用segment的分段鎖機(jī)制實(shí)現(xiàn)線程安全孝宗，其中segment繼承自ReentrantLock。JDK8采用CAS(讀)+Synchronized(寫)保證線程安全耕肩。
3. 鎖的粒度：原來是對需要進(jìn)行數(shù)據(jù)操作的Segment加鎖因妇，JDK8調(diào)整為對每個數(shù)組元素加鎖（Node）。
4. 鏈表轉(zhuǎn)化為紅黑樹：定位結(jié)點(diǎn)的hash算法簡化會帶來弊端猿诸，Hash沖突加劇婚被，因此在鏈表節(jié)點(diǎn)數(shù)量大于8時，會將鏈表轉(zhuǎn)化為紅黑樹進(jìn)行存儲梳虽。
5. 查詢時間復(fù)雜度：從原來的遍歷鏈表O(n)址芯，變成遍歷紅黑樹O(logN)。
6. JDK8推薦使用mappingCount方法而不是size方法獲取當(dāng)前map表的大小，因?yàn)檫@個方法的返回值是long類型谷炸，size方法是返回值類型是int北专。

JDK8的get過程

1. 計(jì)算hash值，定位到該table索引位置旬陡，如果是首節(jié)點(diǎn)符合就返回
2. 如果遇到擴(kuò)容的時候拓颓，會調(diào)用標(biāo)志正在擴(kuò)容節(jié)點(diǎn)ForwardingNode的find方法，查找該節(jié)點(diǎn)描孟，匹配就返回
3. 以上都不符合的話驶睦，就往下遍歷節(jié)點(diǎn)，匹配就返回匿醒，否則最后就返回null

寫到這的時候场航，筆者建議大家去了解下Redis的漸進(jìn)式擴(kuò)容，是另一種思想青抛，都值得學(xué)習(xí)旗闽。一句話幫助理解Redis的漸進(jìn)式擴(kuò)容：由于Redis是單線程，而且數(shù)據(jù)量較大時蜜另，無法一次性快速擴(kuò)容适室，所以Redis首先申請一個新的容量加倍的哈希表，然后在插入举瑰，刪除捣辆，更新操作的時候，調(diào)用rehash函數(shù)（dictRehash函數(shù)）此迅，將原有操作單元的鏈表移植到新的哈希表中汽畴，當(dāng)原有哈希表全部移植過去，擴(kuò)容結(jié)束耸序。

JDK8的size過程

兩個重要變量：

1. baseCount用于記錄節(jié)點(diǎn)的個數(shù)忍些，是個volatile變量
2. counterCells是一個輔助baseCount計(jì)數(shù)的數(shù)組，每個counterCell存著部分的節(jié)點(diǎn)數(shù)量坎怪，這樣做的目的就是盡可能地減少沖突罢坝。

counterCell類使用了 @sun.misc.Contended 標(biāo)記的類，內(nèi)部一個 volatile變量搅窿。這個注解標(biāo)識著這個類需要避免 "偽共享".

避免偽共享(false sharing)嘁酿。緩存系統(tǒng)中是以緩存行（cache line）為單位存儲的。緩存行是2的整數(shù)冪個連續(xù)字節(jié)男应，
一般為32-256個字節(jié)闹司。最常見的緩存行大小是64個字節(jié)。當(dāng)多線程修改互相獨(dú)立的變量時沐飘，如果這些變量共享同一個緩存行游桩，就會無意中影響彼此的性能牲迫，這就是偽共享。所以偽共享對性能危害很大众弓。
沒有這個注解之前恩溅，是通過使用拼接把緩存行加滿來解決這個問題，讓緩存之間的修改互不影響谓娃。

ConcurrentHashMap節(jié)點(diǎn)的數(shù)量 = baseCount+counterCells每個cell記錄下來的節(jié)點(diǎn)數(shù)量

由于JDK8在統(tǒng)計(jì)這個數(shù)量的時候并沒有進(jìn)行加鎖，所以這個結(jié)果并不是絕對準(zhǔn)確的蜒滩。原理都是相通的滨达，可以順道看看LongAdder的longValue方法。想學(xué)習(xí)更多J.U.C的原子操作類俯艰，可以查看這篇博客

更新size的過程：

總體的原則就是：先嘗試更新baseCount捡遍，失敗再利用CounterCell。

1. 通過CAS嘗試更新baseCount 竹握，如果更新成功則完成画株，如果CAS更新失敗會進(jìn)入下一步
2. 線程通過隨機(jī)數(shù)ThreadLocalRandom.getProbe() & (n-1) 計(jì)算出在counterCells數(shù)組的位置，如果不為null啦辐，則CAS嘗試在couterCell上直接增加數(shù)量谓传，如果失敗，counterCells數(shù)組會進(jìn)行擴(kuò)容為原來的兩倍芹关，繼續(xù)隨機(jī)续挟，繼續(xù)添加

JDK8的put過程

對當(dāng)前的table進(jìn)行無條件自循環(huán)直到put成功

1. 如果沒有初始化就先調(diào)用initTable（）方法來進(jìn)行初始化過程
2. 如果沒有hash沖突就直接CAS插入
3. 如果還在進(jìn)行擴(kuò)容操作就先進(jìn)行擴(kuò)容
4. 如果存在hash沖突，就加synchronized鎖來保證線程安全侥衬，這里有兩種情況诗祸，一種是鏈表形式就直接遍歷到尾端插入，一種是紅黑樹就按照紅黑樹結(jié)構(gòu)插入轴总，
5. 最后一個如果該鏈表的數(shù)量大于閾值8直颅，就要先轉(zhuǎn)換成黑紅樹的結(jié)構(gòu)，break再一次進(jìn)入循環(huán)
6. 如果添加成功就調(diào)用addCount方法統(tǒng)計(jì)size怀樟，并且檢查是否需要擴(kuò)容

FAQ

ConcurrentHashMap迭代器是強(qiáng)一致性還是弱一致性功偿？

ConcurrentHashMap迭代器是弱一致性，hashmap迭代器是強(qiáng)一直性漂佩。

ConcurrentHashMap可以支持在迭代過程中脖含，向map添加新元素，而HashMap則拋出了ConcurrentModificationException投蝉，因?yàn)镠ashMap包含一個修改計(jì)數(shù)器养葵，當(dāng)你調(diào)用他的next()方法來獲取下一個元素時，迭代器將會用到這個計(jì)數(shù)器瘩缆。

ConcurrentHashMap一定線程安全么关拒？

ConcurrentHashMap使用不當(dāng)，也會造成死循環(huán)的。以后會有博客來介紹~

哎呀着绊，如果我的名片丟了谐算。微信搜索“全菜工程師小輝”，依然可以找到我