HashMap Resize and Rehash Internals

Fast recall

Quick revision

Core answer

When the number of entries exceeds capacity × loadFactor (default 0.75), HashMap doubles its internal array, recalculates every key's bucket index using the new capacity, and redistributes all entries. In Java 8+, linked-list buckets that exceed 8 nodes are treeified into red-black trees for O(log n) worst-case lookup.

HashMap resize triggers when entry count exceeds capacity × loadFactor — with defaults, that's just 12 entries for a capacity-16 map, allocating a new double-sized array and rehashing everything synchronously on the inserting thread.

Rehash optimization (Java 8):

Since new capacity is exactly double, each entry either stays at its index or moves to oldIndex + oldCapacity
Only one bit of the stored hash decides — no hash recomputation, no equals() calls
Each bucket's chain splits into "low" and "high" sub-chains placed at the two possible destinations

Treeification during rehash:

If a destination chain exceeds 8 entries, it treeifies into a Red-Black tree
Only happens when total capacity ≥ 64 (MIN_TREEIFY_CAPACITY) — below that, Java resizes instead

Prevention:

Pre-size with new HashMap<>(expectedSize / 0.75 + 1) in any hot path
Eliminates resize entirely and avoids GC overhead from the discarded old array

I recommend treating resize-avoidance as standard practice for any HashMap that will grow beyond 10 entries in a performance-sensitive path.

Interview-ready guide

Interview answer

Rehash optimization (Java 8):

Since new capacity is exactly double, each entry either stays at its index or moves to oldIndex + oldCapacity
Only one bit of the stored hash decides — no hash recomputation, no equals() calls
Each bucket's chain splits into "low" and "high" sub-chains placed at the two possible destinations

Treeification during rehash:

If a destination chain exceeds 8 entries, it treeifies into a Red-Black tree
Only happens when total capacity ≥ 64 (MIN_TREEIFY_CAPACITY) — below that, Java resizes instead

Prevention:

Pre-size with new HashMap<>(expectedSize / 0.75 + 1) in any hot path
Eliminates resize entirely and avoids GC overhead from the discarded old array

I recommend treating resize-avoidance as standard practice for any HashMap that will grow beyond 10 entries in a performance-sensitive path.

03 · Deep dive