Motivation
A hash table sends a large key universe into a smaller set of buckets. No such mapping can avoid every collision when the universe has more keys than buckets. Yet if the set of keys is fixed before a hash function is sampled, a carefully chosen random family can make each particular collision unlikely.
We construct such a family from affine maps over a prime field. The reduction from field elements to bucket numbers makes the bucket sizes slightly unequal when the number of buckets does not divide the prime. The proof accounts for that imbalance exactly. It also shows why a guarantee for fixed keys cannot be reused unchanged after an adversary sees the chosen hash.
Definitions
Definition 5.2.1
(A random affine map followed by bucket reduction)
Fix a prime and an integer . The key universe is , identified with . Independently choose uniformly from and uniformly from . Define
where the first remainder is represented by its integer in . The output is a bucket in .
A set of distinct keys is fixed independently of the random seed . An unsuccessful query key is also fixed independently of that seed when its expected chain length is analyzed. The probability statements are over the stated random choice of seed.
For a bucket j, let be the number of integers in congruent to j modulo m. Some buckets can be empty if . Quotient and remainder show that every nonempty or empty bucket size is either or .
Theorem/Proposition
Theorem 5.2.2
(A universal collision bound)
For any two distinct fixed keys ,
This holds for every , including . The bucket outputs of two keys need not be independent or individually uniform over all m buckets.
Theorem 5.2.3
(Expected collisions and chaining)
For a fixed set of distinct keys, let be the number of unordered colliding pairs. Then
For a fixed , its expected bucket occupancy is at most . For a fixed query , its expected bucket occupancy is at most .
Proof sketch or proof idea
Two distinct field images are uniformly distributed
Proof
(Two distinct keys give a uniform pair of distinct field images)
For fixed distinct , consider prescribed distinct field elements . The equations
have the unique solution and in . Both differences are nonzero, so the resulting is allowed. Conversely every allowed seed gives distinct images because multiplication by nonzero a is injective.
There are equally likely seeds and the same number of ordered distinct pairs . Thus is uniform over those pairs. In particular each individual field image is uniform, but the pair is not independent: the two images can never be equal. The prime-field divisions are valid because ; the construction would not have this proof for arbitrary composite moduli.
Unequal bucket sizes still give the stated bound
Proof
(Counting the common bucket)
Condition on the first field image being u. The second is uniformly distributed among the other elements. If u lies in a bucket of size c, exactly c−1 choices collide with it, so the conditional collision probability is .
Every bucket has size at most , and
Therefore the conditional probability is at most , for every u. Averaging over u proves the collision bound. When , every occupied bucket contains one field element, so the collision probability is actually zero. When , the bound is one and every pair collides.
Proof X-ray
Conditioning uses distinct field images, not independent buckets
After the first field image is fixed, the second ranges over the other p−1 field elements. Counting the other members of the first image's bucket gives the bound even when bucket sizes differ. Independence of the bucket outputs is neither assumed nor needed.
Count pairs by indicators
Proof
(Expected pair counts and bucket occupancy)
For each unordered pair of distinct keys in S, use an indicator that equals one exactly on collision. Their sum is X. Linearity of expectation, which does not require the indicators to be independent, gives the displayed expectation. The event is covered by Markov's inequality for the nonnegative integer X, and a probability is never greater than one.
For a fixed key , the occupancy of its bucket is one plus the collision indicators between x and each of the other keys. For a fixed query outside S, it is the sum of its collision indicators with all stored keys. The same pair bound and linearity give the two occupancy estimates. The argument includes for an outside query; there is no inside key to select when S is empty.
Concept lensCombinatorial
Collision probability as a count of ordered pairs
Seeds correspond bijectively to ordered pairs of distinct field elements. So for every pair of distinct keys the collision probability is exactly the fraction of such pairs lying in one bucket:
For , the bucket sizes are , giving . The bound comes from comparing this seed-free count with the largest possible bucket size.
Worked examples
Worked example 5.2.4
(A concrete affine table)
Let , , and . The keys map to buckets , respectively. There is one colliding unordered pair, namely keys 1 and 3. For this fixed four-key set the theorem bounds the expected pair count over all seeds by ; the bound is an average over seeds, not a claim that this particular seed has two collisions.
Worked example 5.2.5
(More buckets than field elements)
With and , the second remainder leaves every field representative unchanged. Every allowed affine map is a permutation of , so distinct keys never collide. Buckets 5, 6 and 7 are empty. The general upper bound is valid but not sharp.
Worked example 5.2.6
(A fixed unsuccessful query)
Let , let a fixed set contain keys and use buckets. For any fixed query key outside the set, the expected number of stored keys in its bucket is at most two. For an unsuccessful query, a simple chain scan therefore uses at most two key comparisons in expectation. Some seeds can still give a longer chain; the expectation is not a worst-case bound for every seed.
From a collision bound to randomized retries
After sampling a seed for a fixed set, insert its keys into buckets and check whether any bucket contains more than one key. If not, the mapping is injective on S. This check can be implemented by initializing m counters and scanning n keys in bucket operations, apart from the cost of computing hashes and sampling the seed.
For , if , the collision probability is at most one half. Independently resample a fresh seed after each failure. The chance that the first t attempts all fail is at most , and the expected number of attempts is at most two: the tail-sum formula gives as an upper bound. For every seed is already injective on S.
This is a construction with a checkable success condition, not a deterministic worst-case bound on the number of trials. It also does not say that a collision-free table using buckets is always the most space-efficient choice. If seeds are sampled with a bounded fair-bit budget and possible abort, the effect of that sampling procedure needs its own analysis.
Dependence remains after bucket reduction
With and , bucket zero contains representatives , while buckets one and two contain two representatives each. For distinct fixed x,y, the probability that both field images fall in bucket zero is
Each individual output is zero with probability , whose product is , not . The two bucket outputs are therefore not independent in this example, and they are not uniform over the three buckets. Nevertheless their collision probability satisfies the proved upper bound. Universal pair-collision control is weaker than a claim of independent uniform bucket outputs.
If a were instead chosen uniformly from all of , including zero, the two field images of distinct keys would be independent uniform field elements: the same two equations have one solution for every ordered pair, including equal pairs. After reduction their bucket outputs would be independent but generally nonuniform. For the resulting collision probability is . Thus including the zero multiplier changes the collision guarantee for this reduction.
Query cost and the fixed-input condition
With separate chaining, a successful search for fixed compares against no more keys than the occupancy of its bucket. An unsuccessful fixed query outside S compares against at most the occupancy of that bucket. The expected comparison bounds therefore follow from the theorem, in addition to computing the hash itself. A successful scan may stop earlier; no assumption about the order within a chain is needed for this upper bound.
These expectations do not automatically apply to a set or query chosen after seeing the seed. For a concrete contrast, let and . Every map from seven keys into three buckets has some bucket with at least three keys. An observer who first sees the chosen hash can select any three keys in such a bucket. All three pairs then collide, so X is always three for this seed-dependent choice. The fixed-set theorem for instead has upper bound one on the expected pair count. There is no contradiction: its set must be independent of the seed.
Counterexample mode
A collision expectation is not an individual worst case
A tempting claim: a fixed three-key set has expected pair count at most one, so any three keys we pick produce at most one colliding pair. This fails when the keys are chosen after the seed. Take , , , , so on . The keys all land in bucket zero and , even though the theorem gives for a set fixed before the seed. Markov's bound likewise controls only the probability of at least one collision for a fixed set; it can equal the trivial bound one, and it does not say that every seed is collision-free.
Computational scope
The construction assumes a supplied prime p and keys represented by field elements; it does not prove that finding a suitable prime is free. It also assumes the prescribed uniform sampling of and . A simple word-operation model can treat field and remainder operations as elementary when the represented values fit the word model. With arbitrary binary-encoded p and m, modular multiplication, division and seed generation have bit costs that must be counted separately.
Only distinct keys fit the set model. Repeated occurrences of the same key always hash together and should be accounted for as multiplicity or as stored records under a separate convention. The collision guarantee concerns distinct input keys, not accidental equality of two representations of the same key.
Common mistakes
Common mistake
(Reading a pair-collision bound as independent uniform outputs)
For , and distinct fixed keys, both outputs are bucket zero with probability , yet each output is bucket zero with probability and . The outputs are neither independent nor uniform over three buckets, especially when does not divide . Only the collision probability is controlled, by .
Common mistake
(Letting the multiplier be zero)
If were allowed to range over all of , the two field images would become independent uniform elements and the collision probability would be . For , this is , so the bound fails. The exclusion is part of the proof.
Common mistake
(Taking the expected chain length for the realized one)
The bound is an average over seeds for a query fixed in advance. With , , and the outside query , the expected number of stored keys in the query's bucket is at most , but the seed , puts both stored keys in the query's bucket, so the scan compares against two keys.
Summary
A nonzero affine multiplier sends two distinct fixed keys to a uniform ordered pair of distinct field elements. Counting their possible common remainder bucket proves collision probability at most , even with uneven buckets. Linearity yields expected pair counts and chain occupancy; a check and independent retries give a collision-free fixed-set construction with controlled expected attempts. Every such probability statement depends on the seed and key-selection model.
Exercises
Quick check
(For , list the buckets of keys 0, 1, 2 and 3 and count colliding pairs.)
Solution · Answer
The outputs are . Keys 0 and 2 form one colliding pair, and keys 1 and 3 form another, so there are two pairs.
Quick check
(If and , what upper bound does the theorem give for the probability of at least one collision?)
Solution · Answer
The bound is .
Quick check
(Why can the expected number of colliding pairs be bounded by summing pair probabilities without assuming that collision events are independent?)
Solution · Answer
The pair count is a finite sum of collision indicators. Linearity of expectation holds regardless of dependence among the indicators.
Quick check
(For , how many field representatives lie in each bucket?)
Solution · Answer
The representatives are , and , so the sizes are 3, 2 and 2.