Snippet for concurrentHashMap to retrieve object or create it if absent (as atomic operation)

Question

In Java, I want to do something like this:

   Object r = map.get(t);
   if (r == null) {
      r = create(); // creating r is an expensive operation.
      map.put(t, r);  
   }

Now that snippet of code can be executed in a multithreaded environment. map can be a ConcurrentHashMap.

But how do I make that logic atomic?

Please don't give me trivial solution like a 'synchronized' block. I 'd expect this problem can be solved neatly once and for all.

Answer 1

I think the solution is documented in concurrency in practice. The trick is to use a Future instead of R as object in the map.

Although I dislike this answer because it looks far far too complex.

here is the code:

public class Memorizer<A, V> implements Computable<A, V> {
    private final ConcurrentMap<A, Future<V>> cache = new ConcurrentHashMap<A, Future<V>>();
    private final Computable<A, V> c;
    public Memorizer(Computable<A, V> c) { this.c = c; }

    public V compute(final A arg) throws InterruptedException {
       while (true) {
          Future<V> f = cache.get(arg);
          if (f == null) {
          Callable<V> eval = new Callable<V>() {
              public V call() throws InterruptedException {
              return c.compute(arg);
          }
       };
       FutureTask<V> ft = new FutureTask<V>(eval);
       f = cache.putIfAbsent(arg, ft);
       if (f == null) { f = ft; ft.run(); }

       try {
          return f.get();
       } catch (CancellationException e) {
          cache.remove(arg, f);
       } catch (ExecutionException e) {
          throw launderThrowable(e.getCause());
       }
    }
}

Answer 2

It's been solved neatly by Guava.

Use CacheBuilder and call build with a CacheLoader. This will return a LoadingCache object. If you really need a Map implementation, you can call asMap().

There's also the older MapMaker with its makeComputingMap, but that's deprecated in favor of the CacheBuilder approach.

Of course you can also implement it manually, but doing that correctly is nontrivial. Several aspects to consider are:

• you want to avoid calling create twice with the same input
• you want to wait for a current thread to finish creating but don't want to do that with an idle loop
• you want to avoid synchronizing in the good case (i.e. element is already in the map).
• if two create calls happen at the same time you want each caller to only wait for the one relevant to him.

Answer 3

try

    value = concurentMap.get(key);
    if(value == null) {
        map.putIfAbsent(key, new Value());
        value = map.get(key);
    }
    return value;

Answer 4

Since Java 8, method ConcurrentMap.computeIfAbsent is what you are looking for: equivalent to the following steps for this map, but atomic:

 V oldValue = map.get(key);
 if (oldValue == null) {
     V newValue = mappingFunction.apply(key);
     if (newValue != null) {
         return map.putIfAbsent(key, newValue);
     } else {
         return null;
     }
 } else {
     return oldValue;
 }

The most common usage is to construct a new object serving as an initial mapped value or memoized result, which is what you are looking for, I think, as in:

 Value v = map.computeIfAbsent(key, k -> new Value(f(k)));

Answer 5

I know this maybe isn't what you're looking for, but I'll include it for sake of argument.

public Object ensureExistsInMap(Map map, Object t) {

    Object r = map.get(t);
    if (r != null) return r; // we know for sure it exists

    synchronized (creationLock) {
        // multiple threads might have come this far if r was null
        // outside the synchronized block
        r = map.get(t); 
        if (r != null) return r;

        r = create();
        map.put(t, r);

        return r;
    }
}

Answer 6

What you describe is basically the Multitone pattern with Lazy Initialization

Here is an example using double locking with modern Java locks

private static Map<Object, Object> instances = new ConcurrentHashMap<Object, Object>();
private static Lock createLock = new ReentrantLock();

private Multitone() {}

public static Object getInstance(Object key) {
    Object instance = instances.get(key);
    if (instance == null) {
        createLock.lock();
        try {
            if (instance == null) {
                instance = createInstance();
                instances.put(key, instance);
            }
        } finally {
            createLock.unlock();
        }
    }
    return instance;
}