Does ConcurrentMap.remove() provide a happens-before edge before get() returns null?

Question

Are actions in a thread prior to calling ConcurrentMap.remove() guaranteed to happen-before actions subsequent to seeing the removal from another thread?

Documentation says this regarding objects placed into the collection:

Actions in a thread prior to placing an object into any concurrent collection happen-before actions subsequent to the access or removal of that element from the collection in another thread.

Example code:

{
    final ConcurrentMap map = new ConcurrentHashMap();
    map.put(1, new Object());

    final int[] value = { 0 };

    new Thread(() -> {
        value[0]++;
        value[0]++;
        value[0]++;
        value[0]++;
        value[0]++;

        map.remove(1); // A

    }).start();

    new Thread(() -> {
        if (map.get(1) == null) { // B
            System.out.println(value[0]); // expect 5
        }

    }).start();
}

Is A in a happens-before relationship with B? Therefore, should the program only, if ever, print 5?

Answer 1

You have found an interesting subtle aspect of these concurrency tools that is easy to overlook.

First, it’s impossible to provide a general guaranty regarding removal and the retrieval of a null reference, as the latter only proves the absence of a mapping but not a previous removal, i.e. the thread could have read the map’s initial state, before the key ever had a mapping, which, of course, can’t establish a happens-before relationship with the actions that happened after the map’s construction.

Also, if there are multiple threads removing the same key, you can’t assume a happens-before relationship, when retrieving null, as you don’t know which removal has been completed. This issue is similar to the scenario when two threads insert the same value, but the latter can be fixed on the application side by only perform insertions of distinguishable values or by following the usual pattern of performing the desired modifications on the value object which is going to be inserted and to query the retrieved object only. For a removal, there is no such fix.

In your special case, there’s a happens-before relationship between the map.put(1, new Object()) action and the start of the second thread, so if the second thread encounters null when querying the key 1, it’s clear that it witnessed the sole removal of your code, still, the specification didn’t bother to provide an explicit guaranty for this special case.

Instead, the specification of Java 8’s ConcurrentHashMap says,

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.)

clearly ruling out null retrievals.

I think, with the current (Java 8) ConcurrentHashMap implementation, your code can’t break as it is rather conservative in that it performs all access to its internal backing array with volatile semantics. But that is only the current implementation and, as explained above, your code is a special case and likely to become broken with every change towards a real-life application.

Answer 2

No, you have the order wrong.

There is a happens-before edge from the put() to the subsequent get(). That edge is not symmetric, and doesn't work in the other direction. There is no happens-before edge from at get() to another get() or a remove(), or from a put() to another put().

In this case, you put an object in the map. Then you modify another object. That's a no-no. There's no edge from the those writes to the get() in the second thread, so those writes may not be visible to the second thread.

On Intel hardware, I think this will always work. However, it isn't guaranteed by the Java memory model, so you have to be wary if you ever port this code to different hardware.