Understanding the Implementation of ConcurrentHashMap in JDK 7 and JDK 8

We know that HashMap cannot guarantee thread safety; inserting into a HashMap under concurrency may cause a loop in the hash bucket during resizing. To achieve thread safety, ConcurrentHashMap (CHM) is used, and its lock mechanism differs significantly between JDK 7 and JDK 8.

CHM in JDK 7

JDK 7 implements CHM with two data structures: Segment and HashEntry. The entire map is divided into 16 segments; each segment contains an array of HashEntry objects that form singly‑linked lists (the hash buckets). Each HashEntry stores a key, value, and hash code.

Each Segment extends ReentrantLock, so the design is often called “lock‑segmentation”. When different threads write to different segments, they acquire different locks, reducing contention.

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    HashEntry<K,V> node = tryLock() ? null :
        scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                K k;
                if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            } else {
                if (node != null)
                    node.setNext(first);
                else
                    node = new HashEntry<>(hash, key, value, first);
                int c = count + 1;
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                else
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        unlock();
    }
    return oldValue;
}

The insertion process first tries to acquire the segment lock via ReentrantLock.tryLock(). If the lock is unavailable, it falls back to scanAndLockForPut():

private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
    HashEntry<K,V> first = entryForHash(this, hash);
    HashEntry<K,V> e = first;
    HashEntry<K,V> node = null;
    int retries = -1; // negative while locating node
    while (!tryLock()) {
        HashEntry<K,V> f; // to recheck first below
        if (retries < 0) {
            if (e == null) {
                if (node == null)
                    node = new HashEntry<>(hash, key, value, null);
                retries = 0;
            } else if (key.equals(e.key))
                retries = 0;
            else
                e = e.next;
        } else if (++retries > MAX_SCAN_RETRIES) {
            lock();
            break;
        } else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) {
            e = first = f; // re‑traverse if entry changed
            retries = -1;
        }
    }
    return node;
}

This method spins on tryLock() up to MAX_SCAN_RETRIES (64 on many‑core machines). If the limit is reached, it acquires the lock in a blocking fashion. It also re‑checks whether the bucket’s head has changed during the spin.

CHM in JDK 8

JDK 8 discards the segment structure and uses the same bucket array as HashMap (a Node[]) with linked lists or red‑black trees. The core insertion method is putVal():

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                new Node<>(hash, key, value, null)))
                break; // no lock when adding to empty bin
        } else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<>(hash, key, value, null);
                                break;
                            }
                        }
                    } else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

The method first computes the key’s hash, initializes the table if necessary, and then attempts a lock‑free insertion using CAS. If the bucket is already occupied, it synchronizes on the bucket head and either appends to the linked list or delegates to the tree bin logic.

Compute the key’s hash code.

If the bucket array is null, call initTable() to create it.

Obtain the bucket index with tabAt() and fetch the head node f.

If f is null, insert the new node with a CAS operation; retry on failure.

If f.hash equals MOVED, help with table resizing via helpTransfer().

Otherwise, acquire a synchronized lock on f and insert the new element into the bucket’s list or tree.

After insertion, check whether the list should be transformed into a red‑black tree.

The evolution from JDK 7 to JDK 8 brings three main benefits:

Lock granularity is refined from segment level to bucket level, eliminating locking when there is no hash collision.

Insertion of a bucket’s head uses lock‑free CAS, which is highly efficient.

Since Java 6, the JVM has heavily optimized synchronized, so it no longer implies a heavyweight lock; it starts as a no‑lock state and inflates only under high contention, reducing context‑switch overhead.