高并發(fā)編程系列：ConcurrentHashMap的實現(xiàn)原理(JDK1.7和JDK1.8)

引言

HashMap、CurrentHashMap 的實現(xiàn)原理基本都是BAT面試必考內(nèi)容乳讥，阿里P8架構(gòu)師談：深入探討HashMap的底層結(jié)構(gòu)、原理、擴容機制深入談過hashmap的實現(xiàn)原理以及在JDK 1.8的實現(xiàn)區(qū)別仆葡，今天主要談CurrentHashMap的實現(xiàn)原理，以及在JDK1.7和1.8的區(qū)別志笼。
哈希表

1 介紹

哈希表就是一種以鍵-值(key-indexed) 存儲數(shù)據(jù)的結(jié)構(gòu)沿盅，我們只要輸入待查找的值即key，即可查找到其對應(yīng)的值纫溃。

哈希的思路很簡單腰涧，如果所有的鍵都是整數(shù)，那么就可以使用一個簡單的無序數(shù)組來實現(xiàn)：將鍵作為索引紊浩，值即為其對應(yīng)的值窖铡，這樣就可以快速訪問任意鍵的值疗锐。這是對于簡單的鍵的情況，我們將其擴展到可以處理更加復(fù)雜的類型的鍵费彼。

2 鏈式哈希表

鏈式哈希表從根本上說是由一組鏈表構(gòu)成滑臊。每個鏈表都可以看做是一個“桶”，我們將所有的元素通過散列的方式放到具體的不同的桶中敌买。插入元素時简珠，首先將其鍵傳入一個哈希函數(shù)（該過程稱為哈希鍵）阶界，函數(shù)通過散列的方式告知元素屬于哪個“桶”虹钮，然后在相應(yīng)的鏈表頭插入元素。查找或刪除元素時膘融，用同們的方式先找到元素的“桶”芙粱，然后遍歷相應(yīng)的鏈表，直到發(fā)現(xiàn)我們想要的元素氧映。因為每個“桶”都是一個鏈表春畔，所以鏈式哈希表并不限制包含元素的個數(shù)。然而岛都，如果表變得太大律姨，它的性能將會降低。

image

3 應(yīng)用場景

我們熟知的緩存技術(shù)（比如redis臼疫、memcached）的核心其實就是在內(nèi)存中維護一張巨大的哈希表择份，還有大家熟知的HashMap、CurrentHashMap等的應(yīng)用烫堤。

ConcurrentHashMap與HashMap等的區(qū)別

3.1 HashMap

我們知道HashMap是線程不安全的荣赶，在多線程環(huán)境下，使用Hashmap進行put操作會引起死循環(huán)鸽斟，導(dǎo)致CPU利用率接近100%拔创，所以在并發(fā)情況下不能使用HashMap。

3.2 HashTable

HashTable和HashMap的實現(xiàn)原理幾乎一樣富蓄，差別無非是

HashTable不允許key和value為nullHashTable是線程安全的但是HashTable線程安全的策略實現(xiàn)代價卻太大了剩燥，簡單粗暴，get/put所有相關(guān)操作都是synchronized的立倍，這相當(dāng)于給整個哈希表加了一把大鎖灭红。

多線程訪問時候，只要有一個線程訪問或操作該對象帐萎，那其他線程只能阻塞比伏，相當(dāng)于將所有的操作串行化，在競爭激烈的并發(fā)場景中性能就會非常差疆导。

3.3 ConcurrentHashMap

主要就是為了應(yīng)對hashmap在并發(fā)環(huán)境下不安全而誕生的赁项，ConcurrentHashMap的設(shè)計與實現(xiàn)非常精巧，大量的利用了volatile，final悠菜，CAS等lock-free技術(shù)來減少鎖競爭對于性能的影響舰攒。

我們都知道Map一般都是數(shù)組+鏈表結(jié)構(gòu)（JDK1.8該為數(shù)組+紅黑樹）。

image

ConcurrentHashMap避免了對全局加鎖改成了局部加鎖操作悔醋，這樣就極大地提高了并發(fā)環(huán)境下的操作速度摩窃，由于ConcurrentHashMap在JDK1.7和1.8中的實現(xiàn)非常不同，接下來我們談?wù)凧DK在1.7和1.8中的區(qū)別芬骄。

4 JDK1.7版本的CurrentHashMap的實現(xiàn)原理

在JDK1.7中ConcurrentHashMap采用了數(shù)組+Segment+分段鎖的方式實現(xiàn)猾愿。

4.1 Segment(分段鎖)

ConcurrentHashMap中的分段鎖稱為Segment，它即類似于HashMap的結(jié)構(gòu)账阻，即內(nèi)部擁有一個Entry數(shù)組蒂秘，數(shù)組中的每個元素又是一個鏈表,同時又是一個ReentrantLock（Segment繼承了ReentrantLock）。

4.2 內(nèi)部結(jié)構(gòu)

ConcurrentHashMap使用分段鎖技術(shù)淘太，將數(shù)據(jù)分成一段一段的存儲姻僧，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候蒲牧，其他段的數(shù)據(jù)也能被其他線程訪問撇贺，能夠?qū)崿F(xiàn)真正的并發(fā)訪問。如下圖是ConcurrentHashMap的內(nèi)部結(jié)構(gòu)圖：

image

從上面的結(jié)構(gòu)我們可以了解到冰抢，ConcurrentHashMap定位一個元素的過程需要進行兩次Hash操作松嘶。

第一次Hash定位到Segment，第二次Hash定位到元素所在的鏈表的頭部晒屎。

4.3 該結(jié)構(gòu)的優(yōu)劣勢

壞處

這一種結(jié)構(gòu)的帶來的副作用是Hash的過程要比普通的HashMap要長

好處

寫操作的時候可以只對元素所在的Segment進行加鎖即可喘蟆，不會影響到其他的Segment，這樣鼓鲁，在最理想的情況下蕴轨，ConcurrentHashMap可以最高同時支持Segment數(shù)量大小的寫操作（剛好這些寫操作都非常平均地分布在所有的Segment上）。

所以骇吭，通過這一種結(jié)構(gòu)橙弱，ConcurrentHashMap的并發(fā)能力可以大大的提高。

5 JDK1.8版本的CurrentHashMap的實現(xiàn)原理

JDK8中ConcurrentHashMap參考了JDK8 HashMap的實現(xiàn)燥狰，采用了數(shù)組+鏈表+紅黑樹的實現(xiàn)方式來設(shè)計棘脐，內(nèi)部大量采用CAS操作，這里我簡要介紹下CAS龙致。

CAS是compare and swap的縮寫蛀缝，即我們所說的比較交換。cas是一種基于鎖的操作目代，而且是樂觀鎖屈梁。在java中鎖分為樂觀鎖和悲觀鎖嗤练。悲觀鎖是將資源鎖住，等一個之前獲得鎖的線程釋放鎖之后在讶，下一個線程才可以訪問煞抬。而樂觀鎖采取了一種寬泛的態(tài)度，通過某種方式不加鎖來處理資源构哺，比如通過給記錄加version來獲取數(shù)據(jù)革答，性能較悲觀鎖有很大的提高。

CAS 操作包含三個操作數(shù) —— 內(nèi)存位置（V）曙强、預(yù)期原值（A）和新值(B)残拐。如果內(nèi)存地址里面的值和A的值是一樣的，那么就將內(nèi)存里面的值更新成B旗扑。CAS是通過無限循環(huán)來獲取數(shù)據(jù)的蹦骑，若果在第一輪循環(huán)中，a線程獲取地址里面的值被b線程修改了臀防，那么a線程需要自旋，到下次循環(huán)才有可能機會執(zhí)行边败。

JDK8中徹底放棄了Segment轉(zhuǎn)而采用的是Node袱衷，其設(shè)計思想也不再是JDK1.7中的分段鎖思想。

Node：保存key笑窜，value及key的hash值的數(shù)據(jù)結(jié)構(gòu)致燥。其中value和next都用volatile修飾，保證并發(fā)的可見性排截。

classNode<K,V>implementsMap.Entry<K,V> {
finalint hash;
final K key;
volatile V val;
volatileNode<K,V> next;
//... 省略部分代碼
}

Java8 ConcurrentHashMap結(jié)構(gòu)基本上和Java8的HashMap一樣嫌蚤，不過保證線程安全性。

在JDK8中ConcurrentHashMap的結(jié)構(gòu)断傲，由于引入了紅黑樹脱吱，使得ConcurrentHashMap的實現(xiàn)非常復(fù)雜，我們都知道认罩，紅黑樹是一種性能非常好的二叉查找樹箱蝠，其查找性能為O（logN），但是其實現(xiàn)過程也非常復(fù)雜垦垂，而且可讀性也非常差宦搬，DougLea的思維能力確實不是一般人能比的，早期完全采用鏈表結(jié)構(gòu)時Map的查找時間復(fù)雜度為O（N）劫拗，JDK8中ConcurrentHashMap在鏈表的長度大于某個閾值的時候會將鏈表轉(zhuǎn)換成紅黑樹進一步提高其查找性能间校。

image

總結(jié)

其實可以看出JDK1.8版本的ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)已經(jīng)接近HashMap，相對而言页慷，ConcurrentHashMap只是增加了同步的操作來控制并發(fā)憔足，從JDK1.7版本的ReentrantLock+Segment+HashEntry聂渊，到JDK1.8版本中synchronized+CAS+HashEntry+紅黑樹。

1.數(shù)據(jù)結(jié)構(gòu)：取消了Segment分段鎖的數(shù)據(jù)結(jié)構(gòu)四瘫，取而代之的是數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)汉嗽。
2.保證線程安全機制：JDK1.7采用segment的分段鎖機制實現(xiàn)線程安全，其中segment繼承自ReentrantLock找蜜。JDK1.8采用CAS+Synchronized保證線程安全饼暑。
3.鎖的粒度：原來是對需要進行數(shù)據(jù)操作的Segment加鎖，現(xiàn)調(diào)整為對每個數(shù)組元素加鎖（Node）洗做。
4.鏈表轉(zhuǎn)化為紅黑樹:定位結(jié)點的hash算法簡化會帶來弊端,Hash沖突加劇,因此在鏈表節(jié)點數(shù)量大于8時弓叛，會將鏈表轉(zhuǎn)化為紅黑樹進行存儲。
5.查詢時間復(fù)雜度：從原來的遍歷鏈表O(n)诚纸，變成遍歷紅黑樹O(logN)撰筷。

參考原文：高并發(fā)編程系列：ConcurrentHashMap的實現(xiàn)原理(JDK1.7和JDK1.8)