Hash tables & chaining

The dictionary problem, solved on average

A hash table implements a dictionary — INSERT, SEARCH, DELETE — in expected $O(1)$ time, beating the $O(\lg n)$ of a balanced BST when you only need membership and don't need ordered operations (MINIMUM, SUCCESSOR, range queries). It works by mapping a key $k$ from a huge universe $U$ into a small array of $m$ slots with a hash function $h:U\to \{0,1,\dots ,m-1\}$, storing the element near index $h(k)$.

The contrast is with a direct-address table, which uses the key itself as the index: $O(1)$ worst-case, but it needs $\Theta (|U|)$ space — four billion slots for 32-bit keys. Hashing compresses $|U|$ down to $m\approx n$ slots, paying for that compression with collisions.

Collisions are unavoidable

A collision is two distinct keys hashing to the same slot, $h(k_1)=h(k_2)$. Whenever $|U|>m$, collisions are guaranteed by the pigeonhole principle — more keys than slots forces a shared slot. So every hash table needs a collision-resolution strategy. The two in CLRS are chaining (this lesson) and open addressing (probe sequences within the array).

Chaining and the load factor

In chaining, each slot $T[j]$ holds a linked list of all elements that hash to $j$.

• INSERT: prepend to the list at $h(k)$ — $O(1)$.
• SEARCH: scan the list at $h(k)$ — $\Theta (1+\alpha )$ on average.
• DELETE: unhook from the list — $O(1)$ given a pointer to the element.

The star of the analysis is the load factor $\alpha =n/m$: the average number of elements per slot. Under the independent uniform hashing assumption (each key equally and independently likely to land in any slot), the expected chain length is $\alpha$, so both successful and unsuccessful searches cost $\Theta (1+\alpha )$ — the "$1+$" pays for computing the hash, the "$\alpha$" for walking the expected-length chain. Keep $n=O(m)$ (resize when $\alpha$ grows) and $\alpha =O(1)$, so every operation is expected $O(1)$. This is exactly how Python dict works — it resizes when $\alpha \approx 2/3$.

Two hash functions, and the adversary

The division method is $h(k)=k\mathrm{mod}m$, with $m$ chosen as a prime not close to a power of 2 (a power-of-2 $m$ would make $h$ depend only on $k$'s low-order bits — bad when keys share bit patterns). The multiplication method $h(k)=\lfloor m(kA\mathrm{mod}1)\rfloor$ is less sensitive to the choice of $m$.

But any fixed hash function is defeatable: an adversary who knows $h$ picks $n$ keys all in one collision class, forcing every key into one slot and every operation to $\Theta (n)$. The fix is universal hashing — choose $h$ randomly from a family $H$ at startup where $\mathrm{Pr}[h(k_1)=h(k_2)]\le 1/m$ for any distinct pair. Now no input is reliably bad, because the input is chosen before the hash function is known. (Same randomization idea as randomized quicksort: move the worst case off the input and onto a coin.)

Worked example — chaining with the division method, m = 4

Use $h(k)=k\mathrm{mod}4$ and insert keys $10,14,22,7$. The hashes are $10\mathrm{mod}4=2$, $14\mathrm{mod}4=2$, $22\mathrm{mod}4=2$, $7\mathrm{mod}4=3$. So 10, 14, 22 all collide into slot 2, forming a three-node chain, while 7 sits alone in slot 3 — load factor $\alpha =4/4=1$. Searching for 14 hashes to slot 2 and scans the chain until it matches; searching 99 ($99\mathrm{mod}4=3$) scans slot 3, doesn't find it, and returns nothing. The collision in slot 2 is exactly the $\Theta (1+\alpha )$ chain-walk the analysis predicts — and a worst-case input where every key hashes to slot 2 would degrade SEARCH to $\Theta (n)$, which is why universal (randomized) hashing matters.