Special hashes

A **rolling hash** hashes every window of a string in O(1) per slide instead of O(window). Treat the window as a number in base B: hash = c0·B^(m-1) + c1·B^(m-2) + … + c(m-1), taken modulo a large number. To slide, subtract the leaving character times B^(m-1), multiply by B and add the entering character.

**Rabin-Karp** uses this to search for a pattern: compute the pattern's hash, slide a window over the text, and compare characters only when the two hashes are equal. Different strings can still share a hash, so an equal hash must be *verified* with a real comparison. Choose the “Tiny modulus (a collision)” preset: with modulus 101 the windows adi and dia have the same hash as the pattern aaa and are rejected only by the character check.

1static int indexOf(String text, String pat, long mod) {
2    int n = text.length(), m = pat.length(); final long B = 31;
3    if (m > n) return -1;
4    long high = 1, hp = 0, hw = 0;
5    for (int i = 0; i < m - 1; i++) high = high * B % mod;            // B^(m-1) % mod
6    for (int i = 0; i < m; i++) {
7        hp = (hp * B + pat.charAt(i)) % mod;                           // hash of the pattern
8        hw = (hw * B + text.charAt(i)) % mod;                          // hash of the first window
9    }
10    for (int s = 0; s + m <= n; s++) {
11        if (hp == hw && text.startsWith(pat, s)) return s;             // equal hashes may still collide: verify
12        if (s + m < n)                                                  // slide: drop text[s], add text[s + m]
13            hw = ((hw - text.charAt(s) * high % mod + mod) * B + text.charAt(s + m)) % mod;
14    }
15    return -1;
16}

1static int indexOf(String text, String pat, long mod) {
2    int n = text.length(), m = pat.length(); final long B = 31;
3    if (m > n) return -1;
4    long high = 1, hp = 0, hw = 0;
5    for (int i = 0; i < m - 1; i++) high = high * B % mod;            // B^(m-1) % mod
6    for (int i = 0; i < m; i++) {
7        hp = (hp * B + pat.charAt(i)) % mod;                           // hash of the pattern
8        hw = (hw * B + text.charAt(i)) % mod;                          // hash of the first window
9    }
10    for (int s = 0; s + m <= n; s++) {
11        if (hp == hw && text.startsWith(pat, s)) return s;             // equal hashes may still collide: verify
12        if (s + m < n)                                                  // slide: drop text[s], add text[s + m]
13            hw = ((hw - text.charAt(s) * high % mod + mod) * B + text.charAt(s + m)) % mod;
14    }
15    return -1;
16}

Any fixed hash function has inputs that collide badly: an adversary who knows it can pick keys that all land in one bucket. **Universal hashing** defeats this by choosing the function *at random* from a family when the table is created. A classic family for integer keys is h(k) = ((a·k + b) mod p) mod m, where p is a prime larger than every key, a is chosen from 1..p-1 and b from 0..p-1.

For such a family, any two distinct keys collide with probability at most 1/m, whatever the keys are. The guarantee is about the random choice, not about the data, so no input is bad in advance. The animation's “Universal hash” preset uses ((a·k + 7) mod 101) mod m with a multiplier a that you can change: the same keys spread differently for different a.

1final class UniversalHash {
2    private static final long P = 2_147_483_647L;                 // prime larger than every int key
3    private final long a, b; private final int m;
4    UniversalHash(int m, java.util.Random rnd) {
5        this.m = m;
6        this.a = 1 + (long) (rnd.nextDouble() * (P - 1));          // 1 .. P-1
7        this.b = (long) (rnd.nextDouble() * P);                    // 0 .. P-1
8    }
9    int hash(int key) { return (int) (((a * key + b) % P) % m); }  // a * key stays below 2^63 for 0 <= key < 2^31
10}

1class ChainedHashSet {
2    private final int m, variant, a;                                // m buckets
3    private final LinkedList<Integer>[] table;                      // one chain per bucket
4    int hash(int key) {                                             // the option picks one variant
5        switch (variant) {
6            case 0: return Math.floorMod(key, m);
7            case 1: return (int) (m * ((key * 0.6180339887) % 1.0));
8            case 2: return 0;                                       // worst case: every key collides
9            default: return ((a * key + 7) % 101) % m;              // universal-style family
10        }
11    }
12    boolean add(int key) {
13        LinkedList<Integer> chain = table[hash(key)];
14        if (chain.contains(key)) return false;                      // walk the chain: duplicate
15        chain.add(key); return true;                                // append to the chain
16    }
17    boolean contains(int key) { return table[hash(key)].contains(key); }
18    boolean remove(int key) { return table[hash(key)].remove((Integer) key); }
19}

A **perfect hash function** maps a *fixed* set of keys to distinct slots: no collisions at all, so a lookup is a single probe in the worst case. It only works for a known, static set, such as the reserved words of a language.

The standard construction (FKS) uses two levels. A first universal hash splits the n keys into n buckets. A bucket holding k keys gets its own second-level table of size k² with a hash function re-picked until it has no collision; because the expected number of collisions in a k²-sized table is below one half, a random function succeeds after a couple of tries. The total space is O(n) on average, and every lookup costs two hash computations.

If a service builds a hash table from attacker-controlled keys (HTTP parameters, JSON field names) and the hash function is known, the attacker can send many keys that all collide. The table degrades to a list, each insertion costs O(n) and n keys cost O(n²): a small request can burn seconds of CPU. This is a **hash flooding** denial-of-service attack.

With Java's String.hashCode, colliding strings are easy to build: "Aa" and "BB" both hash to 2112, and so do "AaAa", "AaBB", "BBAa" and "BBBB" (2031744). Concatenating 10 blocks, each Aa or BB, gives 1024 different strings with the *same* hash code. Defences: Java 8+ treeifies long buckets for Comparable keys, many languages randomise their hash seed per process, and servers limit the number of parameters accepted. Run the “Worst case: all collide” preset to see the effect.

1static List<String> collidingStrings(int blocks) {
2    List<String> strs = List.of("");
3    for (int i = 0; i < blocks; i++) {
4        List<String> next = new ArrayList<>();
5        for (String s : strs) { next.add(s + "Aa"); next.add(s + "BB"); }   // "Aa" and "BB" have the same hashCode
6        strs = next;
7    }
8    return strs;                                                             // 2^blocks strings, one shared hashCode
9}

1class ChainedHashSet {
2    private final int m, variant, a;                                // m buckets
3    private final LinkedList<Integer>[] table;                      // one chain per bucket
4    int hash(int key) {                                             // the option picks one variant
5        switch (variant) {
6            case 0: return Math.floorMod(key, m);
7            case 1: return (int) (m * ((key * 0.6180339887) % 1.0));
8            case 2: return 0;                                       // worst case: every key collides
9            default: return ((a * key + 7) % 101) % m;              // universal-style family
10        }
11    }
12    boolean add(int key) {
13        LinkedList<Integer> chain = table[hash(key)];
14        if (chain.contains(key)) return false;                      // walk the chain: duplicate
15        chain.add(key); return true;                                // append to the chain
16    }
17    boolean contains(int key) { return table[hash(key)].contains(key); }
18    boolean remove(int key) { return table[hash(key)].remove((Integer) key); }
19}

Two facts are easy to mix up. Equal objects **must** have equal hash codes. Unequal objects **may** have equal hash codes. So a matching hash proves nothing about equality: it only says the two keys are worth comparing. A hash table always finishes with equals before declaring a hit.

The same applies to hash-based shortcuts in algorithms: a Rabin-Karp window with the pattern's hash, or a file with the same checksum as another, is a *candidate*. Use the hash to reject quickly, and confirm candidates with a real comparison unless a false positive is acceptable (and with a cryptographic hash, it is negligibly unlikely).

1static void collisionIsNotEquality() {
2    String a = "Aa", b = "BB";
3    System.out.println(a.hashCode() == b.hashCode());     // true: both 2112
4    System.out.println(a.equals(b));                       // false: different strings
5    Set<String> set = new HashSet<>(List.of(a, b));
6    System.out.println(set.size());                        // 2: equals separates them inside the shared bucket
7}