Course contentsShow
← Computer Science
Lesson 438 of 2,87210. Hash TablesFree lesson

Dynamic Resizing and Rehashing Cost

Analyzing the amortized cost of table growth, including when to resize and rehashing all elements.

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:

  1. Allocate a new, larger array (commonly 2× the old size)
  2. For each element in the old table, recompute its hash with the new table size
  3. Insert each element into its new position using your collision resolution strategy
  4. 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.