Collision Resolution: Chaining | Algorithms I

How Chaining Works

In chaining, each slot $T[i]$ of the hash table holds a pointer to a linked list (initially NIL). All pairs that hash to the same index $i$ are stored in the list at $T[i]$ . There are multiple variants of chaining, differing in insertion policy and whether lists are sorted.

Chaining hash table

Variant 1: Unsorted List, Append at End (or Replace on Match)

INSERT: hash to slot, walk the list. If key found, replace value. If not found, append a new cell to the end.
SEARCH: hash to slot, walk the list until key is found or end is reached.
DELETE: hash to slot, walk the list. If found, remove the cell. Otherwise, no-op.

Performance: Expected $O(1 + \alpha)$ where $\alpha = n/m$ is the load factor. Searching for a key that is present takes, on average, half the time of searching for an absent key (since present keys are found halfway down the list on average).

Variant 2: Sorted List

Keep each chain sorted by key order (not hash value order, since all keys in a chain have the same hash).

INSERT: walk down the chain, insert when the next key is larger (or replace if equal).
SEARCH: walk until key found or a larger key encountered (early termination for absent keys).
DELETE: same search then removal.

Performance: Rebind and fresh insert take the same expected time (both stop at the sorted position). Requires keys to be comparable.

Variant 3: Push on Head, Tombstone Deletion

INSERT: always push on the head, regardless of whether the key already exists.
DELETE: push a tombstone entry on the head (key with NIL payload).
SEARCH: walk until the first match for the key is found (ignoring tombstones, or returning NIL if the newest entry is a tombstone).

Performance: INSERT and DELETE are $\Theta(1)$ . SEARCH is $O(I + D)$ where $I$ and $D$ are the total numbers of insert and delete calls — grows without bound. Best for read-only tables or where the table is rebuilt periodically.

Variant 4: Push on Head, Delete from List

INSERT: push on the head.
DELETE: walk the list and remove the first matching key.
SEARCH: walk until first match.

Performance: INSERT: $\Theta(1)$ . SEARCH and DELETE: $O(I)$ where $I$ is the number of insert calls. When a key is deleted, its previous binding “comes back to life,” giving stack-like semantics per key.

Load Factor and Performance

The load factor $\alpha = n/m$ is the average chain length. Under the simple uniform hashing assumption (each key equally likely to hash to any slot), the expected chain length is $\alpha$ , and:

Unsuccessful search: traverse the entire chain, expected $\Theta(1 + \alpha)$ .
Successful search: traverse roughly half the chain, expected $\Theta(1 + \alpha/2) = \Theta(1 + \alpha)$ .

If $\alpha$ is bounded by a constant (by resizing when it exceeds a threshold, say $0.75$ ), all operations are $O(1)$ expected.

Worst Case

All $n$ keys could hash to the same slot. Then each chain is length $n$ , and all operations become $\Theta(n)$ . This requires either a pathological hash function or an adversarial input. Universal hashing (see later note) protects against the latter.

Example

Hash table with $m = 5$ slots, using $h(k) = k \bmod 5$ . Insert 13, 27, 42, 8, 33:

Slot 0: [ ]
Slot 1: [ ]
Slot 2: 42 → 27
Slot 3: 33 → 13 → 8
Slot 4: [ ]

Search for 27: hash to 2, walk list: $42 \neq 27$ , $27$ found. Search for 50: hash to 0, walk: NIL, absent. Load factor $\alpha = 5/5 = 1.0$ .

Summary

Variant	INSERT	SEARCH	DELETE	Notes
Unsorted, append	$O(1+\alpha)$	$O(1+\alpha)$	$O(1+\alpha)$	Rebind faster than fresh
Sorted	$O(1+\alpha)$	$O(1+\alpha)$	$O(1+\alpha)$	Needs comparable keys
Push on head, tombstone	$\Theta(1)$	$O(I+D)$	$\Theta(1)$	SEARCH degrades
Push on head, remove	$\Theta(1)$	$O(I)$	$O(I)$	Stack semantics per key
Load factor	$\alpha = n/m$	Expected $O(1)$ if $\alpha = O(1)$