Motivation
Randomized data structures often assume that distinct keys collide with small probability. An analysis based on that assumption is incomplete unless a suitable hash family can be constructed and its sampling cost understood. A simple affine construction over binary vectors gives uniformly distributed, pairwise-independent hash values using a finite random seed.
Pairwise independence is weaker than full independence of all hash values, but it is enough for many expected-collision calculations. We prove the family property, apply it to a hash table and a collision union bound, and state where the fixed-input assumption matters.
Definitions
Let the key universe be and the bucket set be , with integers . Arithmetic is over the two-element field . Choose a uniformly random binary matrix and an independent uniformly random vector . Define
The seed consists of independent fair bits. A bucket is a -bit vector, so there are possible buckets.
Consider a hash family such that, for any distinct keys and any outputs ,
A family satisfying this condition has pairwise-independent uniform outputs.
This implies each output is uniform and the collision probability is . It does not claim that three or more outputs are jointly independent.
Theorems
Theorem 10.1.1
(Affine binary hash family)
The family has pairwise-independent uniform outputs for distinct binary keys. It uses fair seed bits and can be evaluated using elementary bit operations by direct matrix multiplication.
Theorem 10.1.2
(Expected collisions in a fixed key set)
For any fixed set of distinct keys chosen independently of the random hash function, the expected number of other keys colliding with a specified key is . The probability that any pair in the set collides is at most .
Proof: one row of the matrix
Proof
(Pairwise independence of the affine family)
Fix distinct and put . Since , some coordinate equals one. For one uniformly random row vector of , the dot product is a fair bit: after fixing all other coordinates of , toggling toggles the dot product. Thus
is a uniform -bit vector, because the matrix rows are independent.
The offset is uniform and independent of . Conditional on any , is uniform. Consequently, for any prescribed , first require , which has probability , and then require , which has conditional probability . The joint probability is .
Summing the joint probability over the equal output pairs gives collision probability . The offset also makes each single output uniform, including for the zero key.
Proof X-ray
The offset supplies uniform values
Where each hypothesis enters: is used exactly once, to find a coordinate with ; without it would be zero and the keys would always collide. The key move is to split the pair of outputs into the difference , made uniform by the random matrix, and the location , made uniform by the independent offset. Independence of the rows of makes the bits of independent, and independence of from lets the two factors multiply. The argument involves only the pair , so it proves pairwise independence and nothing about three keys; the four-key relation in the counterexample shows that a stronger claim would be false.
Proof: fixed-set collision bounds
Proof
(Expected collisions and the union bound)
For a fixed key in a fixed set of distinct keys, let indicate that collides with . The number of colliding other keys is . Every indicator has expectation , so linearity gives expectation . The indicators need not be mutually independent.
For any unordered pair of distinct keys, collision probability is . There are pairs. A union bound gives probability at most that at least one pair collides. If this quantity exceeds one, the inequality is still true but gives no useful probability estimate.
The set and query are fixed independently of the hash seed. If an adversary sees the chosen function and then selects keys designed to collide, the same fixed-set probability statement cannot be applied without further analysis.
Worked examples
Worked example 10.1.3
(One output bit)
For , let the random row be and the offset be . For keys and , the outputs are and . They collide exactly when , with probability .
Worked example 10.1.4
(Expected chain length)
For a fixed set of keys hashed into buckets by any family with the same collision bound, a specified stored key has at most other colliding key in expectation. The binary construction itself has power-of-two width, so this numerical example illustrates the collision theorem rather than claiming it uses with .
Worked example 10.1.5
(A union bound can be loose)
For and , the union bound on at least one collision is . It need not equal the true collision probability, because collision events for different pairs can overlap.
Worked example 10.1.6
(The zero key still has a random output)
Without an offset, for every matrix. With the independent offset, is uniform over the buckets. The offset is essential for uniform single-key outputs.
Common mistakes
Counterexample mode
Pairwise independence is not full independence
For the four two-bit keys and any affine binary hash function, the sum of their outputs is zero: the matrix terms and offset each occur an even number of times. Thus the four outputs satisfy a deterministic relation and are not jointly uniform, even though any two distinct outputs are pairwise independent.
Common mistake
(A small expectation does not bound every seed)
An expected collision count is not a guarantee that every seed has a short chain. Some sampled functions can have many collisions; for example, maps every key to . A high-probability bound needs an additional argument and may be weaker than a claim of full randomness.
Common mistake
(Evaluation time is not seed size)
The expression counts elementary bit operations in direct evaluation. A machine-word implementation may evaluate faster for certain dimensions, while storing the seed still costs bits. The theorem does not promise a constant-size seed independent of the key length.
Concept lensAlgebraic
Pairwise independence as surjectivity of a linear map
The seed is uniform on , and is -linear into . For it is onto, because and can be prescribed independently, and a uniform input through an onto linear map gives a uniform output. For the four keys the image lies in the subspace where the outputs sum to zero, so that map is not onto.
Application: chaining
Store each key in the list associated with its hash bucket. For a fixed stored query key , the number of items inspected by a straightforward scan is at most one plus the number of other stored keys in its bucket. Its expectation is therefore at most , apart from the cost of computing the hash and comparing keys.
For a fixed query not in the stored set, the expected number of stored keys in its bucket is , so an unsuccessful scan inspects that many keys in expectation. These statements assume the stored set and query are fixed before the random seed is chosen. They count list items; comparing two -bit keys and evaluating the hash have their own costs.
If is comparable to , the expected number of inspected list entries is constant. This is an average over hash seeds for a fixed input, not a worst-case bound on the length of every bucket. The collision union bound is stronger in a different direction: it controls whether any pair collides, but may require a much larger to be small.
An adaptive choice can force a collision
Suppose and the adversary sees the sampled matrix . The linear map has a nonzero kernel vector , because a map from a -dimensional binary vector space to a -dimensional one cannot be injective. The adversary can choose and . Then
with certainty. This does not contradict the theorem: the key was selected after seeing , so the pair was not fixed independently of the seed. For a fixed nonzero , the probability over a fresh random matrix that is still .
The example also shows why a public hash seed and an adaptive adversary require a model beyond the elementary fixed-key analysis. Depending on the application, one may need secret randomness, periodic rebuilding, stronger assumptions or a different data structure. No such adaptive guarantee follows merely from pairwise independence.
From expectation to a tail bound
Let be the number of other stored keys colliding with a fixed stored query. Since , Markov's inequality gives, for any integer ,
This follows from and the expected-collision formula. The bound can be loose, but it is valid without assuming the collision indicators are independent. In particular, constant expected chain length does not imply that the probability of a very long chain is zero.
For the entire fixed set, the expected number of colliding unordered pairs is by the same indicator argument. If this expectation is less than one, at least one seed has no collisions: otherwise every seed would have at least one colliding pair and the expectation would be at least one. This proves existence, not an efficient deterministic method to find such a seed. Exhaustively testing all seeds can be prohibitively expensive.
How the finite seed is used
The matrix contains bits and the offset contains more. Sampling all of them independently and uniformly specifies one function from the family. The same sampled function is then used for all keys in that hash table or sketch row. Resampling a fresh function for every lookup would generally change bucket assignments and would not maintain the described data structure.
To evaluate one output bit, multiply the corresponding matrix row by the input vector over and add the corresponding offset bit. Direct evaluation uses at most bit products and additions per row, hence elementary bit operations for all output bits. This count assumes the matrix and key are available explicitly. A software implementation may pack bits into words, but its actual word-operation bound depends on the machine model and word size.
Independent sketch rows can be obtained by independently sampling a seed for each row. The outputs within one row have the pairwise property proved above; outputs in different rows are independent because their seeds are independent. This distinction is useful in the Count–Min analysis, where linearity handles collisions within a row and row independence amplifies the probability that at least one row has small noise.
The four-key dependence can be checked coordinate by coordinate. Write the outputs on as , , and , where are the two columns of . Their sum over is zero. Under four fully independent uniform -bit outputs, that equality would occur with probability , not one. Pairwise independence therefore does not extend to this four-key collection.
The collision union bound is sometimes called a birthday-style estimate: there are quadratically many pairs, even though each individual collision has probability only . For instance, ensuring the displayed bound is at most requires . By contrast, keeping the expected number of collisions with one fixed key below a constant needs only proportional to . These are different guarantees and should not be interchanged. If the pair bound exceeds one, replacing it by one gives a valid but trivial probability upper bound; it does not mean the probability itself exceeds one. The bound is useful only when its numerical value provides information below that trivial limit.
Summary
A random binary matrix and offset produce uniform pairwise-independent hash outputs with an explicit finite seed. Pairwise collision probabilities give expected chain lengths and a union bound for fixed key sets, without requiring full independence among all keys.
Exercises
Quick check
(For , how many buckets are there and what is the collision probability of two fixed distinct keys?)
The number of buckets is .
Solution · Answer
There are buckets and the collision probability is .
Quick check
(Why is nonzero when over binary vectors?)
Over , what does say?
Solution · Answer
Over , would imply . Thus distinct keys differ in at least one coordinate and their sum has a one there.
Quick check
(For stored keys and buckets, what is the expected number of other keys colliding with a fixed stored key?)
Add the collision indicators of the other keys.
Solution · Answer
It is under the stated pairwise-uniform family.
Quick check
(Why does the expected-collision proof not require the collision indicators to be mutually independent?)
Which property of expectation holds for every finite sum?
Solution · Answer
Expectation distributes over a finite sum regardless of dependence. The individual collision probability for each other key is enough.