Sign in to watch this lesson
Algorithms - Strings · 5:17
String Hashing
A polynomial rolling hash turns any string into one number, and prefix hashes let us compare two windows of any length with a single integer test. We build the hash of abc and the prefix hashes of abcab, align windows by a power of p instead of a modular inverse, pick the base and modulus, measure the birthday bound (476 colliding pairs among a million strings with one hash, none with two), and watch a Thue-Morse string break every 64-bit overflow hash.
You will learn
- Compute hash(s) = sum of s[i] p^i mod m with a -> 1, a prime base around the alphabet size and a prime modulus near 10^9, in 64-bit arithmetic
- Build prefix hashes and compare any two substrings in O(1) by lifting the earlier one by p^(j-i), handling negative remainders
- Estimate collision risk: about 1/m per comparison and about n^2/(2m) colliding pairs among n strings, and fix it with double hashing
- Explain why modulus 2^64 is hackable (Thue-Morse) and defend with a prime modulus and a base chosen at random at run time