ConcurrentHashMap 學習小結

摘要： 推薦優先閱讀 Java 8系列之重新認識HashMap 1. 資料結構 JDK1.7的 ConcurrentHashMap 底層採用 分段的陣列+連結串列 實現。 JDK1.8的 ConcurrentHashMap 採用的資料結構跟 JDK1.8的 HashMap 結...

推薦優先閱讀 Java 8系列之重新認識HashMap

1. 資料結構

• JDK1.7的 ConcurrentHashMap 底層採用 分段的陣列+連結串列 實現。
• JDK1.8的 ConcurrentHashMap 採用的資料結構跟 JDK1.8的 HashMap 結構一樣，Node陣列+連結串列/紅黑二叉樹。

2. 加鎖方式

• JDK1.7中採用分段鎖方式，將整個桶陣列分割分段(Segment)，每一把鎖只鎖容器其中的一部資料(即該Segment所在範圍段)，多執行緒訪問容器裡不同資料段的資料時，就不會存在鎖競爭，提高併發效率。
• JDK1.8 中幾乎放棄了Segment的概念，採用 synchronized 和 CAS 來操作來控制併發，將鎖直接加在 Node 節點上，鎖的粒度更小，在加上JDK1.6以後，JDK 對 synchronized鎖做了很多優化，讓 ConcurrentHashMap 整體看起來就像優化過並且是執行緒安全的 HashMap，進一步提高了併發訪問效率。雖然在JDK1.8的原始碼中還能看到Segment的資料結構，但是簡化了不少屬性，應該是為了相容舊版本。

3. 執行緒安全的具體實現方式

• JDK1.7版：
  ConcurrentHashMap 是由 Segment 陣列結構和 HashEntry 陣列結構組成。
  Segment 實現了 ReentrantLock,所以 Segment 是一種可重入鎖，扮演鎖的角色。HashEntry 用於儲存鍵值對資料。
  首先將資料分為一段一段的儲存，然後給每一段資料分配一把鎖，當一個執行緒佔用鎖訪問其中一個段資料時，其他段的資料也能被其他執行緒訪問。
  鎖結構示意圖：
  
  

  image

• JDK1.8版本

  ConcurrentHashMap取消了Segment分段鎖，採用CAS和synchronized來保證併發安全。資料結構跟HashMap1.8的結構類似，陣列+連結串列/紅黑二叉樹。

  synchronized只鎖定當前連結串列或紅黑二叉樹的首節點，這樣只要hash不衝突，就不會產生併發，效率又提升N倍。

  鎖結構示意圖：

  

  image