我們上節(jié)講了HashMap，實(shí)際上HashMap并不是線(xiàn)程安全的，在并發(fā)插入元素的時(shí)候有可能出現(xiàn)環(huán)形鏈表，讓下一次讀操作出現(xiàn)死循環(huán)。解決的辦法就是使用線(xiàn)程安全的容器，除了Collections提供的synchronizedMap同步容器外，實(shí)際上我們還可以選擇性能更好的juc提供的同步容器。
一、分段鎖Segment概述
分段鎖Segment是ConcurrentHashMap很重要的一個(gè)概念。
Segment本身就相當(dāng)于一個(gè)HashMap對(duì)象。
同HashMap一樣，Segment包含一個(gè)HashEntry數(shù)組，數(shù)組中的每一個(gè)HashEntry既是一個(gè)鍵值對(duì)，也是一個(gè)鏈表的頭節(jié)點(diǎn)。
像這樣的Segment對(duì)象，在ConcurrentHashMap集合中有2的N次方個(gè)，共同保存在一個(gè)名為segments的數(shù)組當(dāng)中。
因此整個(gè)ConcurrentHashMap的結(jié)構(gòu)如下：
可以說(shuō)，ConcurrentHashMap是一個(gè)二級(jí)哈希表。在一個(gè)總的哈希表下面，有若干個(gè)子哈希表。
這樣的二級(jí)結(jié)構(gòu)，和數(shù)據(jù)庫(kù)的水平拆分有些相似。每一個(gè)Segment就好比一個(gè)高度自治的自治區(qū)。讀寫(xiě)高度自治，Segment之間互不影響。
這種結(jié)構(gòu)下的ConcurrentHashMap有以下特點(diǎn)：
- 不同Segment的寫(xiě)入是可以并發(fā)執(zhí)行的。
- 同一Segment的寫(xiě)和讀是可以并發(fā)執(zhí)行的。
- 對(duì)同一Segment的并發(fā)寫(xiě)入會(huì)被阻塞。
由此可見(jiàn)，ConcurrentHashMap當(dāng)中每個(gè)Segment各自持有一把鎖。在保證線(xiàn)程安全的同時(shí)降低了鎖的粒度，讓并發(fā)操作效率更高。
二、ConcurrentHashMap讀寫(xiě)概述
Get方法：
1.為輸入的Key做Hash運(yùn)算，得到hash值。
2.通過(guò)hash值，定位到對(duì)應(yīng)的Segment對(duì)象
3.再次通過(guò)hash值，定位到Segment當(dāng)中數(shù)組的具體位置。
Put方法：
1.為輸入的Key做Hash運(yùn)算，得到hash值。
2.通過(guò)hash值，定位到對(duì)應(yīng)的Segment對(duì)象
3.獲取可重入鎖
4.再次通過(guò)hash值，定位到Segment當(dāng)中數(shù)組的具體位置。
5.插入或覆蓋HashEntry對(duì)象。
6.釋放鎖。
從以上步驟可以看出，ConcurrentHashMap在讀寫(xiě)時(shí)都需要兩次定位（Hash）操作。
三、ConcurrentHashMap的size()方法
Size方法的目的是統(tǒng)計(jì)ConcurrentHashMap的總元素?cái)?shù)量， 自然需要把各個(gè)Segment內(nèi)部的元素?cái)?shù)量匯總起來(lái)。
但是，如果在統(tǒng)計(jì)Segment元素?cái)?shù)量的過(guò)程中，已統(tǒng)計(jì)過(guò)的Segment瞬間插入新的元素，這時(shí)候該怎么辦呢？
ConcurrentHashMap的Size方法是一個(gè)嵌套循環(huán)，大體邏輯如下：
1.遍歷所有的Segment。
2.把Segment的元素?cái)?shù)量累加起來(lái)。
3.把Segment的修改次數(shù)累加起來(lái)。
4.判斷所有Segment的總修改次數(shù)是否大于上一次的總修改次數(shù)。如果大于，說(shuō)明統(tǒng)計(jì)過(guò)程中有修改，重新統(tǒng)計(jì)，嘗試次數(shù)+1；如果不是。說(shuō)明沒(méi)有修改，統(tǒng)計(jì)結(jié)束。
5.如果嘗試次數(shù)超過(guò)閾值，則對(duì)每一個(gè)Segment加鎖，再重新統(tǒng)計(jì)。
6.再次判斷所有Segment的總修改次數(shù)是否大于上一次的總修改次數(shù)。由于已經(jīng)加鎖，次數(shù)一定和上次相等。
7.釋放鎖，統(tǒng)計(jì)結(jié)束。
這種思想和樂(lè)觀(guān)鎖悲觀(guān)鎖的思想如出一轍。
為了盡量不鎖住所有Segment，首先樂(lè)觀(guān)地假設(shè)Size過(guò)程中不會(huì)有修改。當(dāng)嘗試一定次數(shù)，才無(wú)奈轉(zhuǎn)為悲觀(guān)鎖，鎖住所有Segment保證強(qiáng)一致性。
參考文章
本文作者： catalinaLi
本文鏈接： http://catalinali.top/2018/knowConHashMap/
