Rabin-Karp rolling hash

Compare NUMBERS, not strings. Hash each window; a rolling hash updates it in O(1) per slide.

The rolling hash

• Read a string as a base-B number mod a large prime
• Slide the window: drop the outgoing char, shift, add the incoming char
• H' = ((H − s[i]·Bᵐ⁻¹)·B + s[i+m]) mod M — three ops, O(1)
• Comparing two hashes is O(1) regardless of pattern length

Watch the hash roll

Green = char that just entered · red = char that just left (toy modulus 101). 'abc' hashes to 22; window hits 22 → verify → match at 5.

Superpower: many patterns, one pass

Check each window's hash against a SET of k pattern hashes. 800 patterns: 200× faster than KMP×800.

Probabilistic, so verify

• A hash match is only PROBABLE → confirm with a character check
• Large prime modulus (~2⁶¹) → collision odds ~10⁻¹⁸ (zero seen in 2000 searches)
• Small/predictable modulus → hash-flooding → O(n·m)
• The hash is a filter, not a proof

Takeaway

Randomization + hashing buy CAPABILITIES: fingerprint, dedup, batch-compare. The rolling hash outgrew the algorithm — rsync, backup chunking, plagiarism, git. Next: Boyer-Moore — scan right-to-left, skip forward, read fewer than n chars.