HashMap并发中死循环分析

Myth丶恋晨 2023-05-29 13:07 39阅读 0赞

*  [HashMap并发场景分析][HashMap]
    
     *  [背景][Link 1]
     *  [HashMap并发中存在的问题][HashMap 1]
        
         *  [并发场景下会导致死循环分析][Link 2]
            
             *  [JDK1.8存不存在死循环问题][JDK1.8]
         *  [总结][Link 3]
            
             *  [参考链接][Link 4]

# HashMap并发场景分析 #

## 背景 ##

> 看书过程中《Java并发编程的艺术》,在看这本书的过程中，作者提到，在并发编程中，使用HashMap可能导致程序死循环，那么作者说的到底对不对呢，为什么会这样呢，现在有没有进行改进呢，所以就进行查阅资料，进行学习，并总结成以下文章

## HashMap并发中存在的问题 ##

1.  非线程安全

> 这个是众所周知的

1.  扩容导致死循环

> 这个问题 的背景是JDK 1.7中，JDK1.8中hashMap源码进行了修改，应没有此问题，所以导致死循环问题，只在JDK7中存在

### 并发场景下会导致死循环分析 ###

模拟一个场景，有原HashMap如下: ![image][]

多线程场景下，有线程一和线程二，同时对map 进行扩容, ![image][image 1]

当线程一执行到如下代码时被挂起 ![image][image 2]

此时线程1的数据结构为,table已经扩容完毕，重新计算每个元素位置时被挂起，此时key为3 的还在1的位置， 3的next 为7 ![image][image 3] 这时，线程2完成扩容，扩容后的数据结构为 ![image][image 4]

当线程1被调度回来执行之后，因为线程一执行的e.next = newTable\[i\]; 将key3插入到3号位置，同时3.next = key7, 此时e= key3, next = key7;

![image][image 5]

![image][image 6] 当执行到e=next的时候，e=key7，next=key7；

然后开始下一轮while。但此时因为线程二已经将key=7的next设置为key3（问题就在这里，线程二执行的时候，key7.next已经是null了，但这里线程一去执行的时候key7.next却是key3）。所以当第二轮循环开始，执行next=e.next后，next = key3。

![image][image 7] 之后通过头插法，将key7插入key3之前。在执行完next=e.next 之后，e=key3，next=key3；

![image][image 8]

然后开始第三轮循环。e和next都是key3。所以根据头插法。key3又要插入key7之前，这就导致了key3.next为key7，key7.next为key3

![image][image 9] 所以当我们去get值得时候，当定位到3的时候，就会产生死循环。导致永远拿不到数据。

JDK1.8存不存在死循环问题

> 应该不存在，JDK8中将链表扩容到达一定阈值后，转为红黑树， 没有相关的问题

### 总结 ###

HashMap之所以在并发下的扩容造成死循环，是因为，多个线程并发进行时，因为一个线程先期完成了扩容，将原Map的链表重新散列到自己的表中，并且链表变成了倒序，后一个线程再扩容时，又进行自己的散列，再次将倒序链表变为正序链表。于是形成了一个环形链表，当get表中不存在的元素时，造成死循环。在1.8当中，链表扩容转为红黑树，没有相关的问题。

参考链接

[https://blog.csdn.net/b379685397/article/details/93459564][https_blog.csdn.net_b379685397_article_details_93459564]

[HashMap]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2F400E3E07F9854EEBAD8BE781733BFA6F%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3Dc9055ea8ca6f46e1277a21516dc7cb5d#hashmap%E5%B9%B6%E5%8F%91%E5%9C%BA%E6%99%AF%E5%88%86%E6%9E%90
[Link 1]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2F400E3E07F9854EEBAD8BE781733BFA6F%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3Dc9055ea8ca6f46e1277a21516dc7cb5d#%E8%83%8C%E6%99%AF
[HashMap 1]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2F400E3E07F9854EEBAD8BE781733BFA6F%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3Dc9055ea8ca6f46e1277a21516dc7cb5d#hashmap%E5%B9%B6%E5%8F%91%E4%B8%AD%E5%AD%98%E5%9C%A8%E7%9A%84%E9%97%AE%E9%A2%98
[Link 2]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2F400E3E07F9854EEBAD8BE781733BFA6F%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3Dc9055ea8ca6f46e1277a21516dc7cb5d#%E5%B9%B6%E5%8F%91%E5%9C%BA%E6%99%AF%E4%B8%8B%E4%BC%9A%E5%AF%BC%E8%87%B4%E6%AD%BB%E5%BE%AA%E7%8E%AF%E5%88%86%E6%9E%90
[JDK1.8]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2F400E3E07F9854EEBAD8BE781733BFA6F%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3Dc9055ea8ca6f46e1277a21516dc7cb5d#jdk18%E5%AD%98%E4%B8%8D%E5%AD%98%E5%9C%A8%E6%AD%BB%E5%BE%AA%E7%8E%AF%E9%97%AE%E9%A2%98
[Link 3]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2F400E3E07F9854EEBAD8BE781733BFA6F%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3Dc9055ea8ca6f46e1277a21516dc7cb5d#%E6%80%BB%E7%BB%93
[Link 4]: https://note.youdao.com/md/preview.html?file=%2Fyws%2Fapi%2Fpersonal%2Ffile%2F400E3E07F9854EEBAD8BE781733BFA6F%3Fmethod%3Ddownload%26read%3Dtrue%26shareKey%3Dc9055ea8ca6f46e1277a21516dc7cb5d#%E5%8F%82%E8%80%83%E9%93%BE%E6%8E%A5
[image]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9jOTA1NWVhOGNhNmY0NmUxMjc3YTIxNTE2ZGM3Y2I1ZC9DNjVDMzM5REZCRjM0M0ZFQUYzMTE4RTJFMUFCRTkyMw?x-oss-process=image/format,png
[image 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9jOTA1NWVhOGNhNmY0NmUxMjc3YTIxNTE2ZGM3Y2I1ZC9CNTlBRTM3NDdEN0Y0MUYxODUxODcyNEFGMTI4NjA1Rg?x-oss-process=image/format,png
[image 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9jOTA1NWVhOGNhNmY0NmUxMjc3YTIxNTE2ZGM3Y2I1ZC82RjExNzYxQTEwQTg0RDA0Qjg3REVGOTQxMTk3RUIwNQ?x-oss-process=image/format,png
[image 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9jOTA1NWVhOGNhNmY0NmUxMjc3YTIxNTE2ZGM3Y2I1ZC8yMEJEMDNENjk5MjQ0MUNEOTAzRjhGODE4M0NDQzYzQw?x-oss-process=image/format,png
[image 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9jOTA1NWVhOGNhNmY0NmUxMjc3YTIxNTE2ZGM3Y2I1ZC9EMDM1ODAzNDE5QzA0RUFEOUE1NzRCREQ0RENERTc5Mw?x-oss-process=image/format,png
[image 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9jOTA1NWVhOGNhNmY0NmUxMjc3YTIxNTE2ZGM3Y2I1ZC9GNEQzNDNFNDFDMEQ0QjU1OTRGQTEwNjg4NjQ1RDZBQw?x-oss-process=image/format,png
[image 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9jOTA1NWVhOGNhNmY0NmUxMjc3YTIxNTE2ZGM3Y2I1ZC9BNTY0MjRGQjg1REM0MUY5OEJEOEU5QzI0RTFERTFBQg?x-oss-process=image/format,png
[image 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9jOTA1NWVhOGNhNmY0NmUxMjc3YTIxNTE2ZGM3Y2I1ZC9DMEE2QjM2RkI0QzA0NDEzQjFFNzk3RDVENzJGNEU0NQ?x-oss-process=image/format,png
[image 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9jOTA1NWVhOGNhNmY0NmUxMjc3YTIxNTE2ZGM3Y2I1ZC8yNkIyNjcyQjc4NEQ0OUE5OTk3MzRFNjJGQTRBQ0I3MA?x-oss-process=image/format,png
[image 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS9jOTA1NWVhOGNhNmY0NmUxMjc3YTIxNTE2ZGM3Y2I1ZC9FRDJERDYxNEYwOEQ0REI0OUREMjM1Qzc4MkU0QkJDMQ?x-oss-process=image/format,png
[https_blog.csdn.net_b379685397_article_details_93459564]: https://blog.csdn.net/b379685397/article/details/93459564