為什麼ConcurrentHashMap是執行緒安全的?

語言: CN / TW / HK

「這是我參與2022首次更文挑戰的第3天,活動詳情檢視:2022首次更文挑戰」。

ConcurrentHashMap 是 HashMap 的多執行緒版本,HashMap 在併發操作時會有各種問題,比如死迴圈問題、資料覆蓋等問題。而這些問題,只要使用 ConcurrentHashMap 就可以完美解決了,那問題來了,ConcurrentHashMap 是如何保證執行緒安全的?它的底層又是如何實現的?接下來我們一起來看。

JDK 1.7 底層實現

ConcurrentHashMap 在不同的 JDK 版本中實現是不同的,在 JDK 1.7 中它使用的是陣列加連結串列的形式實現的,而陣列又分為:大陣列 Segment 和小陣列 HashEntry。 大陣列 Segment 可以理解為 MySQL 中的資料庫,而每個資料庫(Segment)中又有很多張表 HashEntry,每個 HashEntry 中又有多條資料,這些資料是用連結串列連線的,如下圖所示: image.png

JDK 1.7 執行緒安全實現

瞭解了 ConcurrentHashMap 的底層實現,再看它的執行緒安全實現就比較簡單了。 接下來,我們通過新增元素 put 方法,來看 JDK 1.7 中 ConcurrentHashMap 是如何保證執行緒安全的,具體實現原始碼如下: java 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 內部陣列 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 到特定位置,如果超過閾值則進行 rehash // 忽略其他程式碼... } } } finally { // 釋放鎖 unlock(); } return oldValue; } 從上述原始碼我們可以看出,Segment 本身是基於 ReentrantLock 實現的加鎖和釋放鎖的操作,這樣就能保證多個執行緒同時訪問 ConcurrentHashMap 時,同一時間只有一個執行緒能操作相應的節點,這樣就保證了 ConcurrentHashMap 的執行緒安全了。 也就是說 ConcurrentHashMap 的執行緒安全是建立在 Segment 加鎖的基礎上的,所以我們把它稱之為分段鎖或片段鎖,如下圖所示: image.png

JDK 1.8 底層實現

在 JDK 1.7 中,ConcurrentHashMap 雖然是執行緒安全的,但因為它的底層實現是陣列 + 連結串列的形式,所以在資料比較多的情況下訪問是很慢的,因為要遍歷整個連結串列,而 JDK 1.8 則使用了陣列 + 連結串列/紅黑樹的方式優化了 ConcurrentHashMap 的實現,具體實現結構如下: image.png 連結串列升級為紅黑樹的規則:當連結串列長度大於 8,並且陣列的長度大於 64 時,連結串列就會升級為紅黑樹的結構。

PS:ConcurrentHashMap 在 JDK 1.8 雖然保留了 Segment 的定義,但這僅僅是為了保證序列化時的相容性,不再有任何結構上的用處了。

JDK 1.8 執行緒安全實現

在 JDK 1.8 中 ConcurrentHashMap 使用的是 CAS + volatile 或 synchronized 的方式來保證執行緒安全的,它的核心實現原始碼如下: java 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) { // 節點為空 // 利用 CAS 去進行無鎖執行緒安全操作,如果 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) { // 細粒度的同步修改操作... } } // 如果超過閾值,升級為紅黑樹 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 來初始化。如果容器不為空則根據儲存的元素計算該位置是否為空,如果為空則利用 CAS 設定該節點;如果不為空則使用 synchronize 加鎖,遍歷桶中的資料,替換或新增節點到桶中,最後再判斷是否需要轉為紅黑樹,這樣就能保證併發訪問時的執行緒安全了。 我們把上述流程簡化一下,我們可以簡單的認為在 JDK 1.8 中,ConcurrentHashMap 是在頭節點加鎖來保證執行緒安全的,鎖的粒度相比 Segment 來說更小了,發生衝突和加鎖的頻率降低了,併發操作的效能就提高了。而且 JDK 1.8 使用的是紅黑樹優化了之前的固定連結串列,那麼當資料量比較大的時候,查詢效能也得到了很大的提升,從之前的 O(n) 優化到了 O(logn) 的時間複雜度,具體加鎖示意圖如下: image.png

總結

ConcurrentHashMap 在 JDK 1.7 時使用的是資料加連結串列的形式實現的,其中陣列分為兩類:大陣列 Segment 和小陣列 HashEntry,而加鎖是通過給 Segment 新增 ReentrantLock 鎖來實現執行緒安全的。而 JDK 1.8 中 ConcurrentHashMap 使用的是陣列+連結串列/紅黑樹的方式實現的,它是通過 CAS 或 synchronized 來實現執行緒安全的,並且它的鎖粒度更小,查詢效能也更高。 ​

是非審之於己,譭譽聽之於人,得失安之於數。

公眾號:Java面試真題解析

文章合集:https://gitee.com/mydb/interview