How does ConcurrentHashMap work internally?

• Java 7: array of 16 Segment objects, each a mini-HashMap with its own ReentrantLock; maximum concurrency = 16
• Java 8+: flat Node[] table (no segments); reads use volatile (no lock); writes use CAS for empty buckets, synchronized on the first Node for non-empty buckets
• Treeification: same as HashMap – threshold 8, buckets convert to Red-Black trees
• Distributed resize: multiple threads help migrate buckets; each claims a stride via CAS on transferIndex
• Atomic operations: computeIfAbsent, merge, compute are all atomic per-key

How did Java 7 ConcurrentHashMap work?

Java 7's ConcurrentHashMap was an array of 16 Segments. Each Segment was essentially a small HashMap protected by its own ReentrantLock. The key determined which segment to use, and only that segment was locked during writes.

This meant at most 16 threads could write concurrently (one per segment). Reads required acquiring a read lock on the segment. The segment count was fixed at creation time and could not be changed.

// Java 7 ConcurrentHashMap (simplified)
class ConcurrentHashMap<K,V> {
    Segment<K,V>[] segments; // default 16 segments

    static class Segment<K,V> extends ReentrantLock {
        HashEntry<K,V>[] table; // each segment has its own bucket array

        V put(K key, int hash, V value) {
            lock(); // lock THIS segment only
            try {
                // find bucket in this segment, insert/replace
            } finally {
                unlock();
            }
        }
    }
}
// Limitation: fixed 16 segments, entire segment locked for write

How does Java 8+ ConcurrentHashMap work?

Java 8 completely redesigned ConcurrentHashMap. It uses a flat Node[] table – the same structure as HashMap. The key improvements are:

1. Reads are lock-free. The get() method uses volatile reads of the table reference, bucket head, and node values. No locks, no CAS, just volatile semantics.

2. Writes to empty buckets use CAS. Compare-And-Swap is a hardware atomic operation. If the bucket is empty (null), CAS atomically sets it to the new Node.

3. Writes to non-empty buckets use synchronized. The synchronized block locks only the first Node of the specific bucket. Other buckets remain accessible.

package com.bank.demo;

import java.math.BigDecimal;
import java.util.concurrent.ConcurrentHashMap;

public class CHMInternalsDemo {
    public static void main(String[] args) {
        ConcurrentHashMap<String, BigDecimal> balances = new ConcurrentHashMap<>();

        // Write to empty bucket: CAS (no lock)
        balances.put("SAV2001", new BigDecimal("150000"));

        // Read: volatile read (no lock)
        BigDecimal bal = balances.get("SAV2001");
        System.out.println("Balance: " + bal);

        // Write to non-empty bucket: synchronized on first node
        // (if another key hashes to the same bucket)
        balances.put("CUR3001", new BigDecimal("75000"));

        // Atomic compound operation
        balances.merge("SAV2001", new BigDecimal("5000"), BigDecimal::add);
        System.out.println("After deposit: " + balances.get("SAV2001"));
    }
}

Balance: 150000
After deposit: 155000

How does distributed resize work?

When the table needs to grow, Java 8+ ConcurrentHashMap distributes the migration across multiple threads:

1. A new table (2x capacity) is allocated.
2. A transferIndex counter starts at the old table's length.
3. Each thread that accesses the map during resize claims a stride of buckets (minimum 16) by atomically decrementing transferIndex.
4. Each thread migrates its claimed buckets to the new table.
5. When all buckets are migrated, the new table becomes active.

This means N threads can help resize simultaneously, making resize N times faster than a single-threaded approach.

// Pseudocode of distributed resize
while (transferIndex > 0) {
    int myStride = Math.max(MIN_TRANSFER_STRIDE, n / ncpu);
    int start = CAS(transferIndex, transferIndex - myStride);
    for (int i = start; i < start + myStride; i++) {
        // migrate bucket i from old table to new table
    }
}

How is Java 8 better than Java 7?

| Feature | Java 7 | Java 8+ |
|---|---|---|
| Structure | Segment[] (16 segments) | Node[] (flat table) |
| Read locking | Segment read lock | None (volatile) |
| Write locking | Segment lock | CAS or sync(bucket) |
| Granularity | 1/16 of map | 1/bucket |
| Max concurrency | 16 writers | Number of buckets |
| Resize | Single-threaded | Multi-threaded |
| Treeification | No | Yes (threshold 8) |
| Atomic ops | Limited | Full (compute, merge) |

What are common mistakes?

Mistake: Assuming size() is exact

ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
// Under concurrent modifications, size() is approximate
int size = map.size(); // may not reflect all concurrent puts
// Use mappingCount() for long return type (avoids int overflow)
long count = map.mappingCount();

Mistake: Blocking in computeIfAbsent

// WRONG: long computation blocks other threads accessing the same key
map.computeIfAbsent("SAV2001", k -> {
    Thread.sleep(5000); // blocks bucket lock for 5 seconds!
    return loadFromDatabase(k);
});
// CORRECT: compute quickly, load lazily
map.computeIfAbsent("SAV2001", k -> new LazyWrapper(k));

What should a senior engineer know?

- The spread function. ConcurrentHashMap uses spread(int h) which is (h ^ (h >>> 16)) & HASH_BITS. The & HASH_BITS (0x7fffffff) ensures the hash is non-negative because negative hashes are used internally for forwarding nodes during resize.

- ForwardingNode. During resize, migrated buckets are replaced with ForwardingNode objects that point to the new table. When a thread encounters a ForwardingNode during put/get, it redirects to the new table.

- CounterCell array. Instead of a single size counter (which would be a contention point), Java 8 CHM uses a CounterCell[] array. Each thread increments its own cell. size() sums all cells.

- computeIfAbsent deadlock. In rare cases, calling computeIfAbsent recursively for the same key can deadlock because the thread holds the bucket lock and tries to acquire it again.

What are common interview follow-up questions?

• "How are reads lock-free?" – Volatile reads of node values and next pointers.
• "What is the concurrency level in Java 8?" – Effectively the number of buckets (no fixed segment count).
• "How does resize work with multiple threads?" – Each thread claims a stride of buckets via CAS on transferIndex.
• "Is computeIfAbsent atomic?" – Yes, per-key atomic. The function executes at most once for a given key.