解释定时导致HashMap.put（）执行无限循环 [英] Explain the timing causing HashMap.put() to execute an infinite loop

问题描述

由于许多人已经注意到并遇到 HashMap.put 可以在并发使用时进入无限执行循环（参见 GRIZZLY-1207 ， JGRP-525 ，可能是 HHH-6414 ，而此SO answer ）。

As a number of people have noted and encountered HashMap.put can go into an infinite execution loop when used concurrently (see GRIZZLY-1207, JGRP-525, possibly HHH-6414, and this SO answer).

HashMap 安全。显然，正确的修复是使用 Map ， ConncurrentHashMap 的线程安全实现。我更加好奇的并发计时导致无限循环。我最近遇到这个循环与Java 7 JRE，并想了解确切的原因。例如，这是由多个投放同时造成的吗？

HashMap is clearly documented as not thread safe. Obviously, the correct fix is to use a thread-safe implementation of Map, ConncurrentHashMap in particular. I'm more curious about the concurrent timing that causes the infinite loop. I encountered this loop recently with a Java 7 JRE and would like to understand the exact causes. For example, is this caused by multiple puts at the same time?

查看 HashMap.put HashMap.Entry 包含到下一个节点的链接（在桶中？）。我假设这些链接正在变坏，包含循环引用，这是造成无限循环。

A look inside HashMap.put shows that HashMap.Entry contains a link to the next node (in the bucket?). I assume these links are getting corrupting to contain circular references, which is causing the infinite loop. However, I still don't understand exactly how that corruption is occurring.

推荐答案

与许多人的想法相反，主要问题与多线程和 HashMaps 不只是一个重复的条目或消失一个...正如你所说，当两个或多个 Threads 同时决定调整 HashMap 的大小时，可能会发生无限循环。

To the contrary of what many people think, the main issue with multi-threading and HashMaps is not just a duplicate entry or a vanishing one... As you said, an infinite loop might occur when two or multiple Threads concurrently decide to resize the HashMap.

如果HashMap的大小超过一个给定的阈值，几个线程可能会尝试同时调整它的大小，如果我们足够幸运（你已经在生产中部署代码），将会永远...

If the size of the HashMap passes a given threshold, several threads might end up trying to resize it at the same time, and if we are lucky enough (you deployed the code in production already) they will keep going forever...

这个问题是由 void resize（int newCapacity）; 和 void transfer（Entry [] newTable）; ，您可以看一下 openjdk源代码。混乱的运气，良好的时序，反转的条目（在此数据结构中不需要排序），并且最终错误地引用对方，而线程保持 while（e！= null ） ...

The issue is caused by the way the void resize(int newCapacity); and void transfer(Entry[] newTable); are implemented, you can take a look at the openjdk source code yourself. A mix of bad luck, good timing, entries that get reversed (ordering is not required in this data structure) and that end up to mistakenly referring to each other while a thread keep going while(e != null)...

虽然我可以尝试给你一个解释，我想给信用保罗泰玛的帖子（我不能比他做得更好），在那里我学会了这是如何工作的，我第一次决定找出为什么我不是几个月前被聘用了一个工作...

While I could try to give you an explanation myself, I want to give credit to Paul Tyma's post (I cannot do better than him anyway) where I learned how this worked the first time I decided to figure out why I wasn't hired for a job several months ago...

http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html

正如保罗所说，最好的词描述这种种族的条件是：美丽

As Paul says, the best word to describe this race is condition is: beautiful

这篇关于解释定时导致HashMap.put（）执行无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！