Java中的ConcurrentHashMap原理詳解
一、什么是ConcurrentHashMap
ConcurrentHashMap和HashMap一樣，是一個(gè)存放鍵值對(duì)的容器。
使用hash算法來(lái)獲取值的地址，因此時(shí)間復(fù)雜度是O(1)。查詢非?？?。 同時(shí)，ConcurrentHashMap是線程安全的HashMap。專門(mén)用于多線程環(huán)境。
二、ConcurrentHashMap和HashMap以及Hashtable的區(qū)別
2.1 HashMap
HashMap是線程不安全的，因?yàn)镠ashMap中操作都沒(méi)有加鎖，因此在多線程環(huán)境下會(huì)導(dǎo)致數(shù)據(jù)覆蓋之類的問(wèn)題，所以，在多線程中使用HashMap是會(huì)拋出異常的。
2.2 HashTable
HashTable是線程安全的,但是HashTable只是單純的在put()方法上加上synchronized。保證插入時(shí)阻塞其他線程的插入操作。雖然安全，但因?yàn)樵O(shè)計(jì)簡(jiǎn)單，所以性能低下。
2.3 ConcurrentHashMap
ConcurrentHashMap是線程安全的，ConcurrentHashMap并非鎖住整個(gè)方法，而是通過(guò)原子操作和局部加鎖的方法保證了多線程的線程安全，且盡可能減少了性能損耗。
由此可見(jiàn)，HashTable可真是一無(wú)是處…
三、ConcurrentHashMap原理
這一節(jié)專門(mén)介紹ConcurrentHashMap是如何保證線程安全的。如果想詳細(xì)了解ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)參考HashMap。
3.1 volatile修飾的節(jié)點(diǎn)數(shù)組
請(qǐng)看源碼
//ConcurrentHashMap使用volatile修飾節(jié)點(diǎn)數(shù)組，保證其可見(jiàn)性，禁止指令重排。 transient volatile Node<K,V>[] table;
再看看HashMap是怎么做的
//HashMap沒(méi)有用volatile修飾節(jié)點(diǎn)數(shù)組。 transient Node<K,V>[] table;
顯然，HashMap并不是為多線程環(huán)境設(shè)計(jì)的。
3.2 ConcurrentHashMap的put()方法
//put()方法直接調(diào)用putVal()方法
public V put(K key, V value) {
return putVal(key, value, false);
}
//所以直接看putVal()方法。
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}我來(lái)給大家講解一下步驟把。
public V put(K key, V value) {首先，put()方法是沒(méi)有用synchronized修飾的。
for (Node<K,V>[] tab = table;;)
新插入一個(gè)節(jié)點(diǎn)時(shí)，首先會(huì)進(jìn)入一個(gè)死循環(huán)， 情商高的就會(huì)說(shuō)，這是一個(gè)樂(lè)觀鎖 進(jìn)入樂(lè)觀鎖后，
if (tab == null || (n = tab.length) == 0)
tab = initTable();如果tab未被初始化，則先將tab初始化。此時(shí)，這輪循環(huán)結(jié)束，因?yàn)楸粯?lè)觀鎖鎖住，開(kāi)始下一輪循環(huán)。 第二輪循環(huán)，此時(shí)tab已經(jīng)被初始化了，所以跳過(guò)。
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}接下來(lái)通過(guò)key的hash值來(lái)判斷table中是否存在相同的key，如果不存在，執(zhí)行casTabAt()方法。 注意，這個(gè)操作時(shí)不加鎖的，看到里面的那行注釋了么// no lock when adding to empty bin。位置為空時(shí)不加鎖。 這里其實(shí)是利用了一個(gè)CAS操作。
CAS(Compare-And-Swap)：比較并交換
這里就插播一個(gè)小知識(shí)，CAS就是通過(guò)一個(gè)原子操作，用預(yù)期值去和實(shí)際值做對(duì)比，如果實(shí)際值和預(yù)期相同，則做更新操作。 如果預(yù)期值和實(shí)際不同，我們就認(rèn)為，其他線程更新了這個(gè)值，此時(shí)不做更新操作。 而且這整個(gè)流程是原子性的，所以只要實(shí)際值和預(yù)期值相同，就能保證這次更新不會(huì)被其他線程影響。
好了，我們繼續(xù)。 既然這里用了CAS操作去更新值，那么就存在兩者情況。
- 實(shí)際值和預(yù)期值相同 相同時(shí)，直接將值插入，因?yàn)榇藭r(shí)是線程安全的。好了，這時(shí)插入操作完成。使用break;跳出了樂(lè)觀鎖。循環(huán)結(jié)束。
- 實(shí)際值和預(yù)期值不同 不同時(shí)，不進(jìn)行操作，因?yàn)榇藭r(shí)這個(gè)值已經(jīng)被其他線程修改過(guò)了，此時(shí)這輪操作就結(jié)束了，因?yàn)檫€被樂(lè)觀鎖鎖住，進(jìn)入第三輪循環(huán)。
第三輪循環(huán)中，前面的判斷又會(huì)重新執(zhí)行一次，我就跳過(guò)不說(shuō)了，進(jìn)入后面的判斷。
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);這里判斷的是tab的狀態(tài)，MOVED表示在擴(kuò)容中，如果在擴(kuò)容中，幫助其擴(kuò)容。幫助完了后就會(huì)進(jìn)行第四輪循環(huán)。 終于，來(lái)到了最后一輪循環(huán)。
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}上面的判斷都不滿足時(shí)，就會(huì)進(jìn)入最后的分支，這條分支表示，key的hash值位置不為null(之前的判斷是hash值為null時(shí)直接做插入操作)，表示發(fā)生了hash沖突，此時(shí)節(jié)點(diǎn)就要通過(guò)鏈表的形式存儲(chǔ)這個(gè)插入的新值。Node類是有next字段的，用來(lái)指向鏈表的下一個(gè)位置，新節(jié)點(diǎn)就往這插。
synchronized (f) {
看，終于加排它鎖了，只有在發(fā)生hash沖突的時(shí)候才加了排它鎖。
if (tabAt(tab, i) == f) {
if (fh >= 0) {重新判斷當(dāng)前節(jié)點(diǎn)是不是第二輪判斷過(guò)的節(jié)點(diǎn)，如果不是，表示節(jié)點(diǎn)被其他線程改過(guò)了，進(jìn)入下一輪循環(huán)， 如果是，再次判斷是否在擴(kuò)容中，如果是，進(jìn)入下一輪循環(huán)， 如果不是，其他線程沒(méi)改過(guò)，繼續(xù)走，
for (Node<K,V> e = f;; ++binCount) {for循環(huán)，循環(huán)遍歷這個(gè)節(jié)點(diǎn)上的鏈表，
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}找到一個(gè)hash值相同，且key也完全相同的節(jié)點(diǎn)，更新這個(gè)節(jié)點(diǎn)。 如果找不到
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}往鏈表最后插入這個(gè)新節(jié)點(diǎn)。因?yàn)樵谂潘i中，這些操作都可以直接操作。終于到這插入就基本完成了。
總結(jié)
做插入操作時(shí)，首先進(jìn)入樂(lè)觀鎖， 然后，在樂(lè)觀鎖中判斷容器是否初始化， 如果沒(méi)初始化則初始化容器， 如果已經(jīng)初始化，則判斷該hash位置的節(jié)點(diǎn)是否為空，如果為空，則通過(guò)CAS操作進(jìn)行插入。 如果該節(jié)點(diǎn)不為空，再判斷容器是否在擴(kuò)容中，如果在擴(kuò)容，則幫助其擴(kuò)容。 如果沒(méi)有擴(kuò)容，則進(jìn)行最后一步，先加鎖，然后找到hash值相同的那個(gè)節(jié)點(diǎn)(hash沖突)， 循環(huán)判斷這個(gè)節(jié)點(diǎn)上的鏈表，決定做覆蓋操作還是插入操作。 循環(huán)結(jié)束，插入完畢。
3.3 ConcurrentHashMap的get()方法
//ConcurrentHashMap的get()方法是不加鎖的，方法內(nèi)部也沒(méi)加鎖。 public V get(Object key)
看上面這代碼，ConcurrentHashMap的get()方法是不加鎖的，為什么可以不加鎖？因?yàn)閠able有volatile關(guān)鍵字修飾，保證每次獲取值都是最新的。
//Hashtable的get()是加鎖的，所以性能差。 public synchronized V get(Object key)
再看看Hashtable，差距啊。
四、使用場(chǎng)景
嗯，多線程環(huán)境下，更新少，查詢多時(shí)使用的話，性能比較高。
樂(lè)觀鎖嘛，認(rèn)為更新操作時(shí)不會(huì)被其他線程影響。
所以時(shí)候再更新少的情況下性能高。
到此這篇關(guān)于Java中的ConcurrentHashMap原理詳解的文章就介紹到這了,更多相關(guān)ConcurrentHashMap原理內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了IDEA 單元測(cè)試覆蓋技巧分享，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-01-01
java報(bào)錯(cuò)Cause: java.sql.SQLException問(wèn)題解決
本文主要介紹了java報(bào)錯(cuò)Cause: java.sql.SQLException問(wèn)題解決,對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-08-08
Spring FactoriesLoader機(jī)制實(shí)例詳解
這篇文章主要介紹了Spring FactoriesLoader機(jī)制實(shí)例詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-03-03
基于SpringBoot+vue實(shí)現(xiàn)前后端數(shù)據(jù)加解密
這篇文章主要給大家介紹了基于SpringBoot+vue實(shí)現(xiàn)前后端數(shù)據(jù)加解密,文中有詳細(xì)的示例代碼,具有一定的參考價(jià)值,感興趣的小伙伴可以自己動(dòng)手試一試2023-08-08
這篇文章主要介紹了Java字符串在內(nèi)存中的存儲(chǔ)位置，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-05-05
idea2020安裝MybatisCodeHelper插件的圖文教程
這篇文章主要介紹了idea2020安裝MybatisCodeHelper插件的方法，本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-09-09
這篇文章主要介紹了Spring中的@Async原理分析,自定義new ThreadPoolExecutor并調(diào)用invokeAll等進(jìn)行并發(fā)編程,后面發(fā)現(xiàn)只要在方法上添加@Async注解,并使用@EnableAsync進(jìn)行開(kāi)啟默認(rèn)會(huì)使用SimpleAsyncTaskExecutor類型,需要的朋友可以參考下2024-01-01
SpringBoot實(shí)現(xiàn)動(dòng)態(tài)加載外部Jar流程詳解
這篇文章主要介紹了SpringBoot動(dòng)態(tài)加載外部Jar的流程，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2023-05-05
SpringBoot Redis緩存數(shù)據(jù)實(shí)現(xiàn)解析
這篇文章主要介紹了SpringBoot Redis緩存數(shù)據(jù)實(shí)現(xiàn)解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-01-01
Mybatis實(shí)現(xiàn)動(dòng)態(tài)排序方式
這篇文章主要介紹了Mybatis實(shí)現(xiàn)動(dòng)態(tài)排序方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-10-10