How to safely modify values in Java HashMaps concurrently?

Question

I have a block of Java code that looks something like this that I'm trying to parallelize:

value = map.get(key);
if (value == null) {
    value = new Value();
    map.put(key,value);
}
value.update();

I want to block any other thread from accessing the map with that particular key until after value.update() is called even if key is not in the key set. Accessing with other keys should be allowed. How could I achieve this?

Answer 1

Short answer is there's no safe way to do this without synchronizing the entire block. You could use java.util.concurrent.ConcurrentHashMap though, see this article for more details. The basic idea is to use ConcurrentHashMap.putIfAbsent instead of the normal put.

Answer 2

You cannot parallelize updates to HashMap because update can trigger resize of the underlying array including recalculation of all keys.

Use other collection, for example java.util.concurrent.ConcurrentHashMap which is a "A hash table supporting full concurrency of retrievals and adjustable expected concurrency for updates." according to javadoc.

Answer 3

I wouldn't use HashMap if you need to be concerned about threading issues. Make use of the Java 5 concurrent package and look into ConcurrentHashMap.

Answer 4

You just described the use case for the Guava computing map. You create it with:

Map<Key, Value> map = new MapMaker().makeComputingMap(new Function<Key, Value>() {
  public Value apply(Key key) {
    return new Value().update();
  }
));

and use it:

Value v = map.get(key);

This guarantees only one thread will call update() and other threads will block and wait until the method completes.

You probably don't actually want your value having a mutable update method on it, but that's another discussion.

Answer 5

private void synchronized functionname() {
    value = map.get(key);
    if (value == null) {
        value = new Value();
        map.put(key,value);
    }
    value.update();
}

You can learn more about synchronized methods here: Synchronized Methods

You might also want to investigate the ConcurrentHashMap class, which might suit your purposes. You can see it on the JavaDoc.

Answer 6

Look into Concurrent HashMap. It has excellent performance even for single-threaded applications. It allows concurrent modification of Map from various threads without any need of blocking them.

Answer 7

One possibility is to manage multiple locks. So you can keep an array of locks that is retrieved based on the key's hash code. This should give you better through-put then synchronizing the whole method. You can size the array based on the number of thread that you believe will be accessing the code.

private static final int NUM_LOCKS = 16;
Object [] lockArray = new Object[NUM_LOCKS];
...
// Load array with Objects or Reentrant Locks

...

Object keyLock = lockArray[key.hashcode % NUM_LOCKS];
synchronize(keyLock){
  value = map.get(key);
  if (value == null) {
    value = new Value();
    map.put(key,value);
  }
  value.update();
}