String Hashing, in depth: prefix hashes, provable collision bounds, the 2^64 trap and the 2^61 - 1 modulus

Prefix hashes and substring hashes

Fix a prime modulus m and a base b chosen uniformly at random from [2, m-2]. Map each character to a value from 1 upwards, never 0. For a string s of length n define prefix hashes H[0] = 0 and H[i+1] = (H[i]*b + val(s[i])) mod m, and powers P[k] = b^k mod m. Then the hash of the half-open substring s[l:r] is (H[r] - H[l]*P[r-l]) mod m. The subtraction removes the prefix, and the multiplication shifts it into the same position it occupies inside H[r].

The worked numbers are small enough to check by hand. With a=1, b=2, n=14 and base 31, the prefix array is 0, 2, 63, 1967, 60978, 1890332, 58600293. The window from index 1 to 4 is 60978 - 2*29791 = 1396, the window from 3 to 6 is 58600293 - 1967*29791 = 1396, and evaluating 'ana' directly gives 961 + 434 + 1 = 1396. Real code would reduce modulo m at every step; here the numbers never reach it.

Why not map 'a' to 0? Because then 'a', 'aa' and the empty string all hash to 0. Leading zero coefficients vanish from a polynomial, so equal hashes no longer imply equal lengths. Starting values at 1 fixes this for same-length comparisons; when lengths can differ, compare lengths first.

Collision bounds you can prove

Here is the bound, from first principles. Take two different strings x and y of the same length n. Their hash difference is a polynomial in the base, D(b) = sum (x_i - y_i) * b^(n-1-i), with at least one non-zero coefficient. Over the field of integers modulo a prime, a non-zero polynomial of degree at most n-1 has at most n-1 roots. The hashes collide only if the random base is one of those roots, so

Pr[hash(x) == hash(y)]  <=  (n - 1) / m        for a uniformly random base, prime m

Three conditions make this true, and breaking any of them breaks the bound: the modulus must be prime (otherwise the root count argument fails), the base must be random and unknown to whoever chose the strings, and the strings must be fixed before the base is drawn.

One comparison is not the whole story. If an algorithm makes Q comparisons, the union bound gives a failure probability of at most Q*(n-1)/m. If it inserts k distinct substrings into a hash set and asks whether any two collide, there are about k^2/2 pairs, and the birthday effect takes over.

The last column uses the worst-case polynomial bound, which is pessimistic for typical inputs, but it is the only number you can defend against adversarial ones. The practical rule: a single 32-bit-sized modulus is fine for a few thousand comparisons and wrong for anything bigger.

Why overflowing 64-bit hashes are broken

Many implementations use unsigned 64-bit arithmetic and let it overflow, which computes the hash modulo 2^64. It is fast and it is broken, because integers modulo 2^64 do not form a field: the root-counting argument above no longer applies, and there is an explicit family of strings that collides for every base.

If the base is even, b^64 is divisible by 2^64, so every character more than 64 positions from the end contributes nothing; any two strings sharing their last 64 characters collide. If the base is odd, use the Thue-Morse construction: S_0 = 'a', S_{k+1} = S_k + flip(S_k) where flip swaps a and b. The hash difference between S_k and flip(S_k) factors into a product of terms b^(2^i) - 1 for i from 0 to k-1. For odd b, the i-th term is divisible by 2^(i+2) when i is at least 1, and the i = 0 term by 2. Summing exponents gives at least 1 + (k-1)(k+4)/2, which reaches 64 at k = 10. Two strings of length 1024 therefore already collide modulo 2^64 for every odd base. Check it yourself:

import random

def thue_morse(k):
    s = "a"
    for _ in range(k):
        s += s.translate(str.maketrans("ab", "ba"))
    return s

def h64(s, b):
    h = 0
    for ch in s:
        h = (h * b + ord(ch)) & 0xFFFFFFFFFFFFFFFF
    return h

s = thue_morse(10)                       # length 1024
t = s.translate(str.maketrans("ab", "ba"))
for _ in range(5):
    b = random.randrange(3, 1 << 63) | 1  # any odd base
    assert h64(s, b) == h64(t, b)         # always collides

A large prime, and palindromes from two hashes

The fix is a large prime modulus. The usual choice is the Mersenne prime 2^61 - 1, because 2^61 is congruent to 1 modulo it and reduction becomes a shift, a mask and an add; the overflow-safe multiplication and its proof are already worked through in Rabin-Karp hashing, so the code below uses Python, where integers do not overflow, and spends its lines on a query that Rabin-Karp does not need: palindromes.

Hash the string forwards and its reverse forwards. The window s[l:r] read backwards is the window rev[n-r:n-l], so the window is a palindrome exactly when those two hashes agree, up to the usual collision probability. Palindromes have a monotone structure around each centre: if the radius-k window is a palindrome, so is every smaller radius. That makes the maximal radius a binary search.

import random

M = (1 << 61) - 1

def prefix(s, b):
    H = [0] * (len(s) + 1)
    for i, ch in enumerate(s):
        H[i + 1] = (H[i] * b + ord(ch) + 1) % M
    return H

def longest_palindrome(s):
    n = len(s)
    if n == 0:
        return ""
    b = random.randrange(1 << 40, M - 1)
    F, R = prefix(s, b), prefix(s[::-1], b)
    P = [1] * (n + 1)
    for i in range(n):
        P[i + 1] = P[i] * b % M
    get = lambda H, l, r: (H[r] - H[l] * P[r - l]) % M
    is_pal = lambda l, r: get(F, l, r) == get(R, n - r, n - l)

    best = (0, 1)
    for c in range(n):
        for odd in (1, 0):                    # odd centre at c, even between c-1 and c
            lo, hi = 0, min(c, n - c - odd)
            while lo < hi:                    # largest radius k with a palindrome
                k = (lo + hi + 1) // 2
                if is_pal(c - k, c + k + odd):
                    lo = k
                else:
                    hi = k - 1
            l, r = c - lo, c + lo + odd
            if r - l > best[1] - best[0] and r > l:
                best = (l, r)
    return s[best[0]:best[1]]

For 'forgeeksskeegfor' this returns 'geeksskeeg', and for 'abacdfgdcaba' it returns 'aba'. The cost is O(n log n). Manacher's algorithm solves the same problem exactly in O(n), so in production prefer it; the hashed version earns its place when you already have prefix hashes built for other queries and want one more answer from them.

Applications: LCP, suffixes, repeats, palindromes

With constant-time substring equality, several problems that look like they need suffix structures become a binary search or a set.

import random

M = (1 << 61) - 1

class Hasher:
    def __init__(self, s, base=None):
        self.b = base or random.randrange(1 << 40, M - 1)
        n = len(s)
        self.H, self.P = [0] * (n + 1), [1] * (n + 1)
        for i, ch in enumerate(s):
            self.H[i + 1] = (self.H[i] * self.b + ord(ch) + 1) % M
            self.P[i + 1] = self.P[i] * self.b % M

    def get(self, l, r):
        return (self.H[r] - self.H[l] * self.P[r - l]) % M

def lcp(h, i, j, n):
    # longest common prefix of suffixes i and j, by binary search on length
    lo, hi = 0, n - max(i, j)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if h.get(i, i + mid) == h.get(j, j + mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

def longest_repeat(s):
    # longest substring occurring at least twice: binary search on length
    h, n = Hasher(s), len(s)
    def has_repeat(L):
        seen = {}
        for i in range(n - L + 1):
            v = h.get(i, i + L)
            for j in seen.get(v, ()):
                if s[j:j + L] == s[i:i + L]:     # verify every same-hash candidate
                    return i
            seen.setdefault(v, []).append(i)
        return -1
    lo, hi, best = 1, n - 1, ""
    while lo <= hi:
        mid = (lo + hi) // 2
        i = has_repeat(mid)
        if i >= 0:
            best, lo = s[i:i + mid], mid + 1
        else:
            hi = mid - 1
    return best

The lcp helper is the workhorse. Comparing two suffixes lexicographically is an LCP query followed by one character comparison, so sorting all suffixes with a hash-based comparator costs O(n log^2 n): a valid fallback when a linear construction such as SA-IS, described in suffix array construction, is more machinery than you need. Palindromes, covered in the previous section, use the same binary-search-on-a-monotone-predicate shape.

Notice the explicit verification in longest_repeat, against every earlier position with the same hash. It turns a Monte Carlo algorithm, which may return a wrong answer, into a Las Vegas one, which is always right and only slow when collisions pile up. Verify whenever the extra comparison is cheap relative to the cost of a wrong answer.

Failure modes

• Fixed, public base. A base hard-coded in a library or a solution template lets an adversary construct collisions offline. Draw it at run time.
• Overflowing 64-bit arithmetic. Broken by Thue-Morse strings of length 1024 for any odd base, as shown above.
• Small modulus at scale. A single 1e9+7 modulus with millions of comparisons or a large hash set produces real collisions on ordinary data.
• Character value 0. Leading zero coefficients vanish, so strings of different lengths collide.
• Negative remainders. In languages where % keeps the sign of the dividend, H[r] - H[l]*P goes negative unless you add the modulus first.
• Intermediate overflow. Multiplying two residues of a 1e18-sized modulus in 64-bit signed integers overflows silently; use 128-bit products or the Mersenne reduction.
• Mixing lengths in one set. Hashes of different-length substrings share a key space; key on (length, hash) when lengths vary.
• Correlated double hashing. Two hashes that share a base, or whose bases are derived from each other, give no extra protection. Independently drawn bases are what multiply the probabilities, even with the same prime modulus.

Choosing and testing in practice

Choose between hashing and exact structures by the cost of being wrong. For deduplication where a false match silently drops a record, verify on every hash match or use exact methods such as the Z-algorithm or a suffix array. For competitive programming, exploratory analysis and candidate generation followed by a check, a single 2^61 - 1 hash with a random base is the right default. When hashes are exposed to untrusted input, for example as hash table keys in a server, use a keyed hash designed for that purpose; the flooding problem is covered in hash tables in depth.

Test hashing code with adversarial inputs, not only random ones: Thue-Morse pairs, long runs of one character, strings that differ only at the first position, and empty substrings.

Trade-offs

What to do next

1. Implement the prefix-hash class with modulus 2^61 - 1 and a random base in your main language.
2. Reproduce the banana example by hand and in code, then confirm the Thue-Morse collision against an overflowing 64-bit hash.
3. Write the LCP-by-binary-search helper and test it against a brute-force LCP on random strings.
4. Solve longest repeated substring with verification, then remove verification and measure the speed difference.
5. Compute the union and birthday bounds for your real workload before trusting an unverified hash.
6. Audit existing code for fixed bases, character value 0, overflowing arithmetic and negative remainders.