ConcurrentHashMap是如何保證線程安全
ConcurrentHashMap 是 HashMap 的多線程版本,HashMap 在并發(fā)操作時(shí)會(huì)有各種問題,比如死循環(huán)問題、數(shù)據(jù)覆蓋等問題。而這些問題,只要使用 ConcurrentHashMap 就可以完美解決了,那問題來了,ConcurrentHashMap 是如何保證線程安全的?它的底層又是如何實(shí)現(xiàn)的?接下來我們一起來看。
JDK 1.7 底層實(shí)現(xiàn)
ConcurrentHashMap 在不同的 JDK 版本中實(shí)現(xiàn)是不同的,在 JDK 1.7 中它使用的是數(shù)組加鏈表的形式實(shí)現(xiàn)的,而數(shù)組又分為:大數(shù)組 Segment 和小數(shù)組 HashEntry。 大數(shù)組 Segment 可以理解為 MySQL 中的數(shù)據(jù)庫(kù),而每個(gè)數(shù)據(jù)庫(kù)(Segment)中又有很多張表 HashEntry,每個(gè) HashEntry 中又有多條數(shù)據(jù),這些數(shù)據(jù)是用鏈表連接的,如下圖所示:
JDK 1.7 線程安全實(shí)現(xiàn)
了解了 ConcurrentHashMap 的底層實(shí)現(xiàn),再看它的線程安全實(shí)現(xiàn)就比較簡(jiǎn)單了。
接下來,我們通過添加元素 put 方法,來看 JDK 1.7 中 ConcurrentHashMap 是如何保證線程安全的,具體實(shí)現(xiàn)源碼如下:
final V put(K key, int hash, V value, boolean onlyIfAbsent) { // 在往該 Segment 寫入前,先確保獲取到鎖 HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); V oldValue; try { // Segment 內(nèi)部數(shù)組 HashEntry<K,V>[] tab = table; int index = (tab.length - 1) & hash; HashEntry<K,V> first = entryAt(tab, index); for (HashEntry<K,V> e = first;;) { if (e != null) { K k; // 更新已有值... } else { // 放置 HashEntry 到特定位置,如果超過閾值則進(jìn)行 rehash // 忽略其他代碼... } } } finally { // 釋放鎖 unlock(); } return oldValue; }
從上述源碼我們可以看出,Segment 本身是基于 ReentrantLock 實(shí)現(xiàn)的加鎖和釋放鎖的操作,這樣就能保證多個(gè)線程同時(shí)訪問 ConcurrentHashMap 時(shí),同一時(shí)間只有一個(gè)線程能操作相應(yīng)的節(jié)點(diǎn),這樣就保證了 ConcurrentHashMap 的線程安全了。
也就是說 ConcurrentHashMap 的線程安全是建立在 Segment 加鎖的基礎(chǔ)上的,所以我們把它稱之為分段鎖或片段鎖,如下圖所示:
JDK 1.8 底層實(shí)現(xiàn)
在 JDK 1.7 中,ConcurrentHashMap 雖然是線程安全的,但因?yàn)樗牡讓訉?shí)現(xiàn)是數(shù)組
DK 1.7 中,ConcurrentHashMap 雖然是線程安全的,但因?yàn)樗牡讓訉?shí)現(xiàn)是數(shù)組 + 鏈表的形式,所以在數(shù)據(jù)比較多的情況下訪問是很慢的,因?yàn)橐闅v整個(gè)鏈表,而 JDK 1.8 則使用了數(shù)組 + 鏈表/紅黑樹的方式優(yōu)化了 ConcurrentHashMap 的實(shí)現(xiàn),具體實(shí)現(xiàn)結(jié)構(gòu)如下:
鏈表升級(jí)為紅黑樹的規(guī)則:當(dāng)鏈表長(zhǎng)度大于 8,并且數(shù)組的長(zhǎng)度大于 64 時(shí),鏈表就會(huì)升級(jí)為紅黑樹的結(jié)構(gòu)。
PS:ConcurrentHashMap 在 JDK 1.8 雖然保留了 Segment 的定義,但這僅僅是為了保證序列化時(shí)的兼容性,不再有任何結(jié)構(gòu)上的用處了。
JDK 1.8 線程安全實(shí)現(xiàn)
在 JDK 1.8 中 ConcurrentHashMap 使用的是 CAS
DK 1.8 中 ConcurrentHashMap 使用的是 CAS + volatile 或 synchronized 的方式來保證線程安全的,它的核心實(shí)現(xiàn)源碼如下:
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; K fk; V fv; if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 節(jié)點(diǎn)為空 // 利用 CAS 去進(jìn)行無鎖線程安全操作,如果 bin 是空的 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value))) break; } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else if (onlyIfAbsent && fh == hash && ((fk = f.key) == key || (fk != null && key.equals(fk))) && (fv = f.val) != null) return fv; else { V oldVal = null; synchronized (f) { // 細(xì)粒度的同步修改操作... } } // 如果超過閾值,升級(jí)為紅黑樹 if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }
從上述源碼可以看出,在 JDK 1.8 中,添加元素時(shí)首先會(huì)判斷容器是否為空,如果為空則使用 volatile 加 CAS 來初始化。如果容器不為空則根據(jù)存儲(chǔ)的元素計(jì)算該位置是否為空,如果為空則利用 CAS 設(shè)置該節(jié)點(diǎn);如果不為空則使用 synchronize 加鎖,遍歷桶中的數(shù)據(jù),替換或新增節(jié)點(diǎn)到桶中,最后再判斷是否需要轉(zhuǎn)為紅黑樹,這樣就能保證并發(fā)訪問時(shí)的線程安全了。
我們把上述流程簡(jiǎn)化一下,我們可以簡(jiǎn)單的認(rèn)為在 JDK 1.8 中,ConcurrentHashMap 是在頭節(jié)點(diǎn)加鎖來保證線程安全的,鎖的粒度相比 Segment 來說更小了,發(fā)生沖突和加鎖的頻率降低了,并發(fā)操作的性能就提高了。而且 JDK 1.8 使用的是紅黑樹優(yōu)化了之前的固定鏈表,那么當(dāng)數(shù)據(jù)量比較大的時(shí)候,查詢性能也得到了很大的提升,從之前的 O(n) 優(yōu)化到了 O(logn) 的時(shí)間復(fù)雜度,具體加鎖示意圖如下:
總結(jié)
ConcurrentHashMap 在 JDK 1.7 時(shí)使用的是數(shù)據(jù)加鏈表的形式實(shí)現(xiàn)的,其中數(shù)組分為兩類:大數(shù)組 Segment 和小數(shù)組 HashEntry,而加鎖是通過給 Segment 添加 ReentrantLock 鎖來實(shí)現(xiàn)線程安全的。而 JDK 1.8 中 ConcurrentHashMap 使用的是數(shù)組+鏈表/紅黑樹的方式實(shí)現(xiàn)的,它是通過 CAS 或 synchronized 來實(shí)現(xiàn)線程安全的,并且它的鎖粒度更小,查詢性能也更高。
到此這篇關(guān)于ConcurrentHashMap是如何保證線程安全的文章就介紹到這了,更多相關(guān)ConcurrentHashMap線程安全內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java基礎(chǔ)類學(xué)習(xí)之String詳解
這篇文章主要為大家詳細(xì)介紹了Java基礎(chǔ)類中String的相關(guān)知識(shí),文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)Java有一定的幫助,需要的可以參考一下2022-12-12Java Socket編程(五) 簡(jiǎn)單的WEB服務(wù)器
Java Socket編程(五) 簡(jiǎn)單的WEB服務(wù)器...2006-12-12Java 實(shí)戰(zhàn)項(xiàng)目錘煉之醫(yī)院門診收費(fèi)管理系統(tǒng)的實(shí)現(xiàn)流程
讀萬卷書不如行萬里路,只學(xué)書上的理論是遠(yuǎn)遠(yuǎn)不夠的,只有在實(shí)戰(zhàn)中才能獲得能力的提升,本篇文章手把手帶你用java+html+jdbc+mysql實(shí)現(xiàn)一個(gè)醫(yī)院門診收費(fèi)管理系統(tǒng),大家可以在過程中查缺補(bǔ)漏,提升水平2021-11-11Java+element實(shí)現(xiàn)excel的導(dǎo)入和導(dǎo)出
本文主要介紹了Java+element實(shí)現(xiàn)excel的導(dǎo)入和導(dǎo)出,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04基于list stream: reduce的使用實(shí)例
這篇文章主要介紹了list stream: reduce的使用實(shí)例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-09-09Java編程幾個(gè)循環(huán)實(shí)例代碼分享
這篇文章主要介紹了Java編程幾個(gè)循環(huán)實(shí)例代碼分享,多看多練,小編覺得還是挺不錯(cuò)的,這里分享給大家,供需要的朋友參考。2017-10-10