HashMap中环及死循环形成原因分析

本文通过源码分析并发情况下jdk1.7中HashMap形成的著名的死循环问题。

进入分析模式以前了解下几个必备知识点：

1.JVM内存模型

本文只做必要的简单介绍

主内存、工作内存、执行引擎

HashMap中环及死循环形成原因分析

2.put源码逻辑流程

HashMap中环及死循环形成原因分析

3.HashMap.Entry结构

HashMap中环及死循环形成原因分析

好了, 熟悉以上知识点后，可以开始按照假定的线程执行步骤来重现环的形成和死循环的发生

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逆序转移,有可能造成环的形成,形成环之后循环取元素时造成死循环