java map concurrent update

Question

I'm trying to create a Map with int values and increase them by multiple threads. two or more threads might increase the same key.

ConcurrentHashMap documentation was very unclear to me since it sais that:

Retrieval operations (including get) generally do not block, so may overlap with update operations (including put and remove)

I wonder if the following code using ConcurrentHashMap will works correctly:

myMap.put(X, myMap.get(X) + 1);

if not, how can I manage such thing?

Answer 1

Best practice. You can use HashMap and AtomicInteger. Test code:

public class HashMapAtomicIntegerTest {
    public static final int KEY = 10;

    public static void main(String[] args) {
        HashMap<Integer, AtomicInteger> concurrentHashMap = new HashMap<Integer, AtomicInteger>();
        concurrentHashMap.put(HashMapAtomicIntegerTest.KEY, new AtomicInteger());
        List<HashMapAtomicCountThread> threadList = new ArrayList<HashMapAtomicCountThread>();
        for (int i = 0; i < 500; i++) {
            HashMapAtomicCountThread testThread = new HashMapAtomicCountThread(
                    concurrentHashMap);
            testThread.start();
            threadList.add(testThread);
        }
        int index = 0;
        while (true) {
            for (int i = index; i < 500; i++) {
                HashMapAtomicCountThread testThread = threadList.get(i);
                if (testThread.isAlive()) {
                    break;
                } else {
                    index++;
                }
            }
            if (index == 500) {
                break;
            }
        }
        System.out.println("The result value should be " + 5000000
                + ",actually is"
                + concurrentHashMap.get(HashMapAtomicIntegerTest.KEY));
    }
}

class HashMapAtomicCountThread extends Thread {
    HashMap<Integer, AtomicInteger> concurrentHashMap = null;

    public HashMapAtomicCountThread(
            HashMap<Integer, AtomicInteger> concurrentHashMap) {
        this.concurrentHashMap = concurrentHashMap;
    }

    @Override
    public void run() {
        for (int i = 0; i < 10000; i++) {
            concurrentHashMap.get(HashMapAtomicIntegerTest.KEY)
                    .getAndIncrement();
        }
    }
}

Results:

The result value should be 5000000,actually is5000000

Or HashMap and synchronized, but much slower than the former

public class HashMapSynchronizeTest {

    public static final int KEY = 10;

    public static void main(String[] args) {

        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        hashMap.put(KEY, 0);
        List<HashMapSynchronizeThread> threadList = new ArrayList<HashMapSynchronizeThread>();
        for (int i = 0; i < 500; i++) {
            HashMapSynchronizeThread testThread = new HashMapSynchronizeThread(
                    hashMap);
            testThread.start();
            threadList.add(testThread);
        }
        int index = 0;
        while (true) {
            for (int i = index; i < 500; i++) {
                HashMapSynchronizeThread testThread = threadList.get(i);
                if (testThread.isAlive()) {
                    break;
                } else {
                    index++;
                }
            }
            if (index == 500) {
                break;
            }
        }
        System.out.println("The result value should be " + 5000000
                + ",actually is" + hashMap.get(KEY));
    }
}

class HashMapSynchronizeThread extends Thread {
    HashMap<Integer, Integer> hashMap = null;

    public HashMapSynchronizeThread(
            HashMap<Integer, Integer> hashMap) {
        this.hashMap = hashMap;
    }

    @Override
    public void run() {
        for (int i = 0; i < 10000; i++) {
            synchronized (hashMap) {
                hashMap.put(HashMapSynchronizeTest.KEY,
                        hashMap
                                .get(HashMapSynchronizeTest.KEY) + 1);
            }
        }
    }
}

Results:

The result value should be 5000000,actually is5000000

Use ConcurrentHashMap will get the wrong results.

public class ConcurrentHashMapTest {

    public static final int KEY = 10;

    public static void main(String[] args) {
        ConcurrentHashMap<Integer, Integer> concurrentHashMap = new ConcurrentHashMap<Integer, Integer>();
        concurrentHashMap.put(KEY, 0);
        List<CountThread> threadList = new ArrayList<CountThread>();
        for (int i = 0; i < 500; i++) {
            CountThread testThread = new CountThread(concurrentHashMap);
            testThread.start();
            threadList.add(testThread);
        }
        int index = 0;
        while (true) {
            for (int i = index; i < 500; i++) {
                CountThread testThread = threadList.get(i);
                if (testThread.isAlive()) {
                    break;
                } else {
                    index++;
                }
            }
            if (index == 500) {
                break;
            }
        }
        System.out.println("The result value should be " + 5000000
                + ",actually is" + concurrentHashMap.get(KEY));
    }
}

class CountThread extends Thread {
    ConcurrentHashMap<Integer, Integer> concurrentHashMap = null;

    public CountThread(ConcurrentHashMap<Integer, Integer> concurrentHashMap) {
        this.concurrentHashMap = concurrentHashMap;
    }

    @Override
    public void run() {
        for (int i = 0; i < 10000; i++) {
            concurrentHashMap.put(ConcurrentHashMapTest.KEY,
                    concurrentHashMap.get(ConcurrentHashMapTest.KEY) + 1);
        }
    }
}

Results:

The result value should be 5000000,actually is11759

Answer 2

One idea would be combining ConcurrentMap with AtomicInteger, which has a increment method.

 AtomicInteger current = map.putIfAbsent(key, new AtomicInteger(1));
 int newValue = current == null ? 1 :current.incrementAndGet();

or (more efficiently, thanks @Keppil) with an extra code guard to avoid unnecessary object creation:

 AtomicInteger current = map.get(key);
 if (current == null){
     current = map.putIfAbsent(key, new AtomicInteger(1));
 }
 int newValue = current == null ? 1 : current.incrementAndGet();

Answer 3

Concurrent map will not help thread safety of your code. You still can get race condition:

Thread-1: x = 1, get(x)
Thread-2: x = 1, get(x)
Thread-1: put(x + 1) => 2
Thread-2: put(x + 1) => 2

Two increments happened, but you still get only +1. You need a concurrent map only if you aim for modifying the map itself, not its content. Even the simplest HashMap is threadsafe for concurrent reads, given the map is not mutated anymore.

So instead of a threadsafe map for primitive type, you need a threadsafe wrapper for the type. Either something from java.util.concurrent.atomic or roll your own locked container if needing an arbitrary type.

Answer 4

Your current code changes the values of your map concurrently so this will not work.

If multiple threads can put values into your map, you have to use a concurrent map like ConcurrentHashMap with non thread safe values like Integer. ConcurrentMap.replace will then do what you want (or use AtomicInteger to ease your code).

If your threads will only change the values (and not add/change the keys) of your map, then you can use a standard map storing thread safe values like AtomicInteger. Then your thread will call:map.get(key).incrementAndGet() for instance.

Answer 5

You could just put the operation in a synchronized (myMap) {...} block.