Hash Tables

Many problems need only three operations on a set of records, each identified by a key: insert a record, search for the record with a given key, and delete a record. This is the dictionary abstract data type (also called an associative array or map), and it is one of the most heavily used data structures in all of computing: symbol tables in compilers, routing tables in networks, the dict in your favorite scripting language. A balanced search tree does all three in $O(\log n)$ time. A hash table does them in expected$O(1)$ time: constant, independent of how many keys are stored.¹ The price is that it gives up the ordering a tree provides, with no efficient next larger key or "all keys in $[a,b]$", in exchange for raw speed on the point operations.

From direct addressing to hashing

Start with the easy case. Suppose every key is drawn from a small universe$U=\left\{0,1,\dots ,m-1\right\}$. Then we can keep an array $T[\mathrm{0..}m-1]$, a direct-address table, and store the record with key $k$ in slot $T[k]$. Insert, search, and delete are each a single array access: worst-case $O(1)$, unbeatable.

Direct addressing fails the moment the universe is large. To store $64$-bit integers we would need an array of $2^{64}$ slots, impossible, even though we may hold only a few thousand keys. The waste is glaring: $T$ is almost entirely empty. The remedy is to use a table $T[\mathrm{0..}m-1]$ that is only as big as the number of keys we expect, and to compute a slot from the key with a hash function

The key $k$ lives in slot $h(k)$. We say $k$ hashes to slot $h(k)$, and $h(k)$ is the hash value. Because $|U|>m$, the function $h$ cannot be injective: two distinct keys can map to the same slot. That event is a collision, and the entire theory of hash tables is the theory of coping with collisions gracefully.

Collision resolution by chaining

The most natural fix is chaining: each slot $T[j]$ holds a linked list of all the keys that hash to $j$. To insert, prepend to the list at $T[h(k)]$; to search, scan that one list; to delete, splice the record out of its list.

Slots $1$, $3$, and $4$ hold chains; the rest are empty. Keys $k_1$, $k_5$, $k_9$ all collided at slot $4$, so they share a list.

Insertion is $O(1)$ (prepend, assuming the key is not already present). Deletion is $O(1)$ given a pointer to the record in a doubly linked list. Search costs time proportional to the length of the chain it scans, and that is what we must analyze.

The load factor and expected search time

Let $n$ be the number of keys stored in a table of $m$ slots. The ratio

is the load factor, the average number of keys per slot. With chaining $\alpha$ may exceed $1$; it is the average chain length.

To say anything about expected chain length we need an assumption about how keys spread out. The standard one is simple uniform hashing: each key is equally likely to hash to any of the $m$ slots, independently of the others.² Under this assumption a chain has expected length $\alpha$, and a search examines on average $\alpha$ keys plus the cost of computing $h$ and indexing the table:

Sketch. For an unsuccessful search on key $k$, we scan the entire chain $T[h(k)]$, whose expected length is $\alpha$; add $\Theta (1)$ to compute $h(k)$. For a successful search, the expected number of elements examined before finding $k$ is $1+\alpha /2-\alpha /(2n)=\Theta (1+\alpha )$ by averaging over the order in which keys were inserted. Either way the bound is $\Theta (1+\alpha )$.

The consequence is the headline result. If we keep the table size proportional to the number of keys, $m=\Theta (n)$ so $\alpha =O(1)$, then every dictionary operation runs in expected $\Theta (1)$ time. Keeping $\alpha$ bounded is the job of dynamic resizing: when $\alpha$ grows past a threshold (say $1$), allocate a table of double the size and rehash every key into it. A single resize costs $\Theta (n)$, but it is triggered only after $\Theta (n)$ cheap operations, so the amortized cost per operation stays $O(1)$, the same doubling argument that makes a dynamic array's append amortized $O(1)$.

Collision resolution by open addressing

Chaining stores keys outside the table. Open addressing stores every key inside the array itself: there are no lists and no pointers, so $\alpha \le 1$ always. When a key's preferred slot is occupied, we probe a deterministic sequence of alternative slots until we find an empty one. The probe sequence is defined by extending the hash function with a probe number $i$:

so the slots tried for key $k$ are $h(k,0),h(k,1),h(k,2),\dots$, which must form a permutation of all $m$ slots so that probing can examine every slot.

Search follows the same probe sequence, stopping when it finds $k$ (success) or an empty slot (failure, since $k$ is not present, because insertion would have used that empty slot). Deletion is the awkward case: simply emptying a slot would break the probe chains of other keys, so deleted slots are marked with a special deleted sentinel that search skips over but insertion may reuse. Heavy deletion is the classic reason to prefer chaining.

Three probing schemes are standard:

• Linear probing. $h(k,i)=(h^{\prime }(k)+i)\mathrm{mod}m$ for an ordinary hash function $h^{\prime }$. Simple and cache-friendly, but it suffers primary clustering: long runs of occupied slots build up and grow ever faster, since any key hashing anywhere into a run must walk to its end.

• Quadratic probing. $h(k,i)=(h^{\prime }(k)+c_{1}i+c_2{i}^2)\mathrm{mod}m$. The quadratic step spreads probes out, eliminating primary clustering, but two keys with the same initial slot follow the same sequence, a milder secondary clustering. The constants and $m$ must be chosen so the sequence hits every slot.
• Double hashing. $h(k,i)=(h_1(k)+i\cdot h_2(k))\mathrm{mod}m$, using a second hash function to set the step size. Different keys with the same start get different step sizes, so probe sequences rarely coincide. Double hashing comes closest to the ideal of uniform hashing (every key's probe sequence equally likely to be any of the $m!$ permutations), and is the strongest of the three.

Cost of open addressing

Under the uniform-hashing assumption, with load factor $\alpha =n/m<1$, the expected number of probes is

The shape of $1/(1-\alpha )$ is the whole story: at $\alpha =0.5$ we expect $2$ probes; at $\alpha =0.9$, ten probes; as $\alpha \to 1$ the cost explodes. Open addressing is fast only when the table is kept comfortably below full; a practical rule of thumb is to resize once $\alpha$ exceeds about $0.7$.

What makes a hash function good

Simple uniform hashing is an assumption; a real hash function must approximate it on real data. A good $h$ should scatter keys so that any regularities in the input, such as sequential integers, common prefixes, or similar strings, do not pile up in the same slots. Two classic constructions:

• The division method. $h(k)=k\mathrm{mod}m$. Fast, but sensitive to $m$: choosing $m$ a power of $2$ makes $h$ depend only on the low bits of $k$, and values near a power of $10$ are bad for decimal data. A prime $m$ not close to a power of $2$ is the safe choice.
• The multiplication method. $h(k)=\lfloor m\cdot (kA\mathrm{mod}1)\rfloor$ for a constant $0<A<1$ ($A=(\sqrt{5}-1)/2$ is a good choice). It is insensitive to the value of $m$, so $m$ can be a power of $2$ for fast bit shifts.

For string keys, treat the string as a base-$b$ number and fold it down, e.g. Horner's rule, $h=(h\cdot b+c)\mathrm{mod}m$ over the characters $c$, so that every character and its position influence the result.³ Skiena stresses the engineer's view: a hash function turns an arbitrary key into a pseudo-random slot, and the quality of that pseudo-randomness is exactly what protects the $O(1)$ bound.

Universal hashing: a guarantee against every input

Any fixed hash function has an Achilles' heel: there exists a set of keys that all collide, and an adversary (or merely unlucky data) can hand it to us, degrading every operation to $\Theta (n)$. Universal hashing defeats this by choosing $h$ at random from a carefully designed family $\mathcal{H}$ of hash functions at runtime, so no single input is bad for all choices.

A family $\mathcal{H}$ of functions from $U$ to $\left\{0,\dots ,m-1\right\}$ is universal if, for every pair of distinct keys $k\ne \ell$,

where the probability is over the random choice of $h$. That is, a randomly chosen $h$ collides any fixed pair no more often than picking two random slots would. This single property suffices to prove that, for any input set of keys, the expected length of the chain holding a given key is at most $1+\alpha$, recovering the $\Theta (1+\alpha )$ bound without assuming anything about the data.⁴ The randomness lives in our coin flips, not in an assumption about the world.

A concrete universal family: pick a prime $p>|U|$, draw random $a\in \left\{1,\dots ,p-1\right\}$ and $b\in \left\{0,\dots ,p-1\right\}$, and set

The collection $\left\{h_{a,b}\right\}$ over all valid $a,b$ is universal. Universal hashing is the rigorous foundation under the everyday claim that hashing is $O(1)$: it is $O(1)$ in expectation, on every input, precisely because we randomize the hash function.

Takeaways

• A hash table implements the dictionary ADT — insert, search, delete — in expected $O(1)$ time by mapping keys into an array with a hash function, trading away the ordered queries a search tree supports.
• Direct addressing is perfect but needs one slot per possible key; hashing shrinks the table to $\Theta (n)$ and resolves the resulting collisions.
• Chaining keeps a list per slot (search cost $\Theta (1+\alpha )$); open addressing stores keys in the array and probes (linear, quadratic, or double hashing), with cost governed by $1/(1-\alpha )$.
• Keeping the load factor $\alpha =n/m$ bounded, via resizing, keeps every operation expected $O(1)$.
• A good hash function scatters structured keys; universal hashing randomizes the choice of $h$ so the $O(1)$ expectation holds against every input, not just under an assumption.