深入解析Hashmap死循環

一、Hashmap死循環場景

在Java中，Hashmap是最常用的數據結構之一。它提供了一種快速的方式，將數據按照Key-Value的形式存儲和查找。然而，在一些特定場景下，Hashmap在使用過程中，會出現死循環，而且非常難以發現和調試。

因此，我們需要對Hashmap死循環現象進行深入分析和解釋。

二、循環Hashmap

在使用Hashmap時，會調用put方法將鍵值對放入Hashmap中。如果hashcode相同，即是「哈希衝突」，這時，Hashmap就會在相應的鏈表中依次查找，然後插入到該鏈表的尾部。如果發生大量的哈希衝突，Hashmap的內部鏈表將會很長，從而導致查找和插入的時間變慢。

這時，我們可以通過擴大Hashmap的容量（大小）來緩解鏈表過長的問題，但容量擴大會導致內存佔用上升，所以需要權衡考慮。

三、Hashmap死循環出現天劍

Hashmap死循環主要是因為在使用Hashmap時，進行Resizing操作的同時，又有一個線程正在對Hashmap進行遍歷，這樣就會導致鏈表出現環形結構。

如果在Hashmap處於「死循環狀態」下，其他線程進行Put操作，則可能會導致Put操作失敗，因為更多的桶被佔用，這可能會進一步加劇性能問題。

四、Hashmap死循環復現

Hashmap死循環很難直接重現，因為它主要是由多個因素共同作用形成的。無法通過單一的測試用例來直接證明是否存在Hashmap死循環。

但是，在多線程的環境下，Hashmap死循環很容易出現。因為Hashmap在並發環境下，可能會進行多個線程的Resize操作，這樣就可能會導致鏈表出現環形結構。

五、Hashmap死循環出現條件

Hashmap死循環造成的主要原因是由於多線程並發訪問，或者測試用例中出現的特殊情況造成的Hashmap性能問題。下面是造成Hashmap死循環的主要因素：

Hashmap容量過小，因為導致頻繁的Rehash操作
多線程並發操作，因為導致數據出現混亂
鏈表過長，因為導致查找時間和插入時間變慢
不同的key的hashcode相同，導致鏈表過長

六、Hashmap死循環圖解

下面是一張圖解，闡明了Hashmap在出現故障和死循環狀態下的鏈表結構。

   bucket1 --> Entry1 --> Entry2 --> ... --> Entryn --> ...
                 ^                                       |
                 |                                       V
                 ------------------------------------------

七、Hashmap死循環後果

Hashmap死循環的主要後果是系統性能下降，因為死循環會導致系統長時間阻塞。此外，還有可能會造成數據出現異常情況，進而進一步影響系統的穩定性和可用性。

八、Hashmap死循環是怎麼發生的

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {

  private static final long serialVersionUID = 362498820763181265L;

  //默認capacity，即初始化桶數組長度
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
  //最大容量，即桶數組的最大長度
  static final int MAXIMUM_CAPACITY = 1 << 30;
  //默認負裝因子，即允許桶的數量為l / DEFAULT_LOAD_FACTOR + 1個
  static final float DEFAULT_LOAD_FACTOR = 0.75f;
  //桶數組，鏈表結構
  transient Node[] table;
  //當前桶的數量
  transient int size;
  //threshold = capacity * load factor
  //threshold的作用是：決定什麼時候需要重建桶數組
  int threshold;
  //負載因子
  final float loadFactor;

  ... //省略其他代碼

  //Resize操作
  //如果通過put方法向Hashmap中添加元素時，桶數組超過了threshold，就會調用此方法進行Resize操作
  final Node[] resize() {
    Node[] 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;
      } else if ((newCap = oldCap << 1) = DEFAULT_INITIAL_CAPACITY)
        //數組長度擴大2倍
        newThr = 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);
    }
    //如果新的擴容閾值還沒有被賦值
    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[] newTab = (Node[])new Node[newCap];
    //修改table的指向，指向新的桶數組
    table = newTab;

    //將舊桶數組中元素複製到新桶數組中
    if (oldTab != null) {
      for (int j = 0; j < oldCap; ++j) {
        Node e;
        //獲取一條鏈表
        if ((e = oldTab[j]) != null) {
          //如果舊桶數組位置j上的元素不為空
          //置空舊桶數組位置j上的元素
          oldTab[j] = null;
          //處理這個鏈表中所有的元素
          if (e.next == null)
            //如果鏈表中只有一個元素，計算出新桶數組中的位置，並將元素添加進去
            newTab[e.hash & (newCap - 1)] = e;
          else if (e instanceof TreeNode)
            //如果這個鏈表是一顆紅黑樹，執行紅黑樹的轉移操作
            ((TreeNode)e).split(this, newTab, j, oldCap);
          else {
            //鏈表長度大於1，執行鏈表的轉移操作
            //loHead和loTail表示鏈表中，hash碰撞位於低位的元素和高位的元素，分別構成鏈表
            Node loHead = null, loTail = null;
            Node hiHead = null, hiTail = null;
            Node next;
            do {
              //循環遍歷原桶數組位置j上的鏈表
              next = e.next;
              if ((e.hash & oldCap) == 0) {
                //如果元素放置到新桶數組位置上的高位
                if (loTail == null)
                  loHead = e;
                else
                  loTail.next = e;
                loTail = e;
              }
              else {
                //如果元素放置到新桶數組位置上的低位
                if (hiTail == null)
                  hiHead = e;
                else
                  hiTail.next = e;
                hiTail = e;
              }
            } while ((e = next) != null);
            //將鏈表中低位的元素放入到新桶數組的相應位置上
            if (loTail != null) {
              loTail.next = null;
              newTab[j] = loHead;
            }
            //將鏈表中高位的元素放入到新桶數組的相應位置上
            if (hiTail != null) {
              hiTail.next = null;
              newTab[j + oldCap] = hiHead;
            }
          }
        }
      }
    }
    return newTab;
  }
}

九、Hashmap死循環JDK8

JDK8中移除了HashMap死循環的原因是，當多個線程在Resize()方法中同時使用CAS來更新next指針時，只有一個線程更新成功，其它線程會重試，這有效地預防了Hashmap死循環問題。

十、Hashmap死循環原因簡單解釋

在並發操作中，如果可以隨時持有一個資源，會導致這個資源的競爭。當這個資源是有狀態的，並且競爭一段時間後，可能會出現狀態不一致的問題。這個問題在Hashmap中得到了體現，即Hashmap的內部鏈表結構出現了環形結構。

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/150734.html