引言
ConcurrentHashMap是線程安全并且高效的HashMap，在并發(fā)編程中經(jīng)?？梢娝氖褂茫陂_始分析它的高并發(fā)實(shí)現(xiàn)機(jī)制前，先講講廢話，看看它是如何被引入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的機(jī)制是在同一時刻只能有一個線程操作，其他的線程阻塞或者輪詢等待，在線程競爭激烈的情況下，這種方式的效率會非常的低下。
?注：小小的多嘴一句，Hashtable擴(kuò)容的時候newSize = 2 * oldSize + 1，這個是常識性的點(diǎn)，但是由于整個jdk源碼封裝比較好，而且Hashtable效率低下，使用較少，貌似好多程序員都不太知道這一點(diǎn)。
?ConcurrentHashMap的為什么高效？
?Hashtable低效主要是因?yàn)樗性L問Hashtable的線程都爭奪一把鎖。如果容器有很多把鎖，每一把鎖控制容器中的一部分?jǐn)?shù)據(jù)，那么當(dāng)多個線程訪問容器里的不同部分的數(shù)據(jù)時，線程之前就不會存在鎖的競爭，這樣就可以有效的提高并發(fā)的訪問效率。這也正是ConcurrentHashMap使用的分段鎖技術(shù)。將ConcurrentHashMap容器的數(shù)據(jù)分段存儲，每一段數(shù)據(jù)分配一個Segment（鎖），當(dāng)線程占用其中一個Segment時，其他線程可正常訪問其他段數(shù)據(jù)。 ConcurrentHashMap實(shí)現(xiàn)分析 在分析ConcurrentHashMap的源碼之前先來看看它的結(jié)構(gòu)：
ConcurrentHashMap類圖
??? .從類圖可以看出：ConcurrentHashMap由Segment和HashEntry組成。
?? ?.Segment是可重入鎖，它在ConcurrentHashMap中扮演分離鎖的角色；
?? .HashEntry主要存儲鍵值對；
??? .CurrentHashMap包含一個Segment數(shù)組，每個Segment包含一個HashEntry數(shù)組并且守護(hù)它，當(dāng)修改HashEntry數(shù)組數(shù)據(jù)時，需要先獲取它對應(yīng)的Segment鎖；而HashEntry數(shù)組采用開鏈法處理沖突，所以它的每個HashEntry元素又是鏈表結(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)
整個初始化是通過參數(shù)initialCapacity，loadFactor和concurrencyLevel來初始化segmentShift（段偏移量）、segmentMask（段掩碼）和segment數(shù)組。
?ConcurrentHashMap初始化具體實(shí)現(xiàn)
計(jì)算segment數(shù)組長度
segment數(shù)組長度ssize是由concurrencyLevel計(jì)算得出，當(dāng)ssize < concurrencyLevel時，ssize *= 2，至于為什么一定要保證ssize是2的N次方是為了可以通過按位與來定位segment；
注：concurrencyLevel的最大值是65535，那么，ssize的最大值就為65536，對應(yīng)到二進(jìn)制就是16位。
初始化segmentShift、segmentMask
segmentShift和segmentMask在定位segment使用，segmentShift = 32 - ssize向左移位的次數(shù)，segmentMask = ssize - 1。ssize的最大長度是65536，對應(yīng)的 segmentShift最大值為16，segmentMask最大值是65535，對應(yīng)的二進(jìn)制16位全1；
初始化segment、
1、初始化每個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算法對元素的hashCode再散列。
ash算法
注：為什么需要再散列？
再散列的目的是為了減少沖突，讓元素可以近似均勻的分布在不同的Segment上，從而提升存儲效率。如果hash算法不好，最差的情況是所有的元素都在一個Segment中，這時候hash表將退化成鏈表，查詢插入的時間復(fù)雜度都會從理想的o(1)退化成o(n^2)，同時，分段鎖也會失去存在的意義。
可以加群找我要課堂鏈接哦
注意：是免費(fèi)的 沒有開發(fā)經(jīng)驗(yàn)誤入哦
1、具有1-5工作經(jīng)驗(yàn)的，面對目前流行的技術(shù)不知從何下手，需要突破技術(shù)瓶頸的。
2、在公司待久了，過得很安逸，但跳槽時面試碰壁。需要在短時間內(nèi)進(jìn)修、跳槽拿高薪的。
3、如果沒有工作經(jīng)驗(yàn)，但基礎(chǔ)非常扎實(shí)，對java工作機(jī)制，常用設(shè)計(jì)思想，常用java開發(fā)框架掌握熟練的。
?4、覺得自己很牛B，一般需求都能搞定。但是所學(xué)的知識點(diǎn)沒有系統(tǒng)化，很難在技術(shù)領(lǐng)域繼續(xù)突破的。
?5. 群號：高級架構(gòu)群 682094304備注好信息！
6.阿里Java高級大牛直播講解知識點(diǎn)，分享知識，多年工作經(jīng)驗(yàn)的梳理和總結(jié)，帶著大家全面、科學(xué)地建立自己的技術(shù)體系和技術(shù)認(rèn)知！
Segment定位
默認(rèn)情況下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二進(jìn)制數(shù)，向右無符號移動28位，讓高4位參與位運(yùn)算（& segmentMask）。
?ConcurrentHashMap相關(guān)操作實(shí)現(xiàn)分析 主要分析ConcurrentHashMap常用的三個操作：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所對應(yīng)的value不存在；
3、根據(jù)hashCode定位table中對應(yīng)的hashEntry，遍歷hashEntry，如果key存在，返回key對應(yīng)的value；
4、步驟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)用場景。
HashEntry value定義
put操作
ConcurrentHashMap提供兩個方法put和putIfAbsent來完成put操作，它們之間的區(qū)別在于put方法做插入時key存在會更新key所對應(yīng)的value，而putIfAbsent不會更新。
?put實(shí)現(xiàn)
put實(shí)現(xiàn)
?1、參數(shù)校驗(yàn)，value不能為null，為null時拋出NPE；
2、計(jì)算key的hashCode；
3、定位segment，如果segment不存在，創(chuàng)建新的segment；
?4、調(diào)用segment的put方法在對應(yīng)的segment做插入操作。
putIfAbsent實(shí)現(xiàn)
putIfAbsent實(shí)現(xiàn)
segment的put方法實(shí)現(xiàn)
?segment的put方法是整個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所對應(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在做插入的時候?qū)嶋H上經(jīng)歷了兩個步驟：
?第一：HashEntry數(shù)組擴(kuò)容；
是否需要擴(kuò)容
在插入元素前會先判斷Segment的HashEntry數(shù)組是否超過threshold，如果超過閥值，則需要對HashEntry數(shù)組擴(kuò)容；
?如何擴(kuò)容
在擴(kuò)容的時候，首先創(chuàng)建一個容量是原來容量兩倍的數(shù)組，將原數(shù)組的元素再散列后插入到新的數(shù)組里。為了高效，ConcurrentHashMap只對某個Segment進(jìn)行擴(kuò)容，不會對整個容器擴(kuò)容。
?第二：定位添加元素對應(yīng)的位置，然后將其放到HashEntry數(shù)組中。
?size實(shí)現(xiàn)
如果需要統(tǒng)計(jì)整個ConcurrentHashMap的容量，需要統(tǒng)計(jì)所有Segment容量然后求和，Segment提供變量count用于存儲當(dāng)前Segment的容量。但是ConcurrentHashMap為了保證線程安全，并不是直接把所有的Segment的count相加來得到整個容器的大小，我們來看看ConcurrentHashMap是怎么來統(tǒng)計(jì)容量的。
默認(rèn)情況下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二進(jìn)制數(shù)，向右無符號移動28位，讓高4位參與位運(yùn)算（& segmentMask）。
?ConcurrentHashMap相關(guān)操作實(shí)現(xiàn)分析
主要分析ConcurrentHashMap常用的三個操作：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所對應(yīng)的value不存在；
3、根據(jù)hashCode定位table中對應(yīng)的hashEntry，遍歷hashEntry，如果key存在，返回key對應(yīng)的value；
?4、步驟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實(shí)現(xiàn)
1、參數(shù)校驗(yàn)，value不能為null，為null時拋出NPE；
?2、計(jì)算key的hashCode；
?3、定位segment，如果segment不存在，創(chuàng)建新的segment；
4、調(diào)用segment的put方法在對應(yīng)的segment做插入操作。
segment的put方法實(shí)現(xiàn)
segment的put方法是整個put操作的核心，它實(shí)現(xiàn)了在segment的HashEntry數(shù)組中做插入
（segment的HashEntry數(shù)組采用開鏈法來處理沖突）。
?具體的執(zhí)行流程如下：
?1、獲取鎖，保證put操作的線程安全；
?2、定位到HashEntry數(shù)組中具體的HashEntry；
3、遍歷HashEntry鏈表，假若待插入key已存在：
需要更新key所對應(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在做插入的時候?qū)嶋H上經(jīng)歷了兩個步驟：
第一：HashEntry數(shù)組擴(kuò)容；
?是否需要擴(kuò)容
在插入元素前會先判斷Segment的HashEntry數(shù)組是否超過threshold，如果超過閥值，則需要對HashEntry數(shù)組擴(kuò)容；
如何擴(kuò)容
在擴(kuò)容的時候，首先創(chuàng)建一個容量是原來容量兩倍的數(shù)組，將原數(shù)組的元素再散列后插入到新的數(shù)組里。為了高效，ConcurrentHashMap只對某個Segment進(jìn)行擴(kuò)容，不會對整個容器擴(kuò)容。
第二：定位添加元素對應(yīng)的位置，然后將其放到HashEntry數(shù)組中。
?size實(shí)現(xiàn)
如果需要統(tǒng)計(jì)整個ConcurrentHashMap的容量，需要統(tǒng)計(jì)所有Segment容量然后求和，Segment 提供變量count用于存儲當(dāng)前Segment的容量。但是ConcurrentHashMap為了保證線程安全，并不是直接把所有的Segment的count相加來得到整個容器的大小，我們來看看ConcurrentHashMap是怎么來統(tǒng)計(jì)容量的。
由于在累加count的操作的過程中之前累加過的count發(fā)生變化的幾率非常小
所以ConcurrentHashMap先嘗試2次不鎖住Segment的方式來統(tǒng)計(jì)每個Segment的大小，如果在統(tǒng)計(jì)的過程中Segment的count發(fā)生了變化，這時候再加鎖統(tǒng)計(jì)Segment的count。
ConcurrentHashMap如何判斷統(tǒng)計(jì)過程中Segment的cout發(fā)生了變化？
Segment使用變量modCount來表示Segment大小是否發(fā)生變化，在put/remove/clean操作里都會將modCount加1，那么在統(tǒng)計(jì)size的前后只需要比較modCount是否發(fā)生了變化，如果發(fā)生變化，Segment的大小肯定發(fā)生了變化。
可以加群找我要課堂鏈接哦 ?注意：是免費(fèi)的 沒有開發(fā)經(jīng)驗(yàn)誤入哦
?1、具有1-5工作經(jīng)驗(yàn)的，面對目前流行的技術(shù)不知從何下手，需要突破技術(shù)瓶頸的。
2、在公司待久了，過得很安逸，但跳槽時面試碰壁。需要在短時間內(nèi)進(jìn)修、跳槽拿高薪的。
?3、如果沒有工作經(jīng)驗(yàn)，但基礎(chǔ)非常扎實(shí)，對java工作機(jī)制，常用設(shè)計(jì)思想，常用java開發(fā)框架掌握熟練的。
4、覺得自己很牛B，一般需求都能搞定。但是所學(xué)的知識點(diǎn)沒有系統(tǒng)化，很難在技術(shù)領(lǐng)域繼續(xù)突破的。
5. 群號：高級架構(gòu)群 481495939備注好信息！
?6.阿里Java高級大牛直播講解知識點(diǎn)，分享知識，多年工作經(jīng)驗(yàn)的梳理和總結(jié)，帶著大家全面、科學(xué)地建立自己的技術(shù)體系和技術(shù)認(rèn)知！
