Java并發-20.ConcurrentHashMap

0. HashMap和HashTable

• HashMap線程不安全

  多線程下HashMap的put操作可能導緻Entry連結清單形成環形資料結構，next節點永不為空，就形成了死循環擷取Entry，例如：

final HashMap<String, String> map = new HashMap<>(2);
        Thread t = new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                new Thread(() -> map.put(UUID.randomUUID().toString(), ""), "ftf" + i).start();
            }
        }, "tft");
        t.start();
        t.join();           

複制

• HashTable用Synchronized保證線程安全，線程激烈競争時效率低下。

1. ConcurrentHashMap的結構

• 由Segment數組和HashEntry數組組成
  • Segment
    • 一種ReentrantLock
    • 作為鎖的角色
    • 數組結構，連結清單結構
  • HashEntry
    • 用于存儲鍵值對
    • 一個Segment包含一個HashEntry
    • 一個HashEntry是一個連結清單結構的元素
• 每個Segment守護着一個HashEntry數組的元素，修改HashSet前要現擷取對應的Segment鎖。

image.png

2. ConcurrentHashMap初始化

• 用initialCapacity，loadFactor，ConcurrencyLevel幾個參數來初始化Segment數組，段偏移量segmentShift，段掩碼segmentMask和每個segment裡面的HashEntry來實作的

2.1 初始化segment數組

• segment數組長度通過concurrencyLevel計算得到
• 數組長度是大于concurrencyLevel的最小2的N次方
• 長度最大值是2^16 = 65536

2.2 segmentShift和segmentMask初始化

• sshift等于ssize從1左移的位數，預設等于4（concurrencyLevel預設等于16，左移4位）
• segmentShift用于定位參與散列運算的位數，等于32 - sshift，預設也就是28
• segmentMask是散列運算的掩碼，等于ssize - 1，預設也就是15
• ssize最大值65536，是以segmentShift最大值16，segmentMask最大值65535

2.3 初始化每個segment

• 以兩個參數初始化每個segment
  • initialCapacity是ConcurrentHashMap的初始化容量
  • loadfactor是每個segment的負載因子
• HashEntry數組長度cap等于initialCapacity除以ssize的倍數c，c大于1就取大于等于c的2^N
• segment容量threshold = (int) cap * loadFactory，預設initialCapacity=16，loadfactory=0.75，cap=1，threshold=0

2.4 定位Segment

• 插入和擷取元素的時候，需要先通過Hash算法定位Segment
• ConcurrentHashMap會對元素的hashCode進行再一次Hash，目的是減少Hash沖突
• 定位segment的hash算法：(hash >>> segmentShift) & segmentMask

3. ConcurrentHashMap的操作

• get操作
  • 經過一次再散列，通過這個散列值定位到Segment，再通過雜湊演算法定位到元素。
  • 高效，不需要加鎖，除非讀到了空值再加鎖重讀
  • get方法用到的共享變量都定義為volatile類型，例如Segment大小，存儲HashEntry的value
• put操作
  • put操作要加鎖
  • 兩步：
    • 判斷是否需要擴容
    • 擴容：
      • 先建立一個容量是原容量兩倍的數組，再将原數組元素散列後插入新數組
      • 不會對整個容器擴容，隻對某個segment擴容
• size操作
  • 先嘗試2次通過不所處Segment的方式統計各Segment大小，如果統計過程中容器count發生了變化，再通過加鎖的方式統計所有Segment大小
  • 判斷count發生變化用了，modCount變量（就是CAS咯）