ArrayIndexOutOfBoundsException while getting values from hashmap in Java 17

I have a static HashMap<UUID, MyObject> ALL = new HashMap<>(); which is used in multi-threading.

To reproduce the error, I made this code:

HashMap<Integer, String> list = new HashMap<>();

list.put(1, "str 1");
list.put(2, "str 2");

new Thread(() -> {
    while(true) {
        ArrayList<String> val;
        synchronized(list) {
            val = new ArrayList<>(list.values());
        }
        System.out.println(val.toString());
        try {
            Thread.sleep(500);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}).start();

new Thread(() -> {
    while(true) {
        list.put(new Random().nextInt(), "some str");
        try {
            Thread.sleep(500);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}).start();

But, after some seconds (around 10), I get this error with Java 16 and Java 17:

java.lang.ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2
    at java.util.HashMap.valuesToArray(HashMap.java:973) ~[?:?]
    at java.util.HashMap$Values.toArray(HashMap.java:1050) ~[?:?]
    at java.util.ArrayList.<init>(ArrayList.java:181) ~[?:?]

With Java 8, I get this:

Exception in thread "Thread-0" java.util.ConcurrentModificationException
    at java.util.HashMap$HashIterator.nextNode(HashMap.java:1473)
    at java.util.HashMap$ValueIterator.next(HashMap.java:1502)
    at java.util.AbstractCollection.toArray(AbstractCollection.java:141)
    at java.util.ArrayList.<init>(ArrayList.java:178)

To test, I remove synchronized key-word, then try again in Java 17 and I get this:

java.util.ConcurrentModificationException: null
    at java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1631) ~[?:?]
    at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:509) ~[?:?]
    at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:499) ~[?:?]
    at java.util.stream.ForEachOps$ForEachOp.evaluateSequential(ForEachOps.java:150) ~[?:?]
    at java.util.stream.ForEachOps$ForEachOp$OfRef.evaluateSequential(ForEachOps.java:173) ~[?:?]
    at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234) ~[?:?]
    at java.util.stream.ReferencePipeline.forEach(ReferencePipeline.java:596) ~[?:?]

Those error seems very strange, especially the first one. I suspect that they comes from the JRE itself. I’m using Java 17.0.1 build 17.0.1+12-LTS-39.

How can I get all values from another thread?

Answer

First of all, you should use better variable names. Even a completely non-informative name is better than using list as the variable name for a HashMap. A HashMap is NOT a list, and it doesn’t even behave like a (proper) list when you iterate it. That variable name is just misleading.

So the problem with your code is that it is not synchronizing correctly. The version as written is using synchronized when updating the HashMap, but not when you are accessing it. To get the proper happens before relationships need to make this code work, both the reader and updater threads would need to use synchronized.

Without that a happens before chain, the Java Memory Model does not guarantee that primitive write operations performed by one thread are visible to another. In this case, it means that HashMap operations performed by the reader are liable to encounter stale values. This can cause all sorts of things to go wrong¹, including incorrect results, ArrayIndexOutOfBoundsExceptions, NullPointerExceptions and even infinite loops.

In addition, if you simultaneously iterate and update a HashMap you are liable to get a ConcurrentModificationException … even if the operations are done in a way that ensures that a happens before chain exists.

In short … this code is wrong.

^{1 – The actual failure mode and frequency are liable to depend on factors such as your JVM version, your hardware (including the number of cores), and whatever else is going on in your application. And various things you can try to investigate the behavior are liable to make the failure change … or go away.}

---

So, how can you fix it?

Well, there are two approaches:

1. Make sure that both the reader and updater threads access the HashMap from inside a synchronized block. In the reader case, be sure to put the entire operation that is iterating the map’s value view into the synchronized block. (Otherwise you will get CME’s)

   The down-side is that the reader will block the updater and vice-versa. That can lead to “lag” in either thread. (It is probably the updater that you are worried about. For that thread, the “lag” will be proportional to the number of entries in the map … and what you are doing with the map entries.)

   This is more or less equivalent to using a Collections.synchronizedMap wrapper. You will get the same amount of “lag”. Note the important caveat in the javadoc about iterating using a synchronized map wrapper. (Look for “It is imperative that …”)

2. Change HashMap to ConcurrentHashMap. That will remove the need to perform operations inside synchronized blocks. The ConcurrentHashMap class is thread-safe … in the sense that you won’t need to worry about memory model induced exceptions and heisenbugs.

   The down-side is that iterating a ConcurrentHashMap does not give you a clean snapshot of the map state. If an entry exists at the start of the iteration and hasn’t been removed by the end of the iteration, you are guaranteed to see it. But if entries are added or remove, you may or may not see them.

---

Declaring the Map variable list as volatile won’t fix this. Doing that only gives a happens before for reads and writes of the reference variable. But it doesn’t give any happens before relations between the operations on the HashMap. So if the reader and updater threads happen to run simultaneously, bad things will happen.

In practice, adding volatile will turn this into a case where the problems occur less frequently, and are much harder to reproduce or test for. IMO, it makes the problem worse.

(Besides, if list is a local variable, as it appears to be in your example, it can’t be declared as volatile anyway.)

---

Q: Is there a solution with O(1) operations that gives you clean map snapshot semantics without lag?

A: AFAIK, no such data structure has been invented / discovered. Certainly, there is no Map implementation in Java SE with those properties.