Foundations
Probability & expected value
Why hash map average is O(1); randomized algorithms and expected counts.
Question: if you scatter 1000 keys into 24 buckets, how long is the longest chain?
Expected average chain length is λ = n/m ≈ 42. But the longest chain is aboutλ + √(2λ ln m) ≈ 56. In a hash map, a single lookup is still O(1) on average. This page unpacks the probability math under "hash map is average O(1)".
By the numbers: load factor
| n keys / m buckets | λ = n/m | Expected chain | Worst expected |
|---|---|---|---|
| 24 / 24 | 1.0 | O(1) | ~4 |
| 1000 / 24 | 41.7 | O(λ) | ~56 |
| 10⁶ / 1.3M | 0.75 | O(1) | ~5 |
One line: if λ is constant (load factor ≤ ~0.75) both the expected and worst expected chain are O(1). Rehash keeps the factor bounded, so "hash map is average O(1)" carries an implicit constant factor assumption.
Where it comes from
Expected value: E[X] = Σ xᵢ · P(xᵢ). n lookups, each costingE[one lookup] on average, total expected n · E[one lookup].
Collision analysis: m buckets, n keys, uniform hash. Each bucket holds on averageλ = n/m keys (Poisson). A lookup walks the chain in the target bucket; expected chain length is λ + 1. If λ is constant (rehash guarantees this) → O(1).
Worst case: all keys collide into one bucket → O(n). Under uniform hashing its probability is negligible, but with attacker-controlled keys (e.g. web framework hash maps) it's a real attack; that's why modern languages use keyed hashing (SipHash).
Trap: "hash map is always O(1)"
No. Average O(1) assumes uniform hashing and constant load factor. Worst case is O(n): bad hash function (all keys to one bucket) or unbounded load factor. Python dictand Java HashMap rehash, but it's still amortized O(1), worst O(n). In an interview, answer "amortized average O(1), worst case O(n)".
Where to go next
- hashing pattern - where hash maps are used in DSA.
- LC 217 Contains Duplicate - hash set, O(n) average.
- LC 1 Two Sum - complement lookup with a hash map, O(n) average.
- Summations - summing expected values.
Exercise
In the simulation below, click +100 a few times. The average chain stays around 1. Now click +1000 repeatedly: λ rises and some buckets visibly overflow. This shows why load factor drives collisions and why rehash is necessary.
bucket occupancy (m = 24) · load factor λ ≈ 0.00