a rolling hash

Suppose you want to compare every length-5 window of a long text against a target, but recomputing a fingerprint of each window from scratch is slow. A rolling hash is a trick that lets you slide the window one step and update the fingerprint in constant time — drop the character leaving on the left, add the one entering on the right — instead of rereading the whole window. It turns a sequence of overlapping windows into a stream of cheap updates.

The standard construction treats a window of characters as the digits of a number in some base b, taken modulo a large prime q to keep it small. The hash of characters c0 c1 ... c(m-1) is (c0*b^(m-1) + c1*b^(m-2) + ... + c(m-1)) mod q, a polynomial in b. The magic is the update rule when the window slides right by one: subtract the contribution of the outgoing leftmost character (its value times b^(m-1)), multiply the whole thing by b to shift every remaining digit up a place, then add the incoming character — all mod q. That is a constant number of arithmetic operations, so each slide costs O(1) after an O(m) setup. Choosing q prime (and often the base b at random) keeps the values well-spread and makes accidental clashes rare.

Rolling hashes are the heart of the Rabin-Karp algorithm and show up wherever you need to compare many substrings quickly: detecting duplicate paragraphs, content-defined chunking in backup systems, and plagiarism checkers. The crucial honesty: a hash match is a strong hint, not a proof. Two different windows can hash to the same value (a collision), so after a hash match you should verify the characters directly. With a good random prime the collision probability per comparison is about 1/q, tiny but not zero — treat the hash as a fast filter, not a final answer.