Serguey Asael Shinder: computeIfAbsent that touches the same map corrupts it or throws
A memoised recursive function is the most natural thing in the world to write like this:
Map<Integer, Long> cache = new HashMap<>();
long fib(int n) {
if (n < 2) return n;
return cache.computeIfAbsent(n, k -> fib(k - 1) + fib(k - 2)); // wrong
}It is wrong, and the javadoc says so directly: the mapping function must not modify the map during computation. The recursive call does exactly that.
What actually happens
computeIfAbsent locates the bucket for the key before calling your function, then writes the result into that location afterwards. If your function inserts into the same map in between, the table may have been resized and rehashed, and the write lands somewhere that no longer means what it meant.
On Java 8 this silently corrupted the map: entries lost, sizes wrong, and — with the right pattern of inserts — an infinite loop on a later get, because a bucket's chain became circular. Nothing threw. You found out much later, somewhere else.
Since Java 9 HashMap detects the structural modification and throws ConcurrentModificationException, on a single thread, with no concurrency involved. That is a large improvement: a loud failure at the point of the mistake rather than a quiet one three hours away.
What to write instead
Do the lookup and the insert as separate steps, so the map is never mid-computation:
long fib(int n) {
if (n < 2) return n;
Long hit = cache.get(n);
if (hit != null) return hit;
long value = fib(n - 1) + fib(n - 2); // map untouched during this
cache.put(n, value);
return value;
}Slightly longer, and it says what it does. If the values can legitimately be null, use containsKey or a sentinel rather than testing the result of get.
Where else this shows up
The recursion is the obvious case. The subtle ones are the ones where the second write is not visible in the same method:
- a mapping function that calls a loader which populates a cache — the same map, one layer down;
- a function that logs through a component whose first call lazily registers something in the same map;
mergeandcompute, which carry the same restriction and the same detection.
ConcurrentHashMap is stricter, and for a better reason. There, a mapping function that tries to update the same map can deadlock, because the bin is locked while your function runs. It detects some cases and throws IllegalStateException — "Recursive update" — but not all of them, and a deadlocked bin does not show up as an exception at all. The rule is the same in both: the function computes a value and does nothing else.