The Rehashing Process: Doubling Capacity
What you'll learn: How HashMap grows its internal bucket array and redistributes all existing entries during rehashing.
How HashMap Doubles Its Capacity
When rehashing is triggered (because the size exceeds the threshold), HashMap doesn't just make the bucket array slightly larger—it doubles the capacity. If you had 16 buckets, you'll now have 32. If you had 32, you'll now have 64. This doubling strategy is fundamental to HashMap's performance.
Why Doubling?
Doubling capacity is a common growth strategy because:
- It ensures amortized O(1) insertion over many operations
- It maintains the power-of-2 sizing that HashMap relies on for efficient hash-to-index calculations
- It balances the cost of resizing (which happens less frequently) against memory usage
The Complete Redistribution Process
Here's what happens during rehashing:
- Create a new array with double the capacity (old capacity × 2)
- Iterate through every bucket in the old array
- For each entry, recalculate its bucket index using the new capacity
- Reinsert the entry into the appropriate bucket in the new array
- Replace the old array with the new one
Why Recalculate Positions?
Since the index calculation depends on the array size (hash & (capacity - 1)), changing capacity means entries must be redistributed. A key that was in bucket 5 of a 16-bucket array might now belong in bucket 21 of a 32-bucket array.
This redistribution spreads out collisions—entries that shared a bucket before may now land in separate buckets, improving performance.
Key Takeaway: HashMap doubles its bucket array capacity during rehashing and redistributes all entries by recalculating their bucket positions based on the new capacity, maintaining efficient O(1) average-case performance as the map grows.