Course contentsShow
← Java
Lesson 1128 of 2,87026. Map ImplementationsFree lesson

Recalculating Hash Indices After Resizing

Understand how entries are repositioned into new buckets based on the doubled capacity during rehashing.

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:

  1. Examines each entry in the bucket (traversing linked lists or tree bins)
  2. Recalculates the index using the new capacity
  3. Places the entry in the appropriate bucket of the new array
  4. 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.