Recalculating Hash Indices After Resizing
You'll learn: How HashMap redistributes entries into new bucket positions when the internal array doubles in size during rehashing.
When a HashMap rehashes (doubles its capacity), it can't simply copy entries from the old array to the same positions in the new array. Why? Because the bucket index depends on the array length, and that length just changed.
Why Indices Change
Remember that HashMap calculates a bucket index using:
index = hash & (capacity - 1)
When capacity doubles from, say, 16 to 32, the bit mask changes. A hash that pointed to bucket 5 in the old array might now point to bucket 5 or bucket 21 in the new array, depending on its additional high-order bits.
The Redistribution Process
During rehashing, HashMap walks through every bucket in the old array:
- Examines each entry in the bucket (traversing linked lists or tree bins)
- Recalculates the index using the new capacity
- Places the entry in the appropriate bucket of the new array
- Rebuilds bucket structures (linked lists or trees) as needed
An Analogy
Think of a library reorganization. When you double the number of shelves, you don't just move entire shelves intact. Books that were grouped together on shelf 5 might now belong on shelf 5 and the new shelf 21, based on their classification numbers and the new total shelf count.
Why This Matters
This recalculation is why rehashing is expensive—every single entry must be examined and potentially moved to a different bucket, even though they stay within the same HashMap instance.
Key Takeaway: After doubling capacity, HashMap recalculates every entry's bucket index using the new array length, redistributing entries across the expanded array based on their hash codes.