How does ConcurrentHashMap achieve thread safety?

The Answer

Say this in the room. 45 seconds.

• Segments are gone. That answer is from Java 7 and it is the fastest way to date yourself in this question.
• Since Java 8 the map is one table, and the lock is one bin. Empty bin: a CAS installs the first node, no lock at all. Occupied bin: synchronized on that bin's head node.
• So write concurrency scales with the table size instead of a concurrencyLevel fixed at construction.
• Reads never lock. Node.val and Node.next are volatile, so get() is a plain read that is guaranteed to see completed writes.
• size() is an estimate maintained by striped counters, iterators are weakly consistent, and neither throws ConcurrentModificationException.
• Null keys and values are rejected, unlike HashMap.
• The part that actually bites: every method is atomic, and your sequence of methods is not. containsKey then put is a race on a perfectly thread-safe map.

Understand It

What it exists to prevent

A HashMap written by several threads at once is undefined behaviour, and it fails in three different ways. This block races one deliberately, alongside a ConcurrentHashMap doing identical work — eight threads each writing five thousand disjoint keys, so nothing should collide and nothing should be lost:

Map<Integer, Integer> plain = new HashMap<>();
int[] plainOutcome = fill(plain);

Map<Integer, Integer> concurrent = new ConcurrentHashMap<>();
int[] concurrentOutcome = fill(concurrent);

System.out.println(THREADS + " threads, " + WRITES_PER_THREAD + " disjoint keys each");
System.out.println(report("HashMap", plain, plainOutcome));
System.out.println(report("ConcurrentHashMap", concurrent, concurrentOutcome));

8 threads, 5000 disjoint keys each
  HashMap            30109 of 40000, lost? yes, threw: 0, still running: 0
  ConcurrentHashMap  40000 of 40000, lost? no, threw: 0, still running: 0

The numbers change on every run, which is why this block is verified for shape. Across runs on the same machine that HashMap line has printed all three of:

• lost? yes — every single time. A quarter of the entries typically vanish.
• threw: 8 — every thread dying with ClassCastException: HashMap$Node cannot be cast to HashMap$TreeNode, because two threads treeified the same bin at once.
• still running: 1 — a thread that never finished, spinning in a bin that a concurrent resize left with a cycle in it.

That third one is why the harness runs those threads as daemons behind a bounded join. This page is compiled and executed on every deploy, and a demonstration that can hang the build is not one worth having. It is also the honest headline: a raced HashMap does not merely lose data, it can corrupt its own structure and stop responding.

ConcurrentHashMap prints 40000 of 40000, every run, with no locks anywhere in the reading path.

How it does it, since Java 8

The Java 7 design was an array of segments, each an independent ReentrantLock covering a slice of the table. concurrencyLevel — default 16 — fixed how many segments existed, at construction, forever. Sixteen writers maximum, whether the map held a hundred entries or ten million.

Java 8 threw that away. There is one table, exactly like HashMap's, and locking is per bin:

Three consequences worth stating out loud in an interview:

• Lock granularity is a bin, so the number of concurrent writers scales with the table. A bigger map is a more concurrent map.
• The uncontended path has no lock, only a CAS, which is why writes to a sparse map are cheap.
• Resizing is cooperative. A thread that finds a bin under transfer joins the transfer rather than waiting, so a resize does not serialise everyone behind one thread.

Long bins treeify into red-black trees on the same rules as HashMap — eight nodes in a bin and at least 64 table slots — which bounds the damage from a bad hashCode.

Thread-safe methods, unsafe sequences

This is the one that costs real money, and the one interviewers use to separate "I know the class name" from "I have used it".

Every individual method is atomic. Two of them in a row are not. Here eight threads race to initialise five thousand keys — once by checking then putting, once with computeIfAbsent. The counter records how many times the expensive value was actually built:

ConcurrentHashMap<Integer, Integer> checkThenAct = new ConcurrentHashMap<>();
AtomicInteger naive = new AtomicInteger();
hammer(id -> {
    for (int k = 0; k < KEYS; k++) {
        if (!checkThenAct.containsKey(k)) checkThenAct.put(k, buildValue(naive, k));
    }
});

ConcurrentHashMap<Integer, Integer> atomic = new ConcurrentHashMap<>();
AtomicInteger guarded = new AtomicInteger();
hammer(id -> {
    for (int k = 0; k < KEYS; k++) atomic.computeIfAbsent(k, key -> buildValue(guarded, key));
});

System.out.println(KEYS + " keys, " + THREADS + " threads racing to initialise each");
System.out.println("  containsKey then put : value built " + naive.get() + " times");
System.out.println("  computeIfAbsent      : value built " + guarded.get() + " times");
System.out.println("  built twice for some key? "
    + (naive.get() > KEYS ? "yes" : "no") + " / " + (guarded.get() > KEYS ? "yes" : "no"));

5000 keys, 8 threads racing to initialise each
  containsKey then put : value built 12795 times
  computeIfAbsent      : value built 5000 times
  built twice for some key? yes / no

Five thousand keys, and the check-then-act version built the value twelve thousand times. If that value is a database query or an HTTP call, you have just tripled the load on something downstream and called it a cache.

computeIfAbsent builds exactly 5000, because the check and the insert happen inside the bin's lock.

The atomic compound operations, and what each is for:

One trap inside the fix: the function you pass to computeIfAbsent runs while the bin is locked. Keep it short, and never touch the same map from inside it — a recursive update on the same bin throws IllegalStateException, and on a different bin it can deadlock.

Iterators, size, and why they are honest about it

Map<String, String> hash = new HashMap<>(Map.of("a", "1", "b", "2"));
try {
    for (String key : hash.keySet()) hash.put("c", "3");
    System.out.println("  HashMap           : iterated, size now " + hash.size());
} catch (ConcurrentModificationException e) {
    System.out.println("  HashMap           : ConcurrentModificationException");
}

Map<String, String> chm = new ConcurrentHashMap<>(Map.of("a", "1", "b", "2"));
for (String key : chm.keySet()) chm.put("c", "3");
System.out.println("  ConcurrentHashMap : iterated, size now " + chm.size());

  HashMap           : ConcurrentModificationException
  ConcurrentHashMap : iterated, size now 3

HashMap's iterator is fail-fast: it tracks a modification count and throws the moment it notices a change. That is a debugging aid, not a safety guarantee — it is best-effort and must never be used for control flow.

ConcurrentHashMap's iterator is weakly consistent: it never throws, it reflects the map at some point at or after creation, and it may or may not show changes made during iteration. It walks the real table, so it sees whatever is there when it arrives.

The same honesty applies to size(). It is maintained by striped counter cells rather than one contended field, so it is an estimate and can be stale the instant it returns. Use it for metrics and logs; never for a decision like "is there room for one more". mappingCount() is the same thing returning a long, and is the correct choice for large maps.

Why null is rejected

HashMap allows one null key and any number of null values. ConcurrentHashMap rejects both, and the reason is not tidiness.

In a single-threaded map, get(k) == null is ambiguous — absent, or present with a null value — and you resolve it with containsKey. In a concurrent map that resolution is worthless: the entry can be added or removed between the two calls, so you can never establish which case you were in. Doug Lea's position is that the ambiguity is unresolvable, so the value is disallowed.

The practical consequence: map.get(missing) returning null is unambiguous here, which is what makes getOrDefault and the compute methods reliable.

Against the alternatives

synchronizedMap has one trap people forget: iteration is not covered by the wrapper. You have to hold the map's monitor manually for the whole loop, and almost nobody does. If your access pattern is genuinely read-mostly with rare bulk replacement, a volatile reference to an immutable map beats all three.

Interviewer's Next Move

The question after the question. This is what the round is actually testing.

1. "How does ConcurrentHashMap achieve thread safety?" Since Java 8, per-bin locking on one table: a CAS installs the first node in an empty bin, and synchronized on the bin's head node covers the rest. Reads never lock because the node fields are volatile. Segments were removed in Java 8.

2. "How did it work before Java 8?" An array of segments, each an independent ReentrantLock over a slice of the table, with the count fixed at construction by concurrencyLevel — default 16. That capped concurrent writers at 16 regardless of map size.

3. "So what is the lock granularity now?" One bin. Which means concurrency scales with the table, and a larger map admits more simultaneous writers — the opposite of the old fixed ceiling.

4. "Is if (!map.containsKey(k)) map.put(k, v) safe on a ConcurrentHashMap?" No. Both calls are atomic; the sequence is not. Another thread can insert between them. Use putIfAbsent or computeIfAbsent — and at eight threads over five thousand keys, the naive version builds the value roughly two and a half times too often.

5. "Why can't it hold null keys or values?" Because get returning null would be ambiguous between absent and present-with-null, and in a concurrent map you cannot resolve that with a follow-up containsKey — the entry may change between the calls. Disallowing null makes a null return mean exactly one thing.

6. "Can you trust size()?" Not for decisions. It is an estimate from striped counter cells and may be stale on return. Fine for metrics; wrong for capacity checks. mappingCount() is the long version.

7. "What happens if you iterate while another thread writes?" Nothing bad. The iterator is weakly consistent — it never throws and may or may not reflect concurrent changes. HashMap would throw ConcurrentModificationException, and even that is best-effort and must not be relied on.

8. "ConcurrentHashMap or Collections.synchronizedMap?" ConcurrentHashMap almost always: bin-level locking versus one monitor for the whole map, and lock-free reads. synchronizedMap also requires you to hold the monitor manually around any iteration, which is a trap most code gets wrong.

Code traps

Trap A — predict before you run:

ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();

void record(String key) {
    counts.put(key, counts.getOrDefault(key, 0) + 1);
}

Trap B:

ConcurrentHashMap<String, List<String>> groups = new ConcurrentHashMap<>();

void add(String group, String member) {
    groups.computeIfAbsent(group, g -> new ArrayList<>()).add(member);
}

Trap C:

if (cache.size() < MAX_ENTRIES) {
    cache.put(key, value);
}

Common wrong answers

Check Yourself

Q1. Where exactly is the lock taken on a write, and when is none taken at all?

Q2. Your cache uses containsKey then put and the database is seeing far more queries than there are distinct keys. Why, and what is the fix?

Q3. map.computeIfAbsent(k, x -> new ArrayList<>()).add(item) — what is still wrong?

Practice