Data Structure

The internal structure mirrors HashMap, consisting of a hash table array with linked lists for collision handling. When a bucket accumulates more than eight entries, it transforms into a red-black tree for optimized search performance.

Implementation Approach

JDK 8 leverages synchronized and CAS operations for concurrent access control. Crucial distinction: This version does not employ segmented locking—that mechanism belonged to the JDK 7 implementation.

Core Operations

The putVal method serves as the primary insertion logic with these steps:

Hash Computation and Table Initialization

First, compute the hash value using spread() to distribute keys evenly. If the underlying array hasn't been initialized, allocate it before proceeding.

Empty Slot Detection

Calculate the bucket index via (n - 1) & hash, equivalent to hash % n. When a bucket contains no entries, atomical insert using casTabAt()—this prevents race conditions where two threads attempt the same insertion simultaneously.

Concurrent Expansion Handling

If the table is undergoing resizing (indicated by MOVED hash), delegate to helpTransfer() which enables calling threads to assist with the expansion. This cooperative approach minimizes pause times during high-contention scenarios.

Collision Resolution

Upon hash collision, synchronize on the bucket's first node—effectively locking the entire chain or tree structure:

• Linked List Traversal: Iterate through the chain, updating existing keys or appending new nodes at the tail
• Tree Operations: When the bucket has been converted to a TreeBin, delegate insertion to putTreeVal

After insertion, if the chain exceeds the TREEIFY_THRESHOLD (8 elements), invoke treeifyBin() to restructure as a red-black tree.

Size Tracking and Expansion

Invoke addCount() to increment the counter. The method accepts the increment value and current bin count, using LongAdder for efficient concurrent increments. Expansion triggers when the table reaches capacity, with participating threads drafted to help redistribute entries.

Implemantation Details

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int chainSize = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> current; int capacity, index, currentHash;
        if (tab == null || (capacity = tab.length) == 0)
            tab = initTable();
        else if ((current = tabAt(tab, index = (capacity - 1) & hash)) == null) {
            if (casTabAt(tab, index, null,
                         new Node<K,V>(hash, key, value, null)))
                break;
        }
        else if ((currentHash = current.hash) == MOVED)
            tab = helpTransfer(tab, current);
        else {
            V previousValue = null;
            synchronized (current) {
                if (tabAt(tab, index) == current) {
                    if (currentHash >= 0) {
                        chainSize = 1;
                        for (Node<K,V> entry = current;; ++chainSize) {
                            K existingKey;
                            if (entry.hash == hash &&
                                ((existingKey = entry.key) == key ||
                                 (existingKey != null && key.equals(existingKey)))) {
                                previousValue = entry.val;
                                if (!onlyIfAbsent)
                                    entry.val = value;
                                break;
                            }
                            Node<K,V> last = entry;
                            if ((entry = entry.next) == null) {
                                last.next = new Node<K,V>(hash, key, value, null);
                                break;
                            }
                        }
                    }
                    else if (current instanceof TreeBin) {
                        TreeBin<K,V> treeRef = (TreeBin<K,V>) current;
                        chainSize = 2;
                        TreeNode<K,V> result = treeRef.putTreeVal(hash, key, value);
                        if (result != null) {
                            previousValue = result.val;
                            if (!onlyIfAbsent)
                                result.val = value;
                        }
                    }
                }
            }
            if (chainSize != 0) {
                if (chainSize >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, index);
                if (previousValue != null)
                    return previousValue;
                break;
            }
        }
    }
    addCount(1L, chainSize);
    return null;
}

Key Design Principles

ConcurrentHashMap balances performance and safety through fine-grained synchronization. During put and remove operations, only individual bucket nodes become locked, leaving other buckets fully accessible to concurrent operations. During resize operations, the implementation recruits helper threads from active put operations, distributing the expansion workload and reducing latency spikes.