A dictionary must distinguish keys even when their values happen to be equal. A hash table first converts a key into a small bucket index, then resolves the ambiguity inside that bucket. The conversion is useful precisely because there may be far fewer buckets than possible keys. Consequently, collisions are unavoidable in general; a correct design must handle them rather than assume that they never occur.
Separate chaining makes the correctness argument particularly clear. Every bucket holds a linked list of entries, and a lookup compares the actual keys along that list. The performance argument is a different matter. We will see why load factor alone does not guarantee short chains, then prove an expected bound by choosing the hash function from a suitable random family.
The bucket is a location, not the identity of a key
Definition 16.1.1
(Chaining invariant and map operations)
Let be a fixed hash function, with buckets. Each stored entry is a key-value pair. The chaining invariant requires:
- every stored key occurs exactly once, in bucket ;
- its entry stores the value currently associated with ;
- each bucket is a finite, acyclic linked list.
get(x) returns the value associated with , or reports that the key is absent. put(x,v) replaces an existing key's value, or adds a new entry if is absent. erase(x) removes that key if present. Distinct keys may have the same bucket index without violating the invariant.
Lookup computes and searches just that chain. If it finds an equal key, uniqueness identifies the required value. If it reaches the end, the key is absent: the invariant forbids an entry with that key in any other bucket. Comparing only the bucket index would discard exactly the information needed to distinguish colliding keys.
Insertion first searches for an existing key. If found, change its value without adding an entry or changing the stored-key count. Otherwise prepend a new entry to the selected chain. Deletion unlinks the matching entry by changing either the bucket head or the preceding entry's next pointer. No other entry changes its key or bucket. These local changes preserve the invariant.
Follow a collision without losing a key
Worked example 16.1.2
(Three different keys, one chain)
Use five buckets and
for integer keys from 0 to 16. The two modular reductions are separate steps:
| Key | Bucket | |
|---|---|---|
Insert (0, "A"), (5, "B"), (9, "C") by prepending new entries. Bucket 1 becomes
head -> (9, "C") -> (5, "B") -> (0, "A") -> end
get(5) compares 9 and then 5, returning "B". put(5, "B2") changes that entry's value and leaves the size at three. It must not prepend a second entry for 5.
Now erase(5) makes the entry for 9 point directly to the entry for 0. Both remaining keys are still reachable. An unsuccessful get(13) searches those two entries before reporting absence. It cannot return either one's value merely because 13 also hashes to bucket 1.
Unlike an array's live length, a chain's length can exceed one while all entries remain valid. Removing a middle list node also leaves no gap that must be marked: the list link now bypasses it. These statements concern separate chaining; a table that probes alternative array positions has a different search invariant.
Common mistake
(Prepending without searching first)
If put(5, "B2") simply prepended a new entry, bucket 1 would hold (5, "B2") -> (9, "C") -> (5, "B") -> (0, "A"): two entries for one key. A later erase(5) would unlink only the first of them, and the stale value "B" would reappear in get(5). The chaining invariant allows each key at most once, so insertion must search the chain before it prepends.
What load factor tells us, and what it does not
For stored keys, define the load factor by . Since the chain lengths sum to , their average over buckets is exactly . This arithmetic fact does not say that the chain chosen by a particular query is short.
Counterexample mode
A small average does not bound the queried chain
Consider the deterministic rule . Keys all occupy bucket 0; four other buckets are empty. The load factor is , but an unsuccessful query for 20 compares all four entries. Prepending more distinct multiples of five keeps extending that same chain.
In general, if all stored keys occupy the queried bucket, a lookup can take comparisons. The average across buckets is still . A useful expected-time claim therefore needs an explicit source of randomness and a collision guarantee; it does not follow from the definition of load factor.
State exactly what randomness guarantees
Definition 16.1.3
(A universal hash family)
A finite indexed family of functions from to buckets is universal if, for every two fixed distinct keys ,
The randomness is in the selected function. The keys in this statement are fixed independently of that choice. A universal family need not forbid collisions for each selected function. Family members are indexed parameter choices; different indices may happen to define the same bucket function.
Choose the function once and keep it fixed while the entries remain in their buckets. The expectation below averages over that initial choice, not over the keys' values or a random ordering of chain entries.
Common mistake
(Drawing a fresh hash function for every operation)
The expectation below is over one random choice, made before any entry is stored. Drawing a new function for each lookup breaks the invariant: key 0 was stored in bucket , and a lookup that searches bucket will usually miss it. Changing the function is legitimate only together with rehashing every stored entry.
Theorem 16.1.4
(Expected chain length under a universal family)
Let be a universal family into buckets, and let be chosen uniformly from it once. Let be a set of stored keys and a key, both fixed independently of . In a chained table, a lookup of compares
- at most keys in expectation if ;
- at most keys in expectation if .
Proof
(Count colliding keys with indicators)
Suppose first that . For each , let
The number of entries in the queried chain is . Linearity of expectation and universality give
An unsuccessful lookup compares exactly these keys. Hash computation and bucket access add constant work, so expected running time is , assuming constant-time key hashing and comparison.
Now suppose . The same argument over the keys shows that the expected number of other keys in the bucket of is at most . Even if the entry for is last in its chain, the lookup stops there, so it makes at most one comparison plus one for each of those keys:
Proof X-ray
What the indicator argument uses
Three ingredients appear, each exactly once. Universality bounds each single pair by . Linearity of expectation adds these bounds. The fixedness of and , chosen before , is what lets the universality inequality apply to every pair at all. The indicators need not be mutually independent, since linearity does not ask for it. If the keys were chosen after inspecting , say keys all in one bucket, the chain would have length and the bound would fail, as in the counterexample above.
The searches performed by put and erase obey the corresponding bounds; their pointer or value updates then take constant time. A selected function can still produce a long chain, so worst-case lookup remains linear. Also, keys deliberately chosen after inspecting that function do not satisfy the independence assumption used in this proof.
Construct a universal family with a prime modulus
Let be prime, choose , and restrict keys to the integers . Select uniformly from and uniformly from , independently. Define
The first stage works in the field . The second groups its possible outputs into buckets. To prove the collision bound, we must understand two distinct keys together, rather than merely show that one output is spread out.
Theorem 16.1.5
(The affine family modulo a prime is universal)
Let be prime and . Choose uniformly from and uniformly from , independently, and set on keys . Then for all distinct keys ,
Proof
(Count distinct field-output pairs, then bucket collisions)
Fix in . For desired field outputs , the equations
have the unique solution
in . The inverse exists because is prime and is nonzero. This solution has . Conversely, a nonzero cannot map distinct to equal field outputs.
Thus the equally likely choices of give each ordered distinct pair exactly once. Conditional on a first output , the second output is uniform among the other residues. These two field outputs are distinct, so they are not independent.
After reducing modulo , each bucket contains at most field residues. Once is fixed, at most of the other residues share its bucket. Therefore
The bound does not require to be divisible by , nor does it require the final bucket probabilities to be exactly equal.
Proof X-ray
The change of variables from parameters to outputs
The key move is to stop treating as the random object and to look at the output pair instead: the map is a bijection from the parameter pairs onto the ordered pairs of distinct residues. Primality is used once, to invert . The restriction matches exactly, which is why ranges over all residues but does not. The final reduction modulo is the only place where the bound can lose: it counts at most residues sharing a bucket with . If and were equal in , there would be no solution at all for , as the next counterexample shows.
Worked example 16.1.6
(The exact collision probability need not equal the bound)
Take , , and fixed keys 0 and 1. There are choices of , corresponding to all ordered distinct field-output pairs.
Bucket 0 contains field residues ; bucket 1 contains . The number of ordered distinct pairs in one bucket is
The exact collision probability is , which is at most . A single field output is uniform among five residues, but its bucket probabilities are and , not one half each. Universality supplies the collision inequality needed by the indicator proof; exact uniformity of bucket outputs is unnecessary.
Counterexample mode
The key domain is part of the theorem
If a program treats 0 and 17 as distinct keys but applies the family with , then and are equal modulo 17 for every parameter choice. Those keys collide with probability one, regardless of how are selected.
There is no contradiction: they are the same element of and violate the theorem's distinct-field-key assumption. The implementation must use an injective representation of its permitted keys in the field, or supply a different justified hash construction. Likewise, the proof uses primality to obtain inverses; arbitrary composite moduli cannot simply replace in that argument.
Worked example 16.1.7
(One bucket and the empty table)
Take . Every function into one bucket is the constant function, so any family is universal, because and a collision probability is at most 1. Every key lies in bucket 0, so with stored keys an unsuccessful lookup compares all of them. Here , so the expected bound of the theorem is attained with equality, and the table has degraded to a single linked list.
At the other end take the empty table, . A lookup computes , reaches an empty chain and compares no keys, so its cost is the constant for hashing and bucket access. This agrees with at : the in the bound is not optional.
Implement the map invariant directly
The following implementation accepts integer keys in . Its constructor assumes that prime really is prime; primality testing is outside this small dictionary example. Parameter ranges are checked, but the code does not randomly select parameters. Passing (17, 5, 3, 1) reproduces the deterministic worked trace. To use the expected bound, choose the parameters with the uniform distribution specified above, independently of the input keys.
class Entry:
def __init__(self, key, value, next_entry):
self.key = key
self.value = value
self.next = next_entry
class ChainedMap:
def __init__(self, prime, bucket_count, a, b):
if not (1 <= bucket_count <= prime and
1 <= a < prime and 0 <= b < prime):
raise ValueError("invalid hash parameter range")
self.prime = prime
self.a, self.b = a, b
self.buckets = [None] * bucket_count
self.size = 0
def _index(self, key):
if not isinstance(key, int) or not 0 <= key < self.prime:
raise ValueError("key outside the integer field domain")
return ((self.a * key + self.b) % self.prime) % len(self.buckets)
def get(self, key):
node = self.buckets[self._index(key)]
while node is not None:
if node.key == key:
return node.value
node = node.next
raise KeyError(key)
def put(self, key, value):
index = self._index(key)
node = self.buckets[index]
while node is not None:
if node.key == key:
node.value = value
return False
node = node.next
self.buckets[index] = Entry(key, value, self.buckets[index])
self.size += 1
return True
def erase(self, key):
index = self._index(key)
previous = None
node = self.buckets[index]
while node is not None:
if node.key == key:
if previous is None:
self.buckets[index] = node.next
else:
previous.next = node.next
self.size -= 1
return True
previous, node = node, node.next
return False
Keep prime, a, b, and the bucket count unchanged while entries remain stored. Changing the function or bucket count requires redistributing every entry according to the new indices; otherwise lookup's invariant fails. Stored entries use space, bucket heads use , and initialization takes time.
With bounded load factor and the stated randomness and word-arithmetic assumptions, the expected operation cost is constant. Keeping the load factor bounded as the table grows requires a resizing and rehashing policy. Rebuilding the whole table is an additional operation whose sequence cost needs its own analysis; the fixed-state expectation proved here does not make rebuilding constant-time.
Exercises and worked solutions
Quick check
(Update a colliding key without creating a duplicate)
Using the five-bucket worked example, insert (0, "A"), (5, "B"), (9, "C"), update 5 to "B2", and erase 9. Give bucket 1's final chain, the size, get(5), and the number of key comparisons in an unsuccessful get(13).
Solution · Answer
The final chain is (5, "B2") -> (0, "A") -> end. Updating 5 changes only its value; erasing the head 9 changes the bucket-head pointer. The size is two, get(5) returns "B2", and get(13) compares both remaining keys before reporting absence.
Quick check
(Apply the expected comparison bounds)
A fixed set of 1,000 keys occupies 250 buckets under a uniformly chosen universal hash function. Give the upper bound for expected comparisons in a fixed absent query, and the corresponding bound for a fixed present query. Are these bounds on every individual run?
Solution · Answer
The absent-query bound is . The present-query bound is . Hash computation adds separate constant work. These expectations are over the hash-function choice, with keys and query fixed independently of it. A particular choice may still produce a much longer chain, so the bounds do not hold for every individual run.
Quick check
(Identify the assumption in the indicator proof)
Must the collision indicators for different stored keys be mutually independent? What assumption on the fixed query and stored keys is actually used when applying the universality inequality?
Solution · Answer
Mutual independence is unnecessary because expectation is linear for any finite sum. Each distinct key pair must satisfy its own collision-probability bound. The stored-key set and query are fixed independently of the random hash choice. Choosing keys adaptively after learning that choice requires a different argument.
Quick check
(Explain a collision that happens for every parameter choice)
With prime 17, why do integer keys 2 and 19 always have the same field output? Which hypothesis must change before the universal-family theorem can be applied to a dictionary that distinguishes them?
Solution · Answer
Their difference is 17, so for every . They represent the same field element. The theorem requires distinct permitted keys to have distinct field representations, for example by choosing a prime larger than every key in a finite nonnegative integer domain. Merely changing the random seed does not fix this domain violation.
Quick check
(Count exact collisions in the small family)
For and distinct fixed keys, explain why there are eight colliding parameter choices out of twenty. Does the fact that a single bucket has probability violate universality?
Solution · Answer
The affine choices enumerate all ordered distinct field-output pairs once. Three residues belong to bucket 0, contributing pairs; two belong to bucket 1, contributing . Thus eight choices collide and the probability is . Universality restricts the collision probability for two distinct keys; it does not require every individual bucket to have probability exactly .
Quick check
(Changing parameters changes where lookup must search)
Store key 0 using . Without moving entries, change the parameters to . Where is key 0 physically stored, and which bucket would the new lookup search? What operation is missing?
Solution · Answer
The entry is still physically in bucket 1, its old index. The new function sends 0 to bucket 0, so lookup would incorrectly report absence. Every stored entry must be rehashed into its new bucket when the parameters change. A mathematically valid new hash function alone does not preserve an old table's representation invariant.