01、多線程下擴容會死循環

眾所周知，HashMap 是通過拉鏈法來解決哈希沖突的，也就是當哈希沖突時，會將相同哈希值的鍵值對通過鏈表的形式存放起來。

JDK 7 時，采用的是頭部插入的方式來存放鏈表的，也就是下一個沖突的鍵值對會放在上一個鍵值對的前面（同一位置上的新元素被放在鏈表的頭部）。擴容的時候就有可能導致出現環形鏈表，造成死循環。

resize 方法的源碼：

// newCapacity為新的容量
void resize(int newCapacity) {
  // 小數組，臨時過度下
  Entry[] oldTable = table;
  // 擴容前的容量
  int oldCapacity = oldTable.length;
  // MAXIMUM_CAPACITY 為最大容量，2 的 30 次方 = 1<<30
  if (oldCapacity == MAXIMUM_CAPACITY) {
      // 容量調整為 Integer 的最大值 0x7fffffff（十六進制）=2 的 31 次方-1
      threshold = Integer.MAX_VALUE;
      return;
  }

  // 初始化一個新的數組（大容量）
  Entry[] newTable = new Entry[newCapacity];
  // 把小數組的元素轉移到大數組中
  transfer(newTable, initHashSeedAsNeeded(newCapacity));
  // 引用新的大數組
  table = newTable;
  // 重新計算閾值
  threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

transfer 方法用來轉移，將小數組的元素拷貝到新的數組中。

void transfer(Entry[] newTable, boolean rehash) {
  // 新的容量
  int newCapacity = newTable.length;
  // 遍歷小數組
  for (Entry<K,V> e : table) {
      while(null != e) {
          // 拉鏈法，相同 key 上的不同值
          Entry<K,V> next = e.next;
          // 是否需要重新計算 hash
          if (rehash) {
              e.hash = null == e.key ? 0 : hash(e.key);
          }
          // 根據大數組的容量，和鍵的 hash 計算元素在數組中的下標
          int i = indexFor(e.hash, newCapacity);

          // 同一位置上的新元素被放在鏈表的頭部
          e.next = newTable[i];

          // 放在新的數組上
          newTable[i] = e;

          // 鏈表上的下一個元素
          e = next;
      }
  }
}

注意 e.next = newTable[i] 和 newTable[i] = e 這兩行代碼，就會將同一位置上的新元素被放在鏈表的頭部。

擴容前的樣子假如是下面這樣子。

那么正常擴容后就是下面這樣子。

假設現在有兩個線程同時進行擴容，線程 A 在執行到 newTable[i] = e; 被掛起，此時線程 A 中：e=3、next=7、e.next=null

線程 B 開始執行，并且完成了數據轉移。

此時，7 的 next 為 3，3 的 next 為 null。

隨后線程A獲得CPU時間片繼續執行 newTable[i] = e，將3放入新數組對應的位置，執行完此輪循環后線程A的情況如下：

執行下一輪循環，此時 e=7，原本線程 A 中 7 的 next 為 5，但由于 table 是線程 A 和線程 B 共享的，而線程 B 順利執行完后，7 的 next 變成了 3，那么此時線程 A 中，7 的 next 也為 3 了。

采用頭部插入的方式，變成了下面這樣子：

好像也沒什么問題，此時 next = 3，e = 3。

進行下一輪循環，但此時，由于線程 B 將 3 的 next 變為了 null，所以此輪循環應該是最后一輪了。

接下來當執行完 e.next=newTable[i] 即 3.next=7 后，3 和 7 之間就相互鏈接了，執行完 newTable[i]=e 后，3 被頭插法重新插入到鏈表中，執行結果如下圖所示：

套娃開始，元素 5 也就成了棄嬰，慘~~~

不過，JDK 8 時已經修復了這個問題，擴容時會保持鏈表原來的順序，參照HashMap 擴容機制的這一篇。

02、多線程下 put 會導致元素丟失

正常情況下，當發生哈希沖突時，HashMap 是這樣的：

但多線程同時執行 put 操作時，如果計算出來的索引位置是相同的，那會造成前一個 key 被后一個 key 覆蓋，從而導致元素的丟失。

put 的源碼：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
             boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;

  // 步驟①：tab為空則創建
  if ((tab = table) == null || (n = tab.length) == 0)
      n = (tab = resize()).length;

  // 步驟②：計算index，并對null做處理 
  if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newNode(hash, key, value, null);
  else {
      Node<K,V> e; K k;

      // 步驟③：節點key存在，直接覆蓋value
      if (p.hash == hash &&
          ((k = p.key) == key || (key != null && key.equals(k))))
          e = p;

      // 步驟④：判斷該鏈為紅黑樹
      else if (p instanceof TreeNode)
          e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

      // 步驟⑤：該鏈為鏈表
      else {
          for (int binCount = 0; ; ++binCount) {
              if ((e = p.next) == null) {
                  p.next = newNode(hash, key, value, null);

                  //鏈表長度大于8轉換為紅黑樹進行處理
                  if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                      treeifyBin(tab, hash);
                  break;
              }

              // key已經存在直接覆蓋value
              if (e.hash == hash &&
                  ((k = e.key) == key || (key != null && key.equals(k))))
                  break;
              p = e;
          }
      }

      // 步驟⑥、直接覆蓋
      if (e != null) { // existing mapping for key
          V oldValue = e.value;
          if (!onlyIfAbsent || oldValue == null)
              e.value = value;
          afterNodeAccess(e);
          return oldValue;
      }
  }
  ++modCount;

  // 步驟⑦：超過最大容量 就擴容
  if (++size > threshold)
      resize();
  afterNodeInsertion(evict);
  return null;
}

問題發生在步驟 ② 這里：

if ((p = tab[i = (n - 1) & hash]) == null)
  tab[i] = newNode(hash, key, value, null);

兩個線程都執行了 if 語句，假設線程 A 先執行了 tab[i] = newNode(hash, key, value, null)，那 table 是這樣的：

接著，線程 B 執行了 tab[i] = newNode(hash, key, value, null)，那 table 是這樣的：

3 被干掉了。

03、put 和 get 并發時會導致 get 到 null

線程 A 執行put時，因為元素個數超出閾值而出現擴容，線程B 此時執行get，有可能導致這個問題。

注意來看 resize 源碼：

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table;
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  int oldThr = threshold;
  int newCap, newThr = 0;
  if (oldCap > 0) {
      // 超過最大值就不再擴充了，就只好隨你碰撞去吧
      if (oldCap >= MAXIMUM_CAPACITY) {
          threshold = Integer.MAX_VALUE;
          return oldTab;
      }
      // 沒超過最大值，就擴充為原來的2倍
      else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
               oldCap >= DEFAULT_INITIAL_CAPACITY)
          newThr = oldThr << 1; // double threshold
  }
  else if (oldThr > 0) // initial capacity was placed in threshold
      newCap = oldThr;
  else {               // zero initial threshold signifies using defaults
      newCap = DEFAULT_INITIAL_CAPACITY;
      newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  // 計算新的resize上限
  if (newThr == 0) {
      float ft = (float)newCap * loadFactor;
      newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  @SuppressWarnings({"rawtypes","unchecked"})
      Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
}

線程 A 執行完 table = newTab 之后，線程 B 中的 table 此時也發生了變化，此時去 get 的時候當然會 get 到 null 了，因為元素還沒有轉移。

這是《Java 程序員進階之路》專欄的第 58 篇，我們來聊了聊為什么 HashMap 是線程不安全的。

為了便于大家更系統化地學習 Java，二哥已經將《Java 程序員進階之路》專欄開源到 GitHub 上了，大家只需輕輕地 star 一下，就可以和所有的小伙伴一起打怪升級了。

GitHub 地址：https://github.com/itwanger/toBeBetterJavaer

到此這篇關于Java京東面試題之為什么HashMap線程不安全的文章就介紹到這了,更多相關Java HashMap線程內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！

原文鏈接：https://blog.csdn.net/qing_gee/article/details/120559630