HashMap為何執行緒不安全？HashMap，HashTable，ConcurrentHashMap對比

2022 年 11 月 30 日
筆記
個人筆記

這兩天寫爬蟲幫組裡收集網上數據做訓練，需要進一步對收集到的json數據做數據清洗，結果就用到了多執行緒下的哈希表數據結構，猛地回想起自己看《Java並發編程的藝術》框架篇的時候，在ConcurrentHashMap的章節看到過使用HashMap是執行緒不安全的，HashTable雖然安全但效率很低，推薦使用ConcurrentHashMap巴拉巴拉，突然有了興趣來查閱一下各自的源碼，看看具體區別在哪裡呢？HashMao為什麼執行緒不安全？順帶記錄下來，還是那句話，好記性不如爛筆頭

我們知道的Java中的哈希表數據結構有下面三種

HashMap
HashTable
ConcurrentHashMap

下面就依次來看看它們是如何保證並發時可靠的，各自有什麼優缺點

HashMap

首先是大家都很熟悉的哈希表：HashMap，刷演算法題必備哈希表數據結構。它的存儲結構如下圖所示

很好看懂的一個圖，簡單來說就是HashMap採用的是拉鏈法處理哈希衝突。所謂哈希衝突就是由於哈希表根據哈希值索引目標節點來對隨機存取獲得O(1)的時間複雜度，那麼每個哈希值當然只能站一個節點，如果存在多個節點計算出的哈希值一致就發生了哈希衝突，此時一般有三種思路：

拉鏈法：在一個哈希值上設置一個數據集結構，也就是一個哈希值代表一個數據集，我們對數據集的隨機存取獲得O(1)時間複雜度，對數據集內獲取目標Key節點獲得O(m)時間複雜度，如果哈希值的數量遠多於數據集內節點的數量，那麼我們近似取到O(1)時間複雜度
開放定址法：一旦碰到哈希衝突就順延後來的節點的哈希值，比如節點A取哈希為1，而哈希值1,2,3上都已經有節點在了，那麼我們根據順延規則取4作為該節點的真實存儲位置，這種方案一般表現比較糟糕
再哈希法：同時構造多個不同的哈希函數，等發生哈希衝突時就使用第二個、第三個，第四個等等等等的其他的哈希函數計算地址，直到不發生衝突為止。雖然不易發生聚集，但是大大增加了計算時間

這裡我們常用的三種哈希表結構全部是採用的拉鏈法，這是一種認可度較高的解決方案，那麼拉鏈法就要求我們每個哈希值都獨立設置一個鏈表來存儲哈希衝突的節點。那麼我們關於多執行緒安全的問題自然也就來自於此。
總的來說，HashMap在多執行緒時視使用的Java版本有以下三大問題

數據覆蓋(一直存在)
死循環(JDK1.7前存在)
數據丟失(JDK1.7前存在)
我們一個一個來看

數據覆蓋

顧名思義，兩個執行緒同時往裡面放數據，但是其中一個數據放丟了，這個問題是根本問題，目前的HashMap依然有這個問題，出問題的原因也很簡單，HashMap本來就沒做多執行緒適配當然出問題，但是原理還是值得一看。

// 程式碼截取自HashMap.java，方法final V putVal()中
for (int binCount = 0; ; ++binCount) {
    // 根據下面程式碼，我們看出其實插入新節點就是反覆探測目前節點的next指針是否為空，若為空則在該指針上插入新節點
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

看完以後我們發現，其實就是很簡單的探測鏈表尾部的方法，看該節點next指針是否為null，若為null說明是尾節點，在其後插入新節點，那麼數據覆蓋的真相也就很簡單了：A，B兩個執行緒同時向同一個哈希值的鏈表發起插入，A探測到C節點的next為空然後時間片用完被換下，此時B也探測到C的next為空並完成了插入，等到A再次換入時間片，完成插入，最終，A，B運行結束，但B插入的新節點就這樣消失了。這就是數據覆蓋問題。

死循環與數據丟失
其實這兩個問題的核心都來自JDK1.7前，HashMap的擴容操作(擴容採用頭插法插入)會重新定位每個桶的下標，並採用頭插法將元素遷移到新數組中。而頭插法會將鏈表的順序翻轉，這也是造成死循環和數據丟失的關鍵。

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    // 採用頭插法
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

怎麼一回事呢？

現在假設執行緒啟動，有執行緒A和執行緒B都準備對HashMap進行擴容操作，此時A和B指向的都是鏈表的頭節點NodeA，而A和B的下一個節點的指針即head.next和head.next都指向NodeB節點。

那麼，開始擴容，這時候，假設執行緒B的時間片用完，被換下CPU，而執行緒A開始執行擴容操作，一直到執行緒A擴容完成後，執行緒B才被喚醒。

此時因為HashMap擴容採用的是頭插法，執行緒A執行之後，鏈表中的節點順序已經倒轉，本來NodeA->NodeB，現在變成了NodeB->NodeA。但就緒態的執行緒B對於發生的一切都不清楚，所以它指向的節點引用依然沒變。那麼一旦B被換上CPU，重複一次剛剛A做過的事情，就會導致NodeA和NodeB的next指針相互指向，導致死循環和數據丟失。

不過JDK1.8以後，HashMap的哈希值擴容改為了尾插法擴容，就不會再出現這些問題了。

HashTable

效率很差的一個類，根據我自己的周邊統計學，我的感覺是這個玩意根本沒人用，用它就類似於如果你給線上項目的MySQL突然整出個表級鎖一樣，等你的只能是一通臭罵！為什麼呢？看下面

// 你就看這個synchronized關鍵字就可以了，不用往下看了
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

很明顯了。HashTable採用了Synchronized關鍵字來保證執行緒安全。

我們知道Synchronized關鍵字的底層原理是給對象頭上的MarkWord的內容做改動從而將該對象當作互斥變數使用，也就是說，這把鎖是對象級別的。
問題就在於我本來哈希衝突只是一個哈希值上的衝突，而你的解決方案是鎖住整個哈希表，這會不會有點太過分了？可以說表級鎖的比喻是很貼切了。

不推薦使用，效率很低。

ConcurrentHashMap

《Java並發編程的藝術》裡面提到的第一個並髮結構，它的思路就是在HashTable表級鎖的基礎上把它改為行級鎖，什麼意思呢？放源碼

// 截取自ConcurrentHashMap.java，final V putVal()方法
// 注意下面這句，f 是我們需要的哈希值對應的首節點
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
      if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
          break;                   // no lock when adding to empty bin
  }
  else if ((fh = f.hash) == MOVED)
      tab = helpTransfer(tab, f);
  else if (onlyIfAbsent // check first node without acquiring lock
           && fh == hash
           && ((fk = f.key) == key || (fk != null && key.equals(fk)))
           && (fv = f.val) != null)
      return fv;
  else {
      V oldVal = null;
// 來到這裡，上面的都不用看，主要是排查初始化情況，這裡synchronized(f)就解釋清楚了我們的ConcurrentHashMap的方法
      synchronized (f) {
          if (tabAt(tab, i) == f) {
              if (fh >= 0) {
                  binCount = 1;
                  for (Node<K,V> e = f;; ++binCount) {
                      K ek;
                      if (e.hash == hash &&
                          ((ek = e.key) == key ||
                           (ek != null && key.equals(ek)))) {
                          oldVal = e.val;
                          if (!onlyIfAbsent)
                              e.val = value;
                          break;
                      }
                      Node<K,V> pred = e;
                      if ((e = e.next) == null) {
                          pred.next = new Node<K,V>(hash, key, value);
                          break;
                      }
                  }
              }

很明顯，ConcurrentHashMap同樣是通過Synchronized關鍵字來實現執行緒安全的，只不過這把鎖從原來的表級鎖，變為了以首節點為對象的行級鎖，當我們並發的對ConcurrentHashMap操作時，鎖只會鎖住某一個哈希值，而不會鎖住整個表，保證了我們的哈希表在高並發場景下的效率。

總結

HashMap只適用於非並發情況下，ConcurrentHashMap適用於並發情況下，而HashTable則不推薦使用

Tags: 個人筆記