Deep Dive into Java's ConcurrentHashMap: Implementation, Put & Remove Mechanics

History of Implementation Evolution

JDK 1.7 employed a segmented lock technique where the hash table was divided into multiple segments, each protected by a Segment lock, allowing concurrent access across segments but requiring exclusive locking within a segment.

JDK 1.8 removed the segment‑based locks, adopting CAS combined with synchronized to control concurrency, and aligned its underlying storage with the modern HashMap implementation that uses an array, linked lists, and red‑black trees.

Important Member Fields

transient volatile Node<K,V>[] table;

Represents the entire hash table, analogous to HashMap 's internal array.

private transient volatile Node<K,V>[] nextTable;

Used during resizing to hold the new table; cleared after resizing completes. private transient volatile long baseCount; Stores the total number of nodes, similar to HashMap 's size field. private transient volatile int sizeCtl; Controls initialization and resizing. Its possible values include:

0 – default value

-1 – table is being initialized

>0 – acts as the threshold (capacity * load factor)

< -1 – multiple threads are resizing concurrently

put Method – Thread‑Safe Insertion

The public put simply delegates to putVal with onlyIfAbsent set to false:

public V put(K key, V value) {
    return putVal(key, value, false);
}

putVal

first validates arguments, computes the hash, and then enters a loop that ensures the table is initialized. If the target bucket is empty, a lock‑free CAS inserts a new node. If the bucket already contains nodes, the method synchronizes on the bucket head and handles three cases:

Insertion into a linked list

Conversion of a long list into a red‑black tree when the size exceeds TREEIFY_THRESHOLD Insertion into an existing tree via TreeBin.putTreeVal After a successful insertion, addCount updates the element count and may trigger a resize.

initTable – Table Initialization

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0) {
            Thread.yield(); // another thread is initializing
        } else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[]) new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2); // threshold = n * 0.75
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

The method ensures that only one thread performs the initialization; other threads spin or yield until the table is ready.

Resizing and Transfer

When the table needs to grow, transfer moves entries from the old table to a new, larger one. Multiple threads cooperate by claiming a range of buckets via transferIndex and processing them in reverse order.

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab;
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        int rs = resizeStamp(tab.length);
        while (nextTab == nextTable && table == tab &&
               (sc = sizeCtl) < 0) {
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

The core of transfer consists of three parts:

Initialize the new table and compute the minimum stride each thread must handle.

Loop to claim bucket ranges, using CAS on TRANSFERINDEX to ensure exclusive ownership of a segment.

For each bucket, either move linked‑list nodes, split them between the two new buckets, or copy/red‑black‑tree nodes, then install a ForwardingNode to mark the old bucket as transferred.

When all buckets are processed, the last thread swaps table with nextTable, clears the auxiliary fields, and updates sizeCtl to the new threshold.

remove Method – Thread‑Safe Deletion

The removal process mirrors put: locate the bucket, assist with resizing if a ForwardingNode is encountered, otherwise synchronize on the bucket head and unlink the target node from either a list or a tree.

Other Common Methods

size() – Returns the total number of key‑value pairs by summing baseCount and any CounterCell values.

get(Object key) – Performs a lock‑free lookup by computing the hash and traversing the appropriate bucket or tree.

clear() – Iterates over all buckets, acquiring each bucket’s lock, setting the bucket to null, and adjusting the count via addCount.

The article concludes that ConcurrentHashMap showcases a sophisticated design that balances lock‑free operations with minimal synchronization, enabling high throughput in multithreaded environments.