Java HashMap Internals (Part 2): Load Factor, Resizing & Red-Black Treeification

In Part 9, we built a basic MyHashMap with separate bucket chaining.

Now imagine your system grows from tracking 10 user sessions to 100,000 active sessions.

If your hash map keeps its original array of 16 buckets, 100,000 nodes pile up inside those 16 bucket chains. On average, every bucket slot contains a linked list of 6,250 nodes.

Instead of running in $O(1)$ constant time, every map.get() now scans through thousands of linked list nodes. Map lookups degrade to $O(N)$ linear time.

To maintain $O(1)$ lookup speed as data grows, a hash map must dynamically expand its bucket array and rehash existing nodes.

---

Why You Need This in Real Life

Understanding load factors and treeification prevents severe production bottlenecks and security exploits:

• Algorithmic Complexity Attacks: In 2011, security researchers discovered that attackers could craft HTTP POST requests with keys designed to produce identical hash codes, forcing web servers to degrade hash map lookups from $O(1)$ to $O(N)$ and causing Denial-of-Service.
• Pre-Sizing High-Volume Maps: If you know you are inserting 1,000,000 items into a HashMap, passing an initial capacity (new HashMap<>(1_500_000)) skips multiple expensive array expansion and rehashing passes.

---

Load Factor and Resizing Threshold

The load factor measures how full the hash table is allowed to get before expanding capacity.

$\text{Load Factor} = \frac{\text{size}}{\text{capacity}}$

Java’s HashMap uses a default load factor of 0.75.

$\text{Threshold} = \text{capacity} \times \text{loadFactor}$

For a default capacity of 16, when size reaches 12 ($16 \times 0.75$), the map doubles its bucket array to 32.

Capacity 16  ---> Threshold 12  (16 * 0.75)
Capacity 32  ---> Threshold 24  (32 * 0.75)
Capacity 64  ---> Threshold 48  (64 * 0.75)

---

The Rehashing Process

Doubling table capacity alters the index formula (hash & (capacity - 1)).

Because capacity - 1 changes from 15 (0000 1111) to 31 (0001 1111), every existing node in the hash map must be re-evaluated and reassigned.

OLD TABLE (Capacity 16, mask 15):
Node hash = 37 (binary 0010 0101)
Index = 37 & 15 = 5

NEW TABLE (Capacity 32, mask 31):
Node hash = 37 (binary 0010 0101)
Index = 37 & 31 = 5 + 16 = 21

A node either stays at its original index j or moves to j + oldCapacity.

---

Adding Resizing to MyHashMap

Here is our updated MyHashMap with dynamic array doubling:

public class MyHashMap<K, V> {
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private Node<K, V>[] table;
    private int size;
    private int threshold;
    private final float loadFactor;

    private static final int DEFAULT_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        this.table = (Node<K, V>[]) new Node[DEFAULT_CAPACITY];
        this.threshold = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR);
    }

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

    private V putVal(int hash, K key, V value) {
        int index = (table.length - 1) & hash;
        Node<K, V> head = table[index];

        if (head == null) {
            table[index] = new Node<>(hash, key, value, null);
        } else {
            Node<K, V> curr = head;
            while (curr != null) {
                if (curr.hash == hash && (curr.key == key || (key != null && key.equals(curr.key)))) {
                    V oldValue = curr.value;
                    curr.value = value;
                    return oldValue;
                }
                if (curr.next == null) break;
                curr = curr.next;
            }
            curr.next = new Node<>(hash, key, value, null);
        }

        if (++size > threshold) {
            resize();
        }
        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        Node<K, V>[] oldTable = table;
        int oldCap = oldTable.length;
        int newCap = oldCap << 1; // Double capacity

        Node<K, V>[] newTable = (Node<K, V>[]) new Node[newCap];

        for (int j = 0; j < oldCap; j++) {
            Node<K, V> e = oldTable[j];
            if (e != null) {
                oldTable[j] = null;
                if (e.next == null) {
                    newTable[e.hash & (newCap - 1)] = e;
                } else {
                    // Split bucket chain into low and high lists
                    Node<K, V> loHead = null, loTail = null;
                    Node<K, V> hiHead = null, hiTail = null;
                    Node<K, V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) { // Remains at index j
                            if (loTail == null) loHead = e;
                            else loTail.next = e;
                            loTail = e;
                        } else { // Moves to index j + oldCap
                            if (hiTail == null) hiHead = e;
                            else hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);

                    if (loTail != null) {
                        loTail.next = null;
                        newTable[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTable[j + oldCap] = hiHead;
                    }
                }
            }
        }
        table = newTable;
        threshold = (int) (newCap * loadFactor);
    }

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

---

JDK 8+ Treeification Mechanics

What happens if an attacker crafts malicious keys that all produce identical hash codes?

In JDK 7, every key landed in the same bucket chain, degrading map lookup to $O(N)$ linear time.

Starting in JDK 8, when a single bucket chain reaches 8 nodes and total table capacity is at least 64, Java converts that bucket linked list into a balanced Red-Black Tree.

CHAIN DEGRADATION (JDK 7):
bucket[4] ---> Node1 ---> Node2 ---> Node3 ... ---> Node8 ---> Node9 ($O(N)$ lookup)

TREEIFICATION (JDK 8+):
bucket[4] ---> TreeNode (Red-Black Tree root) ($O(\log N)$ lookup)

Lookups in a treeified bucket drop from $O(N)$ down to $O(\log N)$ worst-case time complexity, neutralizing hash collision attacks.

---

Quick Summary

• Load factor ($0.75$) balances space efficiency against bucket collision rates.
• Resizing doubles table capacity and splits bucket chains into low (j) and high (j + oldCap) positions.
• Java 8+ converts long bucket chains (8+ nodes) into Red-Black trees to protect against $O(N)$ worst-case degradation.

References & Further Reading

1. OpenJDK Repository. OpenJDK 21 Source Code: java.util.IdentityHashMap & java.util.EnumMap. GitHub.
2. Bloch, J. (2018). Effective Java (3rd Edition) — Item 37: Use EnumMap Instead of Ordinal Indexing. Addison-Wesley.
3. Oracle Corporation. Java SE 21 API Documentation: java.util.IdentityHashMap. Oracle Docs.

---