When Does Rehashing Occur in HashMap

In HashMap, resize() is triggered in four distinct scenarios: 4. Batch Population (putAll): When adding a collection whose size exceeds the current capacity threshold, a single...

🟢 Junior Level

Short Interview Answer (30 seconds)

Rehashing (or resizing) in a HashMap is the process of allocating a new bucket array of doubled capacity ($2 \times$) and redistributing existing entries into new bucket slots.

In HashMap, resize() is triggered in four distinct scenarios:

First put() Invocation (Lazy Allocation): When new HashMap() is created, the bucket array is not allocated (table == null). The backing array (default 16 slots) is allocated upon inserting the very first entry.
Threshold Exceeded During Insertion: When total map size exceeds the operational threshold: $\text{threshold} = \text{capacity} \times \text{loadFactor}$ (by default, $16 \times 0.75 = 12$).
Collision Density in Small Tables: When a single bucket accumulates 8 elements, but total capacity is still less than 64 (table.length < 64), HashMap resizes instead of converting the bucket to a Red-Black tree.
Batch Population (putAll): When adding a collection whose size exceeds the current capacity threshold, a single pre-calculated resize allocates sufficient capacity upfront.

Code Demonstration in Java 21

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

public class RehashingTriggerDemo {
    public static void main(String[] args) {
        // 1. Instantiation: table is null (0 bytes allocated for buckets)
        Map<Integer, String> map = new HashMap<>();

        // 2. First put: resize() allocates table with capacity = 16, threshold = 12
        map.put(1, "A");

        // 3. Populate up to threshold:
        for (int i = 2; i <= 12; i++) {
            map.put(i, "V" + i); // No resize occurs
        }

        // 4. Inserting the 13th element: (++size > threshold) is true (13 > 12)
        // resize() triggers: capacity doubles to 32, threshold becomes 24
        map.put(13, "V13");
    }
}

Real-World Analogy: Rehashing is like relocating an office to a building twice the size of the previous one. The move happens either on day one (opening the initial office) or whenever office occupancy exceeds 75%, preventing crowding and corridor bottlenecks before they impact daily operations.

🟡 Middle Level

The 4 Exact Triggers in OpenJDK `HashMap.java`

Trigger	Condition Evaluated in Source	Action Taken
1. Lazy Initialization	`tab == null \\|\\| tab.length == 0`	Allocates initial `Node<K,V>[]` array (default: 16)
2. Post-Insert Threshold Exceeded	`if (++size > threshold)`	Doubles capacity ($N \to 2N$), doubles threshold
3. Small-Table Treeification Fallback	`tab.length < MIN_TREEIFY_CAPACITY (64)`	If 8 items collide in a bucket, doubles table instead of treeifying
4. Batch Insertion `putAll()`	`targetCap > threshold` in `putMapEntries()`	Calculates required power-of-two size and resizes upfront

Latency Impact and Elimination in Hot Paths

Resizing is the most computationally expensive operation in the lifecycle of a HashMap:

Memory Allocation: Allocates a new array of double the previous size ($O(N)$).
Node Relocation: Iterates through every bucket chain in the old table and re-links nodes into the new array ($O(N)$).
P99 Latency Spikes: In high-throughput, low-latency microservices, an unexpected runtime resize on a map holding 1,000,000 entries can stall the active thread for 20–100 ms.

Sizing Upfront to Prevent Resizing:

// Prior to Java 19:
int expectedElements = 10_000;
int initialCapacity = (int) Math.ceil(expectedElements / 0.75f);
Map<String, User> map = new HashMap<>(initialCapacity);

// Java 19+:
Map<String, User> modernMap = HashMap.newHashMap(expectedElements);

🔴 Senior Level

Deep Source-Level Analysis of Resize Triggers

1. Post-Increment Trigger in `putVal`

In Java 8+, the threshold check executes after the new node has already been linked into its bucket:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // ... bucket lookup and node insertion ...
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Contrast with Java 7: In Java 7, resizing was evaluated before insertion and required two distinct conditions: if ((size >= threshold) && (null != table[bucketIndex])). If the target bucket was currently empty, Java 7 allowed the element to be inserted without resizing, even if size >= threshold.

2. Treeification Fallback in `treeifyBin`

When a collision list reaches TREEIFY_THRESHOLD = 8, HashMap executes treeifyBin:

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // MIN_TREEIFY_CAPACITY = 64
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // Convert linked list to Red-Black Tree (TreeNode)
    }
}

HotSpot Architectural Rationale: Converting a linked list into a Red-Black tree increases memory overhead (each TreeNode consumes 56 bytes versus 32 bytes for a standard Node). When total table capacity is small ($< 64$), clustering is almost always the result of a narrow bitmask rather than a pathological hash function. Doubling the table shifts the bitmask, which statistically splits the 8-node chain into two shorter chains with minimal memory penalty.

3. Preventive Trigger in `putMapEntries` (`putAll`)

When populating via new HashMap<>(Map m) or putAll(m):

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // Uninitialized table
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        } else {
            // Table already initialized
            while (s > threshold && table.length < MAXIMUM_CAPACITY)
                resize();
        }
    }
    // Loop inserting entries via putVal...
}

HashMap calculates the exact power-of-two capacity required to ingest the batch, completely eliminating repeated incremental resizing loops.

Why Geometric Doubling ($2 \times$)?

If the array expanded by a fixed increment (an arithmetic progression such as $+16$), inserting $N$ elements would require $\frac{N}{16}$ separate resize operations, resulting in quadratic insertion complexity: $O(N^2)$.

Geometric doubling ($2 \times$) guarantees amortized $O(1)$ insertion time: the total cost of copying $N$ elements across all resizing steps forms a convergent geometric series: $1 + 2 + 4 + 8 + \dots + N \le 2N$ The amortized cost per single inserted element remains strictly constant.

🎯 Interview Cheat Sheet

1. 30-Second Elevator Pitch

Rehashing in HashMap occurs in four scenarios: (1) lazy array allocation on first put(), (2) when ++size > threshold, (3) when a bucket reaches 8 elements while capacity is below 64, and (4) pre-emptively during batch putAll() calls. Resizing doubles the table array ($2 \times$) to preserve amortized $O(1)$ insertion performance. HashMap never downsizes when items are removed.

2. 4 Tricky Interview Questions with Deep Answers

Question 1: When exceeding the threshold, does `resize()` execute before or after inserting the new element?

Answer: In Java 8+, resize() executes after the element is physically added to the bucket (if (++size > threshold) resize();). In Java 7, resize() was evaluated before insertion, and only if the destination bucket already contained an element (size >= threshold && null != table[bucketIndex]).

Question 2: How many times will `resize()` fire if 10,000 elements are added to an empty `new HashMap<>()` using `putAll()`?

Answer: Exactly 1 time. When putAll() is invoked on an uninitialized map, putMapEntries calculates: $t = \text{tableSizeFor}\left(\left\lceil \frac{10000}{0.75} \right\rceil + 1\right) = \text{tableSizeFor}(13334 + 1) = 16384$ The threshold field is immediately set to 16,384. On inserting the first element, resize() is invoked once, allocating an array of size 16,384. All 10,000 elements are inserted into that single array with zero subsequent resizes.

Question 3: Can a bucket accumulate 12 elements while remaining a linked list without treeifying?

Answer: Yes, it can. If the table capacity is less than 64. For instance, if an initial capacity of 16 is used and all inserted keys share the exact same hash code:

At 8 elements: tab.length < 64 evaluates to true $\to$ resizes to 32.
At 9, 10, 11, 12 elements: capacity is 32 or 64. As long as capacity is below 64, treeifyBin invokes resize() instead of building a tree. Only after the table reaches capacity 64 will that bucket convert into a TreeNode Red-Black tree.

Question 4: If 999,999 elements are removed from a 1,000,000-element `HashMap`, does the table shrink?

Answer: No, never. HashMap does not implement automatic downsizing or array compaction. The internal table array remains sized at $1,048,576$ slots, consuming 4–8 MB of heap space for empty reference pointers. To reclaim this memory, instantiate a new HashMap(map) and allow the old instance to be garbage collected.

3. Common Pitfalls & Red Flags

❌ “HashMap resizes every time a collision occurs.”
Correction: Collisions create linked lists or trees within the bucket; resizing only occurs if total size > threshold or if bucket depth reaches 8 while capacity $< 64$.
❌ “Resize recalculates the hashCode() of every key in the map.”
Correction: Java 8+ uses the cached e.hash field and evaluates a single bit (e.hash & oldCap) == 0 without re-invoking key.hashCode().
❌ “HashMap automatically frees memory and shrinks when entries are removed.”
Correction: HashMap never downsizes its backing array upon remove().
❌ “Default HashMap constructor allocates 16 bucket array slots immediately.”
Correction: Allocation is lazy; the array is null until the first put().

What is Load Factor in HashMap — Threshold calculations
What is Capacity in HashMap — Array sizing and power of two
What Happens During Rehashing — Migration mechanics and single-bit partitioning
What Happens When 8 Elements Are Reached in One Bucket — Treeify conditions
How to Choose the Initial Capacity for HashMap — Pre-sizing formulas