本文通过源码分析并发情况下jdk1.7中HashMap形成的著名的死循环问题。
进入分析模式以前了解下几个必备知识点：
1.JVM内存模型
本文只做必要的简单介绍
主内存、工作内存、执行引擎
2.put源码逻辑流程
3.HashMap.Entry结构
好了, 熟悉以上知识点后，可以开始按照假定的线程执行步骤来重现环的形成和死循环的发生
1.初始化一个Map
final Map<String, Object> map = new HashMap<String, Object>(4);
2.线程安全的put三个对象
map.put("1","S");
map.put("7","A");
map.put("13","C");
此时在堆中已经为HashMap分配一块内存,结构如下
3.用多线程制造并发put
ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
for(int i = 0; i<1000;i++){
executor.execute(new Thread(){
public void run(){
map.put(Math.random()*10+"", "hello world");
}
});
}
executor.shutdown();
4.假设此时并发线程thread1发起操作put("17","A");扩容触发执行到途中绿框那一行,cpu分配的时间片用完,上下文切换,table保存到thread1工作内存中
5.假设此时并发线程thread2发起操作put("27","Aa");触发扩容发生;继续假设thread2有够多的时间片;可以循环足够次数将原始的hashMap中的元素全部转移，以下蓝框内代码循环三次
6.转移第一次循环后
7.转移第二次循环后;让我们假设第二次循环在newTable上的哈希后下标和第一个元素是在同一下标(此二连续的位置分配在同一下标是后面形成环的必要条件)
8.转移第三次循环后;让我们假设第三次循环在newTable上的哈希后下标和第一,第二个元素不是同一下标
9.扩容完成thread2将工作空间了的的newTable赋值给table
并加入新对象后
10.这时thread2执行完成,thread1分配的CPU执行周期争取到了执行时间
假设执行此代码的系统优化结果是store-load;store-store指令未重排序
11.thread1接着绿色框框内的往下执行
12.thread1循环执行
13.thread1循环执行;形成环
14.thread1执行赋值
15.死循环的形成有两种情况:
a.此时thread3来put元素落在下标5上且造成再一次扩容,则会陷入死循环
b.get元素的key下标值也是5且不是这两个元素中的任何一个, 则会陷入死循环
源码如下:
总结: 根本原因是HashMap中的table是共享且非线程安全的。
在触发扩容条件时,并发对HashMap的table进行扩容时会对table逆序转移,有可能造成环的形成,形成环之后循环取元素时造成死循环
