Unveiling Java’s HashMap: From Initialization to Red‑Black Tree Mechanics

Initialization

When a HashMap instance is created, the internal table is not allocated; allocation occurs on the first put call. The constructor validates initial capacity and load factor, then computes the threshold with tableSizeFor.

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

put Method

The public put delegates to putVal, which handles table resizing, hash calculation, node insertion, and collision resolution. The algorithm distinguishes between empty slots, existing nodes, tree nodes, and linked‑list buckets, applying resize(), treeifyBin(), or direct insertion as needed.

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) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // linked‑list handling omitted for brevity
        }
        // further logic for updating value, resizing, etc.
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Core Helper Methods

newNode

– creates a plain Node instance. putTreeVal – inserts a key/value pair into a red‑black tree bucket. treeifyBin – converts a linked‑list bucket into a red‑black tree when the size exceeds TREEIFY_THRESHOLD and the table is large enough. resize – expands the table and rehashes entries.

Node Creation and Hash Calculation

The newNode method simply wraps the supplied fields in a Node. The static hash(Object key) method mixes the high and low 16 bits of the key’s hashCode() to improve low‑order randomness.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Red‑Black Tree Operations

When a bucket becomes a tree, several methods maintain balance: balanceInsertion – restores red‑black properties after insertion. balanceDeletion – restores properties after removal. rotateLeft and rotateRight – perform the necessary rotations. moveRootToFront – ensures the tree root is the first node in the bucket array.

static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
    TreeNode<K,V> r = p.right, pp, rl;
    if ((rl = p.right = r.left) != null)
        rl.parent = p;
    if ((pp = r.parent = p.parent) == null)
        (root = r).red = false;
    else if (pp.left == p)
        pp.left = r;
    else
        pp.right = r;
    r.left = p;
    p.parent = r;
    return root;
}

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
    TreeNode<K,V> l = p.left, pp, lr;
    if ((lr = p.left = l.right) != null)
        lr.parent = p;
    if ((pp = l.parent = p.parent) == null)
        (root = l).red = false;
    else if (pp.right == p)
        pp.right = l;
    else
        pp.left = l;
    l.right = p;
    p.parent = l;
    return root;
}

Removal Process

The public remove method calls removeNode, which locates the target entry, distinguishes between plain nodes and tree nodes, and then either unlinks the node or invokes removeTreeNode for tree‑based buckets. After deletion, the map updates size, modCount, and may rebalance the tree.

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

Thread‑Safety and Usage Tips

HashMap is not thread‑safe; for concurrent scenarios use ConcurrentHashMap. The map permits null keys and values, unlike Hashtable or ConcurrentHashMap. When iterating, prefer entrySet() or forEach over keySet() for better performance.

Summary

The article walks through HashMap’s lazy initialization, the put workflow, key helper methods, hash mixing, bucket conversion to red‑black trees, tree‑balancing algorithms, removal mechanics, and practical considerations such as thread safety and null handling.