Introduction to Hashing

A dictionary (or associative array) supports three operations on a dynamic set of key-value pairs: `Insert(k, v)`, `Delete(k)`, and `Search(k)`. A hash table implements a dictionary using an array $T[0 \ldots m-1]$ of $m$ slots, together with a hash function $h: U \to \{0, 1, \ldots, m-1\}$ that maps each key from a (typically huge) universe $U$ down to a slot index. Instead of storing a key at a position determined by comparisons (as in a search tree), we store it at position $h(\text{key})$, computed directly — no comparisons against other stored keys needed. This is what makes $O(1)$ time plausible: computing $h(k)$ takes time independent of $n$, the number of keys currently stored. The immediate difficulty is the pigeonhole principle: if $|U| > m$, some two keys $k_1 \ne k_2$ must satisfy $h(k_1) = h(k_2)$ — a collision. Worse, the birthday paradox tells us collisions appear far sooner than intuition suggests: with $m$ slots, a random set of only $\Theta(\sqrt{m})$ keys already has a collision with constant probability. So any usable hash table design must include a collision resolution policy. The two classical policies are:

• Chaining (separate chaining): each slot $T[i]$ holds a linked list of all keys that hash to $i$. Insertion is $O(1)$ (prepend); search/delete costs time proportional to the chain length.
• Open addressing: all keys live directly in the array, with no auxiliary structure. On a collision, the algorithm probes a deterministic sequence of alternate slots $h(k, 0), h(k, 1), h(k, 2), \ldots$ until it finds an empty one (for insertion) or the key itself (for search).

To reason about expected performance we need two more concepts. The load factor $\alpha = n/m$ is the average number of keys per slot; it is the single number that governs expected cost. The Simple Uniform Hashing Assumption (SUHA) idealizes the hash function as a uniform random function: each key is equally likely to hash to any of the $m$ slots, independently of other keys. SUHA is an idealization — a real fixed function cannot satisfy it against an adversary who knows the function — which motivates the rigorous fix: a universal hash family $\mathcal{H}$, a collection of functions $U \to \{0,\ldots,m-1\}$ such that for any two distinct keys $x \ne y$,

where $h$ is chosen uniformly at random from $\mathcal{H}$ before seeing the keys. This single inequality, chosen independent of any particular input, is enough to derive SUHA-like expected bounds rigorously, replacing an assumption with a theorem.

Building a universal family. The canonical construction (Carter–Wegman) works over a prime $p$ larger than the universe size. Represent each key as an integer $x \in \{0, \ldots, p-1\}$. For $a \in \{1, \ldots, p-1\}$ and $b \in \{0, \ldots, p-1\}$ chosen uniformly at random, define

The family $\mathcal{H}_{p,m} = \{h_{a,b}\}$ is universal. Choosing $h$ means drawing $a$ and $b$ once, at random, at table-creation time — not per query. This single random choice, made before any keys are known, is exactly what makes the guarantee hold against an adversary who can choose the key set but not the coin flips.

Chaining algorithm. Below is the full mechanism: initialize the table, hash a key, and walk (or build) the chain. ``` CHAINED-HASH-TABLE(m): allocate array T[0 .. m-1], each initialized to an empty list n <- 0 // number of keys stored pick random a, b for h_{a,b} from the universal family return T, n INSERT(T, k, v): i <- h(k) // O(1) hash computation prepend (k, v) to list T[i] // O(1), no search needed n <- n + 1 SEARCH(T, k): i <- h(k) for each (key, value) in list T[i]: if key == k: return value return NOT-FOUND DELETE(T, k): i <- h(k) remove the node with key k from list T[i] // O(1) if using a doubly linked list n <- n - 1 ```

Open addressing algorithm. Here every slot is either empty, occupied, or deleted (a tombstone, needed because naively marking a slot empty on deletion would break probe sequences for other keys). A probe sequence $\langle h(k,0), h(k,1), \ldots, h(k,m-1)\rangle$ must be a permutation of $\{0,\ldots,m-1\}$ for correctness — otherwise some slots become unreachable. ``` OPEN-ADDR-INSERT(T, k, v): for i <- 0 to m-1: slot <- h(k, i) if T[slot] is EMPTY or DELETED: T[slot] <- (k, v) return slot error "hash table overflow" OPEN-ADDR-SEARCH(T, k): for i <- 0 to m-1: slot <- h(k, i) if T[slot] is EMPTY: return NOT-FOUND // key cannot be present further on if T[slot] is occupied and T[slot].key == k: return T[slot].value // else: DELETED or occupied by a different key -> keep probing return NOT-FOUND OPEN-ADDR-DELETE(T, k): for i <- 0 to m-1: slot <- h(k, i) if T[slot] is EMPTY: return // not present if T[slot] is occupied and T[slot].key == k: T[slot] <- DELETED return return ``` Common probing strategies, each defining $h(k,i)$ differently:

• Linear probing: $h(k,i) = (h'(k) + i) \bmod m$. Simple, cache-friendly, but suffers from primary clustering (long runs of occupied slots grow even longer).
• Quadratic probing: $h(k,i) = (h'(k) + c_1 i + c_2 i^2) \bmod m$. Reduces clustering but not all slots are reachable for arbitrary $m$; requires careful choice of $m$ and constants.
• Double hashing: $h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod m$, with $h_2(k)$ never $0$ and coprime to $m$ (e.g., $m$ prime). This most closely approximates a uniform random permutation of slots and is the strategy of choice when SUHA-style analysis is desired.

Space. Chaining uses $\Theta(m + n)$ words: $m$ for the array, $n$ for the stored key–value pairs across all lists. Open addressing uses exactly $\Theta(m)$ words, since keys live directly in the array with no extra pointers — a real memory-density advantage, at the cost of requiring $m \ge n$ always (the table can fill up).

Expected time under SUHA — chaining. Let $\alpha = n/m$. Fix a key $k$ not in the table. Under SUHA, each of the other $n$ keys independently lands in slot $h(k)$ with probability $1/m$. Let $X$ be the number of keys colliding with $k$'s slot; then $X$ is a sum of $n$ indicator variables each with expectation $1/m$, so

by linearity of expectation. An unsuccessful search costs $O(1)$ to compute $h(k)$ plus $O(\mathbb{E}[X]) = O(\alpha)$ to scan the chain, giving expected time $\Theta(1+\alpha)$. A successful search for a key inserted as the $i$-th of $n$ keys has expected chain length (at the moment of its own insertion, counting only later collisions using a symmetric argument) bounded similarly, giving the same $\Theta(1+\alpha)$ bound; the standard CLRS-style argument averages over which key is queried and again invokes linearity of expectation. If $m = \Theta(n)$ — i.e., we resize the table to keep $\alpha = O(1)$ — this is $\Theta(1)$ expected time per operation.

From assumption to theorem — universal hashing. SUHA is unjustifiable for a single fixed $h$: an adversary who knows $h$ can choose $n$ keys that all collide, forcing $\Theta(n)$ time. Universal hashing repairs this. Fix any key $k$ and suppose $h$ is drawn uniformly from a universal family $\mathcal{H}$ before the adversary's key set $S$ (with $|S| = n$) is fixed relative to the random draw (equivalently: the adversary fixes $S$, then $h$ is drawn independently). Define the collision count

By the universal property, $\mathbb{E}[\mathbb{1}[h(k)=h(y)]] = \Pr[h(k)=h(y)] \le 1/m$ for each fixed pair, so by linearity of expectation,

regardless of which keys the adversary chose. This is precisely the SUHA conclusion, but now derived from a concrete, checkable algebraic property of $\mathcal{H}$ rather than assumed. The Carter–Wegman family $h_{a,b}(x) = ((ax+b) \bmod p)\bmod m$ satisfies the universal property because for $x \ne y$, the map $a \mapsto (ax+b) \bmod p$ is a bijection on residues (using that $p$ is prime and $x - y \not\equiv 0$), so the pair $(ax+b \bmod p,\, ay+b \bmod p)$ is uniform over ordered pairs of distinct residues mod $p$; a counting argument then bounds the probability that two such residues collide mod $m$ by $\lceil p/m \rceil / p \le 1/m + 1/p$, which is $\le 2/m$ for $p \ge m$ — universal up to the standard constant factor of 2 (some treatments rescale to get exactly $1/m$).

Open addressing under uniform hashing. Assume each probe sequence is equally likely to be any permutation of the slots (uniform hashing, an idealization stronger than SUHA but standard for analyzing open addressing). For an unsuccessful search with load factor $\alpha < 1$, the expected number of probes is at most

proved by conditioning: the probability the first probe hits an occupied slot is $n/m = \alpha$, and given that, the remaining search behaves like a search in a table with one fewer key and one fewer slot, giving the recurrence $E \le 1 + \alpha \cdot E'$ that solves to the geometric-series bound above. As $\alpha \to 1$, this blows up — open addressing degrades sharply near capacity, unlike chaining, which degrades gracefully (linearly in $\alpha$) even past $\alpha=1$.

Amortized resizing. Both schemes maintain $O(1)$ expected amortized cost per operation by doubling $m$ whenever $\alpha$ exceeds a threshold (e.g., $1$ for chaining, $0.5$–$0.7$ for open addressing) and rehashing all keys with a freshly drawn hash function. Since doubling happens geometrically less often as $n$ grows, the total rehashing cost across $n$ insertions is $O(n)$, an $O(1)$ amortized charge per insertion — the same argument used for dynamic array growth.

Honest tradeoffs. Hashing gives expected, not worst-case, guarantees; an adversary who can force $h$ to be predictable (e.g., a leaked seed) can still degrade performance to $\Theta(n)$, which is why production hash tables reseed randomly per process (hash-flooding defenses in languages like Python and Perl exist precisely because of this). Open addressing is more cache-friendly (better memory locality) but harder to shrink and sensitive to clustering; chaining tolerates $\alpha > 1$ gracefully and supports simple deletion, but pays pointer overhead and worse cache behavior.

Take $m = 5$ slots and the universal family $h_{a,b}(x) = ((ax+b)\bmod 11)\bmod 5$ with $p = 11$. Suppose the random draw at table-creation time gives $a = 3, b = 4$. We insert keys (already encoded as integers) $x \in \{2, 7, 9, 4\}$ with chaining.

After these four insertions: slot 0 holds the chain $\langle 4, 2\rangle$ (most recent prepended first), slot 3 holds $\langle 7 \rangle$, slot 4 holds $\langle 9 \rangle$, and slots 1, 2 are empty. $n = 4$, $m = 5$, so $\alpha = 0.8$. Now `SEARCH(6)`: compute $3(6)+4 = 22$, $22 \bmod 11 = 0$, $0 \bmod 5 = 0$. We scan chain at slot 0: check key 4 (no match), check key 2 (no match), reach end — return `NOT-FOUND` after 2 comparisons, consistent with the expected bound $O(1+\alpha) = O(1.8)$. Contrast with open addressing (linear probing) using the same base hash $h'(x) = (3x+4 \bmod 11)\bmod 5$: inserting $2, 7, 9, 4$ in order places $2\to 0$, $7 \to 3$, $9 \to 4$, then $4 \to 0$ collides, probe $0+1=1$ (empty) — place at slot 1. `SEARCH(6)` computes slot 0, finds key 4 (not a match), probes slot 1, finds key 2 (not a match), probes slot 2, finds it empty, and correctly halts, returning `NOT-FOUND` — this early termination on an empty slot is exactly why open addressing search sequences must never leave "true gaps" unless properly using tombstones for deleted (not merely absent) keys.

Hash tables back the associative arrays and dictionaries built into essentially every modern programming language — Python's `dict`, Java's `HashMap`, JavaScript objects, C++'s `unordered_map` — and language runtimes randomize their hash seeds per process specifically because of the adversarial-collision concern discussed above. Databases use hashing for hash indexes and hash joins, where matching rows across tables is done by hashing join keys into buckets rather than sorting. Compilers and interpreters use hash tables for symbol tables, mapping identifiers to their declarations in constant expected time regardless of program size. Content-addressed storage systems (Git, IPFS, deduplicating backup systems) use cryptographic hash functions — a stricter cousin of the hash functions discussed here — to name and deduplicate data by its hash. Distributed systems use consistent hashing, a direct descendant of universal hashing, to shard data across servers (used in Amazon's Dynamo, Cassandra, and content delivery networks) so that adding or removing a server relocates only a small fraction of keys. Finally, hashing is the computational core of string-processing algorithms like Rabin-Karp and Rolling Hashes, which hash substrings for fast pattern matching, and a comparison point for indexing structures such as Suffix Trees and Suffix Arrays, which solve similar substring problems with different space/time tradeoffs.

Ask the tutor: Can you walk through why the Carter–Wegman construction $h_{a,b}(x) = ((ax+b)\bmod p)\bmod m$ satisfies the universal hashing property in more algebraic detail?