Rolling hash
The conceptHow a program finds a long phrase without rechecking every letter
A rolling hash gives each stretch of text, or window, a number, and updates that number in one step when the window slides by one character. Comparing numbers is much cheaper than comparing whole stretches of text.
To find a 1,000-letter phrase, the naive way checks up to 1,000 letters at every position. A rolling hash slides a 1,000-letter window instead: each step drops the leaving letter's share, shifts the rest and adds the new letter.
Only where the window's number equals the phrase's number do you compare the actual letters. This method is called Rabin–Karp search.
What it’s forUpdates a window's hash when it slides one character to the right.
H′ = (b · (H − c_out · b^(m−1)) + c_in) mod p
- H, H′
- the hash of the old window and of the new window
- b, m
- the base, e.g. 256 for bytes, and the window length in characters
- c_out, c_in
- the character leaving on the left and the one entering on the right
- p
- a large prime that keeps the numbers small enough to fit in memory
What it givesThe new window's hash, computed in a fixed number of steps whatever the window length.
- Base 10, window length 3, no mod: window "123" has H = 123.
- Slide to "234": 10 · (123 − 1 · 100) + 4 = 10 · 23 + 4 = 234.