21

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.

1
  • Do you have the thread dump? Commented Jul 5, 2019 at 5:31

5 Answers 5

18

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.

0
14

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.

14

There is no deadlock. You are just running into an infinite loop. When I run this code (and print key in the loop), the console shows this repeatedly:

0
4294967297
0
4294967297
0
...

If you made map a HashMap instance, you would see that the code raises a ConcurrentModificationException. So you are just modifying the map while iterating through its keys, and ConcurrentHashMap does not throw a concurrent modification exception, thus making your loop endless.

4

The cause of the infinite cycle is a combination of

  1. How are map entries stored internally
  2. How does the key iterator work

1

Map entries are stored as an array of linked lists:
transient volatile Node<K,V>[] table
Every map entry will end up in one of the linked lists in this array, based on its hash(hash % table.length):

//simplified pseudocode
public V put(K key, V value) {
    int hash = computeHash(key) % table.length
    Node<K,V> linkedList = table[hash]
    linkedList.add(new Node(key, value))
}

2 keys with the same hash (like 0 and 4294967297) will end up in the same list

2

An iterator's job is pretty simple: iterate entries one by one.
Given the internal storage is basically a collection of collections it iterates over all entries from table[0] list, than table[1] and so on. But there is an implementation detail that makes our example run forever only for maps with hash collisions:

public final K next() {
    Node<K,V> p;
     if ((p = next) == null)
         throw new NoSuchElementException();
     K k = p.key;
     lastReturned = p;
     advance();
     return k;
}

The next() method implementation returns a value that was pre-computed before and computes the value to be returned on a future invocation. When the iterator is instantiated it gathers the 1st element, when next() is called 1st time it gathers the 2nd element and returns the 1st.
Here's the relevant code from the advance() method:

Node<K,V>[] tab;        // current table; updated if resized
Node<K,V> next;         // the next entry to use
. . .

final Node<K,V> advance() {
    Node<K,V> e;
    if ((e = next) != null)
        e = e.next;
    for (;;) {
        Node<K,V>[] t; int i, n;
        if (e != null)
            return next = e; // our example will always return here
        . . .
    }
}

Here's how the internal state of our map evolves :

Map<Long, Long> map = new ConcurrentHashMap<>();

[ null, null, ... , null ] all buckets (linked lists) are empty

map.put(0L, 0L);

[ 0:0, null, ... , null ] first bucket got an entry

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

[ 0:0 -> 4294967297:0, null, ... , null ] first bucket now has two entries

1st iteration, the iterator returns 0 and holds the 4294967297:0 entry as next

map.remove(0)

[ 4294967297:0, null, ... , null ]

map.put(0, 0) // the entry our iterator holds has its next pointer modified

[ 4294967297:0 -> 0:0, null, ... , null ]

2nd iteration

map.remove(4294967297)

[ 0:0, null, ... , null ]

map.put(4294967297, 0)

[ 0:0 -> 4294967297:0, null, ... , null ]

So after 2 iterations we are back were we started, because our actions boil down to removing an item from the head of a linked list and adding it to its tail, hence we can't finish consuming it.
It does not run into an infinite loop for maps without hash collisions because the linked list we add to was already left behind by the iterator.
Here's an example that proves it:

Map<Long, Long> map = new ConcurrentHashMap<>();
map.put(0L, 0L);
map.put(1L, 0L);
int iteration = 0;
for (long key : map.keySet()) {
    map.put((1L << 32) + 1, 0L);
    map.put((1L << 33) + 2, 0L);
    map.put((1L << 34) + 4, 0L);
    System.out.printf("iteration:%d key:%d  map size:%d %n", ++iteration, key, map.size());
    map.put(key, map.remove(key));
}

The output is:
iteration:1 key:0 map size:5
iteration:2 key:1 map size:5

All the items added inside the loop end up in the same bucket - the first one - the one our iterator already consumed.

1
  • I considered to add some details about the internal workings of the iterator (which is another piece of the puzzle that is relevant in view of the infinite loop), so good to have this here, +1
    – Marco13
    Commented Jul 10, 2019 at 14:03
2

There is no deadlock.A deadlock is when two (or more) threads are blocking each other.obvious,You have only one main thread here.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.