How do we know when a hash table is “too full” and performance will degrade? We need a metric to decide when to resize.
Load factor (α) is the ratio of elements stored to the total table size: α = number_of_elements / table_size. It predicts hash table performance.
- Calculate α = n / m (n = elements, m = table size)
- α ≤ 0.7: good performance, few collisions
- α > 0.7: performance drops, consider resizing
- α close to 1.0: many collisions, O(n) worst case likely
- α = 0.0: empty table (wasted space)
- α = 0.5-0.7: sweet spot for performance
- α > 0.7: collisions increase sharply
- α = 1.0: table full, must resize
- Built from: Hashing, Hash Function
- Builds into: Separate Chaining, Linear Probing
- Related: Collision Resolution
- Contrasts with: Big O Notation (load factor affects actual O(1) performance)
- Low load factor wastes memory (too many empty slots)
- High load factor causes performance collapse
- Resizing requires rehashing ALL elements (expensive)
- Chaining tolerates higher load factors than probing