Hash Functions

A hash function is a function

mapping a universe $U$ of possible keys (integers, strings, records — anything) to a small integer range of size $m$, the number of slots in a hash table. Because $|U|$ is typically vastly larger than $m$, the pigeonhole principle guarantees that distinct keys will sometimes map to the same slot; this is a collision. Hash functions do not eliminate collisions — that is provably impossible when $|U| > m$ — but a good one makes collisions rare and, crucially, unpredictable to anyone trying to trigger them deliberately. Before hashing, keys are usually reduced to non-negative integers via some canonical encoding (e.g., treating a string as a number in a large base, or interpreting bytes as an integer). This article assumes that step is done and focuses on the map from integers to slot indices. Two deterministic constructions dominate practice: the division method, $h(k) = k \bmod m$, and the multiplication method, which uses the fractional part of $kA$ for a well-chosen constant $A$. Both are cheap to compute — a handful of arithmetic operations — which matters because the hash function is evaluated on every table operation. The theoretical backbone for analyzing these (and any) hash functions is the simple uniform hashing assumption (SUHA): each key is equally likely to hash to any of the $m$ slots, independently of where other keys hash. Under SUHA, standard hash table analyses show expected $O(1)$ operations. SUHA is an idealization no fixed deterministic function can truly satisfy against an adversary who knows the function, because for any fixed $h$ there exists a set of keys that all collide. This gap between idealization and reality motivates universal hashing: instead of committing to one fixed function, the table's implementation picks a function at random, at initialization time, from a carefully designed family $\mathcal{H}$. As long as the family is universal — any two distinct keys collide under a randomly chosen $h \in \mathcal{H}$ with probability at most $1/m$ — SUHA-like guarantees hold in expectation over the algorithm's own randomness, for any fixed sequence of keys, even one designed by an adversary who does not know which $h$ was drawn.

The division method. Given table size $m$, define

This requires one modulus operation — extremely fast on real hardware. Its Achilles' heel is that it is only as "random-looking" as the low-order structure of $m$ allows. If $m = 2^p$, then $h(k)$ depends only on the low $p$ bits of $k$, ignoring all higher-order bits entirely; keys that share low bits (common with, e.g., pointers aligned to word boundaries, or IDs padded with trailing zeros) collide systematically. The standard fix is to choose $m$ to be a prime not close to a power of 2 or 10, which spreads dependence across all bits of typical keys.

The multiplication method. Choose a constant $A$ with $0 < A < 1$. Define

where $kA \bmod 1$ denotes the fractional part of $kA$. Intuitively: multiply the key by $A$, throw away the integer part, keep the fractional part (a number in $[0,1)$), and scale it up to the range $[0, m)$. This method is much less sensitive to the choice of $m$ — powers of 2 are fine, which is convenient because computing $m \cdot x$ for $m = 2^p$ is just a bit shift. Knuth recommends

the reciprocal of the golden ratio, because multiplying by it tends to scatter the resulting fractional parts fairly evenly, avoiding clumping patterns that some values of $A$ produce with structured input. In practice, on a machine with $w$-bit words, this is implemented entirely with integer arithmetic: pick an odd integer constant $s$ approximating $A \cdot 2^w$, compute the $w$-bit product $k \cdot s$ (allowing overflow to $2w$ bits), and extract the top $p$ bits of the low $w$-bit half (for $m = 2^p$) as the hash. This avoids floating point entirely and is extremely fast — a single integer multiply and a shift.

Universal hashing. Fix a prime $p$ larger than any key value. A classical universal family (due to Carter and Wegman) is

To use it: pick $a$ and $b$ uniformly at random once, when the table is created (not per key), then use the resulting fixed function $h_{a,b}$ for every operation on that table instance. The randomness is in which function gets chosen, not in re-randomizing per lookup. ```text // One-time setup when the hash table is constructed: UNIVERSAL-HASH-INIT(m, p): a ← random integer in [1, p-1] b ← random integer in [0, p-1] return (a, b) // defines h_{a,b} for the table's lifetime // Evaluated on every insert / search / delete: UNIVERSAL-HASH(k, a, b, p, m): return ((a k + b) mod p) mod m ``` ```text // Division method DIVISION-HASH(k, m): return k mod m // Multiplication method (Knuth's constant, integer arithmetic on w-bit words) // s is a precomputed odd integer approximating A 2^w, m = 2^p MULTIPLICATION-HASH(k, s, w, p): product ← (k * s) mod 2^w // keep only the low w bits of the product return product >> (w - p) // top p bits of that low half ``` The key structural fact used later in the correctness argument: for $h_{a,b} \in \mathcal{H}$ and two distinct keys $k_1 \ne k_2$ both less than $p$, the map $k \mapsto (ak+b) \bmod p$ is a bijection on $\{0,\dots,p-1\}$ for each fixed nonzero $a$ — this is where the collision-probability bound comes from.

Time cost of the hash function itself. Both the division method and the multiplication method compute $h(k)$ in $O(1)$ time — one modulus/multiply plus a few shifts, independent of key size (for fixed-width machine integers) or logarithmic in key size for arbitrary-precision keys. This constant-time evaluation is what allows hash table operations (insertion, search, deletion) to be $O(1)$ on average, since each operation performs a small constant number of hash evaluations plus work proportional to the resulting slot's chain length or probe sequence — topics developed fully in Separate Chaining Collision Resolution and Open Addressing Collision Resolution.

Why SUHA gives $O(1)$ expected time. Under simple uniform hashing, each of $n$ keys lands independently and uniformly in one of $m$ slots. For separate chaining, the expected chain length at any slot is the load factor $\alpha = n/m$, so an unsuccessful search expects to examine $\Theta(1 + \alpha)$ elements: $\Theta(1)$ for computing the hash, and $\Theta(\alpha)$ for scanning the expected chain length. Keeping $\alpha = O(1)$ (e.g., resizing the table when $\alpha$ exceeds a constant threshold) yields expected $O(1)$ operations. The catch, stated honestly: SUHA is unverifiable and generally false for any fixed hash function, because for any deterministic $h$, an adversary who knows $h$ can compute $m$ or more keys that all hash to the same slot — simply invert $h$ on a single target slot value repeatedly. This is not a hypothetical: it is the basis of real denial-of-service attacks against naively hashed web-request parameters and form fields, which is precisely why security-sensitive services randomize their hash seed.

Why universal hashing repairs this. Universal hashing sidesteps the adversary problem by making the function itself the random variable, chosen after (or independent of) the adversary's choice of keys. Formally, a family $\mathcal{H}$ is universal if for every pair of distinct keys $k_1 \ne k_2$,

Proof that the Carter–Wegman family is universal. Fix distinct keys $k_1 \neq k_2$ in $\{0, \ldots, p-1\}$, with $p$ prime and $p >$ every key and $p \geq m$. Define $r_1 = (ak_1 + b) \bmod p$ and $r_2 = (ak_2 + b) \bmod p$ for $a$ drawn uniformly from $\{1, \ldots, p-1\}$ and $b$ uniformly from $\{0, \ldots, p-1\}$. 1. For any fixed nonzero $a$, the map $k \mapsto (ak + b) \bmod p$ is injective as $b$ ranges over $\mathbb{Z}_p$: solving $r_1 \equiv ak_1 + b$ and $r_2 \equiv ak_2 + b \pmod p$ simultaneously gives $r_1 - r_2 \equiv a(k_1 - k_2) \pmod p$. Since $p$ is prime and $k_1 \ne k_2 \pmod p$, $(k_1 - k_2)$ is invertible mod $p$, so for each nonzero $a$ there is exactly one value of $r_1 - r_2$, hence — ranging over all $(a,b)$ pairs uniformly — the pair $(r_1, r_2)$ is uniformly distributed over all $p(p-1)$ ordered pairs of distinct values in $\mathbb{Z}_p \times \mathbb{Z}_p$. 2. So $\Pr[r_1 = r_2] = 0$ exactly (they are forced distinct whenever $a \neq 0$), and $(r_1, r_2)$ is uniform over the $p(p-1)$ distinct ordered pairs. 3. We care about $h(k) = r \bmod m$, not $r$ itself. Fixing $r_1$, the number of values $r_2 \in \mathbb{Z}_p \setminus \{r_1\}$ with $r_2 \equiv r_1 \pmod m$ is at most $\lceil p/m \rceil - 1 \le (p - 1)/m$ (a standard counting bound on residues mod $m$ within a range of size $p$). Dividing by the $p - 1$ available choices of $r_2$ gives

This establishes universality. $\blacksquare$

Consequence for expected chain length. With a universal family, for any fixed sequence of $n$ keys (chosen with no knowledge of $a, b$), and a random $h \in \mathcal{H}$ used to build the table, the expected number of collisions any single key experiences with the other $n-1$ keys is at most $(n-1)/m$ — by linearity of expectation, summing the $\le 1/m$ pairwise collision probability over all other keys. So expected chain length is $O(1 + \alpha)$, matching the SUHA guarantee, but now proved rigorously for any input, with the randomness coming only from the table's own coin flips, not from any assumption about the keys.

Space. A hash function itself uses $O(1)$ extra space (a constant number of parameters: $m$, or $A$/$s$, or $(a,b,p)$). This is separate from the $\Theta(m + n)$ space used by the resulting table with chaining, or $\Theta(m)$ with open addressing.

Honest tradeoffs. The division method is simplest and fastest to reason about but forces careful, often prime, choices of $m$. The multiplication method tolerates power-of-two table sizes (convenient for fast modular arithmetic and cache-line alignment) but the quality of scattering depends on the choice of constant $A$, and poor choices can still produce visible patterns. Universal hashing gives the strongest theoretical guarantee — worst-case-input resilience — but at the cost of a slightly more expensive hash evaluation (a multiply, an add, and two modular reductions) and the operational requirement of generating and storing fresh random parameters per table instance.

Take table size $m = 8$ and keys representing user IDs: $k \in \{18, 41, 22, 44, 59, 32\}$.

Division method, $h(k) = k \bmod 8$:

With $m=8=2^3$, the hash only depends on $k \bmod 8$, i.e., the low 3 bits of $k$. Here it happens to scatter nicely since the low bits of these particular keys vary. But notice: any key set that's arithmetic with common stride 8 (e.g., IDs $8, 16, 24, 32, \dots$ — very plausible if IDs are assigned in blocks per shard) would all collide in slot 0. This is the systematic weakness of power-of-two divisors.

Multiplication method, using $A = 0.6180339887$, $m = 8$: Compute $kA \bmod 1$, then multiply by 8 and floor.

Now the arithmetic-progression weakness is broken: 18 and 32 no longer collide, and the mapping depends on the full magnitude of $k$, not just its low bits — because multiplying by an irrational-like constant mixes all the bits of $k$ into the fractional part.

Universal hashing, with $p = 101$ (a prime bigger than all keys), $m = 8$, and a randomly drawn $(a, b) = (37, 5)$: $h_{a,b}(k) = ((37k + 5) \bmod 101) \bmod 8$.

Here 18 and 44 collide (both slot 1), and 22 and 59 collide (both slot 3) — collisions do happen, as guaranteed to happen sometimes even under universality. The point of universal hashing is not to eliminate this instance's collisions; it is that if a different $(a,b)$ pair had been drawn, a different pair of keys would likely collide instead, and no fixed adversarial key set can force collisions across all draws of $(a, b)$. Rerunning with $(a,b) = (63, 12)$ would scatter these same six keys entirely differently.

The division and multiplication methods for hashing were systematized and popularized in Donald Knuth's The Art of Computer Programming, which analyzed their statistical behavior in depth and recommended the golden-ratio constant for multiplicative hashing. The theoretical leap — proving that randomizing over a family of hash functions gives guarantees independent of the input — came from J. Lawrence Carter and Mark N. Wegman, who introduced universal hashing in 1977, founding a rigorous probabilistic theory of hash function design that underlies modern hash table implementations, Bloom filters, and randomized data-structure security.

Hash functions are the load-bearing layer beneath Hash Tables and Direct Addressing, and every collision-resolution strategy — Separate Chaining Collision Resolution and Open Addressing Collision Resolution — depends entirely on the quality of the underlying hash function for its average-case performance claims to hold. Language runtimes (Python's `dict`, Java's `HashMap`, Go's `map`) all randomize their internal string hash seed at process startup specifically to defend against algorithmic complexity attacks, a direct engineering application of universal hashing's guarantee. Database systems use hash functions for hash joins, hash partitioning, and hash indexes, where a poor hash function can cause severe data skew across partitions. Distributed systems use hashing for consistent hashing in load balancers and distributed caches (e.g., content delivery networks and key-value stores), where the hash function determines which server or shard owns a given key. Networking hardware uses hash functions for flow classification and load balancing across multiple links. Bloom filters and their relatives, and hash-based variants of Tries (hash tries, hashed compressed tries), rely on well-distributed hash functions to keep false-positive rates and lookup times low. Cryptographic contexts use a stricter cousin of these ideas — hash functions with preimage and collision resistance — but the combinatorial core (mapping a large universe into a small range while controlling collisions) is the same idea this article develops in its simplest, fastest, non-adversarial-by-default form.

Ask the tutor: How does a hash function's design choice affect which collision-resolution scheme — chaining or open addressing — performs better in practice?