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

1.哈希表

2.ConcurrentHashMap與HashMap、HashTable的區(qū)別

3.CurrentHashMap在JDK1.7和JDK1.8版本的區(qū)別

哈希表

1.介紹

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

哈希的思路很簡(jiǎn)單，如果所有的鍵都是整數(shù)，那么就可以使用一個(gè)簡(jiǎn)單的無(wú)序數(shù)組來(lái)實(shí)現(xiàn)：將鍵作為索引，值即為其對(duì)應(yīng)的值，這樣就可以快速訪問(wèn)任意鍵的值。這是對(duì)于簡(jiǎn)單的鍵的情況，我們將其擴(kuò)展到可以處理更加復(fù)雜的類型的鍵。

2.鏈?zhǔn)焦１?/p>

鏈?zhǔn)焦１韽母旧险f(shuō)是由一組鏈表構(gòu)成。每個(gè)鏈表都可以看做是一個(gè)“桶”，我們將所有的元素通過(guò)散列的方式放到具體的不同的桶中。插入元素時(shí)，首先將其鍵傳入一個(gè)哈希函數(shù)(該過(guò)程稱為哈希鍵)，函數(shù)通過(guò)散列的方式告知元素屬于哪個(gè)“桶”，然后在相應(yīng)的鏈表頭插入元素。查找或刪除元素時(shí)，用同們的方式先找到元素的“桶”，然后遍歷相應(yīng)的鏈表，直到發(fā)現(xiàn)我們想要的元素。因?yàn)槊總€(gè)“桶”都是一個(gè)鏈表，所以鏈?zhǔn)焦１聿⒉幌拗瓢氐膫€(gè)數(shù)。然而，如果表變得太大，它的性能將會(huì)降低。

3.應(yīng)用場(chǎng)景

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

ConcurrentHashMap與HashMap等的區(qū)別

1.HashMap

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

2.HashTable

HashTable和HashMap的實(shí)現(xiàn)原理幾乎一樣，差別無(wú)非是HashTable不允許key和value為null

HashTable是線程安全的

但是HashTable線程安全的策略實(shí)現(xiàn)代價(jià)卻太大了，簡(jiǎn)單粗暴，get/put所有相關(guān)操作都是synchronized的，這相當(dāng)于給整個(gè)哈希表加了一把大鎖。

多線程訪問(wèn)時(shí)候，只要有一個(gè)線程訪問(wèn)或操作該對(duì)象，那其他線程只能阻塞，相當(dāng)于將所有的操作串行化，在競(jìng)爭(zhēng)激烈的并發(fā)場(chǎng)景中性能就會(huì)非常差。

3.ConcurrentHashMap

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

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

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

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

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

1.Segment(分段鎖)

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

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

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

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

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

3.該結(jié)構(gòu)的優(yōu)劣勢(shì)

壞處

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

好處

寫(xiě)操作的時(shí)候可以只對(duì)元素所在的Segment進(jìn)行加鎖即可，不會(huì)影響到其他的Segment，這樣，在最理想的情況下，ConcurrentHashMap可以最高同時(shí)支持Segment數(shù)量大小的寫(xiě)操作(剛好這些寫(xiě)操作都非常平均地分布在所有的Segment上)。

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

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

JDK8中ConcurrentHashMap參考了JDK8 HashMap的實(shí)現(xiàn)，采用了數(shù)組+鏈表+紅黑樹(shù)的實(shí)現(xiàn)方式來(lái)設(shè)計(jì)，內(nèi)部大量采用CAS操作，這里我簡(jiǎn)要介紹下CAS。

CAS是compare and swap的縮寫(xiě)，即我們所說(shuō)的比較交換。cas是一種基于鎖的操作，而且是樂(lè)觀鎖。在java中鎖分為樂(lè)觀鎖和悲觀鎖。悲觀鎖是將資源鎖住，等一個(gè)之前獲得鎖的線程釋放鎖之后，下一個(gè)線程才可以訪問(wèn)。而樂(lè)觀鎖采取了一種寬泛的態(tài)度，通過(guò)某種方式不加鎖來(lái)處理資源，比如通過(guò)給記錄加version來(lái)獲取數(shù)據(jù)，性能較悲觀鎖有很大的提高。

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

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

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

class Node implements Map.Entry { final int hash; final K key; volatile V val; volatile Node next; //... 省略部分代碼}

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

在JDK8中ConcurrentHashMap的結(jié)構(gòu)，由于引入了紅黑樹(shù)，使得ConcurrentHashMap的實(shí)現(xiàn)非常復(fù)雜，我們都知道，紅黑樹(shù)是一種性能非常好的二叉查找樹(shù)，其查找性能為O(logN)，但是其實(shí)現(xiàn)過(guò)程也非常復(fù)雜，而且可讀性也非常差，Doug

Lea的思維能力確實(shí)不是一般人能比的，早期完全采用鏈表結(jié)構(gòu)時(shí)Map的查找時(shí)間復(fù)雜度為O(N)，JDK8中ConcurrentHashMap在鏈表的長(zhǎng)度大于某個(gè)閾值的時(shí)候會(huì)將鏈表轉(zhuǎn)換成紅黑樹(shù)進(jìn)一步提高其查找性能。

ConcurrentHashMap實(shí)現(xiàn)原理總結(jié)

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

1.數(shù)據(jù)結(jié)構(gòu)：取消了Segment分段鎖的數(shù)據(jù)結(jié)構(gòu)，取而代之的是數(shù)組+鏈表+紅黑樹(shù)的結(jié)構(gòu)。

2.保證線程安全機(jī)制：JDK1.7采用segment的分段鎖機(jī)制實(shí)現(xiàn)線程安全，其中segment繼承自ReentrantLock。JDK1.8采用CAS+Synchronized保證線程安全。

3.鎖的粒度：原來(lái)是對(duì)需要進(jìn)行數(shù)據(jù)操作的Segment加鎖，現(xiàn)調(diào)整為對(duì)每個(gè)數(shù)組元素加鎖(Node)。

4.鏈表轉(zhuǎn)化為紅黑樹(shù):定位結(jié)點(diǎn)的hash算法簡(jiǎn)化會(huì)帶來(lái)弊端,Hash沖突加劇,因此在鏈表節(jié)點(diǎn)數(shù)量大于8時(shí)，會(huì)將鏈表轉(zhuǎn)化為紅黑樹(shù)進(jìn)行存儲(chǔ)。

5.查詢時(shí)間復(fù)雜度：從原來(lái)的遍歷鏈表O(n)，變成遍歷紅黑樹(shù)O(logN)。

更多高并發(fā)架構(gòu)設(shè)計(jì)專題

資料獲取方式

關(guān)注+轉(zhuǎn)發(fā)后，私信關(guān)鍵詞 【高并發(fā)】即可獲取！

優(yōu)知學(xué)院(youzhixueyuan.com):IT人升值加薪進(jìn)階站，BAT總監(jiān)經(jīng)驗(yàn)分享平臺(tái)，分享bat面試+架構(gòu)+CTO進(jìn)階干貨！

編輯

請(qǐng)點(diǎn)擊輸入圖片描述

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的currenthashmap扩容原理_高并发编程系列：深入探讨ConcurrentHashMap的实现原理(JDK1.7和JDK1.8)...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。