深入解析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/n/150734.html