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?

In Java 8, this can safely be done with `myMap.merge(X, 1, Integer::sum)`. — shmosel, Jan 13 '17 at 02:27

score 13 · Accepted Answer · edited May 23 '17 at 11:45

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.

I have spent crazy time asking my self why on earth a collection wrapped in an AtomicReference gets always unacurate when processed concurently. Then i saw your reply, burdden unloaded ! — Java Main, Oct 19 '19 at 11:46

Thilo · Answer 2 · 2014-01-17T12:23:09.403

4

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();

edited Jan 17 '14 at 12:23

answered Aug 27 '12 at 11:48

Thilo

257,207
101
511
656

if you use a ConcurrentMap there is no point in also using atomic integers, ConcurrentHashMap.replace(K, V, V) is made for this. – jolivier Aug 27 '12 at 11:52
If updates a rare, a simple synchronized like @dflemstr suggests will also work. Not sure how much throughput you need to justify AtomicInteger. – Thilo Aug 27 '12 at 11:53
1

@jolivier `replace` is subject to retrying, whereas `getAndIncrement` is not. – Marko Topolnik Aug 27 '12 at 11:55
1

I usually check if the value exists before the `putIfAbsent()` to avoid creating a new `AtomicInteger` every time. – Keppil Aug 27 '12 at 11:55
@MarkoTopolnik the same retrying that is wrapped in `getAndIncrement`, I agree its easier to write with an AtomicInteger but for me its overkill. – jolivier Aug 27 '12 at 11:59
2

@jolivier I'd definitely avoid implementing my own retry logic every time. For me this fully justifies the use of `AtomicInteger`. It does the retrying natively, in a way that cannot even be reproduced through Java. – Marko Topolnik Aug 27 '12 at 12:02
@jolivier You understand a replace will effect other entries in the CHM? Each replace will acquire a lock for that particular bucket. If you have even a few collisions this will degrade performance for other AtomicIntegers in the CHM. And if anything, `replace` is unbelievable overkill. Using a thread safe incrementing integer is much less overkill then implementing your own. – John Vint Aug 27 '12 at 14:21
@JohnVint I see, my remarks where more on an general interface level: there is no point in putting a thread safe structure in another thread safe structure in this case, only the container need to be thread safe. I was not considering implementations and in this particular case (incrementing an integer) its clear that the AtomicInteger is far easier to use than my `for(;;) {get;replace;}`. I was also assuming there were concurrent map implementation that were more efficient by CASing but I'm unsure now i'll go back to CHMV8 and see... – jolivier Aug 27 '12 at 15:16
1

According to documentation http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentHashMap.html#putIfAbsent%28K,%20V%29 `putIfAbsent` may return `null`. Won't your code throw NPE in certain scenario? – Tvaroh Jan 15 '14 at 23:46
@Tvaroh: True. It seems you need a null check here. Updating the answer. – Thilo Jan 17 '14 at 12:20

score 4 · Answer 3 · edited Dec 05 '15 at 01:59

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

score 1 · Answer 4 · answered Aug 27 '12 at 11:48

1

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

answered Aug 27 '12 at 11:48

dflemstr

25,947
5
70
105

although this answer is theoretically correct, we should not do because of performance implications. – best wishes Mar 08 '21 at 07:26
@bestwishes what performance implications do you mean here? – v1shnu Mar 05 '22 at 17:46

jolivier · Answer 5 · 2012-08-27T12:14:09.553

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.

java map concurrent update

5 Answers5