Load Factor and Rehashing
What you'll learn: How hash tables decide when they're too full and need to grow to maintain performance.
What is Load Factor?
The load factor is a simple ratio that tells you how full your hash table is:
Load Factor = Number of Elements / Table Size
For example, if you have 7 elements in a table with 10 slots, your load factor is 0.7 (or 70% full).
Why It Matters
Think of a hash table like a parking lot. When it's mostly empty, finding a spot is instant. But as it fills up (especially with open addressing from our previous lessons), finding an empty slot takes longer. With separate chaining, long chains form at each slot, making searches slow.
A high load factor means:
- More collisions
- Longer probe sequences (linear probing, quadratic probing)
- Longer chains (separate chaining)
- Slower operations overall
Load Factor Thresholds
Most hash tables set a maximum load factor threshold:
- Separate chaining: Often 0.75 to 1.0
- Open addressing: Usually 0.5 to 0.7 (needs more empty space for probing)
When you exceed this threshold, it's time to rehash.
The Rehashing Process
When the load factor crosses your threshold:
- Create a new, larger table (typically double the size)
- Recompute hash values for all existing elements (the hash function output depends on table size!)
- Insert all elements into the new table
- Replace the old table with the new one
This is expensive (O(n) time), but happens infrequently enough that the average-case insertion remains O(1).
Key Takeaway: The load factor measures how full your hash table is; when it exceeds a threshold, rehashing to a larger table maintains efficient performance.