ConcurrentHashMap internals

the picture

the concurrent collections chapter covers when to reach for it. this one is about how 6,400 lines of Doug Lea's code avoid a global lock.

think of a supermarket. a Hashtable is one checkout for the whole shop (synchronized on every method). java 7's ConcurrentHashMap opened 16 checkouts (segments) and sent each customer to one by their surname. java 8 tore the checkouts out: you pay at the shelf you took from, and if nobody's standing at an empty shelf you don't even queue.

java 7's segments were a decent idea with a fixed ceiling: the number of segments (concurrencyLevel, default 16) was set in the constructor and never changed, so at most 16 writers could make progress at once no matter how big the map got. java 8 drops that ceiling. the lock count is the bin count, and it grows with the table. the constructor still accepts concurrencyLevel, but now it's only a sizing hint, and the Segment class left in the jdk 25 source exists purely so old serialized maps still deserialize.

put: CAS first, lock second

putVal is one loop. the branches that matter, read straight from the source:

two details make this safe:

• using the first node as the lock costs zero extra memory (the source says it doesn't want "a distinct lock object" per bin). it works because new nodes are only ever appended, so a node that's first stays first until it's removed or the bin is moved. that's also why the code re-checks tabAt(tab, i) == f after it gets the lock: if the head changed while it was waiting, it locked the wrong thing and goes round again.
• reads don't need the lock because the fields they touch are published safely: tabAt is an acquire read of the array slot, and Node.val and Node.next are volatile. a reader sees either the old chain or the new one, never a half-built node. (the happens-before rules behind that are in the java memory model.)

how often do two writers actually collide on one bin? the source works it out: for two threads touching different random keys, roughly 1 in (8 × number of elements). on a map with a million entries, that's basically never.

resizing together

a HashMap resize is one thread doing all the work while nobody else is allowed near the map. ConcurrentHashMap can't stop the world, so it turns the resize into a job board. whoever starts it allocates the new array and posts the work as transferIndex. anyone who walks into a moved bin takes a stride of bins off the board and moves them, then goes back to what they were doing.

sizeCtl is one volatile int that means five different things, depending on its sign and the moment:

the stamp is numberOfLeadingZeros(n) | (1 << 15), shifted up 16. the 1 << 15 makes the whole int negative, and the leading-zero count makes the stamp different for every table size. the source calls it a generation stamp: it's what stops two resizes from overlapping. the stride is max(16, (n >>> 3) / NCPU): tiny tables get handed out 16 bins at a time, big tables get split across your cores. and bins are moved from the top down (index n - 1 first), which is part of how iterators running mid-resize avoid skipping or repeating nodes.

counting without a counter

a size field updated by every put would be one memory location that every core fights over. the same problem LongAdder solves, solved the same way (the source calls its counter "a specialization of LongAdder"):

1. try a CAS on baseCount. no contention, done.
2. lost the CAS? from then on, add to a CounterCell picked by the thread's random probe. cells are padded with @Contended so two of them never share a cache line.
3. still colliding on a cell? double the cell array, up to the number of CPUs.

size() just adds baseCount and every cell.

the sum isn't a snapshot. while you add up cell 3, someone can increment cell 0 behind you. so size() is exact when the map is quiet and an estimate when it isn't, and that's fine: a size that's correct for one nanosecond is useless to a concurrent program anyway. if the map can hold more than Integer.MAX_VALUE entries, use mappingCount(), which returns the long.

no nulls, ever

HashMap lets you store null keys and values. ConcurrentHashMap throws NullPointerException for either.

var m = new ConcurrentHashMap<String, Integer>();
m.put("a", 1);
IO.println(m.get("b"));
m.put("b", null);
IO.println("done");

the reason is ambiguity under concurrency. in a HashMap, if get(k) returns null you can follow up with containsKey(k) to find out whether that meant "absent" or "mapped to null", because nobody changes the map between your two calls. in a concurrent map, somebody can. so ConcurrentHashMap makes null mean exactly one thing, "not there right now", and it can only promise that if null can never be stored. the javadoc leans on the same idea for its bulk operations: since keys and values are never null, a null result is a reliable "no result".

void main() {
    var m = new ConcurrentHashMap<String, Integer>();
    m.put("a", 1);
    IO.println(m.get("b"));
    try {
        m.put("b", null);
    } catch (NullPointerException e) {
        IO.println("NullPointerException");
    }
}

null
NullPointerException

the traps

thread-safe methods don't make your sequence of calls thread-safe.

if (!cache.containsKey(id)) {
    cache.put(id, load(id)); // two threads both load
}
Integer n = counts.get(word);
counts.put(word, n == null ? 1 : n + 1); // lost updates

cache.computeIfAbsent(id, this::load);
counts.merge(word, 1, Integer::sum);

computeIfAbsent, compute and merge run your function while holding the bin's lock (for an empty bin, the bin holds a placeholder ReservationNode while it runs). that makes them atomic, and it means the function must be short and must never touch the same map. the textbook way to break that rule is memoized recursion:

final ConcurrentHashMap<Integer, Long> memo = new ConcurrentHashMap<>();
 
long fib(int n) {
    if (n < 2) return n;
    return memo.computeIfAbsent(n, k -> fib(k - 1) + fib(k - 2));
}
 
void main() {
    IO.println("fib(20) with a memo...");
    IO.println(fib(20));
}

fib(20) with a memo...
Exception in thread "main" java.lang.IllegalStateException: Recursive update

computing key 20 parks a ReservationNode in bin 4 (20 & 15). sixteen levels down, key 4 hashes to the same bin, finds the reservation, and the map refuses to deadlock with itself. a plain HashMap throws ConcurrentModificationException for the same code. memoize with an explicit get and putIfAbsent, or just use a loop.