☕ DSA Java Articles

Topics › Strings › Hard String Problems

Hashing In Strings - Theory

Easy TUF ID 2399 A2Z

Java source ↗ Edit this article ↗

What string hashing is for

Comparing two strings of length L character by character costs O(L). Many string problems compare the same text again and again: “does this window equal the pattern?”, “is this prefix equal to that suffix?”, “how many different substrings are there?”. If each comparison costs O(L), the whole algorithm becomes quadratic or worse.

String hashing turns a string into a single number, its hash, so that equal strings always get equal numbers, and different strings almost always get different numbers. Comparing two numbers is O(1). The trick that makes it pay off is that hashes of related strings (a string and that string with one more character, or two overlapping windows) can be computed from each other in O(1) instead of from scratch.

This is a concept article. It defines the polynomial rolling hash, shows how to get the hash of any substring in constant time, how to slide a window, what collisions are and how to make them negligible, and finishes with one complete application. Every snippet is a method of the accompanying Java file and is checked in its main. Strings here are lowercase letters, and each letter gets a value: a = 1, b = 2, …, z = 26.

The polynomial rolling hash

Treat the string as a number written in base B, with the letters as digits, and reduce it modulo a large prime M:

hash(s) = (s[0]·B^(n-1) + s[1]·B^(n-2) + ... + s[n-1]·B^0) mod M

Computing powers is unnecessary. Horner’s rule builds the same value left to right: start with h = 0 and, for each character, do h = (h·B + value) mod M. Each step “shifts” the number built so far one digit to the left and writes the new digit at the end, just like reading a decimal number digit by digit.

static final long MOD = 1_000_000_007L;
static final long BASE = 31;

static long polyHash(String s) {
    long h = 0;
    for (int i = 0; i < s.length(); i++) {
        h = (h * BASE + (s.charAt(i) - 'a' + 1)) % MOD;
    }
    return h;
}

Worked example with B = 31:

after reading computation h
a 0·31 + 1 1
ab 1·31 + 2 33
abc 33·31 + 3 1026

Without the modulus, this mapping is one-to-one, because base-31 digits between 1 and 26 describe a unique number. The modulus is what keeps the numbers small enough for a long, and it is also the only source of collisions.

Choosing the base and the modulus

Prefix hashes: any substring in O(1)

Store the hash of every prefix: pre[0] = 0 and pre[i + 1] = pre[i]·B + s[i], all mod M. Also store the powers pw[k] = B^k mod M.

The hash of the substring s[l..r) (from l inclusive to r exclusive) is hidden inside pre[r]. The prefix s[0..r) equals s[0..l) shifted left by r - l digits, plus the substring. Subtracting the shifted part leaves the substring:

hash(s[l..r)) = (pre[r] - pre[l]·B^(r-l)) mod M

static long[] prefixHashes(String s) {
    long[] pre = new long[s.length() + 1];
    for (int i = 0; i < s.length(); i++) {
        pre[i + 1] = (pre[i] * BASE + (s.charAt(i) - 'a' + 1)) % MOD;
    }
    return pre;
}

static long[] powers(int n) {
    long[] pw = new long[n + 1];
    pw[0] = 1;
    for (int k = 1; k <= n; k++) pw[k] = pw[k - 1] * BASE % MOD;
    return pw;
}

static long substringHash(long[] pre, long[] pw, int l, int r) {
    return ((pre[r] - pre[l] * pw[r - l]) % MOD + MOD) % MOD;
}

Worked example with s = "abcab": pre = [0, 1, 33, 1026, 31807, 986019]. The substring s[3..5) = "ab" has hash 986019 - 1026·31^2 = 986019 - 985986 = 33, the same as pre[2], the hash of s[0..2) = "ab". Two O(1) lookups confirm that the two occurrences of "ab" match, without comparing any characters.

The double % MOD in substringHash is deliberate. In Java, % keeps the sign of the left operand, so pre[r] - pre[l]·B^(r-l) reduced mod M can be negative. Adding M and reducing again maps it back into [0, M).

Rolling a window of fixed length

When the substrings of interest are all the windows of a fixed length k, there is an even lighter technique that needs no arrays. To go from the window s[i-k..i) to s[i-k+1..i+1):

  1. Remove the leftmost character, whose weight is B^(k-1).
  2. Multiply by B to shift everything one place left.
  3. Add the new character.

From "abc" (hash 1026) to "bca": 1026 - 1·31^2 = 65, then 65·31 = 2015, then 2015 + 1 = 2016, which is indeed hash("bca") = (2·31 + 3)·31 + 1.

static long[] windowHashes(String s, int k) {
    int n = s.length();
    if (k <= 0 || k > n) return new long[0];
    long[] out = new long[n - k + 1];
    long high = 1;                                   // BASE^(k-1): weight of the window's first char
    for (int i = 1; i < k; i++) high = high * BASE % MOD;
    long h = 0;
    for (int i = 0; i < k; i++) h = (h * BASE + (s.charAt(i) - 'a' + 1)) % MOD;
    out[0] = h;
    for (int i = k; i < n; i++) {
        h = (h - (s.charAt(i - k) - 'a' + 1) * high % MOD + MOD) % MOD;   // remove the leftmost char
        h = (h * BASE + (s.charAt(i) - 'a' + 1)) % MOD;                   // shift and append the new char
        out[i - k + 1] = h;
    }
    return out;
}

This is the engine of the Rabin-Karp pattern search: hash the pattern once, roll a window across the text, and compare characters only where the hashes agree.

Collisions, and why double hashing helps

A hash squeezes infinitely many strings into M values, so different strings must sometimes share a hash. This is a collision. With a tiny modulus they are easy to produce: under B = 31, M = 101, both "ab" and "dj" hash to 33, since 4·31 + 10 = 134 and 134 mod 101 = 33. In fact the pigeonhole principle guarantees a collision among the 676 two-letter strings, because there are only 101 possible values. The Java file checks both facts with the general version of the hash.

static long polyHash(String s, long base, long mod) {
    long h = 0;
    for (int i = 0; i < s.length(); i++) {
        h = (h * base + (s.charAt(i) - 'a' + 1)) % mod;
    }
    return h;
}

With M ≈ 10^9, one fixed comparison of two different strings collides with probability about 1/M, which is tiny. The danger is the birthday effect: among k strings there are about k^2 / 2 pairs, so with k = 10^5 strings in one hash set we expect roughly 5 collisions. Two remedies:

Application: counting distinct substrings

A string of length n has n(n+1)/2 non-empty substrings. Count how many of them are different. For "abab" the answer is 7: a, b, ab, ba, aba, bab, abab.

Brute force. Put every substring itself into a HashSet<String>. Creating and hashing a substring costs its length, so the total is O(n^3).

static int countDistinctBrute(String s) {
    Set<String> seen = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + 1; j <= s.length(); j++) seen.add(s.substring(i, j));
    }
    return seen.size();
}

With rolling hashes. Fix a start i and extend the end j one character at a time. Each extension updates both hashes in O(1) (Horner’s rule again), and the packed double hash goes into a HashSet<Long>. The total is O(n^2).

static int countDistinctHashing(String s) {
    final long M1 = 1_000_000_007L, B1 = 31, M2 = 1_000_000_009L, B2 = 37;
    int n = s.length();
    Set<Long> seen = new HashSet<>();
    for (int i = 0; i < n; i++) {
        long h1 = 0, h2 = 0;
        for (int j = i; j < n; j++) {                // extend s[i..j] one char at a time
            int v = s.charAt(j) - 'a' + 1;
            h1 = (h1 * B1 + v) % M1;
            h2 = (h2 * B2 + v) % M2;
            long key = h1 * M2 + h2;                 // one long that is unique per pair (h1, h2)
            seen.add(key);
        }
    }
    return seen.size();
}

On "banana" both give 15, and on "mississippi" both give 53; the Java file also compares them on 200 random strings.

Pitfalls