Buckets hold keys, not guarantees
A hash table for a set of keys must answer membership queries without confusing keys that share a hash value. In separate chaining, a function maps each key to one of buckets, and each bucket stores a list of its keys.
Definition 5.1.1
(Separate-chaining table and load factor)
A separate-chaining table with hash function and buckets stores a set of distinct keys so that each stored key lies in exactly one list, the list of bucket . Its load factor is .
- Search computes the bucket, then compares the query with the keys of that list until a match is found or the list ends.
- Insert first checks whether the key already exists; if not, it adds it to its bucket.
- Delete removes the matching key from the list.
Thus the structure represents a set of distinct keys, even when collisions occur.
Assume evaluating , comparing two keys, and accessing a bucket each take constant time; count one comparison per visited key. Linked-list deletion also requires maintaining a reference to the preceding node or an equivalent link.
A concrete table
Worked example 5.1.2
(Five keys in five buckets)
Let , , and insert in that order, appending to each bucket. The nonempty lists are
Searching for visits bucket and makes two key comparisons; searching for absent visits bucket and also makes two. Deleting leaves in bucket and does not affect the reachability of . Colliding keys are not equal keys, so the search must actually compare them.
Common mistake
(Treating a shared bucket as an equal key)
In the table above, and both have hash value . A search that stopped as soon as the bucket was nonempty would answer that is present, although the list of bucket is . Equal hash values only say where to look; membership is decided by comparing the query with the stored keys, which is why the search above makes two comparisons before reporting absence.
Counterexample mode
Average load is not a worst-case bound
The load factor is the average number of stored keys per bucket, not a bound on every bucket. For the same remainder hash, keys all enter bucket when : the load factor is but that list has length . For every , use the remainder hash modulo and insert . The load stays while one chain has keys; an absent query makes comparisons. A deterministic hash and a small average load alone do not establish constant worst-case lookup.
A collision assumption and its consequence
Definition 5.1.3
(Family with a pairwise collision bound)
A finite family of functions from the keys to buckets has the pairwise collision bound if, for every pair of distinct keys ,
where is chosen uniformly from .
Choose uniformly from such a family, once, before any key is stored. Fix a set of distinct keys and a query independently of the random choice of .
Theorem 5.1.4
(Expected search cost under the pairwise collision bound)
Let be chosen from a family with the pairwise collision bound, and let and be fixed independently of . Then the expected number of key comparisons in a chained table holding is at most
- for an unsuccessful search, ;
- for a successful search, .
Under the stated cost assumptions an unsuccessful search takes expected time .
Proof
(Count the keys that share the bucket of the query)
Let and let be the number of keys of in the searched bucket. By linearity of expectation,
An unsuccessful search compares exactly those keys, and the other work (computing , reaching the bucket) is constant, so the expected time is .
For the searched list has length
The same assumption, applied to the keys , bounds its expected length by . A successful search visits no more keys than the full list, whatever the order of the list, so its expected comparison count is at most that quantity.
Proof X-ray
What the linearity argument uses
Only two facts enter: the pairwise bound on each and linearity of expectation, which adds such bounds with no condition on how the events depend on one another. The assumption that and were fixed independently of is what allows the pairwise bound to be applied to each pair. In the successful case the extra is the query key itself, which is always in its own list. The expectation is over the choice of , so the theorem says nothing about the worst chain of a particular table; the counterexample above shows that one table can have a chain of length .
Keeping bounded therefore gives an expected constant lookup bound in this model. If a set or query is selected adaptively after observing the hash function, the fixed-input argument above does not automatically apply. Resizing and rehashing have their own costs and are not analyzed here. The lists and bucket array use space.
Worked example 5.1.5
(Exact expected chain length for a tiny family)
Take three possible keys , two buckets, and let be all functions from the keys to the two buckets. For two distinct keys the hash values agree in exactly half of the functions, so the collision probability is and the family has the pairwise collision bound. Store and search for , so , , .
If , the number of stored keys in bucket is for the four choices . The case is symmetric. So takes the values in each half, and
The bound holds with equality, and individual tables differ: one has a chain of two keys, another has an empty chain.
Worked example 5.1.6
(One bucket and the empty table)
With every function sends all keys to bucket , so any family has collision probability and the pairwise bound holds trivially. A table with keys is then a single list, an unsuccessful search makes comparisons, and : the bound is attained and the table is just a linked list.
For the empty table, , every list is empty. A search computes , finds an empty list and makes no key comparison, so its cost is only the constant work of hashing and reaching the bucket. This agrees with at .
Common mistake
(Drawing a new hash function after the keys are stored)
The expected bound refers to one random choice of made before insertion. If a new is drawn when a query arrives, the stored keys still sit in the lists of the old function . With the table above, a key stored in bucket may be looked up in the bucket and reported absent. A new function is legitimate only if every stored key is moved to the bucket given by the new function.
Exercises with solutions
Quick check
(Bucket trace. In the concrete table, what bucket is searched for and how many comparisons are needed if it is absent?)
Solution · Answer
Since , bucket is searched. It contains , so there is one comparison.
Quick check
(A guaranteed collision. If for distinct keys, may the table discard one?)
Solution · Answer
No. Both keys remain in the list and equality comparisons distinguish them.
Quick check
(Expected count. Under the stated collision bound, what upper bound applies to expected unsuccessful comparisons for ?)
Solution · Answer
At most for a fixed absent query and fixed set independent of .
Quick check
(Assumptions. Does the proof need the collision events for different to be mutually independent?)
Solution · Answer
No. Linearity of expectation and the individual probability bounds suffice.