How Does ConcurrentHashMap Turn Buckets into Red‑Black Trees?

Red‑Black Tree fundamentals

A red‑black tree is a self‑balancing binary search tree that guarantees O(log n) lookup, insertion and deletion. Each node stores a color (red or black) and must satisfy five invariants:

Every node is either red or black.

The root is black.

All leaves (the NIL sentinel nodes) are black.

If a node is red, both of its children are black.

Every path from a node to its descendant leaves contains the same number of black nodes.

Rotations

Rotations restructure the tree while preserving the binary‑search order. They are the primitive operations used during insertions and deletions.

Left rotation : the right child of a node becomes its parent, and the original node becomes the left child of that new parent.

Right rotation : the left child of a node becomes its parent, and the original node becomes the right child of that new parent.

Insertion handling

New keys are inserted as red nodes. If the parent is black the tree remains valid. A red‑red conflict (new node and its parent are red) is resolved based on the uncle's color:

Uncle is red : recolor the parent and uncle to black, recolor the grand‑parent to red, and continue fixing up the tree.

Uncle is black : perform rotations and recoloring. The situation splits into:

Outer insertion (parent and new node on the same side) – a single rotation (left or right) followed by a color swap.

Inner insertion (parent and new node on opposite sides) – a double rotation (first opposite‑side, then same‑side) followed by recoloring.

The helper method tieBreakOrder(Object a, Object b) provides a deterministic ordering when keys are not mutually comparable:

static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null) return 0;
    if ((d = a.getClass().getName().compareTo(b.getClass().getName())) == 0) {
        d = (System.identityHashCode(a) <= System.identityHashCode(b)) ? -1 : 1;
    }
    return d;
}

ConcurrentHashMap treeifyBin process

When a bucket’s linked‑list length reaches TREEIFY_THRESHOLD (default 8) and the table size is at least MIN_TREEIFY_CAPACITY (64), ConcurrentHashMap converts the list into a red‑black tree to keep lookup cost near O(log n).

if (binCount >= TREEIFY_THRESHOLD) {
    treeifyBin(tab, i);
}

treeifyBin

iterates over the existing Node chain, creates a TreeNode for each element, links them into a doubly‑linked list, and finally replaces the bucket with a TreeBin that holds the tree root.

private final void treeifyBin(Node<K,V>[] tab, int index) {
    Node<K,V> b; int n, sc;
    if (tab != null) {
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
            tryPresize(n << 1);
        } else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
            synchronized (b) {
                if (tabAt(tab, index) == b) {
                    TreeNode<K,V> hd = null, tl = null;
                    for (Node<K,V> e = b; e != null; e = e.next) {
                        TreeNode<K,V> p = new TreeNode<>(e.hash, e.key, e.val, null, null);
                        if ((p.prev = tl) == null)
                            hd = p;
                        else
                            tl.next = p;
                        tl = p;
                    }
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
                }
            }
        }
    }
}

The TreeNode class extends Node and adds the fields required for a red‑black tree:

static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent; // red‑black links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;   // needed to unlink on deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next, TreeNode<K,V> parent) {
        super(hash, key, val, next);
        this.parent = parent;
    }
    // other balancing methods omitted for brevity
}

Step‑by‑step example

The following sequence demonstrates how a bucket containing the keys {12, 1, 9, 2, 0, 11, 7, 19} is transformed into a red‑black tree. After each insertion the appropriate case (recolor or rotation) is applied.

12 becomes the black root.

1 is inserted as red; its parent (12) is black, so no adjustment is needed.

9 is inserted as the right child of 1, creating a red‑red conflict with a black uncle. The algorithm performs a left rotation on 1 and then recolors, making 9 the parent of 1.

2 is inserted as the right child of 1. Its uncle (9) is red, so a simple recolor of 1, 9 and the grand‑parent (12) restores the properties.

0 is inserted as the left child of 1; the parent is black, so no further action is required.

11 is inserted as the left child of 12; the parent is black, so the tree remains valid.

7 is inserted as the right child of 2, causing a red‑red conflict with a red uncle (0). Recoloring of 2, 0 and their grand‑parent (1) resolves the conflict.

19 is inserted as the right child of 12; the parent is black, so no adjustment is needed.

After processing all keys the final tree satisfies all five red‑black properties: