# 并发容器：HashMap死循环形成的原因是什么？

在这里插入图片描述

# 介绍

HashMap 死循环主要发生在 JDK 1.7 及以前的版本中，其根本原因在于：在多线程并发扩容时，HashMap 使用的“头插法”倒序迁移链表节点，导致链表形成了环形结构（ $A \rightarrow B \rightarrow A$ ）

当后续对该位置进行 get() 或 put() 操作遍历此链表时，CPU 就会陷入 while(e != null) 的死循环，占用率飙升至 100%

void resize(int newCapacity) {
	Entry[] oldTable = table;
	int oldCapacity = oldTable.length;
	if (oldCapacity == MAXIMUM_CAPACITY) {
		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函数中，默认情况下rehash为false

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;
        }
    }
}

# 正常的transfer过程

例子不考虑扩容阈值，假设放4个元素时开始扩容

在这里插入图片描述

主要有2个有意思的地方

原来在oldTable[i]位置的元素，会被放到newTable[i]或者newTable[i+oldTable.length]的位置
链表在复制的时候会反转

# 并发下异常的transfer

假设线程1执行完Entry<K,V> next = e.next后被挂起，此时e指向key3，next指向key7

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; // 线程1执行完这一句被挂起
            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;
        }
    }
}