Skip to content
Path to Engineer
All lessons
JavaCollections18 min read

ConcurrentHashMap internals and CopyOnWriteArrayList

How ConcurrentHashMap gets thread safety without locking the whole map, and when CopyOnWriteArrayList is the right trade.

Day 53 of the 488-day pathway. Published in full — nothing held back.

Concurrent collections — ConcurrentHashMap internals, CopyOnWriteArrayList Virtual memory — paging, page tables, MMU, TLB

Closes the collections block. ConcurrentHashMap internals are a common follow-up once you've answered Day 048 well.

Part 1 — L-053 · Concurrent collections

Why HashMap fails under concurrency

Day 048's demo lost entries. Two distinct failure modes:

Lost updates — two threads compute the same bucket index, both create a node, one overwrites the other. Ordinary read-modify-write racing (Day 040's B-06).

The Java 7 infinite loop — resizing rehashed entries and reversed chain order. Two threads resizing simultaneously could link node A → B and B → A, creating a cycle. A later get() on that bucket would spin forever at 100% CPU. Java 8's order-preserving split (Day 048) removed this specific disaster, but HashMap remains unsafe.

The wrong fixes

Map<K,V> m = new Hashtable<>();                             // 💀 legacy
Map<K,V> m = Collections.synchronizedMap(new HashMap<>());  // 💀 barely better

Both lock the entire map on every operation. Two problems:

  1. No concurrency at all — one thread at a time, even for reads on different keys.
  2. Compound operations are still broken:
synchronized (map) {                      // you must lock EXTERNALLY anyway
    if (!map.containsKey(k)) map.put(k, v);
}

Per-method synchronization gives you the cost without the benefit (Day 045). Each call is atomic; your sequence of calls is not.

ConcurrentHashMap

Java 7: lock striping

The map was divided into 16 segments, each with its own lock. Threads touching different segments never contended.

Concurrency level 16 — better than one lock, but coarse and memory-hungry.

Java 8: per-bucket locking + CAS

The segments were removed entirely. The current design:

Operation Mechanism
Read (get) Completely lock-free — volatile reads of the table and nodes
Insert into an empty bucket CAS — a single atomic compare-and-swap, no lock
Insert into an occupied bucket synchronized on that bucket's first node only
Resize Cooperative — multiple threads help transfer 
   table
   ┌────┐
 0 │ ●──┼──▶ [A]        ← thread 1 locks THIS node
   ├────┤
 1 │null│               ← thread 2 CASes a node in here — no lock at all
   ├────┤
 2 │ ●──┼──▶ [B]─▶[C]   ← thread 3 locks THIS node
   └────┘
   Three threads, three buckets, zero contention.

Effective concurrency is now the number of buckets, not 16. On a table of 1024 buckets, up to 1024 writers can proceed simultaneously.

Reads never block. get() is a volatile read walk — no lock, no CAS. Since most workloads are read-heavy, this is the single biggest win.

Cooperative resizing

When a resize is in progress, a thread that arrives to write helps transfer buckets rather than blocking. A ForwardingNode marks transferred buckets so readers are redirected to the new table.

Parallel resizing under load — one of the more elegant things in the JDK.

Why nulls are banned

Day 045 gave the argument; state it precisely:

map.get(k)      // null

Absent, or present-and-null? On HashMap you resolve it with containsKey. On a concurrent map that's useless — the mapping can change between the two calls. The ambiguity is unresolvable, so nulls are forbidden for both keys and values.

The atomic compound operations — the actual API

This is what you should be using, and it's what most people miss:

map.putIfAbsent(k, v);                       // atomic check-then-put
map.computeIfAbsent(k, key -> expensive());  // atomic — the function runs ONCE
map.computeIfPresent(k, (key, v) -> v + 1);
map.compute(k, (key, v) -> v == null ? 1 : v + 1);
map.merge(k, 1, Integer::sum);               // ✅ the idiomatic counter
map.replace(k, oldV, newV);                  // atomic CAS on the value
map.getOrDefault(k, 0);

// 💀 NOT atomic even on ConcurrentHashMap — two calls, race between them
if (!map.containsKey(k)) map.put(k, compute());

// ✅ atomic
map.computeIfAbsent(k, key -> compute());

// 💀 lost updates
map.put(k, map.getOrDefault(k, 0) + 1);

// ✅
map.merge(k, 1, Integer::sum);

merge for counters is the idiom to remember. It's atomic, concise, and correct.

One caveat: the function passed to computeIfAbsent runs while holding the bucket lock. Keep it short, and never have it modify the same map — that deadlocks or corrupts state.

CopyOnWriteArrayList

Every mutation copies the entire backing array.

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        Object[] newEs = Arrays.copyOf(es, es.length + 1);   // FULL COPY
        newEs[es.length] = e;
        setArray(newEs);
        return true;
    }
}
Cost
Read / iterate O(1), completely lock-free
add / remove O(n) — copies the whole array

Use only when reads vastly outnumber writes. The canonical case is a listener list: registered once at startup, iterated on every event.

Its iterator holds a snapshot of the array at creation, so it never throws ConcurrentModificationException (Day 052) — but it also never sees later changes, and it.remove() throws UnsupportedOperationException.

The decision table

Need Use
Concurrent map ConcurrentHashMap
Concurrent sorted map ConcurrentSkipListMap
Read-mostly list (listeners) CopyOnWriteArrayList
Concurrent set ConcurrentHashMap.newKeySet()
Producer-consumer ArrayBlockingQueue / LinkedBlockingQueue
Lock-free queue ConcurrentLinkedQueue
Atomic counter LongAdder (better than AtomicLong under contention)

ConcurrentSkipListMap is the concurrent sorted map — a skip list rather than a red-black tree, because skip lists are far easier to make lock-free (rebalancing a tree concurrently is very hard).

LongAdder over AtomicLong for high-contention counters: it maintains per-thread cells and sums them on read, avoiding CAS contention on a single memory location. Day 068.

Type this yourself

import java.util.*;
import java.util.concurrent.*;

public class ConcurrentDemo {
    public static void main(String[] args) throws Exception {
        int threads = 8, perThread = 100_000;

        // ---- 1. HashMap loses data ----
        Map<Integer,Integer> unsafe = new HashMap<>();
        runAll(threads, t -> { for (int i = 0; i < perThread; i++) unsafe.put(t * perThread + i, i); });
        System.out.println("--- correctness ---");
        System.out.printf("   HashMap:           expected %,d got %,d%n",
                threads * perThread, unsafe.size());

        Map<Integer,Integer> safe = new ConcurrentHashMap<>();
        runAll(threads, t -> { for (int i = 0; i < perThread; i++) safe.put(t * perThread + i, i); });
        System.out.printf("   ConcurrentHashMap: expected %,d got %,d%n",
                threads * perThread, safe.size());

        // ---- 2. Throughput: synchronizedMap vs ConcurrentHashMap ----
        Map<Integer,Integer> sync = Collections.synchronizedMap(new HashMap<>());
        long start = System.currentTimeMillis();
        runAll(threads, t -> { for (int i = 0; i < perThread; i++) sync.put(t * perThread + i, i); });
        long syncTime = System.currentTimeMillis() - start;

        Map<Integer,Integer> chm = new ConcurrentHashMap<>();
        start = System.currentTimeMillis();
        runAll(threads, t -> { for (int i = 0; i < perThread; i++) chm.put(t * perThread + i, i); });
        long chmTime = System.currentTimeMillis() - start;

        System.out.printf("%n--- %d threads × %,d puts ---%n", threads, perThread);
        System.out.printf("   synchronizedMap:   %,5d ms   ← ONE lock%n", syncTime);
        System.out.printf("   ConcurrentHashMap: %,5d ms   ← per-bucket%n", chmTime);

        // ---- 3. Compound operations still race ----
        Map<String,Integer> counter = new ConcurrentHashMap<>();
        runAll(threads, t -> {
            for (int i = 0; i < 50_000; i++)
                counter.put("k", counter.getOrDefault("k", 0) + 1);      // NOT atomic
        });
        System.out.printf("%n--- counter ---%n   get-then-put: expected %,d got %,d   ← LOST UPDATES%n",
                threads * 50_000, counter.get("k"));

        Map<String,Integer> counter2 = new ConcurrentHashMap<>();
        runAll(threads, t -> { for (int i = 0; i < 50_000; i++) counter2.merge("k", 1, Integer::sum); });
        System.out.printf("   merge():      expected %,d got %,d   ← ATOMIC%n",
                threads * 50_000, counter2.get("k"));

        // ---- 4. computeIfAbsent runs once ----
        Map<String,String> cache = new ConcurrentHashMap<>();
        var calls = new java.util.concurrent.atomic.AtomicInteger();
        runAll(threads, t -> {
            for (int i = 0; i < 1000; i++)
                cache.computeIfAbsent("key", k -> { calls.incrementAndGet(); return "value"; });
        });
        System.out.printf("%n   computeIfAbsent called the function %d time(s) across %d threads%n",
                calls.get(), threads);

        // ---- 5. CopyOnWriteArrayList ----
        System.out.println("\n--- CopyOnWriteArrayList ---");
        List<Integer> cow = new CopyOnWriteArrayList<>();
        start = System.currentTimeMillis();
        for (int i = 0; i < 20_000; i++) cow.add(i);
        System.out.printf("   20,000 adds:  %,5d ms   ← O(n) copy each time%n",
                System.currentTimeMillis() - start);

        start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 200; i++) for (int v : cow) sum += v;
        System.out.printf("   200 full iterations: %,d ms   ← lock-free (sum=%d)%n",
                (System.nanoTime() - start) / 1_000_000, sum);

        // ---- 6. nulls ----
        System.out.println("\n--- nulls ---");
        try { new ConcurrentHashMap<String,String>().put("k", null); }
        catch (NullPointerException e) {
            System.out.println("   rejected — get() returning null must mean ABSENT");
        }
    }

    interface Task { void run(int threadId); }

    static void runAll(int n, Task task) throws Exception {
        Thread[] ts = new Thread[n];
        for (int i = 0; i < n; i++) { int id = i; ts[i] = new Thread(() -> task.run(id)); ts[i].start(); }
        for (Thread t : ts) t.join();
    }
}

Four results to record:

  1. HashMap loses entries; ConcurrentHashMap doesn't.
  2. ConcurrentHashMap outperforms synchronizedMap, often by a large factor — that's per-bucket versus global locking.
  3. getOrDefault + put loses updates even on a ConcurrentHashMap. Individual operations are atomic; your sequence is not. merge fixes it.
  4. computeIfAbsent calls the function exactly once across eight threads and eight thousand calls. That's what "atomic" buys you.

Part 2 — B-10 · Virtual memory

The idea

Every process sees a private, contiguous address space. The hardware translates to scattered physical frames.

   Virtual (per process)        Page table            Physical RAM
   ┌──────────┐                 ┌────────┐            ┌──────────┐
   │ page 0   │ ──────────────▶ │ frame 7│ ─────────▶ │ frame 0  │
   │ page 1   │ ──────────────▶ │ frame 2│            │ frame 1  │
   │ page 2   │ ──────────────▶ │ on disk│            │ frame 2  │◀─ page 1
   │ page 3   │ ──────────────▶ │ frame 0│            │ ...      │
   └──────────┘                 └────────┘            │ frame 7  │◀─ page 0
                                                      └──────────┘

Three things it buys:

  1. Isolation — a process can only reach its own mapped pages (Day 003, Day 023's kernel mode)
  2. No external fragmentation — any free frame fits any page (Day 050's B-09)
  3. More virtual memory than physical — unused pages live on disk

Address translation

   32-bit virtual address, 4 KB pages:
   ┌──────────────────────┬───────────────┐
   │  page number (20)    │  offset (12)  │
   └──────────────────────┴───────────────┘
            │                     │
            ▼                     │
      page table lookup           │
            │                     │
            ▼                     ▼
   ┌──────────────────────┬───────────────┐
   │  frame number        │  offset       │   physical address
   └──────────────────────┴───────────────┘

The offset passes through unchanged — only the page number is translated. That's why the page size determines the split.

The MMU and the TLB

The MMU (Memory Management Unit) is hardware that performs translation on every single memory access.

The problem: a page-table lookup is itself a memory access. So every access would cost two — one to read the table, one to read the data. That doubles memory latency.

The TLB (Translation Lookaside Buffer) is a small, very fast cache of recent translations — typically 64–1024 entries, fully associative.

   Access an address
        │
        ├─ TLB HIT  (~99%)  → translate in ~1 cycle
        │
        └─ TLB MISS (~1%)   → walk the page table (~100+ cycles), then cache it

TLB hit rates above 99% are normal because of locality — the same reason CPU caches work (Day 001).

And this is why a context switch is expensive (Day 033's B-04): switching processes changes the page table, so TLB entries are invalidated and the new process starts with cold translations. Switching threads within a process keeps the same page table, so the TLB survives — which is exactly why thread switches are cheaper.

Page faults

Accessing a page not currently in RAM traps to the kernel:

   1. MMU finds the page-table entry marked "not present" → page fault
   2. Kernel checks whether the access is legal
        → illegal? SIGSEGV
   3. Find a free frame (evict one if necessary — Day 057's B-11)
   4. Read the page from disk
   5. Update the page table, restart the instruction
Type Meaning
Minor The page is in memory but not mapped for this process — cheap
Major Must be read from disk — ~100 µs, roughly 1000× a RAM access (Day 001)

Thrashing — so many major faults that the system spends more time paging than computing. Throughput collapses. Day 057's B-11 covers replacement policies.

Why this matters for the JVM

  • Heap pages are allocated lazily — -Xms reserves address space, but physical frames are committed on first touch. Which is why -Xms = -Xmx (Day 027) helps: the reservation happens once.
  • A major page fault on heap memory is catastrophic for GC. A collector scanning a swapped-out heap generates thousands of disk reads, so a pause that should be 50 ms becomes seconds. This is why you never let a JVM swap — configure the container so the heap fits in RAM.
  • Huge pages (2 MB instead of 4 KB) reduce TLB pressure for large heaps — -XX:+UseLargePages is a real tuning option for multi-gigabyte heaps.
  • MaxRAMPercentage (Day 027) exists so the heap plus Metaspace plus thread stacks plus direct buffers all fit within the cgroup limit — otherwise the OOM killer terminates the process with no Java-level error at all.

Interview questions

Q: How does ConcurrentHashMap achieve thread safety?

In Java 8 and later, reads are entirely lock-free — volatile reads of the table and nodes. Writes into an empty bucket use a single CAS. Writes into an occupied bucket synchronize on that bucket's first node only, so threads touching different buckets never contend. Resizing is cooperative: arriving writers help transfer buckets rather than blocking. Java 7 used sixteen segment locks; the current design's effective concurrency is the number of buckets.

Q: Why is Collections.synchronizedMap worse?

It wraps every method in a lock on the whole map, so only one thread proceeds at a time even for reads on unrelated keys. And it still doesn't make compound operations atomic — a containsKey followed by a put is two separately-locked calls with a race between them, so you have to lock externally anyway.

Q: Is ConcurrentHashMap fully thread-safe?

Each individual operation is atomic, but a sequence of operations isn't. map.put(k, map.getOrDefault(k,0)+1) loses updates because the read and the write are separate. You have to use the atomic compound methods — merge, compute, computeIfAbsent, putIfAbsent.

Q: Why does ConcurrentHashMap forbid nulls?

A null return from get would be ambiguous between absent and mapped-to-null, and unlike HashMap you can't disambiguate with containsKey because the mapping can change between the two calls.

Q: When would you use CopyOnWriteArrayList?

Only when reads vastly outnumber writes, because every mutation copies the entire array. The canonical case is a listener registry populated at startup and iterated on every event. Iteration is lock-free over a snapshot, so it never throws ConcurrentModificationException — but it also never sees changes made after the iterator was created.

Q: What is the TLB and why does it matter?

A hardware cache of virtual-to-physical page translations. Without it every memory access would need a page-table lookup, itself a memory access, doubling latency. Hit rates above 99% are typical due to locality. It's also why process context switches cost more than thread switches — changing the address space invalidates TLB entries, while threads in one process share a page table.

Q: Why must a JVM never swap?

Garbage collection scans large regions of the heap, so if pages have been swapped out the collector triggers thousands of major page faults at roughly 100 microseconds each. A pause that should be tens of milliseconds becomes seconds. The heap must fit in physical memory.

Mini task

  1. Run ConcurrentDemo. Record all four results, especially the lost-update counter.
  2. Rewrite a synchronizedMap-based cache using computeIfAbsent. Compare throughput.
  3. Find every non-atomic compound operation in some code you have and convert it.
  4. Measure CopyOnWriteArrayList add versus iterate at 1k, 10k and 50k elements.
  5. Check your machine's TLB size (cpuid on Linux, or Get-ComputerInfo) and page size.

Exit questions

  1. Give two ways HashMap fails under concurrency.
  2. Describe ConcurrentHashMap's Java 8 design — reads, empty-bucket writes, occupied-bucket writes, resize.
  3. What is the effective concurrency level, and how does it differ from Java 7?
  4. Why is synchronizedMap insufficient — two reasons?
  5. Show a compound operation that races on a ConcurrentHashMap, and fix it.
  6. Why are nulls forbidden?
  7. When is CopyOnWriteArrayList appropriate?
  8. Explain virtual address translation and what the offset does.
  9. What is the TLB, and how does it explain the process-vs-thread switch cost difference?
  10. Why must a JVM heap never be swapped out?

Articulation drill

Two minutes: "How does ConcurrentHashMap differ from HashMap and from synchronizedMap?"

Lock-free reads, per-bucket write locking, cooperative resize — then the caveat that compound operations still need the atomic methods. That caveat is what separates a good answer from a recited one.

Previous: Day 052 · Next: Day 054 — generics (not yet written — see Days index)

Collections block complete: Days 045–053. You can now explain every major implementation's internals, choose correctly between them, and whiteboard HashMap — which is your Stage 1 exit-gate item and the most-asked Java interview question.