Polynomial Hashing

The mathematics behind string hashing: why it works, how likely a collision is, and how to choose the parameters. (For the code and the practical recipe, see String Hashing.)

The polynomial view

Treat a string $s$ of length $n$ as the polynomial

$P_s(x)={\sum }_{i=0}^{n-1}{s}_i{x}^i\in {\mathbb{F}}_M[x],$

and define $H(s)=P_s(B)\mathrm{mod}M$ for a chosen evaluation point $B$.

Two strings collide exactly when
$P_s(B)\equiv P_t(B)(\mathrm{mod}M)⟺(P_s-P_t)(B)\equiv 0.$

So a collision means $B$ is a root of the difference polynomial.

The collision bound

$P_s-P_t$ is a non-zero polynomial of degree $<n$ over the field ${\mathbb{F}}_M$ (assuming $M$ prime). A non-zero polynomial of degree $d$ has at most $d$ roots. Therefore, for a uniformly random $B$:

$\mathrm{Pr}[\text{collision}]\le \frac{n-1}{M}.$

This is the Schwartz-Zippel lemma in one variable, and it is the entire justification for hashing.

Over $q$ comparisons, a union bound gives $\mathrm{Pr}[\text{any collision}]\le qn/M$. With $M=2^{61}-1$, $n=10^6$ and $q=10^6$, that is about $4\cdot 10^{-7}$ — safe.

Why randomising $B$ matters

The bound above requires $B$ to be random and unknown to the adversary. With a fixed $B$, a problem setter can:

• precompute a colliding pair by a birthday attack in $O(\sqrt{M})$ work, offline, once;
• for $M=2^{64}$ (unsigned overflow), construct the Thue-Morse sequence, which collides for every base in $O(\log )$ length.

Randomising $B$ at runtime moves the adversary from “precompute one counterexample” to “guess the seed”, which is infeasible.

Birthday paradox — the other failure mode

Even with a random $B$, if you insert $k$ distinct strings into a hash set, the chance that some pair collides is roughly

$1-e^{-k^2/(2M)}\approx \frac{k^2}{2M}.$

$M$	$k$ for a 1% collision chance
$10^9+7$	$\approx 4500$
$2^{31}$	$\approx 6500$
$2^{61}-1$	$\approx 2\cdot 10^8$
double hashing ($\approx 10^{18}$)	$\approx 1.4\cdot 10^8$

This is why $10^9+7$ is not enough when you hash $10^5$ or more distinct substrings: $k=10^5$ gives a collision probability near 1. Use $2^{61}-1$ or double hashing.

Choosing the modulus

$M$	Verdict
$2^{64}$ (unsigned overflow)	never — Thue-Morse breaks it deterministically
$10^9+7$	too small for many distinct strings; fine for a single pattern match
$2^{31}-1$	too small
$2^{61}-1$	the right default — Mersenne prime, fast reduction, huge
two primes near $10^9$	equivalent strength, two multiplications

Fast reduction modulo $2^{61}-1$

static const unsigned long long M = (1ULL << 61) - 1;
unsigned long long mul(unsigned long long a, unsigned long long b) {
    __uint128_t r = (__uint128_t)a * b;
    unsigned long long lo = (unsigned long long)(r & M), hi = (unsigned long long)(r >> 61);
    unsigned long long s = lo + hi;
    return s >= M ? s - M : s;
}

Because $2^{61}\equiv 1$, the high bits fold into the low ones with a shift and an add — no division.

Composability

Polynomial hashes concatenate cleanly:

$H(st)=H(s)\cdot B^{|t|}+H(t).$

That identity is what makes prefix hashing, rolling hashes, and hashing inside a segment tree all work — a segment tree node storing (hash, length) merges in $O(1)$, giving hashes of a string under point updates.

Beyond strings

The same argument hashes anything with a polynomial encoding:

• Sequences of integers — same formula with the values as coefficients.
• Multisets — $\sum f(x_i)$ for a random scramble $f$; order-independent, and collision-resistant by the same counting argument.
• Trees — combine children’s hashes with a commutative, scrambled operation.
• Sets over ${\mathbb{F}}_2$ — XOR of random 64-bit values per element (Zobrist hashing), used for board positions in game engines.

See also: String Hashing · Rolling Hash · Birthday Paradox