Understanding Java 8 HashMap and ConcurrentHashMap Internals

Today we will study ConcurrentHashMap , a data structure that is so important it must be mastered for technical interviews.

1. Preface

Continuing from the previous article, we now look at the first part of Java 8's HashMap and ConcurrentHashMap.

2. Java 8 HashMap

Java 8 modifies HashMap by adding a red‑black tree, so the internal representation becomes an array + linked list + red‑black tree. In Java 7, after locating the bucket by hash, a linear search through the linked list yields O(n) time. In Java 8, when a bucket’s list exceeds eight elements, it is transformed into a red‑black tree, reducing the lookup cost to O(log N).

Below is a simple diagram (illustrative only, actual structures will expand before reaching this state):

Key implementation differences:

Java 7 uses Entry objects; Java 8 uses Node for linked‑list entries and TreeNode for tree entries.

The type of the first node in a bucket determines whether the bucket is a list or a tree.

Put operation analysis

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // ... (full source code omitted for brevity) ...
}

The main differences from Java 7 are that Java 8 performs the insertion before triggering a resize, whereas Java 7 expands the table first.

Array resizing

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // ... (full source code omitted) ...
    return newTab;
}

Get operation analysis

The get method is straightforward:

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

It first computes the hash, locates the bucket, checks the first node, then either uses the tree lookup or traverses the linked list until a matching key is found.

3. Java 8 ConcurrentHashMap

Java 7’s ConcurrentHashMap is already complex; Java 8 introduces significant changes, including the use of red‑black trees similar to HashMap but with additional concurrency control.

Structure diagram (illustrative):

Initialization

public ConcurrentHashMap() {}

public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();
    int cap = (initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
        MAXIMUM_CAPACITY :
        tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1);
    this.sizeCtl = cap;
}

The constructor computes sizeCtl as roughly 1.5 × initialCapacity rounded up to the nearest power of two.

Put operation analysis (ConcurrentHashMap)

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

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // ... (full source code omitted for brevity) ...
}

The algorithm handles three cases:

If the bucket is empty, a CAS operation inserts the new node without locking.

If the bucket is being moved (hash == MOVED), the thread helps with data migration.

If the bucket contains a list or tree, the thread acquires the bucket’s monitor, performs insertion, and may trigger treeification or resizing.

Treeification occurs when the list length reaches TREEIFY_THRESHOLD (8). If the table size is less than 64, the implementation prefers resizing over tree conversion.

After insertion, addCount updates the size and may trigger another resize.

Overall, the article walks through the critical sections of Java 8’s HashMap and ConcurrentHashMap, explaining how red‑black trees, resizing, and concurrency mechanisms are integrated to achieve high performance and thread safety.