一段代码让你彻底搞懂HashMap的死循环
2020-05-16 本文已影响0人
张于宴
在多线程环境下，使用HashMap进行put操作会引起死循环，导致CPU利用率接近100%，HashMap在并发执行put操作时会引起死循环，是因为多线程会导致HashMap的Entry链表
形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，在get操作时遍历链表就会产生死循环。那么这个死循环是如何生成的呢？我们来具体分析下。
HashMap扩容流程
引发死循环，是在HashMap的扩容操作中，正常的扩容操作是这个流程。HashMap的扩容在put操作中会触发扩容，主要是三个方法：
微信图片_20200516112707.png
微信图片_202005161127071.png
微信图片_202005161127072.png
综合来说，HashMap一次扩容的过程：
1、取当前table的2倍作为新table的大小
2、根据算出的新table的大小new出一个新的Entry数组来，名为newTable
3、轮询原table的每一个位置，将每个位置上连接的Entry，算出在新table上的位置，并以链表形式连接
4、原table上的所有Entry全部轮询完毕之后，意味着原table上面的所有Entry已经移到了新的table上，HashMap中的table指向newTable
案例分析
这里我们写个简单的demo模拟一下transfer方法中的逻辑
public class HashMap {
private transient Entry[] table;
public void test() {
Entry c = new Entry("c", null);
Entry b = new Entry("b", c);
Entry a = new Entry("a", b);
table = new Entry[4];
table[1] = a;
System.out.println("原始链表：" + a.toString());
Thread thread = new Thread(new Runnable() {
@Override
public void run() {
Entry[] newTable = new Entry[8];
for (Entry e : table) {
if (null != e) {
System.out.println("线程1让出CPU时间片前,操作的entry为：" + e.toString());
}
while (null != e) {
Entry next = e.next;
//产生死循环主要在这里，第一次遍历上述的next为 b->c->null,
// 下一次遍历 b时，由于线程2修改成了 c->b->a->null导致 b 节点的next又重新指向 a节点
//线程1让出CPU时间片,等线程二操作完
sleep(5000);
System.out.println("线程1继续执行,操作的entry为：" + e.toString());
e.next = newTable[1];
newTable[1] = e;
// System.out.println("执行后的entry为："+e.toString());
System.out.println("=============================");
e = next;
}
}
table = newTable;
}
});
thread.start();
new Thread(new Runnable() {
@Override
public void run() {
Entry[] newTable = new Entry[8];
for (Entry e : table) {
if (null != e) {
System.out.println("线程2开始,操作的entry为：" + e.toString());
}
while (null != e) {
sleep(500);
Entry next = e.next;
e.next = newTable[1];
newTable[1] = e;
e = next;
}
}
System.out.println("线程2扩容完,entry为：" + newTable[1].toString());
sleep(6000);
table = newTable;
}
}).start();
sleep(20000);
System.out.println("2个线程扩容完毕后,最终entry为：" + table[1].value + "->" + table[1].next.value + "->" + table[1].next.next.value);
}
private void sleep(long time) {
try {
Thread.sleep(time);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public void transfer(Entry[] newTable) {
}
private int indexFor(int hash, int length) {
return hash & (length - 1);
}
///////////// HashMap节点移动相关逻辑 //////////////////
// 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;
// }
// }
// }
static class Entry {
private String value;
private Entry next;
private int hash = 1;
public Entry(String value, Entry next) {
this.value = value;
this.next = next;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public Entry getNext() {
return next;
}
public void setNext(Entry next) {
this.next = next;
}
@Override
public String toString() {
if (null != value) {
return value + "->" + (null == next ? null : next.toString());
}
return null;
}
}
}
调用上述test方法，输出结果为
微信图片_202005161127073.png
我们看到最终的一个结果是a->b->a的一个循环链表，其中节点c也丢失了。由此能看到hashmap线程不安全不仅体现在循环链表，还有可能数据丢失。
debug调试如下图
微信图片_202005161127074.png
总结
在并发的情况，发生扩容时，可能会产生循环链表，在执行get的时候，会触发死循环，引起CPU的100%问题，所以一定要避免在并发环境下使用HashMap。
