liveBook · Manning

Rolling hash

As explained in Algorithms Every Programmer Should Know

A rolling hash updates the hash of a sliding window by removing the outgoing value and incorporating the incoming value instead of recomputing the hash from scratch.

When a fixed-size window slides across a string, recomputing its hash from every character repeats work. A rolling hash reuses the previous window’s hash: remove the outgoing character’s contribution and add the incoming character’s contribution. This updates the hash in constant time per shift. section 4.0 section 4.4

Slide from ALI to LIC

Map letters to numbers: A=1, L=12, I=9, C=3. With a simple sum hash, ALI hashes to 22. When the window shifts, subtract A’s value and add C’s: 22 − 1 + 3 = 24, the hash for LIC. A positional hash can distinguish more strings: for example, using powers of 10 gives characters different place values. Its rolling update removes the outgoing character’s weighted contribution before adding the new character. section 4.1

A hash match is only a candidate match: different substrings can collide and produce the same value. Rabin–Karp therefore checks the actual characters whenever hashes match. A weak hash can cause frequent collisions and repeated checks, making performance degrade to O(n × m); the average and best cases are O(n + m). section 4.1 section 4.0

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through a numeric example, a positional-hash update, collision checks, and complexity, without deriving a general hash formula.
Examples
Uses alphabet-number mappings to update the hash from ALI to LIC and contrasts simple-sum and positional hashes.
What you can do after
Apply it via Rabin–Karp to update text-window hashes and verify candidate matches character by character.
How it connects
Connects rolling hash to Rabin–Karp, string matching, sliding windows, and hash collisions.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.