Dynamic Resizing and Rehashing Cost
What you'll learn: How to analyze the amortized cost of growing a hash table and rehashing all its elements.
Why Hash Tables Need to Resize
As you insert more elements into a hash table, the load factor increases. When it crosses a threshold (often 0.7-0.75), performance degrades due to more collisions. To maintain efficiency, the table must resize — typically doubling its capacity — and rehash every element into the new, larger table.
The Rehashing Process
When resizing:
- Allocate a new, larger array (commonly 2× the old size)
- For each element in the old table, recompute its hash with the new table size
- Insert each element into its new position using your collision resolution strategy
- Discard the old table
This sounds expensive — and it is for that single operation! If you have n elements, rehashing takes O(n) time.
Amortized Cost Analysis
Here's the key insight: resizing happens rarely. Think of it like moving to a bigger apartment — it's a lot of work once, but you don't move every day.
If you double the table size each time, you'll resize at sizes 1, 2, 4, 8, 16, 32... By the time you have n elements, you've done roughly log₂(n) resizes, and the total rehashing work across all operations is proportional to: 1 + 2 + 4 + 8 + ... + n ≈ 2n.
Spread this O(n) total cost over n insertions, and each insertion costs O(1) on average — we call this amortized O(1).
Key Takeaway: While a single resize/rehash operation costs O(n), it happens infrequently enough that the amortized cost per insertion remains O(1), making dynamic hash tables efficient even as they grow.