Under simple uniform hashing the expected length of a chain is the load factor α = n/m, so a search costs Θ(1 + α) expected. That is an average over an assumption about the keys, and the worst case is Θ(n): no hash function removes it. At m = 8 and n = 20 the lab measures 2.3 probes on random keys and 10.5 on a key set with the same α.
Core ideas
Three statements, and the third is the one that turns a slogan into an engineering fact. The first two are arithmetic; the third is what the arithmetic assumed.
α = n/m is the average chain length by definition: n keys shared over m slots. With chaining there is no upper limit on α — twenty keys in eight slots is α = 5/2 and the table works fine, just more slowly. A search costs one probe to find the slot plus a walk along the chain, which is Θ(1 + α), and the 1 matters precisely when α is small.
Simple uniform hashing says each key is equally likely to hash to each slot, independently of the others. That is an assumption about the input, and the hash function does not enforce it: h(k) = k mod m sends every multiple of m to slot 0 no matter how clever the rest of the table is. When the assumption fails the expectation says nothing.
For any fixed hash function into m slots there is a set of n keys that all collide, because there are far more keys than slots. So the worst-case search is Θ(n), permanently. The honest statement is two-part — Θ(1 + α) expected, Θ(n) worst — and dropping the second half is how “hash tables are O(1)” gets said.
The material
Where the two expectations come from, the exact fractions at m = 8, and two key sets with the same load and very different costs.
A table of m slots and a hash function h from keys to {0, …, m−1}. Each slot holds a linked list — a chain — of every key that hashed to it. Insert prepends to the chain; search computes h(k) and walks the chain; delete unlinks. The load factor is α = n/m, the number of keys divided by the number of slots.
The division hash function is h(k) = k mod m. It is the one this lesson uses, because its failure mode is arithmetic rather than mysterious.
Assume each key is equally likely to hash to any of the m slots, independently. Then an unsuccessful search examines α keys in expectation, and a successful search examines 1 + α/2 − α/2m. Both are Θ(1 + α) once the constant probe for the slot itself is counted.
The unsuccessful case is immediate: the search walks the whole chain at h(k), whose expected length is n/m = α by linearity of expectation over the n keys. The successful case is smaller than α because the search stops at the key it wants and, on average, that key is halfway along — and the correction −α/2m is because the key being searched for is itself one of the n, so it does not collide with itself.
Linearity of expectation is doing all the work in the first half, and it is imported from Discrete Mathematics’ “Linearity of Expectation”: the expected number of keys in a given slot is the sum over keys of the probability that key lands there, which is n × 1/m. No independence is needed for that step, only for the assumption to be stated the way it usually is.
Twenty keys into eight slots. The lab computes every quantity as an exact fraction over big integers, never as a decimal that is nearly one, and then counts the probes an actual search makes:
23/10 against an expected 67/32: the measurement came in above the expectation, which is ordinary at twenty keys, and the two numbers are close. The chain lengths 4, 5, 1, 2, 0, 1, 4, 3 add to twenty and average 2.5, as they must — the average chain length is α by arithmetic, not by luck. What varies is how unevenly the keys landed, and the longest chain here is 5, twice the average.
Now keep m = 8 and n = 20 and choose the keys to be 8, 16, 24, …, 160 — every one a multiple of 8. Each of them hashes to slot 0:
The load factor did not move. The expectation did not move. The measured cost went up by a factor of five, and it is not a fluke or a bad seed — it is the worst case, reached deliberately, by keys that a real application produces all the time: record identifiers spaced by a round number, addresses aligned to a power of two, prices in whole units. The table is now a linked list with an index on the front of it.
So the quotable statement about a hash lookup has two halves and needs both: Θ(1 + α) expected under simple uniform hashing, Θ(n) in the worst case, for any fixed hash function. System Design’s “Hash vs Tree for Ranges” is where those same two facts decide a disk index rather than an in-memory one, and there the second half is joined by a third problem: a hash index cannot answer a range query at all, at any load factor.
Interactive
Expected cost is Θ(1 + α); the worst case is Θ(n), and you can build it
Method
Compute the expectation first, measure second, and then try to break it — in that order, because the third step is meaningless without the first two.
n/m, exactly. 20/8 is 5/2, not 2.5 and certainly not 2. Every other quantity on the page is built from α, and a rounded load factor puts a rounding error into all of them.
α for an unsuccessful search, 1 + α/2 − α/2m for a successful one. They differ, they are both Θ(1 + α), and knowing which one a measurement should be compared with is half of reading the lab correctly.
The mean is pinned to α by arithmetic and tells you nothing about spread. The longest chain is the cost of the unluckiest key, and at m = 8, n = 20 it is 5 — twice the mean, on keys that were drawn at random.
For h(k) = k mod m, use multiples of m. The load factor will not move and the measured cost will. This step is the lesson: a structure whose guarantee is an expectation over the input has to be tested against the input that expectation assumes away.
A half-loaded table, where the fractions are small enough to check by hand and the degenerate set is only eight keys long.
9/8 against an expected 79/64: 1.125 measured, 1.234 expected, and the measurement came in slightly under. At eight keys that is nothing but variance, and it is worth noticing that the measurement can land on either side — a lab that always confirmed the expectation would be reporting the expectation.
The stride set quadruples the measured cost at the same α = 1/2. On a half-loaded table. The expected cost of a successful search on eight keys in one chain is (1 + 2 + … + 8)/8 = 9/2, which is exactly what was measured, because there is no randomness left: every search walks a known list.
For a faded rehearsal, set m = 8 and n = 8 so that α = 1. The supplied first step is the expectation: 1 + 1/2 − 1/16 = 23/16 = 1.4375. Predict the mean probe count for random keys, then measure it; then switch to the stride set and predict (1 + 2 + … + 8)/8 before measuring that. Say which of your four numbers were computed from a definition and which were counted.
You should be able to compute α and both expectations as exact fractions, say which expectation a given measurement should be compared with, produce a key set that sends every key to one slot for h(k) = k mod m, and quote Θ(1 + α) expected and Θ(n) worst case as a single two-part statement.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.