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

.

<code>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);
}</code>

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.

<code>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;
}</code>

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.

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

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.

<code>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;
}</code>

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.

<code>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;
}</code>

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.