Performance Impact of Rehashing
You'll learn why rehashing is expensive but rarely causes performance problems in practice.
The Cost of Rehashing
When a HashSet exceeds its threshold (capacity × load factor), rehashing must occur. This operation costs O(n) time because every single element in the set must be reprocessed:
- A new, larger backing array is allocated
- Every element's hash code is recalculated for its position in the new array
- Each element is inserted into the new array at its new bucket location
This is much more expensive than a normal add() operation, which is O(1).
Why It Happens Infrequently
The key insight: as capacity grows, rehashing becomes increasingly rare. Here's why:
- First rehash might happen at 16 elements (if default capacity is 16)
- Second rehash at 32 elements
- Third rehash at 64 elements
- Fourth rehash at 128 elements
Notice the pattern? The gaps between rehashes double each time. The more elements you add, the less frequently you pay the rehashing cost.
The Analogy
Think of moving to a bigger house. Moving is exhausting and time-consuming (O(n) — you must pack and unpack everything). But if you move from a 2-bedroom to a 4-bedroom, then eventually to an 8-bedroom mansion, you're moving less frequently even as you acquire more possessions. The disruption becomes negligible relative to your daily life.
Amortized Impact
While any single rehash costs O(n), the amortized cost per insertion remains O(1) because rehashing happens logarithmically with respect to the number of elements — not linearly.
Key Takeaway: Rehashing costs O(n) time because all elements must be repositioned, but exponential capacity growth ensures these expensive operations become increasingly rare, preserving O(1) average insertion performance.