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

问题描述

正如许多人所注意到并遇到的那样，HashMap.put 在并发使用时会进入无限执行循环(请参阅 GRIZZLY-1207, JGRP-525，可能是 HHH-6414，和这个 SO 回答).

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 时遇到了这个循环，并想了解确切的原因.比如，这是同时多个put造成的吗?

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.

推荐答案

与很多人的想法相反，multi-threading 和 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)...

虽然我可以尝试自己给你一个解释，但我想感谢 Paul Tyma 的帖子 (反正我不能比他做得更好)在那里我第一次决定弄清楚为什么几个月前我没有被录用时就知道了这是如何工作的......

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屋！