HashMap之JAVA7下的死循环

快来打我* 2023-07-09 10:29 17阅读 0赞

# 概述 #

上篇分析了HashMap的设计思想以及Java7和Java8源码上的实现，当然还有一些"坑"还没填完，比如大家都知道HashMap是线程不安全的数据结构，多线程情况下HashMap会引起死循环引用，它是怎么产生的？Java8引入了红黑树，那是怎么提高效率的？本篇先填第一个坑，还是以图解的形式加深理解。

### Java7分析 ###

通过上一篇的整体学习，可以知道当存入的键值对超过HashMap的阀值时，HashMap会扩容，即创建一个新的数组，并将原数组里的键值对"转移"到新的数组中。在“转移”的时候，会根据新的数组长度和要转移的键值对key值重新计算在新数组中的位置。重温下Java7中负责"转移"功能的代码

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

为了加深理解，画个图如下

![format_png][]

这里假设扩容前后5号坑石头、盖伦、蒙多的hash值与新旧数组长度取模运算后还是5。上篇文章也总结了，Java7扩容转移前后链表顺序会倒置。当只有单线程操作hashMap时，一切都是那么美好，但是如果多线程同时操作一个hashMap，问题就来了，下面看下多线程操作一个hashMap在Java7源码下是怎样引起死循环引用。

前戏是这样的：有两个线程分别叫Thread1和Thread2，它们都有操作同一个hashMap的权利，假设hashMap中的键值对是12个，石头和盖伦扩容前后的hash值与新旧数组长度取模运算后还是5。扩容前的模拟堆内存情况如图

![format_png 1][]

Thread1得到执行权(Thread2被挂起)，Thread1往hashMap里put第13个键值对的时候判断超过阀值，执行扩容操作，Thread1创建了一个新数组，还没来得及转移旧键值对的时候，系统时间片反手切到Thread2(Thread1被挂起)，整个过程用图表示

![format_png 2][]

可以看到Thread1只是创建了个新数组，还没来得及转移就被挂起了，新数组没有内容，此时在Thread1的视角认的是e是石头，next是盖伦；此时的模拟内存图情况

![format_png 3][]

再看下Thread2的操作，同样Thread2往hashMap里put第13个键值对的时候判断超过阀值，执行扩容操作，Thread2先创建一个新数组，不同的是，Thread2运气好，在时间片轮换前转移工作也走完了。第一次遍历

![format_png 4][]

第二次遍历

![format_png 5][]

此时模拟的内存情况

![format_png 6][]

可以看到此时对于盖伦来说，他的next是石头；对于石头来说，它的next为null，隐患就此埋下。接下来时间片又切到Thread1(停了半天终于轮到我出场了)，先看下Thread1的处境

![format_png 7][]

结合代码分析如下

第一步：

![format_png 8][]

第二步：

![format_png 9][]

第三步：

![format_png 10][]

第四步：

![format_png 11][]

第五步：

![format_png 12][]

第六步：

![format_png 13][]

第七步：

![format_png 14][]

第八步：

![format_png 15][]

第九步：

![format_png 16][]

第10步：

![format_png 17][]

到这终于看到盖伦和石头"互指"，水乳交融。

![format_png 18][]

那这会带来什么后果呢？后续操作新数组的5号坑会进入死循环(注意，操作其他坑并不会有问题)，例如Java7 put操作

![format_png 19][]

Java7 get操作会执行getEntry，同样会引起死循环。

![format_png 20][]

到此，Java7多线程操作HashMap可能形成死循环的原因剖析完成。

### Java8分析 ###

通过上一篇的学习可知，Java7转移前后位置颠倒，而Java8转移键值对前后位置不变。同样的前戏，看下代码

![format_png 21][]

此时模拟堆内存情况

![format_png 3][]

Thread1的情况

![format_png 22][]

这时候Thread2获得执行权，扩容并完成转移工作，通过上篇的学习可知，Java8在转移前会创建两条链表，即扩容后位置不加原数组长度的lo链和要加原数组长度的hi链，这里假设石头和盖伦扩容前后都在5号坑，即这是一条lo链(其实就算不在同一个坑也不影响，原因就是Java8扩容前后链顺序不变)。Thread2遍历第一次

![format_png 23][]

第二次

![format_png 24][]

可以看到Thread2全程是没有去修改石头和盖伦的引用关系，石头.next是盖伦，盖伦.next是null。那么Thread1得到执行权后其实只是重复了Thread2的工作。

### 总结 ###

通过源码分析，J**ava7在多线程操作hashmap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系；Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。**那是不是意味着Java8就可以把HashMap用在多线程中呢？个人感觉即使不会出现死循环，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，建议使用ConcurrentHashMap。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhOTVjYWNhYmM?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhOTFhYTdlOTI?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhOTIyNjRiYzI?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhOTQ2OGUzOWE?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhOTI5ZDFkZDc?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhOTM5NzkxNWM?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhZDdiMGM4YjI?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhZGJiYzg5NmI?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhZGU4NTkyNDI?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhZTRkZDAzNmQ?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhZWMwNTRiNmY?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWVhZGRhOWEyNmM?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViMDQ4YzZmMDc?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViMGIxYWUwY2E?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViMGMzMTk3MGY?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViMWRiMTZhMzE?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViMTFmNWY0NzI?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViMzFhZTk5ZTI?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViMzdhMTY4MGE?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViM2YzNzU3Njk?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViMzk4ZjIzMDQ?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViM2UwN2QzYzk?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWViNGJmYTcxNDk?x-oss-process=image/format,png
[format_png 23]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi8zLzE2MDFjODJhNGNhNTZjY2Y?x-oss-process=image/format,png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxNy8xMi80LzE2MDIxZWZjYjQ3ZmQ1N2Y?x-oss-process=image/format,png

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 HashMap的死循环

于HashMap并非是线程安全的，所以在高并发的情况下必然会出现问题。如果是在单线程下使用HashMap，自然是没有问题的，如果后期由于代码优化，这段逻辑引入了多线程并发...

Bertha 。/ 2024年04月17日 05:34/ 0 赞/ 100 阅读

相关 HashMap的死循环

问题由于HashMap并非是线程安全的，所以在高并发的情况下必然会出现问题，这是一个普遍的问题，虽然网上分析的文章很多，还是觉得有必须写一篇文章，让关注我公众号的同学能够

墨蓝/ 2024年03月22日 17:55/ 0 赞/ 80 阅读

相关 HashMap的死循环

HashMap的死循环历史背景数据插入原理导致死循环的原因解决方案总结历史背景 HashMap的死循环只是在JDK1.7

拼搏现实的明天。/ 2023年09月26日 23:27/ 0 赞/ 154 阅读

相关 HashMap之JAVA7下的死循环

概述上篇分析了HashMap的设计思想以及Java7和Java8源码上的实现，当然还有一些"坑"还没填完，比如大家都知道HashMap是线程不安全的数据结构，多线程情况

快来打我*/ 2023年07月09日 10:29/ 0 赞/ 18 阅读

相关 Java1.7 HashMap的死循环原因

原文链接： https://coolshell.cn/articles/9606.html https://blog.csdn.net/v123411739/artic

向右看齐/ 2023年06月24日 04:44/ 0 赞/ 45 阅读

相关 HashMap在并发下引起的死循环

问题的症状发现线上程序经常占了100%的CPU，查看堆栈，你会发现程序都hang在了HashMap.get()这个方法上了，重启程序后问题消失，但是过段时间又会来。而且

小鱼儿/ 2022年12月13日 04:35/ 0 赞/ 173 阅读

相关 JDK1.7的HashMap死循环

> 为什么在JDK1.7多线程情况下会很容易出现HashMap死循环，这个还是要根据它采取的扩容策略来看，它的扩容策略是头插法，因此会导致这样的问题。在JDK1.8改进为尾插法

我不是女神ヾ/ 2022年11月30日 15:53/ 0 赞/ 206 阅读

相关【HashMap】JAVA HASHMAP的死循环

问题的症状从前我们的Java代码因为一些原因使用了HashMap这个东西，但是当时的程序是单线程的，一切都没有问题。后来，我们的程序性能有问题，所以需要变成多线程的，于

落日映苍穹つ/ 2022年06月15日 08:23/ 0 赞/ 257 阅读

相关 Java HashMap的死循环

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障，并且这个事发生了很多次，原因是在Java语言在并发情况下使用HashMap造成Race Condition，从而导

- 日理万妓/ 2022年06月14日 00:43/ 0 赞/ 241 阅读

相关 Java-HashMap死循环问题

Hash表数据结构 HashMap通常会用一个指针数组（假设为table\[\]）来做分散所有的key，当一个key被加入时，会通过Hash算法通过key算出这个数组的下

末蓝、/ 2022年05月22日 10:20/ 0 赞/ 265 阅读