java - Explain the timing causing HashMap.put() to execute an infinite loop

Question

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 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?

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.

Answer 1

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.

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...

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