🔑 Section 10 · Question #19

What Happens During Rehashing

4. Old Array Reclamation: The table reference is redirected to the new array, allowing the Garbage Collector (GC) to reclaim the old array.

🔑 HashMap equals hashCode 📄 Source Markdown

🟢 Junior Level

Short Interview Answer (30 seconds)

Rehashing (or table resizing) is an internal HashMap procedure where a new bucket array of double the previous capacity ($2N$) is allocated, and all existing entries are redistributed into their new bucket positions.

Step-by-Step Execution:

  1. Array Allocation: A new array Node<K,V>[] of double the size ($16 \to 32$, $32 \to 64$, etc.) is allocated on the heap.
  2. Node Relocation: Every existing node from the old table is migrated. Due to power-of-two arithmetic, an element either remains at its original index or moves to oldIndex + oldCap.
  3. Threshold Update: The next resize threshold is doubled: $\text{threshold} = \text{newCapacity} \times \text{loadFactor}$.
  4. Old Array Reclamation: The table reference is redirected to the new array, allowing the Garbage Collector (GC) to reclaim the old array.

Code Demonstration in Java 21

import java.util.HashMap;
import java.util.Map;

public class RehashingVisualDemo {
    public static void main(String[] args) {
        // Initial capacity = 16, threshold = 12
        Map<Integer, String> map = new HashMap<>();

        for (int i = 1; i <= 12; i++) {
            map.put(i, "Value" + i);
        }

        // Inserting the 13th element triggers resize():
        // 1. Allocates new array of 32 slots
        // 2. All 13 entries are migrated into the new slots
        // 3. New threshold becomes 24 (32 * 0.75)
        map.put(13, "TriggerResize");
    }
}

Real-World Analogy: Imagine a coatroom with 16 numbered sections. The room expands to 32 sections. Rather than reshuffling every coat randomly, the attendant follows a simple rule: keep the coat in its current section or move it forward by exactly 16 sections.

🟡 Middle Level

The Single-Bit Decision: (e.hash & oldCap)

The defining architectural improvement in Java 8+ resizing is that HashMap never recalculates hash codes and does not compute full bitmask indexing (newCap - 1) & hash for every node.

Because capacity is strictly a power of two ($2^k$), doubling the table exposes exactly one additional high bit in the index mask (corresponding to the binary weight of oldCap):

Old Capacity (16):  oldCap = 00010000_2
Old Mask (15):      n - 1  = 00001111_2
New Capacity (32):  newCap = 00100000_2
New Mask (31):      n - 1  = 00011111_2
                                ^
                      The single newly exposed bit!

An entry’s destination depends entirely on that single bit in its precomputed hash code:

if ((e.hash & oldCap) == 0) {
    // Newly exposed bit is 0 -> Index REMAINS UNCHANGED (oldIndex)
} else {
    // Newly exposed bit is 1 -> Index MOVES to (oldIndex + oldCap)
}

Partitioning Collision Chains: Lo- and Hi-Lists

When iterating through a collision list, HashMap partitions the chain into two independent linked lists in a single linear pass using Tail Insertion:

// OpenJDK HashMap.java resize() partition loop:
Node<K,V> loHead = null, loTail = null; // Sub-list for original index
Node<K,V> hiHead = null, hiTail = null; // Sub-list for (index + oldCap)
Node<K,V> next;

do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    } else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead; // Placed at original index
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead; // Placed at offset index
}
  • Tail Insertion Advantage: Appending to the tail preserves the relative sequence of nodes. In Java 7, Head Insertion was used, which reversed node order during migration. Under concurrent access, that reversal caused circular pointer references, trapping worker threads in 100% CPU infinite loops.

🔴 Senior Level

Red-Black Tree Splitting & Untreeification (TreeNode.split)

When a bucket containing a Red-Black tree is resized, the operation delegates to TreeNode.split(this, newTab, j, oldCap).

A TreeNode exhibits a dual nature: it maintains both Red-Black tree pointers (left, right, parent) and doubly linked list pointers (prev, next).

During tree splitting:

  1. split() traverses the next pointers of the doubly linked list, building loHead and hiHead chains while counting their nodes (lc and hc).
  2. Untreeification: If a partitioned sub-group contains $\le \text{UNTREEIFY_THRESHOLD}$ (6 nodes), the tree structure is dismantled and converted back into a standard Node linked list: 
    if (lc <= UNTREEIFY_THRESHOLD)
    tab[index] = loHead.untreeify(map);
else {
    tab[index] = loHead;
    if (hiHead != null)
        loHead.treeify(tab); // Full Red-Black Tree rebalancing
}
  3. If a partition retains 7 or more elements, treeify(tab) rebalances the nodes into an independent Red-Black tree with updated colors and rotations.

Heap Footprint & Garbage Collector Pressure

During resize():

  • Concurrent Array Memory: Both oldTab and newTab exist simultaneously in the heap.
    • At capacity 2 million: oldTab claims $\approx 8\text{ MB}$ of reference slots (with Compressed OOPs); newTab claims $\approx 16\text{ MB}$. Peak memory temporarily demands 24 MB for pointer arrays alone.
  • GC Write Barriers: Reassigning references across millions of array slots triggers Garbage Collector write barriers (in G1, ZGC, Shenandoah), registering updates in Card Tables and Remembered Sets.
  • Old Generation Burden: Once resize() finishes, the old array becomes garbage. If the map is long-lived, reclaiming that array requires an Old Generation concurrent marking or mixed GC cycle.

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

During rehashing, HashMap doubles its bucket array ($2N$) and redistributes entries. In Java 8+, hash codes are never recalculated; instead, a single bit check (e.hash & oldCap) == 0 partitions entries into Lo (original index) and Hi (index + oldCap) lists using tail-insertion. Treeified buckets split their nodes; if a sub-list drops to $\le 6$ nodes, it untreeifies back into a linked list. The 2-element gap between treeification (8) and untreeification (6) implements hysteresis to prevent thrashing.

2. 4 Tricky Interview Questions with Deep Answers

Question 1: Why is key.hashCode() never recomputed during rehashing in Java 8+?

Answer: Each Node<K,V> caches the 32-bit hash code computed upon initial insertion in an immutable field: final int hash;. During resize(), HashMap reads e.hash directly and performs the bitwise test (e.hash & oldCap) == 0. This eliminates all CPU overhead associated with re-hashing complex objects (such as long strings or composite records).

Question 2: Why is UNTREEIFY_THRESHOLD = 6 rather than 8?

Answer: The 2-unit gap between treeification (8) and untreeification (6) is an architectural hysteresis mechanism designed to prevent flapping (thrashing). If both thresholds were 8, alternating put() and remove() operations near the boundary would cause continuous, expensive conversions between linked lists and Red-Black trees. The buffer between 6 and 8 absorbs boundary fluctuations smoothly.

Question 3: What happens if Thread A invokes map.get("key") while Thread B is executing resize()?

Answer: HashMap is not thread-safe. Unsynchronized concurrent access leads to:

  1. Phantom null Lookups: resize() assigns the new array reference table = newTab early in the process. If Thread A queries table before Thread B has migrated that specific bucket, it reads a null array slot and falsely concludes the key does not exist.
  2. ConcurrentModificationException: Active iterators tracking modCount fail fast.
  3. Memory Visibility Lags: Without memory barriers or volatile fields, Thread A may read stale next pointers from CPU core caches.

Question 4: Can the table capacity exceed MAXIMUM_CAPACITY ($2^{30}$) during rehashing?

Answer: No. In resize(), HotSpot enforces:

if (oldCap >= MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return oldTab;
}

If capacity has already reached $2^{30}$, resizing is permanently halted. The threshold is set to Integer.MAX_VALUE ($2^{31} - 1$), and all subsequent insertions are placed into existing buckets, lengthening collision chains and trees without allocating new arrays.

3. Common Pitfalls & Red Flags

  • ❌ “Rehashing calls hashCode() on every key in the map.”
    Correction: It reuses the cached final int hash on each node; key.hashCode() is never called again.

  • ❌ “Rehashing redistributes elements randomly across the table.”
    Correction: It deterministically partitions each bucket into at most two specific destination slots: index or index + oldCap.

  • ❌ “Java 8 tail-insertion makes HashMap safe for multithreaded use.”
    Correction: It fixes the infinite circular reference loop bug of Java 7, but race conditions, silent data loss, and phantom nulls remain. ConcurrentHashMap must be used for concurrency.

  • ❌ “Trees are never converted back into linked lists once formed.”
    Correction: Resizing splits tree nodes; any partition with $\le 6$ nodes is converted back into a linked list via untreeify().