Load Factor & Rehashing
Watch what happens when a HashMap gets too full and needs to resize.
The load factor measures how full the hash table is:
- Java's default: 0.75 (75% full triggers resize)
- Higher load factor: More space efficient, more collisions
- Lower load factor: Fewer collisions, wastes space
Rehashing is triggered when:
Example: With capacity=8 and loadFactor=0.75:
When size > 6, rehashing occurs
Click "Add Entry" to start adding items
| Index | Entries |
|---|---|
| 0 | (empty) |
| 1 | (empty) |
| 2 | (empty) |
| 3 | (empty) |
| 4 | (empty) |
| 5 | (empty) |
| 6 | (empty) |
| 7 | (empty) |
- 1
Create New Array
A new bucket array is created with double the capacity.
- 2
Recalculate All Indices
For each entry, compute new index:
hashCode % newCapacity. Indices will change because capacity changed! - 3
Move All Entries
Each entry is inserted into its new bucket in the larger array.
- 4
Update Threshold
New threshold = newCapacity × loadFactor. The map can now hold more entries.
The bucket index depends on the capacity through the modulo operation. When capacity changes, the index changes too:
Old Capacity = 8
New Capacity = 16
Notice how all indices changed! This is why we must recalculate positions for every entry.
Cost of Rehashing
- • O(n) time to move all entries
- • Temporarily doubles memory usage
- • Can cause latency spikes
Why It's Worth It
- • Maintains O(1) average operations
- • Reduces collision chains
- • Amortized cost is still O(1) per insert
Tip: If you know the approximate size ahead of time, initialize the HashMap with that capacity to avoid rehashing:
Map<String, Integer> map = new HashMap<>(1000);