String Hashing and Fingerprints
Polynomial rolling hashes turn strings into integers that can be compared and updated in constant time, powering fast substring algorithms.
Turning a string into a number
A polynomial hash treats a string as the digits of a number in some base and reduces it modulo a large prime. For characters c0, c1, ..., c(m-1) the hash is c0*base^(m-1) + ... + c(m-1), all taken modulo the prime. Two equal strings always hash equally, and unequal strings collide only rarely with a well-chosen base and modulus.
Why rolling is the point
The design pays off when comparing many overlapping windows of a text. A rolling update recomputes the hash of the next window from the current one in O(1): subtract the leaving character's weighted contribution, multiply by the base, and add the entering character. This is what makes Rabin-Karp substring search efficient.
- Compute a length-m hash: O(m) once
- Slide the window: O(1) per step
- Compare two substrings by hash: O(1)
- False positives possible — verify on a hash match
Choosing base and modulus
The base should exceed the alphabet size and the modulus should be a large prime to spread values and limit collisions. Using a modulus near the machine word size keeps arithmetic fast, and using two independent hashes together (a double hash) makes an accidental collision astronomically unlikely, which matters because adversarial inputs can otherwise be engineered to collide.
Where fingerprints are used
String hashing supports fast substring comparison, longest-common-substring search by binary-searching the length and hashing candidates, plagiarism detection through document fingerprints, and deduplication of data blocks. It complements structural methods like suffix trees by offering constant-time equality tests without building an index, at the price of a small false-positive rate that verification removes.