引言
ConcurrentHashMap是線程安全並且高效的HashMap，在併發編程中經常可見它的使用，在開始分析它的高併發實現機制前，先講講廢話，看看它是如何被引入jdk的。
為什麼引入ConcurrentHashMap？
HashMap線程不安全，它的線程不安全主要發生在put等對HashEntry有直接寫操作的地方:
HashMap線程不安全操作源碼示例
從put操作的源碼不難看出，線程不安全主要可能發生在這兩個地方：
key已經存在，需要修改HashEntry對應的value； key不存在，在HashEntry中做插入。
Hashtable線程安全，但是效率低下：
Hashtable源碼示例.png
從Hashtable示例的源碼可以看出，Hashtable是用synchronized關鍵字來保證線程安全的，由於synchronized的機制是在同一時刻只能有一個線程操作，其他的線程阻塞或者輪詢等待，在線程競爭激烈的情況下，這種方式的效率會非常的低下。
注：小小的多嘴一句，Hashtable擴容的時候newSize = 2 * oldSize + 1，這個是常識性的點，但是由於整個jdk源碼封裝比較好，而且Hashtable效率低下，使用較少，貌似好多程序員都不太知道這一點。
ConcurrentHashMap的為什麼高效？
Hashtable低效主要是因為所有訪問Hashtable的線程都爭奪一把鎖。如果容器有很多把鎖，每一把鎖控制容器中的一部分數據，那麼當多個線程訪問容器裡的不同部分的數據時，線程之前就不會存在鎖的競爭，這樣就可以有效的提高併發的訪問效率。這也正是ConcurrentHashMap使用的分段鎖技術。將ConcurrentHashMap容器的數據分段存儲，每一段數據分配一個Segment（鎖），當線程佔用其中一個Segment時，其他線程可正常訪問其他段數據。 ConcurrentHashMap實現分析 在分析ConcurrentHashMap的源碼之前先來看看它的結構：
ConcurrentHashMap類圖
.從類圖可以看出：ConcurrentHashMap由Segment和HashEntry組成。
.Segment是可重入鎖，它在ConcurrentHashMap中扮演分離鎖的角色；
.HashEntry主要存儲鍵值對；
.CurrentHashMap包含一個Segment數組，每個Segment包含一個HashEntry數組並且守護它，當修改HashEntry數組數據時，需要先獲取它對應的Segment鎖；而HashEntry數組採用開鏈法處理衝突，所以它的每個HashEntry元素又是鏈表結構的元素。
ConcurrentHashMap結構圖
初始化ConcurrentHashMap
ConcurrentHashMap構造方法
可以看出，ConcurrentHashMap的構造方法都調用了public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)，初始化部分都由它來完成，我們來看一看它是怎麼來初始化ConcurrentHashMap的。
ConcurrentHashMap初始化具體實現
整個初始化是通過參數initialCapacity，loadFactor和concurrencyLevel來初始化segmentShift（段偏移量）、segmentMask（段掩碼）和segment數組。
ConcurrentHashMap初始化具體實現
計算segment數組長度
segment數組長度ssize是由concurrencyLevel計算得出，當ssize < concurrencyLevel時，ssize *= 2，至於為什麼一定要保證ssize是2的N次方是為了可以通過按位與來定位segment；
注：concurrencyLevel的最大值是65535，那麼，ssize的最大值就為65536，對應到二進制就是16位。
初始化segmentShift、segmentMask
segmentShift和segmentMask在定位segment使用，segmentShift = 32 - ssize向左移位的次數，segmentMask = ssize - 1。ssize的最大長度是65536，對應的 segmentShift最大值為16，segmentMask最大值是65535，對應的二進制16位全1；
初始化segment、
1、初始化每個segment的HashEntry長度；
2、創建segment數組和segment[0]。
注：HashEntry長度cap同樣也是2的N次方，默認情況，ssize = 16，initialCapacity = 16，loadFactor = 0.75f，那麼cap = 1，threshold = (int) cap * loadFactor = 0。
Segment定位
•Hash算法
ConcurrentHashMap使用分段鎖segment來保護數據，也就是說，在插入和讀取元素，需要先通過hash算法定位segment。ConcurrentHashMap使用了變種hash算法對元素的hashCode再散列。
ash算法
注：為什麼需要再散列？
再散列的目的是為了減少衝突，讓元素可以近似均勻的分佈在不同的Segment上，從而提升存儲效率。如果hash算法不好，最差的情況是所有的元素都在一個Segment中，這時候hash表將退化成鏈表，查詢插入的時間複雜度都會從理想的o(1)退化成o(n^2)，同時，分段鎖也會失去存在的意義。
Segment定位
默認情況下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二進制數，向右無符號移動28位，讓高4位參與位運算（& segmentMask）。
ConcurrentHashMap相關操作實現分析 主要分析ConcurrentHashMap常用的三個操作：get/put/size的具體實現。
get操作
get實現
1、根據key，計算出hashCode；
2、根據步驟1計算出的hashCode定位segment，如果segment不為null && segment.table也不為null，跳轉到步驟3，否則，返回null，該key所對應的value不存在；
3、根據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替換鎖的經典應用場景。
HashEntry value定義
put操作
ConcurrentHashMap提供兩個方法put和putIfAbsent來完成put操作，它們之間的區別在於put方法做插入時key存在會更新key所對應的value，而putIfAbsent不會更新。
put實現
put實現
1、參數校驗，value不能為null，為null時拋出NPE；
2、計算key的hashCode；
3、定位segment，如果segment不存在，創建新的segment；
4、調用segment的put方法在對應的segment做插入操作。
putIfAbsent實現
putIfAbsent實現
segment的put方法實現
segment的put方法是整個put操作的核心，它實現了在segment的HashEntry數組中做插入
（segment的HashEntry數組採用開鏈法來處理衝突）。
segment put實現
具體的執行流程如下：
1、獲取鎖，保證put操作的線程安全；
2、定位到HashEntry數組中具體的HashEntry；
3、遍歷HashEntry鏈表，假若待插入key已存在：
需要更新key所對應value（!onlyIfAbsent），更新oldValue -> newValue，跳轉到步驟5；
否則，直接跳轉到步驟5；
4、遍歷完HashEntry鏈表，key不存在，插入HashEntry節點，oldValue = null，跳轉到步驟5；
5、釋放鎖，返回oldValue。
步驟4在做插入的時候實際上經歷了兩個步驟：
第一：HashEntry數組擴容；
是否需要擴容
在插入元素前會先判斷Segment的HashEntry數組是否超過threshold，如果超過閥值，則需要對HashEntry數組擴容；
如何擴容
在擴容的時候，首先創建一個容量是原來容量兩倍的數組，將原數組的元素再散列後插入到新的數組裡。為了高效，ConcurrentHashMap只對某個Segment進行擴容，不會對整個容器擴容。
第二：定位添加元素對應的位置，然後將其放到HashEntry數組中。
size實現
如果需要統計整個ConcurrentHashMap的容量，需要統計所有Segment容量然後求和，Segment提供變量count用於存儲當前Segment的容量。但是ConcurrentHashMap為了保證線程安全，並不是直接把所有的Segment的count相加來得到整個容器的大小，我們來看看ConcurrentHashMap是怎麼來統計容量的。
默認情況下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二進制數，向右無符號移動28位，讓高4位參與位運算（& segmentMask）。
ConcurrentHashMap相關操作實現分析
主要分析ConcurrentHashMap常用的三個操作：get/put/size的具體實現。
get操作
1、根據key，計算出hashCode；
2、根據步驟1計算出的hashCode定位segment，如果segment不為null && segment.table也不為null，跳轉到步驟3，否則，返回null，該key所對應的value不存在；
3、根據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替換鎖的經典應用場景。
put操作
ConcurrentHashMap提供兩個方法put和putIfAbsent來完成put操作，它們之間的區別在於put方法做插入時key存在會更新key所對應的value，而putIfAbsent不會更新。
put實現
1、參數校驗，value不能為null，為null時拋出NPE；
2、計算key的hashCode；
3、定位segment，如果segment不存在，創建新的segment；
4、調用segment的put方法在對應的segment做插入操作。
segment的put方法實現
segment的put方法是整個put操作的核心，它實現了在segment的HashEntry數組中做插入
（segment的HashEntry數組採用開鏈法來處理衝突）。
具體的執行流程如下：
1、獲取鎖，保證put操作的線程安全；
2、定位到HashEntry數組中具體的HashEntry；
3、遍歷HashEntry鏈表，假若待插入key已存在：
需要更新key所對應value（!onlyIfAbsent），更新oldValue -> newValue，跳轉到步驟5；
否則，直接跳轉到步驟5；
4、遍歷完HashEntry鏈表，key不存在，插入HashEntry節點，oldValue = null，跳轉到步驟5；
5、釋放鎖，返回oldValue。
步驟4在做插入的時候實際上經歷了兩個步驟：
第一：HashEntry數組擴容；
是否需要擴容
在插入元素前會先判斷Segment的HashEntry數組是否超過threshold，如果超過閥值，則需要對HashEntry數組擴容；
如何擴容
在擴容的時候，首先創建一個容量是原來容量兩倍的數組，將原數組的元素再散列後插入到新的數組裡。為了高效，ConcurrentHashMap只對某個Segment進行擴容，不會對整個容器擴容。
第二：定位添加元素對應的位置，然後將其放到HashEntry數組中。
size實現
如果需要統計整個ConcurrentHashMap的容量，需要統計所有Segment容量然後求和，Segment 提供變量count用於存儲當前Segment的容量。但是ConcurrentHashMap為了保證線程安全，並不是直接把所有的Segment的count相加來得到整個容器的大小，我們來看看ConcurrentHashMap是怎麼來統計容量的。
由於在累加count的操作的過程中之前累加過的count發生變化的幾率非常小
所以ConcurrentHashMap先嚐試2次不鎖住Segment的方式來統計每個Segment的大小，如果在統計的過程中Segment的count發生了變化，這時候再加鎖統計Segment的count。
ConcurrentHashMap如何判斷統計過程中Segment的cout發生了變化？
Segment使用變量modCount來表示Segment大小是否發生變化，在put/remove/clean操作裡都會將modCount加1，那麼在統計size的前後只需要比較modCount是否發生了變化，如果發生變化，Segment的大小肯定發生了變化。
閱讀更多 程序猿的內心獨白 的文章
