引言
ConcurrentHashMap是線程安全并且高效的HashMap诗力，在并發(fā)編程中經(jīng)尘悴。可見它的使用粱甫，在開始分析它的高并發(fā)實現(xiàn)機制前胜宇，先講講廢話耀怜，看看它是如何被引入jdk的。
為什么引入ConcurrentHashMap桐愉？
-
HashMap線程不安全财破，它的線程不安全主要發(fā)生在put等對HashEntry有直接寫操作的地方：
HashMap線程不安全操作源碼示例
從put操作的源碼不難看出，線程不安全主要可能發(fā)生在這兩個地方：
key已經(jīng)存在从诲，需要修改HashEntry對應(yīng)的value左痢；
key不存在，在HashEntry中做插入系洛。
-
Hashtable線程安全俊性，但是效率低下：
Hashtable源碼示例.png
從Hashtable示例的源碼可以看出，Hashtable是用synchronized關(guān)鍵字來保證線程安全的描扯，由于synchronized的機制是在同一時刻只能有一個線程操作磅废，其他的線程阻塞或者輪詢等待，在線程競爭激烈的情況下荆烈，這種方式的效率會非常的低下拯勉。
注：小小的多嘴一句竟趾，Hashtable擴容的時候newSize = 2 * oldSize + 1，這個是常識性的點宫峦，但是由于整個jdk源碼封裝比較好岔帽，而且Hashtable效率低下，使用較少导绷，貌似好多程序員都不太知道這一點犀勒。
ConcurrentHashMap的為什么高效？
Hashtable低效主要是因為所有訪問Hashtable的線程都爭奪一把鎖妥曲。如果容器有很多把鎖贾费，每一把鎖控制容器中的一部分?jǐn)?shù)據(jù)，那么當(dāng)多個線程訪問容器里的不同部分的數(shù)據(jù)時檐盟，線程之前就不會存在鎖的競爭褂萧，這樣就可以有效的提高并發(fā)的訪問效率。這也正是ConcurrentHashMap使用的分段鎖技術(shù)葵萎。將ConcurrentHashMap容器的數(shù)據(jù)分段存儲导犹，每一段數(shù)據(jù)分配一個Segment（鎖），當(dāng)線程占用其中一個Segment時羡忘，其他線程可正常訪問其他段數(shù)據(jù)谎痢。
ConcurrentHashMap實現(xiàn)分析
在分析ConcurrentHashMap的源碼之前先來看看它的結(jié)構(gòu)：
從類圖可以看出：ConcurrentHashMap由Segment和HashEntry組成。
Segment是可重入鎖卷雕，它在ConcurrentHashMap中扮演分離鎖的角色节猿；
HashEntry主要存儲鍵值對；
CurrentHashMap包含一個Segment數(shù)組漫雕，每個Segment包含一個HashEntry數(shù)組并且守護它沐批，當(dāng)修改HashEntry數(shù)組數(shù)據(jù)時，需要先獲取它對應(yīng)的Segment鎖蝎亚；而HashEntry數(shù)組采用開鏈法處理沖突，所以它的每個HashEntry元素又是鏈表結(jié)構(gòu)的元素先馆。
由此可以得出ConcurrentHashMap的結(jié)構(gòu)圖如下：
初始化ConcurrentHashMap
可以看出发框，ConcurrentHashMap的構(gòu)造方法都調(diào)用了public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)，初始化部分都由它來完成煤墙，我們來看一看它是怎么來初始化ConcurrentHashMap的梅惯。
ConcurrentHashMap初始化具體實現(xiàn)
整個初始化是通過參數(shù)initialCapacity，loadFactor和concurrencyLevel來初始化segmentShift（段偏移量）仿野、segmentMask（段掩碼）和segment數(shù)組铣减。
- 計算segment數(shù)組長度
segment數(shù)組長度ssize是由concurrencyLevel計算得出，當(dāng)ssize < concurrencyLevel時脚作，ssize *= 2葫哗，至于為什么一定要保證ssize是2的N次方是為了可以通過按位與來定位segment缔刹；
注：concurrencyLevel的最大值是65535，那么劣针，ssize的最大值就為65536校镐，對應(yīng)到二進制就是16位。
初始化segmentShift捺典、segmentMask
segmentShift和segmentMask在定位segment使用鸟廓，segmentShift = 32 - ssize向左移位的次數(shù)，segmentMask = ssize - 1襟己。ssize的最大長度是65536引谜，對應(yīng)的 segmentShift最大值為16，segmentMask最大值是65535擎浴，對應(yīng)的二進制16位全1员咽；-
初始化segment
- 初始化每個segment的HashEntry長度；
- 創(chuàng)建segment數(shù)組和segment[0]退客。
注：HashEntry長度cap同樣也是2的N次方骏融，默認(rèn)情況，ssize = 16萌狂，initialCapacity = 16档玻，loadFactor = 0.75f，那么cap = 1茫藏，threshold = (int) cap * loadFactor = 0误趴。
Segment定位
-
Hash算法
ConcurrentHashMap使用分段鎖segment來保護數(shù)據(jù)，也就是說务傲，在插入和讀取元素凉当，需要先通過hash算法定位segment。ConcurrentHashMap使用了變種hash算法對元素的hashCode再散列售葡。
Hash算法
注：為什么需要再散列看杭？
再散列的目的是為了減少沖突，讓元素可以近似均勻的分布在不同的Segment上挟伙，從而提升存儲效率楼雹。如果hash算法不好，最差的情況是所有的元素都在一個Segment中尖阔，這時候hash表將退化成鏈表贮缅，查詢插入的時間復(fù)雜度都會從理想的o(1)退化成o(n^2)，同時介却，分段鎖也會失去存在的意義谴供。
-
Segment定位
ConcurrentHashMap將hashCode進行位運算來定位具體的segment：
Segment定位
默認(rèn)情況下，segmentShift = 28齿坷， segmentMask = 15桂肌，hashCode最大是32位的二進制數(shù)数焊，向右無符號移動28位，讓高4位參與位運算（& segmentMask）轴或。
ConcurrentHashMap相關(guān)操作實現(xiàn)分析
主要分析ConcurrentHashMap常用的三個操作：get/put/size的具體實現(xiàn)昌跌。
-
get操作
get實現(xiàn)- 根據(jù)key，計算出hashCode照雁；
- 根據(jù)步驟1計算出的hashCode定位segment蚕愤，如果segment不為null && segment.table也不為null，跳轉(zhuǎn)到步驟3饺蚊，否則萍诱，返回null，該key所對應(yīng)的value不存在污呼；
- 根據(jù)hashCode定位table中對應(yīng)的hashEntry裕坊，遍歷hashEntry，如果key存在燕酷，返回key對應(yīng)的value籍凝；
- 步驟3結(jié)束仍未找到key所對應(yīng)的value，返回null苗缩，該key鎖對應(yīng)的value不存在饵蒂。
比起Hashtable，ConcurrentHashMap的get操作高效之處在于整個get操作不需要加鎖酱讶。如果不加鎖退盯，ConcurrentHashMap的get操作是如何做到線程安全的呢？原因是volatile泻肯，所有的value都定義成了volatile類型渊迁，volatile可以保證線程之間的可見性，這也是用volatile替換鎖的經(jīng)典應(yīng)用場景灶挟。
-
put操作
ConcurrentHashMap提供兩個方法put和putIfAbsent來完成put操作琉朽，它們之間的區(qū)別在于put方法做插入時key存在會更新key所對應(yīng)的value，而putIfAbsent不會更新稚铣。-
put實現(xiàn)
put實現(xiàn)- 參數(shù)校驗箱叁，value不能為null，為null時拋出NPE榛泛；
- 計算key的hashCode；
- 定位segment噩斟，如果segment不存在曹锨，創(chuàng)建新的segment；
- 調(diào)用segment的put方法在對應(yīng)的segment做插入操作剃允。
-
putIfAbsent實現(xiàn)
putIfAbsent實現(xiàn)
putIfAbsent的執(zhí)行過程與put方法是一致的沛简，除了最后調(diào)用的segment的put方法參數(shù)onlyIfAbsent傳參不一樣齐鲤。
segment的put方法實現(xiàn)
segment的put方法是整個put操作的核心，它實現(xiàn)了在segment的HashEntry數(shù)組中做插入（segment的HashEntry數(shù)組采用開鏈法來處理沖突）椒楣。
segment put實現(xiàn)
具體的執(zhí)行流程如下：- 獲取鎖给郊，保證put操作的線程安全；
- 定位到HashEntry數(shù)組中具體的HashEntry捧灰；
- 遍歷HashEntry鏈表淆九，假若待插入key已存在：
- 需要更新key所對應(yīng)value（!onlyIfAbsent），更新oldValue -> newValue毛俏，跳轉(zhuǎn)到步驟5炭庙；
- 否則，直接跳轉(zhuǎn)到步驟5煌寇；
- 遍歷完HashEntry鏈表焕蹄，key不存在，插入HashEntry節(jié)點阀溶，oldValue = null腻脏，跳轉(zhuǎn)到步驟5；
- 釋放鎖银锻，返回oldValue永品。
步驟4在做插入的時候?qū)嶋H上經(jīng)歷了兩個步驟：
- 第一：HashEntry數(shù)組擴容；
- 是否需要擴容
在插入元素前會先判斷Segment的HashEntry數(shù)組是否超過threshold徒仓，如果超過閥值腐碱，則需要對HashEntry數(shù)組擴容； - 如何擴容
在擴容的時候掉弛，首先創(chuàng)建一個容量是原來容量兩倍的數(shù)組症见，將原數(shù)組的元素再散列后插入到新的數(shù)組里。為了高效殃饿，ConcurrentHashMap只對某個Segment進行擴容谋作，不會對整個容器擴容。
- 是否需要擴容
- 第二：定位添加元素對應(yīng)的位置乎芳，然后將其放到HashEntry數(shù)組中遵蚜。
-
-
size實現(xiàn)
如果需要統(tǒng)計整個ConcurrentHashMap的容量，需要統(tǒng)計所有Segment容量然后求和奈惑，Segment提供變量count用于存儲當(dāng)前Segment的容量吭净。但是ConcurrentHashMap為了保證線程安全，并不是直接把所有的Segment的count相加來得到整個容器的大小肴甸，我們來看看ConcurrentHashMap是怎么來統(tǒng)計容量的寂殉。
size實現(xiàn)
由于在累加count的操作的過程中之前累加過的count發(fā)生變化的幾率非常小，所以ConcurrentHashMap先嘗試2次不鎖住Segment的方式來統(tǒng)計每個Segment的大小原在，如果在統(tǒng)計的過程中Segment的count發(fā)生了變化友扰，這時候再加鎖統(tǒng)計Segment的count彤叉。
ConcurrentHashMap如何判斷統(tǒng)計過程中Segment的cout發(fā)生了變化？
Segment使用變量modCount來表示Segment大小是否發(fā)生變化村怪，在put/remove/clean操作里都會將modCount加1秽浇，那么在統(tǒng)計size的前后只需要比較modCount是否發(fā)生了變化，如果發(fā)生變化甚负，Segment的大小肯定發(fā)生了變化柬焕。
