ConcurrentHashMap computeIfAbsent

Question

There is a new computeIfAbsent API introduced in Java 8. The javadocs for ConcurrentHashMap's impelementation of it state:

If the specified key is not already associated with a value, attempts to compute its value using the given mapping function and enters it into this map unless null. The entire method invocation is performed atomically, so the function is applied at most once per key. Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map.

So, what does it say about locking of this implementation in case when the the key already exists and the computation is unneeded? Is the whole method computeIfAbsent synchronized as stated in docs even if no calculation is needed or just the mapping function call is syncronized to prevent calling the function twice?

Answer 1

The implementation of ConcurrentHashMap is quite complex, as it is specifically designed to allow concurrent readability while minimizing update contention. At a very high level of abstraction, it is organized as a bucketed hash table. All read operations do not require locking, and (quoting the javadoc) "there is not any support for locking the entire table in a way that prevents all access". To accomplish this, the internal design is highly sophisticated (but still elegant), with key-value mappings held in nodes which can be arranged in various ways (such as lists or balanced trees) in order to take advantage of fine grained locks. If you're interested in implementation details you can also have a look at the source code.

Trying to answer your questions:

So, what does it say about locking of this implementation in case when the the key already exists and the computation is unneeded?

It is reasonable to think that, as with any read operation, no locking is required to check if the key already exists and the mapping function does not need to be executed.

Is the whole method computeIfAbsent synchronized as stated in docs even if no calculation is needed or just the mapping function call is synchronized to prevent calling the function twice?

No, the method is not synchronized in terms of locking, but from the point of view of the caller it is executed atomically (i.e. the mapping function is applied at most once). If the key is not found, an update operation must be performed using the value computed by the mapping function and some kind of locking is involved while that function is invoked. It is reasonable to think that such locking is very fine-grained and only involves a very small portion of the table (well, the specific data structure where the key has to be stored) and this is why (quoting the javadoc, emphasis mine) "some attempted update operations by other threads may be blocked while computation is in progress".