Hashing, Independence & Pseudorandomness

Keys, Buckets and the Art of Controlled Collision

Imagine sorting letters into numbered mailboxes. A rule sends every address to one mailbox; if two addresses share a box, the sorter must handle a collision. A hash function does the same for data keys. Because there are often more possible keys than buckets, some collisions are unavoidable. The useful question is how likely a collision is when we choose the rule at random before seeing the keys.

For a small illustration, number four keys $0,1,2,3$ and use three buckets. The rule $h(x)=x\bmod 3$ sends them to $0,1,2,0$, so keys $0$ and $3$ collide. A different rule changes which pair collides. A hash family is a set of such rules; a seed chooses one. A guarantee describes the choice of seed for fixed distinct keys, rather than promising that every rule is collision-free. This distinction links the preceding chapter's probability bounds to practical streaming sketches: collisions create error, and the randomness assumptions determine whether we can bound its expectation, variance, or tail.

Hashing also supports distributing events, estimating similarity, and selecting samples. These uses ask for different properties. A rule suitable for low expected collisions may be unsuitable for estimating Jaccard similarity or resisting an attacker who sees its seed. Reproducibility means workers can intentionally share a seed and get the same answer; independent repetitions require different, independently chosen seeds.

The Independence Ladder

Fix a finite universe $U$ and bucket set $B$ of size $m$. Choose a random function $h$ from a family $\mathcal H$ by sampling a seed. Uniform marginals mean each fixed key's output is uniform on $B$. Pairwise independent outputs mean for every two distinct fixed keys $x,y$ and every $a,b\in B$, $\Pr(h(x)=a, h(y)=b)=1/m^2$. This implies uniform marginals and collision probability $1/m$. A universal family only needs $\Pr(h(x)=h(y))\le1/m$ for each distinct fixed pair; that weaker statement need not imply independent outputs. For $k$-wise independence, the corresponding joint uniformity holds for every set of up to $k$ distinct fixed keys. Full independence requires it for every finite set of keys, which can need far more stored randomness.

A concrete pairwise-independent family works over a prime field $\mathbb F_p$: choose $a,b$ independently and uniformly from $\mathbb F_p$, then set $h_{a,b}(x)=ax+b\pmod p$ for $x\in\mathbb F_p$. For distinct $x,y$, the map from $(a,b)$ to $(h(x),h(y))$ is bijective because $x-y\ne0$ has a multiplicative inverse modulo $p$. Thus each ordered pair of outputs has probability $1/p^2$. The seed selects one of $p^2$ functions and can be stored in $2\lceil\log_2p\rceil$ bits. That is a representation upper bound, not a claim about an arbitrary $m$-bucket reduction. Reducing these outputs modulo a nondivisor $m$ may spoil exact uniformity and the stated pairwise guarantee.

Other goals occupy different branches. Exact min-wise independence asks that for every nonempty fixed set $S$ and each $x\in S$, $\Pr(h(x)=\min_{y\in S}h(y))=1/|S|$, assuming ties are resolved by a specified rule; a uniformly random permutation has this property. Approximate min-wise families allow a quantified error, often with much shorter seeds. Tabulation hashing splits a key into characters and combines seeded table lookups; its exact independence and other useful properties depend on the construction, not its name alone. A pseudorandom generator expands a short seed into a longer deterministic sequence. Statistical limited independence is an information-theoretic property of selected outputs; computational pseudorandomness instead concerns what a bounded adversary can distinguish. Neither is automatically implied by the other.

flowchart TD
    F["Choose a function from a family"] --> U["Uniform output per fixed key"]
    F --> C["Universal: bounded pair collision"]
    P["Pairwise independent outputs"] --> U
    P --> C
    K["k-wise independent outputs"] --> P
    R["Fully random function"] --> K
    F --> M["Min-wise property: ranking a set"]
    F --> G["PRG: computational claim"]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class F,R navy; class P,K,U,C teal; class M purple; class G crimson;

Collision Probabilities, Seeds and Adversaries

For a fixed set of $n$ distinct keys, let $C=\sum_{i\lt j}I_{\{h(x_i)=h(x_j)\}}$ count colliding pairs. If a family is universal into $m$ buckets, linearity of expectation gives $\mathbb E[C]\le\binom n2/m$. No independence between the indicators is needed for this first-moment claim. Markov then gives $\Pr(C\ge t)\le\mathbb E[C]/t$ for $t\gt 0$; at $t=1$ this is the familiar union-bound-style estimate for any collision. A variance calculation requires covariances of pair indicators: pairwise independence of key outputs alone does not automatically make all those indicators independent when pairs overlap.

For $p=7$ and fixed keys $1,2,3,4$, affine hashing has six distinct-key pairs, each colliding with probability $1/7$, so $\mathbb E[C]=6/7$. One sampled seed may yield $C=0$; the expectation is over all $49$ equally likely seeds. In fact $a=0$ makes all four keys collide, while any $a\ne0$ is a permutation of $\mathbb F_7$ and makes none collide. Therefore $C=6$ with probability $1/7$ and $C=0$ with probability $6/7$: its mean is indeed $6/7$. This striking example shows why an expected collision bound is not a strong tail bound. It also shows that forbidding $a=0$ changes the family: it removes those collisions but no longer gives uniform independent outputs for a fixed pair.

The randomness budget is part of the analysis. A full random function from $U$ to $m$ buckets can be specified with about $|U|\log_2m$ bits; the affine family over $\mathbb F_p$ needs two field elements. If independent rows or trials are required, each needs fresh independent seed material. Reusing one seed across trials creates correlated failures and defeats a median-amplification proof. A seeded PRG may reduce stored randomness, but then the guarantee must explicitly state whether it is computational or whether a construction preserves the limited independence the proof needs.

Finally, fix the order of choices. The universal guarantee is over a random seed for a fixed pair selected independently of that seed. After a seed is published, a party able to choose keys can search for colliders; a seed-dependent pair is outside the original quantifiers. For untrusted keys, use a defense justified under an explicit adaptive or computational threat model and test operational limits; a simple universal-family calculation is not a denial-of-service guarantee.

flowchart TD
    A["Fix keys before sampling seed"] --> B["Universal pair collision bound"]
    B --> C["Sum indicators by linearity"]
    C --> D["Expected collision pairs"]
    D --> E["Markov for a weak tail"]
    D --> F{"Need a sharper tail?"}
    F -->|Yes| G["Prove enough independence or structure"]
    A --> H{"Are keys chosen after seed?"}
    H -->|Yes| I["Original guarantee does not apply"]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class A,B,C navy; class D,E,G teal; class I crimson; class F,H purple;

Hashing Across Distributed Event Pipelines

Approachable routing. A school assigns numbered lockers to four parcel IDs. A family drawn from $\mathbb F_7$ can spread four fixed IDs over seven lockers; a chosen seed $a=2,b=1$ maps IDs $1,2,3,4$ to $3,5,0,2$ with no collisions. The random-family statement concerns the probability before the assignment is chosen. After it is chosen, the clerk can inspect the actual load exactly.

Production telemetry. Suppose four regional workers consume $200{,}000$ events per second, keep separate compact summaries, and merge them hourly. If they hash the same user ID using different seeds or differently normalized bytes, their bucket indices do not refer to the same coordinates; adding counters produces a meaningless merged sketch. Specify key encoding, family/version, seed, bucket count, and hash independence required by the downstream estimator. If workers use the same seed, the results are reproducible and mergeable under an estimator whose merge algebra permits it; this sharing is intentional and must not be misdescribed as four independent trials. Measure throughput, seed storage, hot-bucket rates, and whether seed rotation requires rebuilding summaries.

Misleading and adversarial setting. A public API accepts user-chosen IDs, and an adversary can send many requests after learning the routing seed or observing hot partitions. A fixed-key universal bound gives no assurance about those chosen IDs. The operator needs an explicitly justified adversarial strategy, potentially a secret keyed hashing primitive, access controls, monitoring, and rotation policy. Likewise, using a fast noncryptographic family for deduplication does not make accidental hash collisions proof that two payloads are equal; a confirmatory comparison is needed if false merges are costly. The formal abstraction ignores data encoding, malicious selection, and operational costs until those are written into the contract.

Choose a Hash Family and Defend the Choice

An appropriate family is the smallest one whose proven property covers the required step of the streaming algorithm under the actual input model. It must also fit the seed, update-time, and merge budgets. The following exercises test whether the choice and its quantifiers can be defended independently of a particular implementation.