引言

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

為什么引入ConcurrentHashMap？

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

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

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

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

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

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

Hashtable源碼示例.png

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

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

ConcurrentHashMap的為什么高效？

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

ConcurrentHashMap實現(xiàn)分析

在分析ConcurrentHashMap的源碼之前先來看看它的結構：

ConcurrentHashMap類圖

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

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

• HashEntry主要存儲鍵值對；

• CurrentHashMap包含一個Segment數(shù)組，每個Segment包含一個HashEntry數(shù)組并且守護它，當修改HashEntry數(shù)組數(shù)據(jù)時，需要先獲取它對應的Segment鎖；而HashEntry數(shù)組采用開鏈法處理沖突，所以它的每個HashEntry元素又是鏈表結構的元素。

由此可以得出ConcurrentHashMap的結構圖如下：

ConcurrentHashMap結構圖

初始化ConcurrentHashMap

ConcurrentHashMap構造方法

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

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

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

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

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

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

  注：concurrencyLevel的最大值是65535，那么，ssize的最大值就為65536，對應到二進制就是16位。

• 初始化segmentShift、segmentMask

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

• 初始化segment、

  1、初始化每個segment的HashEntry長度；

  2、創(chuàng)建segment數(shù)組和segment[0]。

  注：HashEntry長度cap同樣也是2的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再散列。

• 

ash算法

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

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

Segment定位

• 默認情況下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二進制數(shù)，向右無符號移動28位，讓高4位參與位運算（& segmentMask）。

ConcurrentHashMap相關操作實現(xiàn)分析

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

get操作

get實現(xiàn)

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

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

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

4、步驟3結束仍未找到key所對應的value，返回null，該key鎖對應的value不存在。

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

HashEntry value定義

put操作

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

put實現(xiàn)

put實現(xiàn)

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

2、計算key的hashCode；

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

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

putIfAbsent實現(xiàn)

putIfAbsent實現(xiàn)

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

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

segment put實現(xiàn)

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

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

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

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

• 需要更新key所對應value（!onlyIfAbsent），更新oldValue -> newValue，跳轉到步驟5；

• 否則，直接跳轉到步驟5；

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

5、釋放鎖，返回oldValue。

步驟4在做插入的時候實際上經(jīng)歷了兩個步驟：

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

• 是否需要擴容

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

• 如何擴容

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

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

• size實現(xiàn)

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

默認情況下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二進制數(shù)，向右無符號移動28位，讓高4位參與位運算（& segmentMask）。

ConcurrentHashMap相關操作實現(xiàn)分析

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

get操作

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

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

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

4、步驟3結束仍未找到key所對應的value，返回null，該key鎖對應的value不存在。

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

put操作

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

put實現(xiàn)

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

2、計算key的hashCode；

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

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

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

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

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

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

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

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

• 需要更新key所對應value（!onlyIfAbsent），更新oldValue -> newValue，跳轉到步驟5；

• 否則，直接跳轉到步驟5；

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

5、釋放鎖，返回oldValue。

步驟4在做插入的時候實際上經(jīng)歷了兩個步驟：

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

• 是否需要擴容

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

• 如何擴容

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

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

size實現(xiàn)

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

由于在累加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ā)生了變化。