Is put() method in ConcurrentHashMap also atomic?

Question

In ConcurrentHashMap, putIfAbsent() is atomic. My question is method put() in ConcurrentHashMap also atomic?

Answer 1

It is not stated explicitly in the documentation that put or get are atomic. However, the javadoc states this:

Retrievals reflect the results of the most recently completed update operations holding upon their onset. (More formally, an update operation for a given key bears a happens-before relation with any (non-null) retrieval for that key reporting the updated value.)

That implies if one thread does a put and another does a get with the same key, then the get will either see the "before the put" state or the "after the put" state. That effectively means that get and put are atomic with respect to each other, and with respect to other explicitly atomic operations ... all for a given key. Indeed, if this wasn't the case, then ConcurrentHashMap would not be thread-safe in the conventional / intuitive sense.

However, the javadocs do not provide strong guarantees for operations involving different keys. Atomicity is therefore limited.

This kind of atomicity not a particularly interesting or useful property. For example, while put and get are individually atomic, a put followed by a get is not atomic. It is hard to see how you would exploit the limited atomicity of these operations ... beyond general thread-safety.

(IMO, that is probably the reason that they don't bother to explicitly mention the atomicity of get and put in the javadoc.)

The more interesting property is the atomicity (or not) of the more complex operations. For example, operations like putIfAbsent, compute and merge are atomic, but the bulk operations are not atomic.

Answer 2

Oracle's documentation for ConcurrentHashMap::put​(K key, V value) does not explicitly state about the Atomicity of this method.

Let us see this ourselves (OpenJDK 11_{version "11.0.2" 2019-01-15}):

V put(K key, V value) calls V putVal(K key, V value, boolean onlyIfAbsent), which, in turn, looks like this:

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (ConcurrentHashMap.Node<K,V>[] tab = table;;) {
        ConcurrentHashMap.Node<K,V> f; int n, i, fh; K fk; V fv;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new ConcurrentHashMap.Node<K,V>(hash, key, value)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else if (onlyIfAbsent // check first node without acquiring lock
                && fh == hash
                && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                && (fv = f.val) != null)
            return fv;
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (ConcurrentHashMap.Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                            (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            ConcurrentHashMap.Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new ConcurrentHashMap.Node<K,V>(hash, key, value);
                                break;
                            }
                        }
                    }
                    else if (f instanceof ConcurrentHashMap.TreeBin) {
                        ConcurrentHashMap.Node<K,V> p;
                        binCount = 2;
                        if ((p = ((ConcurrentHashMap.TreeBin<K,V>)f).putTreeVal(hash, key,
                                value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                    else if (f instanceof ConcurrentHashMap.ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

As you can see, it's a partially atomic and thread-safe; however, it is not FULLY atomic operation, per se, and it depends on the state of the table, state of the bucket/entry you're adding, and some other peculiar details.

Answer 3

If I was in charge of this API I'd add it to the docs, but there is an explanation:

put is inherently a singular operation. As in, the definition of what put does (from java.util.Map's definition) is atomic.

Of course, just because some method task is described in an atomic fashion does not imply that the implementation is atomic, and for a great many things in the collections framework, they aren't. ArrayList's add method is an atomic description, but not an atomic implementation.

The difference is, the description of the add job is simply 'add the element to the end'. It is not 'search for the end node, and once found, add this element as tail reference to it'. It is not 'obtain the size of the list and remember it. Then, check the capacity of this list, if it is insufficient to add items to it, expand the capacity by the growth factor first, then, set the value for the earlier obtained 'size' index to the passed in object.'

Even though that latter long-winded description is more or less properly describing what ArrayList.add actually does.

So, the javadoc of ConcurrentHashMap at the class level and at the method level work together:

put() is described inherently as an atomic operation, whilst putIfAbsent's description is not atomic at all. It's explicitly described as a two-step process; it's even in the name! put, if absent - it's a two-step name. Therefore the docs need to go out of their way to say: Even though it sounds like a two-step operation, consider it atomic in purpose.

And then the class javadoc of CHM say that all operations intended to be atomic are in fact atomically implemented.

To give some contrast, something like putAll is described as a multi-step process, and the CHM docs do not explicitly state that putAll is atomic. And indeed it isn't. You can observe half of the stuff you're adding with putAll having been added in a separate list (putAll acts pretty much exactly as if for (var e : in.entries()) put(e.getKey(), e.getValue()); is run.