Load Factor: When a Hash Table Must Grow

Lesson notes

Key points

• The load factor, written alpha, is the number of stored keys divided by the number of buckets in the table.
• With chaining, the expected search cost is about one plus alpha, so a fuller table means longer chains to scan.
• When alpha passes a chosen threshold, the table allocates a bigger array and reinserts every key using the new size, which is called rehashing.
• One rehash costs O(n), but doubling makes it rare, so the amortised cost per insertion stays O(1).

Takeaway: Keep α low by doubling and rehashing; inserts stay amortised O(1).

Load factorCost grows with αRehashingAmortised O(1)