ConcurrentHashMap does not work as expected

Question

I am counting votes for electronic election and I have only one party in my initial version. There will be different threads per voter and the threads will update the votes count of a given party.

I decided to use ConcurrentHashMap, but the results are not what I expected...

Map<String, Integer> voting = new ConcurrentHashMap<>();

for (int i = 0; i < 16; i++) {
  new Thread(() -> {
    voting.put("GERB", voting.getOrDefault("GERB", 0) + 1);
  }).start();
}

for (int i = 0; i < 100; i++) {
  voting.put("GERB", voting.getOrDefault("GERB", 0) + 1);
}

Thread.sleep(5000); // Waits for the threads to finish

for (String s : voting.keySet()) {
  System.out.println(s + ": " + voting.get(s));
}

The result is different every time - it ranges from 114 to 116.

Isn't ConcurrentHashMap supposed to be synchronised?

Answer 1

Well, there's a compound action here. You get the map value given a key, increment it by one, and place it back in the map against the same key. You have to guarantee that all these statements execute atomically. But the given implementation does not impose that prerequisite. Hence you end up with a safety failure.

To fix this, you can use the atomic merge operation defined in ConcurrentHashMap. The entire method invocation is performed atomically. Here's how it looks.

Map<String, Integer> voting = new ConcurrentHashMap<>();

for (int i = 0; i < 16; i++)
    new Thread(() -> {
        voting.merge("GERB", 1, Integer::sum);
    }).start();

for (int i = 0; i < 100; i++)
    voting.merge("GERB", 1, Integer::sum);

Thread.sleep(5000); // Waits for the threads to finish

for (String s : voting.keySet())
    System.out.println(s + ": " + voting.get(s));

Running this program produces the following output:

GERB: 116

Answer 2

Assume there are two or more threads performs voting.put("GERB", voting.getOrDefault("GERB", 0) + 1);

what happens? Lets say value on key "GERB" now equals 10

1. Thread #1 gets value voting.getOrDefault("GERB", 0). It is 10
2. Thread #2 gets value voting.getOrDefault("GERB", 0). It is 10
3. Thread #1 adds 1, now it is 11
4. Thread #2 adds 1, now it is 11
5. Thread #1 writes values 11 back to voting
6. Thread #2 writes values 11 back to voting

Now, although 2 threads completes, the value increased only by 1 because of concurency.

So, yes, methods of ConcurrentHashMap are synchronized. That means, when one thread executes e.g. put, another thread waits. But they do not synchronize threads outside anyhow.

If you perform several calls you have to synchronize them on your own. E.g.:

final Map<String, Integer> voting = new ConcurrentHashMap<>();

for (int i = 0; i < 16; i++) {
  new Thread(() -> {
    synchronized (voting) { // synchronize the whole operation over the same object
       voting.put("GERB", voting.getOrDefault("GERB", 0) + 1);
    }
  }).start();
}

UPD As it noted in the comments, keep in mind that synchronization over voting object does not guarantee synchronization with ConcurentHahMap's methods itself. You have to perform that synchronization for every call to voting methods if those calls can be performed concurrently. In fact, you can use any other object to synchronize (it's not required to be voting): it only needs to be the same for all the threads.

But, as it noted by @Holger, this defeats the very purpose of the ConcurentHashMap. To utilize the atomic mechanics of ConcurentHashMap without locking the threads you can use method replace to retry the operation if the value was altered by another thread:

for (int i = 0; i < 16; i++) {
  new Thread(() -> {
    Integer oldValue, newValue;
    do {
       oldValue = voting.getOrDefault("GERB", 0);
       newValue = oldValue + 1; // do some actions over the value
    } while (!voting.replace("GERB", oldValue, newValue)); // repeat if the value was changed
  }).start();
}