Separate Chaining Collision Resolution

A hash table with separate chaining consists of an array $T[0..m-1]$ of $m$ buckets, where each bucket $T[j]$ is a linked list (a chain) holding every key $k$ currently in the table such that $h(k) = j$, for some hash function $h$. Collisions are not treated as errors or exceptions to be resolved by finding another slot; they are simply expected, and the bucket itself is designed to hold more than one element. This is the crucial conceptual difference from Open Addressing Collision Resolution, where a slot holds at most one key and a colliding key must be relocated elsewhere in the array via a probe sequence. The central quantity governing performance is the load factor

where $n$ is the number of keys currently stored and $m$ is the number of buckets. Intuitively, $\alpha$ is the average chain length: if keys are spread evenly, each of the $m$ buckets holds about $n/m = \alpha$ keys. Unlike open addressing, $\alpha$ is not bounded by 1 — a chained table can hold arbitrarily many keys in a fixed-size array, at the cost of longer and longer chains. This makes chaining structurally forgiving: performance degrades smoothly as $\alpha \to \infty$ rather than hitting a hard wall at $\alpha = 1$. The analysis of chaining rests on an assumption called simple uniform hashing: any given key is equally likely to hash to any of the $m$ buckets, independently of where other keys hash. This is an idealization (no single hash function truly achieves this for adversarial key distributions), but it is a reasonable model when the hash function mixes bits well and keys are not chosen to defeat it, and it is the same idealization used to analyze Hash Tables and Direct Addressing more generally.

Each bucket is an independent, unordered singly linked list. The three fundamental operations — search, insert, delete — reduce entirely to standard linked-list operations, applied only within the one relevant bucket.

Search hashes the key to find its bucket, then walks that bucket's list comparing keys, since the table gives no other information about where in the chain a key might be.

Insert hashes the key and prepends a new node to the front of that bucket's list; prepending is preferred over appending because it takes $O(1)$ time without needing a tail pointer or traversal, and duplicate suppression (if desired) is handled by an optional search-before-insert.

Delete hashes the key, searches the chain, and unlinks the matching node — an $O(1)$ operation once the node is found, since the list is singly or doubly linked and removal from a known position requires only pointer surgery. ``` struct Node: key value next # pointer to next Node in this bucket's chain struct HashTable: T[0..m-1] # array of Node pointers (bucket heads), each init to NIL n # number of keys currently stored m # number of buckets function HASH(key): return h(key) mod m # h is a fixed hash function function CHAINED-SEARCH(T, key): j = HASH(key) x = T.array[j] while x != NIL: if x.key == key: return x # found: return node (gives value) x = x.next return NIL # not found function CHAINED-INSERT(T, key, value): j = HASH(key) x = new Node x.key = key x.value = value x.next = T.array[j] # prepend: O(1), no traversal needed T.array[j] = x T.n = T.n + 1 if T.n / T.m > ALPHA-MAX: # optional: maintain bounded load factor REHASH(T, 2 * T.m) function CHAINED-DELETE(T, key): j = HASH(key) x = T.array[j] prev = NIL while x != NIL: if x.key == key: if prev == NIL: T.array[j] = x.next else: prev.next = x.next T.n = T.n - 1 return TRUE prev = x x = x.next return FALSE # key not present function REHASH(T, new_m): old_array = T.array T.array = new array of size new_m, all NIL T.m = new_m for each bucket b in old_array: x = b while x != NIL: nxt = x.next j = h(x.key) mod new_m x.next = T.array[j] # re-prepend into new bucket T.array[j] = x x = nxt ``` The `REHASH` routine is the standard response to a growing load factor: when $\alpha$ exceeds a chosen threshold, the table doubles in size and every key is rehashed into the new, larger array. Because doubling happens geometrically, the amortized cost of all rehashing over $n$ insertions remains $O(1)$ per insertion — exactly the same amortized-doubling argument used for dynamic arrays.

Space. The table uses $\Theta(m + n)$ space: $\Theta(m)$ for the bucket array (most of which may be empty pointers) and $\Theta(n)$ for the $n$ list nodes actually storing keys. This is the chief structural cost of chaining relative to open addressing, which stores keys directly in the array with no extra pointers.

Time — worst case. In the worst case, an adversarial or unlucky hash function sends every key to the same bucket, producing one chain of length $n$. Search, insert-with-duplicate-check, and delete all become $\Theta(n)$ in this pathological case — no better than an unsorted linked list. Chaining offers no protection against a bad hash function; its guarantees are only average-case guarantees under a randomness assumption on $h$.

Time — expected case, the $\Theta(1+\alpha)$ derivation. Assume simple uniform hashing: each key is equally likely to land in any of the $m$ buckets, independent of other keys. Fix a bucket $j$ and let $n_j$ be the number of the $n$ keys hashed there. Then $E[n_j] = n/m = \alpha$ by linearity of expectation and the uniformity assumption, since each of the $n$ keys independently has probability $1/m$ of landing in bucket $j$. For an unsuccessful search (the key is not in the table), the algorithm must hash to bucket $h(k)$ and scan the entire chain there to confirm absence, giving expected cost

The $\Theta(1)$ term accounts for computing the hash function and array indexing, which takes constant time regardless of $\alpha$. For a successful search, the standard argument (as in CLRS) considers the $i$-th key inserted, $k_i$, and observes that a search for $k_i$ examines, in expectation, $1$ (for itself) plus the expected number of keys inserted before $k_i$ that also hash to $k_i$'s bucket (assuming new keys are prepended, so later insertions land in front and are found before $k_i$ during a search — but by symmetry of the uniform assumption, the exact insertion-order bookkeeping still yields the same asymptotic bound). Averaging over all $n$ keys gives expected successful search cost

Either way, the headline result is:

The $1$ accounts for hashing overhead that is independent of table size; the $\alpha$ accounts for the average chain traversal. If $m$ is chosen proportional to $n$ (i.e., the table is resized to keep $\alpha = O(1)$, as `REHASH` does), then expected search, insert, and delete are all $\Theta(1)$ — the hallmark constant-time guarantee of hash tables.

Insertion cost specifically is $O(1)$ worst case with prepend-only insertion (no traversal needed at all), though maintaining a bounded $\alpha$ requires amortized $O(1)$ extra work for periodic table doubling — identical in spirit to dynamic array resizing.

Correctness argument. The invariant maintained by `CHAINED-INSERT` and `CHAINED-DELETE` is: > After any sequence of operations, key $k$ is present in the table if and only if $k$ appears as a node in the chain at $T[\text{HASH}(k)]$. This invariant holds trivially on the empty table (all chains empty). `CHAINED-INSERT` adds $k$ exactly to chain $\text{HASH}(k)$, preserving the invariant. `CHAINED-DELETE` removes the unique node in that same chain matching $k$ (searching guarantees it finds the correct node, since $h$ is a deterministic function — every occurrence of $k$ hashes to the identical bucket). `CHAINED-SEARCH` looks in precisely the chain the invariant guarantees $k$ must be in if present, and correctly reports absence when the chain is exhausted without a match. No probing sequence, tombstone bookkeeping, or clustering behavior can violate this invariant, which is exactly why chaining's correctness proof is comparatively simple next to Open Addressing Collision Resolution.

Tradeoffs, honestly stated. Chaining's simplicity comes at a price: pointer overhead per node, worse cache locality (chain traversal follows pointers scattered in memory rather than scanning contiguous array slots), and no bound on the number of keys per bucket without rehashing. Open addressing avoids pointer overhead and improves cache behavior but requires careful probe-sequence design and degrades sharply as $\alpha \to 1$. Chaining degrades linearly and gracefully even for $\alpha > 1$, making it the safer default when load factor is hard to control precisely.

Take $m = 8$ buckets and a hash function $h(k) = (\text{first letter's alphabet position}) \bmod 8$. Insert the following 11 three-letter keys in order: `cat, dog, owl, ant, hen, map, elk, bee, cow, fox, yak, pig` — actually 12 keys; we use 11, dropping `pig` for now and adding it at the end to demonstrate a bucket reaching length 3 during the trace. Letter positions: a=1, b=2, c=3, d=4, e=5, f=6, h=8, m=13, o=15, p=16, y=25.

Because insertion prepends, tracing through in order produces final chains:

Total keys $n = 11$, buckets $m = 8$, so $\alpha = 11/8 = 1.375$, matching the average chain length $(1+2+1+2+1+2+1+1)/8 = 11/8$ exactly, as the theory predicts.

Search for "cat": compute $h(\text{cat}) = 3$, go to bucket 3, scan chain `cow → cat`: compare against `cow` (miss), then `cat` (hit) — 2 comparisons.

Search for "bat" (not present): $h(\text{bat}) = 2 \bmod 8 = 2$ (b=2), go to bucket 2, scan chain `bee`: compare against `bee` (miss), reach NIL — report not found after 1 comparison, consistent with the expected-cost bound $\Theta(1+\alpha) \approx 2.4$ comparisons averaged over all possible misses.

Insert "pig" ($p = 16$, $h = 0$): prepend to bucket 0, giving chain `pig → hen`, length 2. New $n = 12$, $\alpha = 1.5$.

Delete "yak" from bucket 1 (`yak → ant`): search finds `yak` as head, unlink it (bucket 1's head pointer is redirected to `ant`), giving chain `ant`, length 1. New $n = 11$, $\alpha = 1.375$. This trace shows the entire lifecycle: hashing distributes keys unevenly in the short run (bucket 3 got 2 keys while bucket 0 initially got 1), but the average chain length tracks $\alpha$ closely, exactly as the $\Theta(1+\alpha)$ bound predicts even for small, concrete instances.

Separate chaining emerged from the broader development of hash tables and symbol-table techniques in the 1950s–60s, when memory was scarce and efficient string lookup was essential for early compilers and assemblers. The idea of attaching a list to each hash bucket appears in some of the earliest published treatments of hashing, and its clean amortized analysis became a standard example in the algorithms literature once formal average-case analysis matured.

Separate chaining underlies many production hash-table implementations because of its forgiving degradation and simple correctness argument. Java's `HashMap` historically used chaining (with a modern optimization that converts long chains into balanced trees once a length threshold is exceeded, bounding worst-case behavior to $O(\log n)$ per bucket instead of $O(n)$). The `.NET` `Dictionary` and many compiler symbol tables use chained hashing for identifier resolution during parsing and semantic analysis. Database systems use chained hash tables for in-memory hash-join operators, where each bucket's chain holds rows sharing a join-key hash. Network routers and firewalls sometimes use chained hash tables for flow tracking, where the graceful degradation under bursty traffic (rather than a hard failure at $\alpha=1$) is operationally valuable. Understanding chaining is also the natural stepping stone to contrasting collision-resolution philosophies in Open Addressing Collision Resolution, and both techniques rest on the same Hash Tables and Direct Addressing foundations and the same list-manipulation primitives from Linked Lists.

Ask the tutor: How does the expected successful-search cost derivation change if insertions append to the tail instead of prepending to the head?