Java ConcurrentHashMap

Why not Hashtable or synchronizedMap?

The old options serialise everything. Hashtable and Collections.synchronizedMap guard every method with one monitor, so a read waits behind an unrelated write and throughput stops scaling after a couple of cores. Java 5's ConcurrentHashMap split the table into a fixed number of segments, each with its own lock, so up to that many writers could proceed at once. Java 8 rewrote it: there are no segments any more, writes lock individual bins, reads are lock-free, and long collision chains become balanced trees. The concurrencyLevel constructor argument survives only as a sizing hint for compatibility.

Why not Hashtable or synchronizedMap?

The old options serialise everything. Hashtable and Collections.synchronizedMap guard every method with one monitor, so a read waits behind an unrelated write and throughput stops scaling after a couple of cores. Java 5's ConcurrentHashMap split the table into a fixed number of segments, each with its own lock, so up to that many writers could proceed at once. Java 8 rewrote it: there are no segments any more, writes lock individual bins, reads are lock-free, and long collision chains become balanced trees. The concurrencyLevel constructor argument survives only as a sizing hint for compatibility.

The table, the hash spread and bin types

The map is an array of bins whose length is always a power of two. A key's bin is chosen from its hashCode() after a spreading step that folds the high bits into the low bits, because the index is taken by masking the low bits and many real hash codes differ only in their high bits. The spread also clears the sign bit, which leaves negative hash values free to mark special nodes.

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;     // HASH_BITS = 0x7fffffff
}
int index = (table.length - 1) & spread(key.hashCode());

Each bin is in one of a few states, shown in the diagram: empty (null), a linked list of Node objects, a TreeBin holding a red-black tree, a ForwardingNode that says this bin has already moved to a larger table, or a ReservationNode that holds the slot while a computeIfAbsent or compute runs on an empty bin. The negative hash values (-1, -2 and -3) let every operation recognise the special cases with one comparison.

Reads: lock-free and visible

A get computes the index, reads the bin head with a volatile-strength read, and walks the list or searches the tree. It takes no lock and never blocks. The val and next fields of a node are volatile, so a reader sees a fully initialised node and its latest value. If it meets a forwarding node in the middle of a resize, it simply continues the search in the new table. If it meets a tree bin that a writer is restructuring, it falls back to walking the nodes as a plain linked list rather than waiting.

The memory model guarantee is stated in the java.util.concurrent package documentation: placing an object into a concurrent collection happens-before a subsequent access to it from another thread. In practice this means you can build an object, put it in the map, and another thread that gets it will see every field you set before the put. It does not mean later mutations of that object are safe; the map publishes references, not a lock around their contents.

Writes: CAS, bin locks and trees

A write follows a short decision tree, simplified here from putVal:

for (Node<K,V>[] tab = table;;) {
    if (tab == null)                    tab = initTable();          // lazy, CAS on sizeCtl
    else if ((f = tabAt(tab, i)) == null) {
        if (casTabAt(tab, i, null, new Node<>(hash, key, value)))
            break;                      // empty bin: one CAS, no lock at all
    }
    else if (f.hash == MOVED)           tab = helpTransfer(tab, f);  // resizing: help, then retry
    else {
        synchronized (f) {              // lock only this bin's head node
            if (tabAt(tab, i) == f) {   // re-check: the head may have changed
                // walk list or tree: replace value or append node
            }
        }
        if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i);
        break;
    }
}
addCount(1L, binCount);                 // update size, maybe trigger resize

The common case on a well-sized map is an empty bin, which costs one compare-and-swap. Otherwise the writer locks the head node with synchronized, then re-checks that the node is still the head, because another thread may have replaced it between the read and the lock. Contention therefore exists only between threads that hash to the same bin at the same moment.

When a list bin reaches eight nodes (TREEIFY_THRESHOLD), it converts to a red-black tree, bounding lookups at O(log n) even under heavy collisions, as long as the keys are Comparable or have well-spread hashes. If the table is still smaller than 64 bins, the map resizes instead, since a small table is the likelier cause of long chains. A tree shrinks back to a list at six nodes.

Cooperative resizing

The map grows when the element count crosses a threshold of three quarters of the table length (the load factor is fixed at 0.75 after construction). Resizing doubles the table and is cooperative: rather than one thread copying everything while others wait, the work is split into strides of bins, and any thread that arrives during a resize claims a stride and helps. A single control field, sizeCtl, encodes whether the table is being initialised, the next resize threshold, or how many threads are currently transferring.

Each old bin is moved under its head lock. Because the table doubles, every node either keeps its index or moves up by exactly the old length, so a bin splits cleanly into a low list and a high list. When a bin is done, a forwarding node is installed in the old slot. Readers follow it to the new table; writers that hit it join the transfer. The practical upshot is that resizes do not stop the world, but they are still real work. If you know the final size, pass it to the constructor so a large map does not resize repeatedly while you load it.

Counting without a hot counter

A single shared counter updated by every put and remove would become the bottleneck the bin locks were designed to avoid. Instead the map keeps a baseCount and, once CAS updates on it start failing, an array of CounterCell objects, the same striping idea as LongAdder. Each thread updates a cell chosen by a per-thread probe, so updates rarely collide. size() sums baseCount and all cells without locking.

That sum is exact only when nothing is changing; under concurrent writes it is a value the map passed through, or close to one. size() also returns an int and saturates at Integer.MAX_VALUE; mappingCount() returns a long and is the preferred call. Use either for metrics and capacity estimates, never for decisions such as "insert if size is below 1000": two threads can both see 999.

Atomic compound operations

Every individual method is thread-safe, but a sequence of calls is not atomic. The classic bug is check-then-act:

// RACE: two threads can both see "absent" and both put
if (!map.containsKey(key)) {
    map.put(key, expensiveLoad(key));
}

// Atomic alternatives
map.putIfAbsent(key, value);                       // insert only if absent
map.computeIfAbsent(key, k -> expensiveLoad(k));   // load at most once per key
map.merge(word, 1L, Long::sum);                    // atomic counter
map.compute(key, (k, v) -> v == null ? 1 : v + 1); // general read-modify-write
map.replace(key, expectedOld, newValue);           // compare-and-set on a value
map.remove(key, expectedValue);                    // remove only if unchanged

The compute family runs your function while holding the bin's lock, or the reservation node for an absent key. That gives atomicity and imposes three rules. Keep the function short, because every other writer to that bin, including writers of unrelated keys that share it, waits for it. Never modify the same map from inside the function: since Java 9 the map detects many such recursive updates and throws IllegalStateException ("Recursive update"), while Java 8 could spin forever. And never do blocking I/O inside it. On Java 8, computeIfAbsent also locked the bin even when the key was present; Java 9 added a lock-free fast path, so on old runtimes a get before computeIfAbsent helps hot keys.

The null ban exists for the same reason. In a concurrent map, get(k) == null must mean absent, because there is no lock to hold between get and containsKey to tell absent apart from a stored null. Returning null from a compute function removes the mapping. If you need to remember a negative result, store a sentinel object or an Optional.

Worked example: a coalescing price cache

A worked example: a service calls a slow pricing backend and wants each product price fetched once, even when fifty requests for the same product arrive at the same moment. Putting the loaded value directly into computeIfAbsent would hold the bin lock for the whole remote call. Storing a future instead makes the critical section tiny: the first caller installs a future, and everyone else gets the same future.

final class PriceCache {
    private final ConcurrentHashMap<String, CompletableFuture<Price>> cache = new ConcurrentHashMap<>(1 << 14);
    private final PricingClient client;
    private final Executor io;

    PriceCache(PricingClient client, Executor io) { this.client = client; this.io = io; }

    CompletableFuture<Price> get(String sku) {
        CompletableFuture<Price> f = cache.computeIfAbsent(sku,
            k -> CompletableFuture.supplyAsync(() -> client.fetch(k), io));   // fast: only creates the future
        // don't cache failures forever: remove exactly this future if it failed
        f.whenComplete((p, ex) -> { if (ex != null) cache.remove(sku, f); });
        return f;
    }
}

The function only creates and schedules a future, so the bin lock is held for microseconds. Concurrent callers coalesce onto one backend request. The two-argument remove(sku, f) evicts only the failed future, never a newer successful one another thread installed. What this cache lacks is a size bound and expiry; that is the point at which you should switch to a caching library such as Caffeine, which provides both on top of the same ideas.

Iteration and bulk operations

Iterators, keySet(), values() and entrySet() views are weakly consistent: they traverse the table as it is while they run, never throw ConcurrentModificationException, visit each element that existed when they were created exactly once, and may or may not reflect later changes. That makes it safe to scan a live map, for example to evict expired entries with removeIf, but it is not a snapshot. If you need a consistent picture, copy under an external lock or use an immutable map you swap atomically.

Java 8 added bulk operations, forEach, search and reduce with typed variants, which take a parallelismThreshold. Pass Long.MAX_VALUE to run sequentially or a smaller number to split the work across the common ForkJoinPool when the map has at least that many elements. ConcurrentHashMap.newKeySet() gives a concurrent Set backed by the same machinery.

Failure modes in production

To diagnose, take a thread dump with jcmd <pid> Thread.print and look for threads blocked inside ConcurrentHashMap.putVal or compute; a cluster of them on one address points at a hot bin or a slow function. Java Flight Recorder's monitor-blocked events show the same contention with stack traces.

When to use something else

What to do next

1. Search your codebase for containsKey followed by put on shared maps and replace each with an atomic method.
2. Review every compute and computeIfAbsent function for I/O, locks, or writes to the same map.
3. Make map keys immutable and check their hashCode spreads well.
4. Replace size()-based limits with a semaphore or atomic counter.
5. Size large maps at construction, and put any map used as a cache behind a bounded cache library.
6. Practise reading a thread dump for blocked putVal frames before you need to.
7. Read on: Java concurrency fundamentals, the Java Memory Model, atomic classes and CompletableFuture.