4.3Load factor and expected cost
The idea
The load factor α = n/m controls speed: chaining costs about 1 + α, open addressing about 1/(1 − α) probes.
Think of it like this: A bus that gets slower as it fills: nearly empty is quick, nearly full is a crawl.
Why it exists
This is why real tables resize before they fill up.
How it works
- Chaining: α can exceed 1, cost 1 + α.
- Open addressing needs α < 1.
- At α = 0.5, unsuccessful search takes 2 probes; at α = 0.9, 10 probes.
- Doubling the table when α is too high gives amortised O(1) inserts.
Worked example: n = 30 keys, m = 40
α = 0.75. Chaining: 1.75 steps. Open addressing: 1 / (1 − 0.75) = 4 probes for an unsuccessful search.
Now play with it
- →Drag the plot to α = 0.9 and see the curve explode.
- →Use the calculator to compare chaining against open addressing.
load factor α = 0.5 → probes (unsuccessful, open addressing) = 2
Open addressing: 1/(1 − α) probes. At α = 0.5 that is 2, at α = 0.9 it is 10. Chaining stays at 1 + α.
Check yourself
With uniform hashing and open addressing at α = 0.5, the expected number of probes for an unsuccessful search is at most
Exam notes (the dense version)
For chaining, unsuccessful search takes Θ(1 + α) and successful about 1 + α/2. For open addressing with uniform hashing, an unsuccessful search needs at most 1/(1 − α) probes and a successful one (1/α) ln(1/(1 − α)). Performance collapses as α → 1, so tables are resized at α around 0.5 to 0.75. Resizing by doubling gives amortised O(1) insertion.
Previous year questions: Hashing (6)
PYQs are grouped by topic, so this is the full set for Hashing; try the ones that match this subtopic. Open all 6 on the topic page.