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.