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

The Rehashing Process: Creating a Larger Array

Walk through how HashSet doubles its capacity and creates a new bucket array during rehashing.

The Rehashing Process: Creating a Larger Array

You'll learn how HashSet doubles its internal capacity and builds a fresh bucket array when the load factor threshold is crossed.

What Happens During Rehashing

When your HashSet reaches its threshold (size exceeds capacity × load factor), Java doesn't just resize the bucket array—it performs a complete rehashing. Here's the process:

Step 1: Double the Capacity

HashSet creates a brand new bucket array with double the capacity of the old one. If you had 16 buckets before, you now have 32. This isn't a simple array copy—it's a fresh start.

Step 2: Why a New Array Is Necessary

Remember that each element's bucket position depends on its hash code modulo the array size. When the array size changes, the same hash code produces a different bucket index:

Old: hashCode % 16 = bucket 7
New: hashCode % 32 = bucket 23  // Different location!

Step 3: Rehash Every Element

HashSet must iterate through every single element in the old array, recalculate its bucket position using the new capacity, and insert it into the new array. This is why rehashing is expensive—it's an O(n) operation touching all n elements.

The Doubling Strategy

Java specifically doubles capacity (not just adds a constant) to ensure rehashing happens infrequently. With geometric growth, rehashing occurs only logarithmically often as you add elements, keeping the amortized cost manageable.

Key Takeaway: During rehashing, HashSet allocates a new bucket array with double the capacity and repositions every existing element by recalculating bucket indices—an expensive but necessary operation to maintain performance as the set grows.