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 \bmod 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 \bmod 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 $\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 \bmod 4$ and insert keys $10, 14, 22, 7$. The hashes are $10 \bmod 4 = 2$, $14 \bmod 4 = 2$, $22 \bmod 4 = 2$, $7 \bmod 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 \bmod 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.