引言

ConcurrentHashMap是線程安全并且高效的HashMap，在并發(fā)編程中經(jīng)?？梢娝氖褂?，在開始分析它的高并發(fā)實(shí)現(xiàn)機(jī)制前，先講講廢話，看看它是如何被引入jdk的。

為什么引入ConcurrentHashMap？

HashMap線程不安全，它的線程不安全主要發(fā)生在put等對(duì)HashEntry有直接寫操作的地方：

HashMap線程不安全操作源碼示例

從put操作的源碼不難看出，線程不安全主要可能發(fā)生在這兩個(gè)地方：

key已經(jīng)存在，需要修改HashEntry對(duì)應(yīng)的value；

key不存在，在HashEntry中做插入。

Hashtable線程安全，但是效率低下：

Hashtable源碼示例.png

從Hashtable示例的源碼可以看出，Hashtable是用synchronized關(guān)鍵字來保證線程安全的，由于synchronized的機(jī)制是在同一時(shí)刻只能有一個(gè)線程操作，其他的線程阻塞或者輪詢等待，在線程競爭激烈的情況下，這種方式的效率會(huì)非常的低下。

注：小小的多嘴一句，Hashtable擴(kuò)容的時(shí)候newSize = 2 * oldSize + 1，這個(gè)是常識(shí)性的點(diǎn)，但是由于整個(gè)jdk源碼封裝比較好，而且Hashtable效率低下，使用較少，貌似好多程序員都不太知道這一點(diǎn)。

ConcurrentHashMap的為什么高效？

Hashtable低效主要是因?yàn)樗性L問Hashtable的線程都爭奪一把鎖。如果容器有很多把鎖，每一把鎖控制容器中的一部分?jǐn)?shù)據(jù)，那么當(dāng)多個(gè)線程訪問容器里的不同部分的數(shù)據(jù)時(shí)，線程之前就不會(huì)存在鎖的競爭，這樣就可以有效的提高并發(fā)的訪問效率。這也正是ConcurrentHashMap使用的分段鎖技術(shù)。將ConcurrentHashMap容器的數(shù)據(jù)分段存儲(chǔ)，每一段數(shù)據(jù)分配一個(gè)Segment（鎖），當(dāng)線程占用其中一個(gè)Segment時(shí)，其他線程可正常訪問其他段數(shù)據(jù)。

ConcurrentHashMap實(shí)現(xiàn)分析

在分析ConcurrentHashMap的源碼之前先來看看它的結(jié)構(gòu)：

ConcurrentHashMap類圖

從類圖可以看出：ConcurrentHashMap由Segment和HashEntry組成。

• Segment是可重入鎖，它在ConcurrentHashMap中扮演分離鎖的角色；

• HashEntry主要存儲(chǔ)鍵值對(duì)；

• CurrentHashMap包含一個(gè)Segment數(shù)組，每個(gè)Segment包含一個(gè)HashEntry數(shù)組并且守護(hù)它，當(dāng)修改HashEntry數(shù)組數(shù)據(jù)時(shí)，需要先獲取它對(duì)應(yīng)的Segment鎖；而HashEntry數(shù)組采用開鏈法處理沖突，所以它的每個(gè)HashEntry元素又是鏈表結(jié)構(gòu)的元素。

由此可以得出ConcurrentHashMap的結(jié)構(gòu)圖如下：

ConcurrentHashMap結(jié)構(gòu)圖

初始化ConcurrentHashMap

ConcurrentHashMap構(gòu)造方法

可以看出，ConcurrentHashMap的構(gòu)造方法都調(diào)用了public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)，初始化部分都由它來完成，我們來看一看它是怎么來初始化ConcurrentHashMap的。

ConcurrentHashMap初始化具體實(shí)現(xiàn)

整個(gè)初始化是通過參數(shù)initialCapacity，loadFactor和concurrencyLevel來初始化segmentShift（段偏移量）、segmentMask（段掩碼）和segment數(shù)組。

ConcurrentHashMap初始化具體實(shí)現(xiàn)

• 計(jì)算segment數(shù)組長度

  segment數(shù)組長度ssize是由concurrencyLevel計(jì)算得出，當(dāng)ssize < concurrencylevel時(shí)，ssize="" *="">

  注：concurrencyLevel的最大值是65535，那么，ssize的最大值就為65536，對(duì)應(yīng)到二進(jìn)制就是16位。

• 初始化segmentShift、segmentMask

  segmentShift和segmentMask在定位segment使用，segmentShift = 32 - ssize向左移位的次數(shù)，segmentMask = ssize - 1。ssize的最大長度是65536，對(duì)應(yīng)的 segmentShift最大值為16，segmentMask最大值是65535，對(duì)應(yīng)的二進(jìn)制16位全1；

• 初始化segment、

  1、初始化每個(gè)segment的HashEntry長度；

  2、創(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來保護(hù)數(shù)據(jù)，也就是說，在插入和讀取元素，需要先通過hash算法定位segment。ConcurrentHashMap使用了變種hash算法對(duì)元素的hashCode再散列。

• 

ash算法

• 注：為什么需要再散列？

  再散列的目的是為了減少?zèng)_突，讓元素可以近似均勻的分布在不同的Segment上，從而提升存儲(chǔ)效率。如果hash算法不好，最差的情況是所有的元素都在一個(gè)Segment中，這時(shí)候hash表將退化成鏈表，查詢插入的時(shí)間復(fù)雜度都會(huì)從理想的o(1)退化成o(n^2)，同時(shí)，分段鎖也會(huì)失去存在的意義。

Segment定位

• 默認(rèn)情況下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二進(jìn)制數(shù)，向右無符號(hào)移動(dòng)28位，讓高4位參與位運(yùn)算（& segmentMask）。

ConcurrentHashMap相關(guān)操作實(shí)現(xiàn)分析

主要分析ConcurrentHashMap常用的三個(gè)操作：get/put/size的具體實(shí)現(xiàn)。

get操作

get實(shí)現(xiàn)

1、根據(jù)key，計(jì)算出hashCode；

2、根據(jù)步驟1計(jì)算出的hashCode定位segment，如果segment不為null && segment.table也不為null，跳轉(zhuǎn)到步驟3，否則，返回null，該key所對(duì)應(yīng)的value不存在；

3、根據(jù)hashCode定位table中對(duì)應(yīng)的hashEntry，遍歷hashEntry，如果key存在，返回key對(duì)應(yīng)的value；

4、步驟3結(jié)束仍未找到key所對(duì)應(yīng)的value，返回null，該key鎖對(duì)應(yīng)的value不存在。

比起Hashtable，ConcurrentHashMap的get操作高效之處在于整個(gè)get操作不需要加鎖。如果不加鎖，ConcurrentHashMap的get操作是如何做到線程安全的呢？原因是volatile，所有的value都定義成了volatile類型，volatile可以保證線程之間的可見性，這也是用volatile替換鎖的經(jīng)典應(yīng)用場景。

HashEntry value定義

put操作

ConcurrentHashMap提供兩個(gè)方法put和putIfAbsent來完成put操作，它們之間的區(qū)別在于put方法做插入時(shí)key存在會(huì)更新key所對(duì)應(yīng)的value，而putIfAbsent不會(huì)更新。

put實(shí)現(xiàn)

put實(shí)現(xiàn)

1、參數(shù)校驗(yàn)，value不能為null，為null時(shí)拋出NPE；

2、計(jì)算key的hashCode；

3、定位segment，如果segment不存在，創(chuàng)建新的segment；

4、調(diào)用segment的put方法在對(duì)應(yīng)的segment做插入操作。

putIfAbsent實(shí)現(xiàn)

putIfAbsent實(shí)現(xiàn)

segment的put方法實(shí)現(xiàn)

segment的put方法是整個(gè)put操作的核心，它實(shí)現(xiàn)了在segment的HashEntry數(shù)組中做插入（segment的HashEntry數(shù)組采用開鏈法來處理沖突）。

segment put實(shí)現(xiàn)

具體的執(zhí)行流程如下：

1、獲取鎖，保證put操作的線程安全；

2、定位到HashEntry數(shù)組中具體的HashEntry；

3、遍歷HashEntry鏈表，假若待插入key已存在：

• 需要更新key所對(duì)應(yīng)value（!onlyIfAbsent），更新oldValue -> newValue，跳轉(zhuǎn)到步驟5；

• 否則，直接跳轉(zhuǎn)到步驟5；

4、遍歷完HashEntry鏈表，key不存在，插入HashEntry節(jié)點(diǎn)，oldValue = null，跳轉(zhuǎn)到步驟5；

5、釋放鎖，返回oldValue。

步驟4在做插入的時(shí)候?qū)嶋H上經(jīng)歷了兩個(gè)步驟：

第一：HashEntry數(shù)組擴(kuò)容；

• 是否需要擴(kuò)容

  在插入元素前會(huì)先判斷Segment的HashEntry數(shù)組是否超過threshold，如果超過閥值，則需要對(duì)HashEntry數(shù)組擴(kuò)容；

• 如何擴(kuò)容

  在擴(kuò)容的時(shí)候，首先創(chuàng)建一個(gè)容量是原來容量兩倍的數(shù)組，將原數(shù)組的元素再散列后插入到新的數(shù)組里。為了高效，ConcurrentHashMap只對(duì)某個(gè)Segment進(jìn)行擴(kuò)容，不會(huì)對(duì)整個(gè)容器擴(kuò)容。

第二：定位添加元素對(duì)應(yīng)的位置，然后將其放到HashEntry數(shù)組中。

• size實(shí)現(xiàn)

  如果需要統(tǒng)計(jì)整個(gè)ConcurrentHashMap的容量，需要統(tǒng)計(jì)所有Segment容量然后求和，Segment提供變量count用于存儲(chǔ)當(dāng)前Segment的容量。但是ConcurrentHashMap為了保證線程安全，并不是直接把所有的Segment的count相加來得到整個(gè)容器的大小，我們來看看ConcurrentHashMap是怎么來統(tǒng)計(jì)容量的。

默認(rèn)情況下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二進(jìn)制數(shù)，向右無符號(hào)移動(dòng)28位，讓高4位參與位運(yùn)算（& segmentMask）。

ConcurrentHashMap相關(guān)操作實(shí)現(xiàn)分析

主要分析ConcurrentHashMap常用的三個(gè)操作：get/put/size的具體實(shí)現(xiàn)。

get操作

1、根據(jù)key，計(jì)算出hashCode；

2、根據(jù)步驟1計(jì)算出的hashCode定位segment，如果segment不為null && segment.table也不為null，跳轉(zhuǎn)到步驟3，否則，返回null，該key所對(duì)應(yīng)的value不存在；

3、根據(jù)hashCode定位table中對(duì)應(yīng)的hashEntry，遍歷hashEntry，如果key存在，返回key對(duì)應(yīng)的value；

4、步驟3結(jié)束仍未找到key所對(duì)應(yīng)的value，返回null，該key鎖對(duì)應(yīng)的value不存在。

比起Hashtable，ConcurrentHashMap的get操作高效之處在于整個(gè)get操作不需要加鎖。如果不加鎖，ConcurrentHashMap的get操作是如何做到線程安全的呢？原因是volatile，所有的value都定義成了volatile類型，volatile可以保證線程之間的可見性，這也是用volatile替換鎖的經(jīng)典應(yīng)用場景。

put操作

ConcurrentHashMap提供兩個(gè)方法put和putIfAbsent來完成put操作，它們之間的區(qū)別在于put方法做插入時(shí)key存在會(huì)更新key所對(duì)應(yīng)的value，而putIfAbsent不會(huì)更新。

put實(shí)現(xiàn)

1、參數(shù)校驗(yàn)，value不能為null，為null時(shí)拋出NPE；

2、計(jì)算key的hashCode；

3、定位segment，如果segment不存在，創(chuàng)建新的segment；

4、調(diào)用segment的put方法在對(duì)應(yīng)的segment做插入操作。

segment的put方法實(shí)現(xiàn)

segment的put方法是整個(gè)put操作的核心，它實(shí)現(xiàn)了在segment的HashEntry數(shù)組中做插入（segment的HashEntry數(shù)組采用開鏈法來處理沖突）。

具體的執(zhí)行流程如下：

1、獲取鎖，保證put操作的線程安全；

2、定位到HashEntry數(shù)組中具體的HashEntry；

3、遍歷HashEntry鏈表，假若待插入key已存在：

• 需要更新key所對(duì)應(yīng)value（!onlyIfAbsent），更新oldValue -> newValue，跳轉(zhuǎn)到步驟5；

• 否則，直接跳轉(zhuǎn)到步驟5；

4、遍歷完HashEntry鏈表，key不存在，插入HashEntry節(jié)點(diǎn)，oldValue = null，跳轉(zhuǎn)到步驟5；

5、釋放鎖，返回oldValue。

步驟4在做插入的時(shí)候?qū)嶋H上經(jīng)歷了兩個(gè)步驟：

第一：HashEntry數(shù)組擴(kuò)容；

• 是否需要擴(kuò)容

  在插入元素前會(huì)先判斷Segment的HashEntry數(shù)組是否超過threshold，如果超過閥值，則需要對(duì)HashEntry數(shù)組擴(kuò)容；

• 如何擴(kuò)容

  在擴(kuò)容的時(shí)候，首先創(chuàng)建一個(gè)容量是原來容量兩倍的數(shù)組，將原數(shù)組的元素再散列后插入到新的數(shù)組里。為了高效，ConcurrentHashMap只對(duì)某個(gè)Segment進(jìn)行擴(kuò)容，不會(huì)對(duì)整個(gè)容器擴(kuò)容。

第二：定位添加元素對(duì)應(yīng)的位置，然后將其放到HashEntry數(shù)組中。

size實(shí)現(xiàn)

如果需要統(tǒng)計(jì)整個(gè)ConcurrentHashMap的容量，需要統(tǒng)計(jì)所有Segment容量然后求和，Segment提供變量count用于存儲(chǔ)當(dāng)前Segment的容量。但是ConcurrentHashMap為了保證線程安全，并不是直接把所有的Segment的count相加來得到整個(gè)容器的大小，我們來看看ConcurrentHashMap是怎么來統(tǒng)計(jì)容量的。

由于在累加count的操作的過程中之前累加過的count發(fā)生變化的幾率非常小，所以ConcurrentHashMap先嘗試2次不鎖住Segment的方式來統(tǒng)計(jì)每個(gè)Segment的大小，如果在統(tǒng)計(jì)的過程中Segment的count發(fā)生了變化，這時(shí)候再加鎖統(tǒng)計(jì)Segment的count。

ConcurrentHashMap如何判斷統(tǒng)計(jì)過程中Segment的cout發(fā)生了變化？

Segment使用變量modCount來表示Segment大小是否發(fā)生變化，在put/remove/clean操作里都會(huì)將modCount加1，那么在統(tǒng)計(jì)size的前后只需要比較modCount是否發(fā)生了變化，如果發(fā)生變化，Segment的大小肯定發(fā)生了變化。