# Deep Dive (java.util.concurrent) -ConcurrentHashMap

> *"The map that lets multiple threads read and write simultaneously — without tearing itself apart."*

`ConcurrentHashMap` is the crown jewel of `java.util.concurrent`. This deep dive covers its evolution from segmented locks (Java 7) to CAS + synchronized nodes (Java 8+), and explains how it achieves thread-safe O(1) operations without global locking.

* * *

## Why Not Just Synchronize HashMap?

```java
// Option 1: Collections.synchronizedMap — SLOW
Map<String, Integer> sync = Collections.synchronizedMap(new HashMap<>());
// Every method acquires the SAME lock:
// Thread A: sync.get("x") → LOCKED → Thread B waits for ANY operation
// Thread C: sync.put("y", 1) → waits for Thread A to finish get()!

// Option 2: ConcurrentHashMap — FAST
ConcurrentHashMap<String, Integer> chm = new ConcurrentHashMap<>();
// Thread A: chm.get("x") → NO LOCK (volatile read)
// Thread B: chm.put("y", 1) → locks only bucket for "y"
// Thread C: chm.put("z", 2) → locks only bucket for "z" (different bucket!)
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/2604e6c9-8e8c-4f0c-8123-4c94ccc7b0fa.png align="center")

* * *

## Java 7: Segmented Locking (Historical)

In Java 7, ConcurrentHashMap used an array of **Segments**, each being a mini-HashMap with its own lock:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/b78ea71a-7fac-453e-a012-816f5666b561.png align="center")

**Limitations of Java 7 approach:**

*   Fixed number of segments (default 16)
    
*   Each segment is a separate hash table → wasted memory
    
*   Resizing was per-segment, not global
    
*   `size()` required locking ALL segments
    

* * *

## Java 8+: CAS + Per-Bucket Synchronization

Java 8 completely rewrote ConcurrentHashMap. The new design:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/98c78533-27a2-4b5f-9c5a-056038c78bd8.png align="center")

### The Node Class

```java
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;      // volatile! Visible to reading threads without lock
    volatile Node<K,V> next; // volatile! Chain is visible without lock
}
```

**The** `volatile` **keyword is critical** — it means reading threads can see the latest values without acquiring any lock.

* * *

## How put() Works — Thread-Safe Insert

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/07dd85da-a441-4f7a-963e-664e0bdca9b1.png align="center")

### Simplified Source

```java
final V putVal(K key, V value, boolean onlyIfAbsent) {
    int hash = spread(key.hashCode());
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();  // Lazy init with CAS
        
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // Empty bucket → CAS (no lock!)
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                break;  // CAS won
            // CAS failed → retry loop
        }
        
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);  // Help ongoing resize!
        
        else {
            // Non-empty bucket → lock the first node
            synchronized (f) {
                if (tabAt(tab, i) == f) {  // Double-check under lock
                    // Walk chain or tree, insert/update
                }
            }
        }
    }
    addCount(1L, binCount);  // Update size with spread counter
    return null;
}
```

**Key design decisions:**

1.  **CAS for empty buckets** — no locking needed for the common case
    
2.  **synchronized per bucket** — only the first node of each bucket is the lock monitor
    
3.  **Double-check after locking** — the bucket might have been resized/moved
    
4.  **Helping mechanism** — if a resize is in progress, the thread helps!
    

* * *

## How get() Works — Lock-Free Read

This is the beautiful part. `get()` **never acquires any lock**:

```java
public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {  // volatile read
        
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;  // volatile read of val
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;  // TreeBin
        
        while ((e = e.next) != null) {  // volatile read of next
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/0f45a5b0-b2cc-4bbe-aac2-54b66525883f.png align="center")

**Why is this safe?**

1.  `table` reference is volatile
    
2.  `Node.val` and `Node.next` are volatile
    
3.  `tabAt()` uses `Unsafe.getObjectVolatile()` for array element access
    
4.  Volatile reads establish **happens-before** relationships with writes
    

* * *

## Concurrent Resizing — Helping Mechanism

When ConcurrentHashMap needs to resize, **multiple threads can help** transfer entries from the old table to the new table simultaneously:

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/a8ab64e4-785b-43da-b1da-e506c96576f5.png align="center")

```java
// When a thread encounters hash == MOVED during put():
else if ((fh = f.hash) == MOVED)
    tab = helpTransfer(tab, f);  // Join the resize effort!
```

**Each thread claims a range of buckets** to transfer, preventing duplication. Once a bucket is transferred, a `ForwardingNode` is placed in the old table to redirect readers to the new table.

* * *

## Counting Elements — The Spread Counter

`size()` in a concurrent map is tricky. ConcurrentHashMap uses a **distributed counter** (inspired by `LongAdder`):

```java
// Instead of one volatile long size:
private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;

// Each thread increments a different cell → no contention!
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/498b3681-072f-4193-bf90-065365f0f062.png align="center")

**How it works:**

1.  On `put()`, try CAS on `baseCount`
    
2.  If CAS fails (contention), pick a random `CounterCell` and increment it
    
3.  `size()` sums `baseCount` + all `CounterCell` values
    
4.  The sum is **approximate** (reads are not atomic across cells)
    

> **Warning:** `size()` returns a **best-effort estimate** in a concurrent environment. It may not reflect in-flight operations.

* * *

## Bulk Operations — forEach, reduce, search

Java 8 added parallel bulk operations with a `parallelismThreshold`:

```java
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
// ... populate ...

// Parallel forEach — threshold controls when to go parallel
map.forEach(1000, // parallelize if size > 1000
    (key, value) -> System.out.println(key + "=" + value)
);

// Parallel reduce — find max value
int max = map.reduceValues(1000,
    (a, b) -> Math.max(a, b)
);

// Parallel search — find first match
String found = map.search(1000,
    (key, value) -> value > 100 ? key : null
);

// Parallel with transformation
long sum = map.reduceValuesToLong(1000,
    value -> (long) value,  // transform
    0L,                     // identity
    Long::sum               // reduce
);
```

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/b5af969f-ee1b-4a14-b53d-39c585149375.png align="center")

* * *

## ConcurrentHashMap vs Alternatives

| Feature | ConcurrentHashMap | synchronizedMap | Hashtable |
| --- | --- | --- | --- |
| **Lock granularity** | Per-bucket | Entire map | Entire map |
| **Read locking** | None (volatile) | Global lock | Global lock |
| **Null keys/values** | ❌ Neither | ✅ Both | ❌ Neither |
| **ConcurrentModificationException** | ❌ Never | ✅ Possible | ✅ Possible |
| **Bulk parallel ops** | ✅ forEach/reduce/search | ❌ | ❌ |
| **Throughput (highly concurrent)** | 🟢 Excellent | 🔴 Poor | 🔴 Poor |
| **Iterator semantics** | Weakly consistent | Fail-fast | Fail-fast |
| **Legacy** | Java 5+ | Java 2+ | Java 1.0 |

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/9f8940d9-7d87-4cfc-9a0a-33b42137a843.png align="center")

* * *

## Common Pitfalls

### Pitfall 1: Null Keys and Values Not Allowed

```java
// ❌ NullPointerException!
ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
map.put(null, "value");  // NPE!
map.put("key", null);    // NPE!

// Why? Because get() returning null would be ambiguous:
// does the key not exist, or is the value null?
// In a concurrent context, this ambiguity is dangerous.
```

### Pitfall 2: Compound Operations Are Not Atomic

```java
// ❌ RACE CONDITION: check-then-act is not atomic
if (!map.containsKey("key")) {
    map.put("key", computeValue());  // Another thread could put between these two!
}

// ✅ Use atomic compound operations
map.putIfAbsent("key", computeValue());
map.computeIfAbsent("key", k -> computeValue());
map.compute("key", (k, v) -> v == null ? 1 : v + 1);
map.merge("key", 1, Integer::sum);
```

### Pitfall 3: size() is Approximate

```java
// ❌ Don't rely on exact size in concurrent code
if (map.size() == 0) {
    // Another thread might add an element right HERE
    doSomethingAssumingEmpty(); // WRONG!
}

// ✅ size() is best-effort. Use isEmpty() when possible
// (though it's also a snapshot, it's at least a single volatile read)
```

### Pitfall 4: Iterators Are Weakly Consistent

```java
// Iterators may or may not reflect concurrent modifications
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    // This will NOT throw ConcurrentModificationException
    // But may not see entries added by other threads during iteration
    // And may or may not see entries removed by other threads
}
```

* * *

## Summary

![](https://cdn.hashnode.com/uploads/covers/637f189ed7d9bcd845996b4b/e746a184-c087-42ca-be1e-d54ea92bc931.png align="center")

**The one-liner:** ConcurrentHashMap uses CAS for empty buckets, per-node synchronized blocks for chains, volatile reads for lock-free gets, and cooperative resizing — making it the only correct choice for concurrent Map access on the JVM.