Constant-time search, insert, and delete — by computing the array index from the key instead of searching for it, and by having a good answer for when two keys collide.
A hash table is the most used data structure in software, and it is the only one in this book that gives Θ(1) expected time for all three of search, insert, and delete. It buys that by throwing away order: no minimum, no successor, no range queries. The chapter has two halves. The first is collision resolution — chaining and open addressing, and what each costs. The second is hash functions, and it makes a point that most treatments skip: a fixed hash function can always be defeated by an adversary, so the function itself should be chosen at random.
Start with the case where hashing is unnecessary. Suppose keys are drawn from a small universe U = {0, 1, …, m-1} and no two elements share a key. Then use an array T[0 : m-1], called a direct-address table, where slot k holds the element with key k, or NIL.
DIRECT-ADDRESS-SEARCH(T, k) return T[k]
DIRECT-ADDRESS-INSERT(T, x) T[x.key] = x
DIRECT-ADDRESS-DELETE(T, x) T[x.key] = NILAll three are Θ(1) worst case. Nothing could be faster.
|U| slots. If keys are 64-bit integers, or strings, or IP addresses, |U| is astronomically larger than the number of keys you actually store. Storing a thousand 32-bit keys would need a 4-billion-slot array, of which 99.99997% would be NIL. The space is proportional to the universe, not the data.k is stored in slot h(k), where the hash function h : U → {0, 1, …, m-1} maps the universe into a table of size m, with m much smaller than |U|. Storage drops from Θ(|U|) to Θ(m), and we choose m proportional to the number of keys stored.The immediate problem: |U| > m means h cannot be injective. Two distinct keys will map to the same slot. That is a collision, and it is not a rare accident to be engineered away.
m slots you expect a collision after only about √m insertions. A table with a million slots collides after roughly a thousand keys. Collisions are the normal case, and the whole design question is what to do about them.The simplest answer: put all elements that hash to the same slot into a linked list, and store a pointer to the list head in the slot.
CHAINED-HASH-INSERT(T, x)
1 insert x at the head of list T[h(x.key)] // O(1)
CHAINED-HASH-SEARCH(T, k)
1 search for an element with key k in list T[h(k)] // Θ(chain length)
CHAINED-HASH-DELETE(T, x)
1 delete x from the list T[h(x.key)] // O(1) if doubly linkedInsertion goes at the head, so it is O(1) and does not check for duplicates. Deletion is O(1) given a pointer, provided the chains are doubly linked — exactly the Chapter 10 caveat.
m slots holding n elements, the load factor is α = n/m: the average number of elements per chain. It may be less than, equal to, or greater than 1.Worst case is dismal and worth stating plainly: all n keys hash to the same slot, the table degenerates into one linked list of length n, and search is Θ(n). Hashing gives no worst-case guarantee at all.
The average case needs an assumption about how h distributes keys:
m slots, independently of where any other key has hashed. This is the idealisation the analysis uses. CLRS is careful to say it is not implementable — a real function of the key is deterministic, not random — but it is the right model for what a good hash function approximates.| Theorem | Statement |
|---|---|
| 11.1 | In a hash table with chaining, an unsuccessful search takes Θ(1 + α) expected time, under independent uniform hashing. |
| 11.2 | A successful search also takes Θ(1 + α) expected time. |
The unsuccessful case is immediate: the expected chain length is α, and you scan all of it. The successful case is the nicer argument, and it uses indicator variables from Chapter 5. When element x was inserted, it went to the head of its chain, so the elements examined when later searching for x are exactly those inserted after it that hashed to the same slot. Averaging over insertion order gives 1 + α/2 - α/2n, which is Θ(1 + α).
n = O(m), then α = O(1) and all three operations run in Θ(1) expected time. So keep the table size proportional to the number of elements — typically by doubling m and rehashing when α exceeds a threshold, which by Chapter 16’s amortized argument adds only O(1) per operation.A good hash function should satisfy independent uniform hashing approximately, and it must be fast. Three concrete constructions.
h(k) = k mod mFast — one division. But the choice of m matters enormously.
m = 2ᵖ, then k mod m is just the low p bits of k, so the hash ignores every other bit. Any regularity in the low bits — and there usually is some, since object addresses are aligned and IDs are often sequential or padded — maps straight into clustering. For the same reason avoid m = 2ᵖ - 1 when keys are strings interpreted in radix 2ᵖ. A prime not too close to an exact power of 2 is the standard safe choice.h(k) = ⌊ m · (k·A mod 1) ⌋ for a constant 0 < A < 1Multiply the key by A, keep the fractional part, scale by m, take the floor. The advantage over division: the value of m is not critical, so you may freely use a power of 2. Knuth suggests A ≈ (√5 - 1)/2 = 0.6180339887…, the golden ratio conjugate, which spreads keys well in practice.
New emphasis in the 4th edition, and this is what fast implementations really do. With w-bit words and m = 2ℓ, pick an odd w-bit constant a and compute
hₖ(k) = (k·a mod 2ᵧ) >> (w - ℓ)One multiply and one shift, no division at all. Multiplication mixes the high bits of the product with information from the whole key, and the shift extracts the top ℓ bits of the low word.
Every method above has the same fatal property: it is fixed. Whatever h you choose, the set of keys that all collide under it is determined, and an adversary who knows h can hand you exactly that set.
Θ(1) lookups into Θ(n) and pinning the CPU. The fix deployed everywhere was randomized hashing, seeded per process.H of functions. No single input is bad, because the adversary cannot know which function you drew. This is exactly the Chapter 5 move from average-case to expected-case, applied to hashing.The family must have a specific property:
A family H of hash functions is universal if, for every pair of
distinct keys k ≠ l, the number of functions h ∈ H with h(k) = h(l)
is at most |H|/m.
Equivalently: for h chosen uniformly at random from H,
Pr{ h(k) = h(l) } ≤ 1/m for any fixed k ≠ l.That is the collision probability you would get from a genuinely random function. And it is enough:
m slots, the expected length of the chain containing any given key is at most 1 + α — the same bound as independent uniform hashing, but now with no assumption about the input distribution.The proof is one line of indicator variables: for a key k, define Xₖₗ = I{h(k) = h(l)} for each other key l. Each has expectation at most 1/m, and there are at most n of them, so the expected chain length is at most n/m = α, plus k itself.
A standard universal family, given a prime p larger than every key:
hₓₖ(k) = ((a·k + b) mod p) mod m for a ∈ {1,…,p-1}, b ∈ {0,…,p-1}Draw a and b at random once, at table creation. The multiply-shift method above also yields a universal family when a is drawn as a random odd word.
Chaining stores pointers and allocates a node per element. Open addressing avoids both: every element lives in the table itself, and there are no lists at all.
h(k, i) for i = 0, 1, …, m-1, and the sequence ⟨h(k,0), h(k,1), …, h(k,m-1)⟩ must be a permutation of all m slots, so that every slot is eventually tried.An immediate structural consequence: α ≤ 1 always. The table cannot hold more elements than it has slots.
HASH-INSERT(T, k)
1 i = 0
2 repeat
3 q = h(k, i)
4 if T[q] == NIL
5 T[q] = k
6 return q
7 else i = i + 1
8 until i == m
9 error "hash table overflow"
HASH-SEARCH(T, k)
1 i = 0
2 repeat
3 q = h(k, i)
4 if T[q] == k
5 return q
6 i = i + 1
7 until i == m or T[q] == NIL
8 return NILSearch stops at the first NIL, because if the key had been inserted it would have claimed that slot.
NIL into the freed slot: any key whose probe sequence passed through it would then become unreachable, because search stops at the first NIL. The fix is a special DELETED marker — insertion treats it as free, search treats it as occupied and keeps probing. But then search times no longer depend only on α, and a long-lived table fills with tombstones. This is the standard reason CLRS says to prefer chaining when keys must be deleted.| Scheme | Probe function | Distinct sequences | Problem |
|---|---|---|---|
| Linear probing | h(k,i) = (h′(k) + i) mod m |
m |
Primary clustering: long runs of occupied slots build up and grow ever faster, since any key hashing anywhere into a run extends it. |
| Quadratic probing | h(k,i) = (h′(k) + c₁i + c₂i²) mod m |
m |
Secondary clustering: two keys with the same initial probe follow the identical sequence forever. Also, c₁, c₂, and m must be chosen with care or the sequence misses slots. |
| Double hashing | h(k,i) = (h₁(k) + i·h₂(k)) mod m |
Θ(m²) |
Best of the three. The step size depends on the key, so two keys colliding initially still diverge. Requires h₂(k) to be relatively prime to m. |
Assuming independent uniform permutation hashing (each key’s probe sequence is equally likely to be any of the m! permutations), with α = n/m < 1:
| Search | Expected probes |
|---|---|
| Unsuccessful (Theorem 11.6) | ≤ 1/(1 - α) |
| Insertion (Corollary 11.7) | ≤ 1/(1 - α) — insertion is an unsuccessful search plus a write |
| Successful (Theorem 11.8) | ≤ (1/α)·ln(1/(1 - α)) |
The intuition for 1/(1-α): each probe hits an occupied slot with probability about α, so the number of probes is geometric with success probability 1 - α, whose mean is 1/(1-α).
Load factor α | Table is | Unsuccessful probes 1/(1-α) | Successful probes |
|---|---|---|---|
| 0.50 | half full | 2.0 | 1.39 |
| 0.75 | three quarters | 4.0 | 1.85 |
| 0.90 | 90% full | 10.0 | 2.56 |
| 0.95 | 95% full | 20.0 | 3.15 |
| 0.99 | 99% full | 100.0 | 4.65 |
α = 0.7 and then explodes. This is why every real open-addressed table resizes at a load factor well below 1 — typically 0.5 to 0.75. The last few percent of capacity is unaffordable.If the key set is static — fixed once and never changed, like reserved words in a compiler or a routing table — you can do better than expected O(1) and get O(1) worst case.
n keys into m = n slots. Slot j receives nⱼ keys, and instead of a chain it gets a secondary hash table of size mⱼ = nⱼ², with its own randomly chosen hash function, retried until that table has no collisions at all.Two results make it work:
nⱼ², the probability of any collision is below ½, so a couple of random retries suffice. This is the birthday paradox used in reverse: to make collisions unlikely, make the table quadratically larger than the number of keys.O(n). Summing squares looks alarming, but the expected value of ∑ nⱼ² is less than 2n when m = n.The result: two probes, worst case, guaranteed, in O(n) space. The limitation is that the key set cannot change without rebuilding.
| Chaining | Open addressing | |
|---|---|---|
| Load factor | May exceed 1 | Must stay below 1; resize by ~0.7 |
| Deletion | Easy, O(1) | Needs tombstones |
| Memory per element | Extra pointer, plus allocation | None — all in the array |
| Cache behaviour | Pointer chase per chain step | Contiguous probes, prefetch-friendly |
| Degrades under high load | Gracefully, chains lengthen linearly | Sharply, as 1/(1-α) |
| Sensitive to hash quality | Moderately | Severely, because of clustering |
α passes your threshold, and rehash everything. Never use a hash table when you need ordered iteration, a minimum, or a range query — use a balanced tree from Chapter 13. And remember that iteration order is arbitrary and may change between runs, so never depend on it.Θ(1) worst case but needs Θ(|U|) space. Hashing trades that for Θ(m) space and the possibility of collisions.√m keys.α = n/m. With chaining, search is Θ(1 + α) expected. Keep n = O(m) and everything is Θ(1).Θ(n) — every key in one chain. Hashing never gives a worst-case guarantee.k mod m with m a prime, not near a power of 2. Multiplication and multiply-shift let m be a power of 2 and avoid division.h at random at run time. It gives the 1 + α bound with no assumption about the input, and it is the defence against hash-flooding attacks.α ≤ 1. Probe sequences: linear (primary clustering), quadratic (secondary clustering), double hashing (best spread).1/(1-α) unsuccessful, which is 10 at α = 0.9 and 100 at α = 0.99. Resize by 0.7.O(1) worst case in O(n) space for a static key set, using two levels with secondary tables of size nⱼ².Hash tables destroy order to get speed. Chapter 12 takes the other path: a binary search tree keeps the keys ordered, so it can answer minimum, maximum, successor, predecessor, and in-order traversal — none of which a hash table can do at any price. The cost is that operations run in O(h) where h is the height, and an unlucky insertion order makes h = n. Chapter 13 fixes that.