Strange HashMap exception (HashMap$Node cannot be cast to HashMap$TreeNode)

Question

After another question asked on stackoverflow, (Java- Why this program not throwing concurrent Modification exception) I started to experiment with the HashMap. Here are a few lines of code which I wrote:

import java.util.HashMap;
import java.util.Random;

public class Concurrency {
    public static void putEntriesToMap(HashMap<String, String> hashMap) {
        for (int count = 0; count < 10000; count++) {
            hashMap.put(Integer.toString(count), Integer.toString(count));
            Random random = new Random();
            if (random.nextBoolean()) {
                hashMap.remove(count + "");
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        final HashMap<String, String> hashMap = new HashMap<String, String>();
        Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                putEntriesToMap(hashMap);
            }
        });

        Thread t2 = new Thread(new Runnable() {
            @Override
            public void run() {
                putEntriesToMap(hashMap);
            }
        });
        t1.start();
        t2.start();
        t1.join();
        t2.join();
    }
}

Once upon a time (approx 1 in 20 runs), when executing this code, I get

Exception in thread "Thread-0" Exception in thread "Thread-1" java.lang.ClassCastException: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
    at java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1819)
    at java.util.HashMap$TreeNode.treeify(HashMap.java:1936)
    at java.util.HashMap.treeifyBin(HashMap.java:771)
    at java.util.HashMap.putVal(HashMap.java:643)
    at java.util.HashMap.put(HashMap.java:611)
    at Concurrency.putEntriesToMap(Concurrency.java:9)
    at Concurrency$1.run(Concurrency.java:27)
    at java.lang.Thread.run(Thread.java:745)

This, however, seems strange to me, because it looks like it is an internal HashMap error. I know that the concurrency is not used correctly, but it is done on purpose.

I tried to google the exception, but I found almost no info.

Can you even reproduce the same exception?

I am using oracle jdk 1.8.0_40

EDIT:

Firstly, thanks for answers, it is now clear for me. I just want to point out that I knew how to avoid the program from breaking by using thread safe precautions, but I didn't know why specifically this exception is thrown in given situation. Thomas has explained it very well in the comments below. It is also well explained in the accepted answer. Thanks again :).

Solution 1

I also found the same exception with your code. I added a synchronized modifier on the putEntriesToMap() method, and the error seemed to stop occurring. The problem is that both threads are modifying the same map at once. There is an object that must be converted to put the entry in. However, the second thread is dealing with a mutated object, which throws a ClassCastException. So, make sure that no two threads are accessing the same map at once. The synchronized modifier stops all other threads from doing anything with the class/instance if another thread is doing the same. Synchronized static methods synchronize the class itself, whereas synchronized non-static methods only synchronize the instance of the class.

Solution 2

I was getting the same ClassCastException with concurrent calls to HashMap.computeIfAbsent. I fixed by changing the implementation to use ConcurrentHashMap.

Comments

[Admin]

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.