Course contentsShow
← Java
Lesson 1062 of 2,87025. Set ImplementationsFree lesson

Rehashing Elements: Recalculating Bucket Positions

Learn why every element must be rehashed and placed into new buckets after capacity changes.

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:

  1. A new, larger bucket array is created (typically double the old capacity)
  2. Each element in the old array is visited
  3. For each element, its hash code is used with the new capacity to determine its new bucket position
  4. The element is placed into the new bucket at that position
  5. 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.