iii. Randomized Hashing and Verification

Randomized hashes compress structured objects (strings, sets, multisets, positions) into fingerprints for $O(1)$ comparison or dictionary lookup, and random test points verify identities that are expensive to compute. Hash equality is evidence, not proof: budget the error over all comparisons, and keep the randomness hidden from the adversary. Polynomial string hashing in depth is in Hashing.

Check	Method	Error
two multisets equal	sum of random 64-bit weights (mod $2^{64}$)	$\approx 2^{-64}$ per comparison
every value occurs an even number of times	XOR of random weights (Zobrist)	$\approx 2^{-64}$
subarray is a permutation of $\mathrm{1..}k$	sum hash against the hash of $\{\mathrm{1..}k\}$	$\approx 2^{-64}$
$AB=C$ for matrices	Freivalds: test $A(Br)=Cr$ for random $r$	$\le \frac{1}{2}$ per round with a 0/1 vector, $\le \frac{1}{p}$ with a random vector mod $p$
polynomial identically zero, two expressions equal	evaluate at random points (Schwartz–Zippel)	$\le \frac{d}{
a perfect matching exists	random Tutte matrix, rank	$\le \frac{n}{p}$: General Matching
two rooted trees isomorphic	random polynomial tree hash	Tree Isomorphism

Verifying is easier than computing: Freivalds checks a matrix product in $O(n^2)$ instead of $O(n^{\omega })$, and randomness closes the gap.

Set hashing and Zobrist hashing

Assign each value a random 64-bit weight; hash a multiset by the sum of the weights (mod $2^{64}$) and a set-with-parity by the XOR. Updates are $O(1)$, so prefix arrays give subarray hashes. Uses: comparing multisets, board positions in game engines (Zobrist hashing), tree hashing, “do these two ranges contain the same multiset”, counting subarrays where every value occurs an even number of times (pairs of equal prefix XORs), or a multiple of $k$ times (a base-$k$ digit hash).

struct SetHashing {                                      // values a[i] in [0, maxValue]
    vector<ull> weight, prefSum, prefXor, permSum;
    SetHashing(const vector<int>& a, int maxValue, ull seed) {
        mt19937_64 gen(seed); weight.resize(maxValue + 1);
        for (auto& w : weight) w = gen();
        int n = sz(a); prefSum.assign(n + 1, 0); prefXor.assign(n + 1, 0);
        for (int i = 0; i < n; i++) prefSum[i + 1] = prefSum[i] + weight[a[i]], prefXor[i + 1] = prefXor[i] ^ weight[a[i]];
        permSum.assign(maxValue + 2, 0);                 // permSum[k] = weight[1] + ... + weight[k]
        for (int k = 1; k <= maxValue; k++) permSum[k] = permSum[k - 1] + weight[k];
    }
    ull sumHash(int l, int r) const { return prefSum[r] - prefSum[l]; }   // multiset of a[l, r)
    ull xorHash(int l, int r) const { return prefXor[r] ^ prefXor[l]; }   // values with odd count
    bool isPermutation(int l, int r) const { int k = r - l; return k < sz(permSum) && sumHash(l, r) == permSum[k]; }
};
 
ll countEvenCountSubarrays(const SetHashing& h, int n) {   // subarrays where every value occurs an even number of times
    unordered_map<ull, int> seen; ll res = 0;
    for (int i = 0; i <= n; i++) res += seen[h.prefXor[i]]++;
    return res;
}
 
// Subarrays where every value occurs a multiple of k times: hash sum_v (count_v mod k) * w_v modulo 2^61 - 1.
ll countMultipleOfKSubarrays(const vector<int>& a, int k, int maxValue, ull seed) {
    const ull M = (1ULL << 61) - 1;
    auto mulmod = [&](ull x, ull y) { __uint128_t z = (__uint128_t)x * y; ull r = (ull)(z & M) + (ull)(z >> 61); return r >= M ? r - M : r; };
    mt19937_64 gen(seed); vector<ull> w(maxValue + 1); for (auto& x : w) x = gen() % M;
    vector<int> cnt(maxValue + 1, 0); ull H = 0; map<ull, int> seen; seen[0] = 1; ll res = 0;
    for (int v : a) {
        if (cnt[v] == k - 1) { H = (H + M - mulmod(w[v], k - 1)) % M; cnt[v] = 0; }   // digit k-1 -> 0
        else { H = (H + w[v]) % M; cnt[v]++; }
        res += seen[H]++;
    }
    return res;
}

Proof: collision probabilities of set hashing

Two different multisets $X\ne Y$ (as count vectors) collide iff ${\sum }_v(x_v-y_v)w_v\equiv 0(\mathrm{mod}{2}^{64})$. Pick a value $v$ where $d=x_v-y_v\ne 0$ has the fewest factors of 2, say $2^e\parallel d$ with $e<64$ (counts are below $2^{64}$). Fixing all other weights, the condition becomes $d\cdot w_v\equiv c$, which has at most $2^e$ solutions among the $2^{64}$ values of $w_v$; when the multisets differ in an odd count somewhere the probability is $2^{-64}$, and in general it is at most $2^{e-64}$ (tiny for realistic counts). For the XOR hash, the sets of odd-count values differ in some $v$, and $w_v$ uniform makes the XOR uniform: probability exactly $2^{-64}$. Even counts: every count in $a[l,r)$ is even iff the prefix XOR hashes at $l$ and $r$ agree (with that error), so counting pairs of equal prefix values counts such subarrays. Multiples of $k$: the prefix state is the vector of counts mod $k$; the hash is a linear function of that vector with random coefficients mod a prime $p=2^{61}-1$, so two different states collide with probability $\le \frac{1}{p}$ (Schwartz–Zippel with degree 1). The update keeps $H={\sum }_v(c_v\mathrm{mod}k)w_v$. All functions were checked against brute force on random arrays with small values.

Freivalds and Schwartz–Zippel

// Probabilistic check of A * B == C (n x n, entries mod p), O(rounds * n^2); false is always correct.
bool freivalds(const vector<vector<ll>>& A, const vector<vector<ll>>& B, const vector<vector<ll>>& C, ll p, int rounds, mt19937_64& rng) {
    int n = sz(A);
    auto mul = [&](const vector<vector<ll>>& M, const vector<ll>& x) {
        vector<ll> y(n, 0); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) y[i] = (y[i] + (i128)M[i][j] * x[j]) % p; return y;
    };
    while (rounds--) {
        vector<ll> r(n); for (auto& x : r) x = rng() % p;
        if (mul(A, mul(B, r)) != mul(C, r)) return false;
    }
    return true;
}

Schwartz–Zippel. A non-zero polynomial of total degree $d$ over a field, evaluated at a point whose coordinates are independent uniform elements of a finite set $S$, vanishes with probability at most $\frac{d}{|S|}$. This one lemma underlies polynomial identity testing (evaluate both sides of a conjectured identity at random points mod a large prime), string and tree hashing, the Tutte matching test and Freivalds with random vectors.

Proof: Schwartz–Zippel and Freivalds

Schwartz–Zippel. Induction on the number of variables $k$. For $k=1$ a non-zero polynomial of degree $d$ has at most $d$ roots. For $k>1$ write $P={\sum }_{i=0}^t{x}_1^i{Q}_i(x_2,\dots ,x_k)$ with $Q_t\ne 0$, $\mathrm{deg}{Q}_t\le d-t$. By induction $\mathrm{Pr}[Q_t(x_2..x_k)=0]\le \frac{d-t}{|S|}$; if $Q_t\ne 0$ at the chosen point, $P$ is a non-zero polynomial of degree $t$ in $x_1$ and vanishes with probability $\le \frac{t}{|S|}$. Union: $\le \frac{d}{|S|}$.

Freivalds. If $AB\ne C$, then $D=AB-C$ has a non-zero row $i$, and $(Dr{)}_i={\sum }_j{D}_{ij}{r}_j$ is a non-zero linear polynomial in $r$; with $r$ uniform mod $p$ it vanishes with probability $\frac{1}{p}$ (with $r\in \{0,1{\}}^n$ the bound is $\frac{1}{2}$: pair each $r$ with the one that flips a coordinate where $D_{ij}\ne 0$; at most one of the pair gives 0). If $AB=C$ the test always passes, so the error is one-sided. Checked: correct products always pass; products with one corrupted entry are always rejected in the tests.

Anti-hash attacks and defences

Attack	Breaks
Thue–Morse strings of length $2^{11}$	every polynomial hash modulo $2^{64}$ (natural ull overflow), for every base
even base modulo $2^{64}$	only the last 64 characters matter: $b^{64}\equiv 0$
birthday attack	a fixed $(B,M)$ in $O(\sqrt{M})$ offline work: trivial for $M=10^9+7$
keys that are multiples of the bucket count	unordered_map with the default hash<long long> (the identity on GCC)

Defences: a random base modulo the Mersenne prime $2^{61}-1$ (or two independent moduli), seeded from the clock; for hash maps the randomized splitmix64 SafeHash in C++ for CP (or gp_hash_table with it); store lengths when sequences of different sizes must be distinguished; avoid zero encodings (map characters to $\mathrm{1..}\sigma$).

Proof: the Thue–Morse collision

Let $T_0=$ “a”, $T_{q+1}=T_q\overline{T_q}$ (complement swaps a and b), and compare $T_q$ with $\overline{T_q}$. The difference of their hashes is $\pm (a-b){\prod }_{j<q}(1-x^{2^j})$ evaluated at the base $x$: by induction, the signed indicator $\sum \pm x^i$ of $T_{q+1}$ is $D_q(x)-x^{2^q}{D}_q(x)=(1-x^{2^q})D_q(x)$. For odd $x$, $1-x^{2^j}$ is divisible by $2^{j+1}$ (since $x^{2^j}\equiv 1(\mathrm{mod}{2}^{j+2})$ for $j\ge 1$, and $2\mid 1-x$), so the product is divisible by $2^{1+2+\cdots +q}=2^{q(q+1)/2}$, which is $\ge 2^{64}$ for $q=11$: strings of length 2048 collide for every odd base. For even bases $x^{64}\equiv 0$, so characters at distance $\ge 64$ from the end are ignored. Checked with random bases. Lesson: never hash modulo $2^{64}$ alone on hackable problems.

Working rule. Find collisions in a tiny modulus deliberately to see the birthday bound in action; then quantify why a larger, independently randomized field changes the bound ($q$ comparisons, error $\approx q/M$, plus $\left(\genfrac{}{}{0ex}{}{q}{2}\right)/M$ when all pairs are compared).

Related notes

• Hashing (polynomial string hashing, double hashing)
• Randomized Algorithms
• Containers and Hashing