【笔记】HashMap的头插死循环问题

本文主要是介绍【笔记】HashMap的头插死循环问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HashMap头插死循环是指在JDK1.7中，多线程环境下，HashMap进行扩容时由于多个线程一起执行扩容，可能会导致某一结点被错误插入头部并形成一个循环链表。
发生死循环的源码如下：

// hashmap由数组+链表构成
void transfer(Entry[] newTable) {Entry[] src = table;int newCapacity = newTable.length;//  遍历老的数组元素，移动到新数组里for (int j = 0; j < src.length; j++) {Entry<K,V> e = src[j];  // 老数组元素，一个链表if (e != null) {src[j] = null;  // 删除旧链表do {// 重点看这里的几行代码，采用的是头插法Entry<K,V> next = e.next;// 找到新链表对应数组下标int i = indexFor(e.hash, newCapacity);  e.next = newTable[i];newTable[i] = e;e = next;} while (e != null);}}
}

HashMap由数组+链表构成，假设容量为2，扩容因子=0.75：
在这里插入图片描述
现在有两个线程T1和T2还要put元素5和7，刚好hash冲突，都放在了下标1的位置，在线程T1和T2把要put的元素都被放进链表后（通过链表解决哈希冲突），它们发现超过了扩容因子，所以两个线程开始执行扩容：
此时T1、T2都指着同一个位置，都是e指针指着7，next指针指着5，注意！这里是不带头结点的链表，所以每个结点都存数据，e就是head，旧链表：
在这里插入图片描述
因为内存不够，它们都意识到要对hashmap进行扩容，扩容到4（0~3），新链表：

假设T1得到时间片先完成了扩容，然后通过新的hash函数变到了新位置（这里刚好还是1），然后用不带头结点的头插法把原来位置的元素挪过来，因为头插法所以顺序变反了（735变成357），但T2还是e指针指着7，next指针指着5（下图是T2的e）
在这里插入图片描述
在轮到T2扩容的时候，e.next=newTable[i], newTable[i] = e; e = next; 就形成了一个循环链表。

虽然JDK1.8改成尾插法了，不会死循环，但是因为put和get都没加同步锁，仍是线程不安全的