Rehashing Elements: Recalculating Bucket Positions
What you'll learn: Why every element must find its new home when a HashSet grows.
When a HashSet triggers rehashing (crosses the threshold), it doesn't just copy elements from the old bucket array to a new, larger one. Instead, every single element must be rehashed — its bucket position recalculated from scratch.
Why Elements Can't Keep Their Old Positions
Remember that bucket positions are determined by a calculation involving the hash code and the array capacity. A typical formula looks like:
bucket_index = hash_code % array_capacity
When capacity changes (say, from 16 to 32 buckets), this calculation produces different results for the same hash code. An element that lived in bucket 5 in the old array might now belong in bucket 21 in the new array.
The Recalculation Process
During rehashing:
- A new, larger bucket array is created (typically double the old capacity)
- Each element in the old array is visited
- For each element, its hash code is used with the new capacity to determine its new bucket position
- The element is placed into the new bucket at that position
- The old array is discarded
The Analogy: Moving to a Bigger Parking Lot
Imagine a parking lot with 16 spaces that assigns spots by license plate number. When you expand to 32 spaces, you can't just move car #5 to spot #5 in the new lot — you must recalculate: "license plate modulo 32" gives you a completely different spot number.
Key Takeaway: Rehashing requires recalculating every element's bucket position because the bucket index formula depends on array capacity, which has changed.