ConcurrentHashMap CAS race condition #Java

If two threads try to update the same empty bucket at the exact same time, only one thread wins, and the other fails safely. [1, 2, 3]

Here is exactly what happens step-by-step behind the scenes:

1. The Race Condition

• Initial State: Bucket #5 in the ConcurrentHashMap is currently null (empty).
• Thread A and Thread B both want to insert a new key-value pair into Bucket #5.
• Both threads read the current value of Bucket #5 and see that it is null.
• For both threads, the Expected Value is null.

2. The Atomic Showdown

Both threads issue a CPU-level CAS instruction at nearly the exact same instant: [1]

• Thread A tells the CPU: “If Bucket #5 is still null, change it to Node A."
• Thread B tells the CPU: “If Bucket #5 is still null, change it to Node B."

Because the CPU executes CAS at the hardware level (using bus locking or cache line locking), it serializes these requests. One thread will inevitably hit the memory controller a fraction of a nanosecond faster. [1]

Get Prateek Das’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

3. The Winner and the Loser

• Thread A Wins: The CPU sees Bucket #5 is indeed null. It swaps null with Node A. Thread A's CAS returns true (success).
• Thread B Loses: A fraction of a nanosecond later, the CPU processes Thread B’s request. The CPU checks Bucket #5, but it is no longer null (it now contains Node A). Because the current value does not match Thread B's expected value (null), the CPU rejects the swap. Thread B's CAS returns false (failure). [1, 2, 3, 4, 5]

4. What Happens to the Loser (Thread B)?

ConcurrentHashMap wraps this CAS operation inside an infinite loop (called a spin lock or retry loop). [1]

1. Thread B detects that its CAS failed.
2. The loop restarts.
3. Thread B reads Bucket #5 again. This time, it sees Bucket #5 is not empty; it contains Node A.
4. Because the bucket is no longer empty, ConcurrentHashMap changes tactics. It stops trying CAS and instead uses a standard synchronized lock on Node A to safely append its new node as a linked list or tree structure. [1]

If you want to explore the source code or see a visual representation of this logic, tell me if you would like to see:

• The actual Java source code snippet (tab[i] == null loop)
• A breakdown of how it switches from CAS to synchronized once a bucket fills up