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