ConcurrentHashMap stuck in infinite loop - Why?

Question

While doing some in-depth analysis of ConcurrentHashMap, Found a blog post on the internet which says even ConcurrentHashMap may get stuck in an infinite loop.

It gives this example. When I ran this code - it got stuck:

public class Test {     public static void main(String[] args) throws Exception {         Map<Long, Long> map = new ConcurrentHashMap<>();         map.put(0L, 0L);         map.put((1L << 32) + 1, 0L);         for (long key : map.keySet()) {             map.put(key, map.remove(key));         }     } } 

Please explain why this deadlock happens.

Answer 1

As others have already said: It's not a deadlock, but an infinite loop. Regardless of that, the core (and title) of the question is: Why does this happen?

The other answers don't go into much detail here, but I was curious to better understand this as well. For example, when you change the line

map.put((1L << 32) + 1, 0L); 

to

map.put(1L, 0L); 

then it does not get stuck. And again, the question is why.

---

The answer is: It's complicated.

^{The ConcurrentHashMap is one of the most complex classes from the concurrent/collections framework, with a whopping 6300 lines of code, with 230 lines of comments only explaining the basic concept of the implementation, and why the magic and unreadable code actually works. The following is rather simplified, but should at least explain the basic issue.}

First of all: The set that is returned by Map::keySet is a view on the internal state. And the JavaDoc says:

Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined. The set supports element removal, [...]

^{(Emphasis by me)}

However, the JavaDoc of ConcurrentHashMap::keySet says:

Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, [...]

^{(Note that it does not mention the undefined behavior!)}

Usually, modifying the map while iterating over the keySet would throw a ConcurrentModificationException. But the ConcurrentHashMap is able to cope with this. It remains consistent and can still be iterated over, even though the results may still be unexpected - as in your case.

---

Coming to the reason for the behavior that you observed:

A hash table (or hash map) basically works by computing a hash value from the key, and using this key as an indicator for the "bucket" that the entry should be added to. When multiple keys are mapped to the same bucket, then the entries in the bucket are usually managed as a linked list. The same is the case for the ConcurrentHashMap.

The following program uses some nasty reflection hacks to print the internal state of the table - particularly, the "buckets" of the table, consisting of nodes - during the iteration and modification:

import java.lang.reflect.Array; import java.lang.reflect.Field; import java.util.Map; import java.util.concurrent.ConcurrentHashMap;  public class MapLoop {     public static void main(String[] args) throws Exception     {         runTestInfinite();         runTestFinite();     }      private static void runTestInfinite() throws Exception     {         System.out.println("Running test with inifinite loop");          Map<Long, Long> map = new ConcurrentHashMap<>();         map.put(0L, 0L);         map.put((1L << 32) + 1, 0L);          int counter = 0;         for (long key : map.keySet())         {             map.put(key, map.remove(key));              System.out.println("Infinite, counter is "+counter);             printTable(map);              counter++;             if (counter == 10)             {                 System.out.println("Bailing out...");                 break;             }         }          System.out.println("Running test with inifinite loop DONE");     }      private static void runTestFinite() throws Exception     {         System.out.println("Running test with finite loop");          Map<Long, Long> map = new ConcurrentHashMap<>();         map.put(0L, 0L);         map.put(1L, 0L);          int counter = 0;         for (long key : map.keySet())         {             map.put(key, map.remove(key));              System.out.println("Finite, counter is "+counter);             printTable(map);              counter++;         }          System.out.println("Running test with finite loop DONE");     }       private static void printTable(Map<Long, Long> map) throws Exception     {         // Hack, to illustrate the issue here:         System.out.println("Table now: ");         Field fTable = ConcurrentHashMap.class.getDeclaredField("table");         fTable.setAccessible(true);         Object t = fTable.get(map);         int n = Array.getLength(t);         for (int i = 0; i < n; i++)         {             Object node = Array.get(t, i);             printNode(i, node);         }     }      private static void printNode(int index, Object node) throws Exception     {         if (node == null)         {             System.out.println("at " + index + ": null");             return;         }         // Hack, to illustrate the issue here:         Class<?> c =             Class.forName("java.util.concurrent.ConcurrentHashMap$Node");         Field fHash = c.getDeclaredField("hash");         fHash.setAccessible(true);         Field fKey = c.getDeclaredField("key");         fKey.setAccessible(true);         Field fVal = c.getDeclaredField("val");         fVal.setAccessible(true);         Field fNext = c.getDeclaredField("next");         fNext.setAccessible(true);          System.out.println("  at " + index + ":");         System.out.println("    hash " + fHash.getInt(node));         System.out.println("    key  " + fKey.get(node));         System.out.println("    val  " + fVal.get(node));         System.out.println("    next " + fNext.get(node));     } } 

---

The output for the runTestInfinite case is as follows (redundant parts omitted) :

Running test with infinite loop Infinite, counter is 0 Table now:    at 0:     hash 0     key  4294967297     val  0     next 0=0 at 1: null at 2: null ... at 14: null at 15: null Infinite, counter is 1 Table now:    at 0:     hash 0     key  0     val  0     next 4294967297=0 at 1: null at 2: null ... at 14: null at 15: null Infinite, counter is 2 Table now:    at 0:     hash 0     key  4294967297     val  0     next 0=0 at 1: null at 2: null ... at 14: null at 15: null Infinite, counter is 3 ... Infinite, counter is 9 ... Bailing out... Running test with infinite loop DONE 

One can see that the entries for the key 0 and the key 4294967297 (which is your (1L << 32) + 1) always end in bucket 0, and they are maintained as a linked list. So the iteration over the keySet starts with this table:

Bucket   :   Contents    0     :   0 --> 4294967297    1     :   null   ...    :   ...   15     :   null 

In the first iteration, it removes the key 0, basically turning the table into this one:

Bucket   :   Contents    0     :   4294967297    1     :   null   ...    :   ...   15     :   null 

But the key 0 is immediately added afterwards, and it ends in the same bucket as the 4294967297 - so it is appended at the end of the list:

Bucket   :   Contents    0     :   4294967297 -> 0    1     :   null   ...    :   ...   15     :   null 

(This is indicated by the next 0=0 part of the output).

In the next iteration, the 4294967297 is removed and re-inserted, bringing the table into the same state that it had initially.

And that's where your infinite loop comes from.

---

In contrast to that, the output for the runTestFinite case is this:

Running test with finite loop Finite, counter is 0 Table now:    at 0:     hash 0     key  0     val  0     next null   at 1:     hash 1     key  1     val  0     next null at 2: null ... at 14: null at 15: null Finite, counter is 1 Table now:    at 0:     hash 0     key  0     val  0     next null   at 1:     hash 1     key  1     val  0     next null at 2: null ... at 14: null at 15: null Running test with finite loop DONE 

One can see that the keys 0 and 1 end up in different buckets. So there is no linked list to which the removed (and added) elements could be appended, and the loop terminates after iterating through the relevant elements (i.e. the first two buckets) once.

Answer 2

I don't think this has anything to do with thread safety that ConcurrentHashMap offers. It doesn't even look like a deadlock at all, but an infinite loop.

And this is due to the map being modified while iterating over the keyset, which is backed by the same map!

Here is an excerpt from the documentation of map.keySet():

The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined.