Lesson · Strings and Pattern Matching · Hashing, and the verification

A Rolling Hash, and a Collision You Can Read

Rabin–Karp hashes the pattern once and each window in constant time from the window before, so the scan is n arithmetic steps. Equal hashes are not a match: on the lab's opening text 7 windows hash to 36 and only 4 of them are occurrences. The other three are printed with their characters so they can be checked by eye, and the verification that separates them is not an optimisation that can be skipped — it is the only reason the answer is right.

Open the interactive lesson Practice

hash of a window: its characters as digits in base b, taken modulo m roll forward: drop the leading digit, shift, add the trailing one base 256, modulus 41: the pattern ain hashes to 36 41 windows, 7 hash equal to 36, 4 are matches, 3 are collisions the collisions are at offsets 33, 36 and 38: ' th', 'e p', 'pla' 21 characters compared verifying, 9 of them spent on the collisions

One number per window, and the three windows that share the pattern's

Core ideas

What this lesson establishes

The hard idea is that the hash decides nothing on its own. The other two are how the roll works and why the arithmetic is exact rather than machine-dependent.

A hash equal is a candidate, and a candidate must be verified

The scan compares numbers, and equal numbers mean the characters might be equal. On the opening text 7 of the 41 windows hash to 36, the pattern's value, and 3 of those are not ain at all: the panel lists them with their characters, at offsets 33, 36 and 38. Every one of the 7 costs m = 3 character comparisons to settle, so 21 comparisons are spent on verification of which 9 establish nothing but a false alarm. Removing the verification does not make the algorithm faster, it makes it wrong.

The roll is the one value on the page derived from another value

Every other number in this kit is computed from the input. The next window's hash is computed from the current one: subtract the leading character's contribution, multiply by the base, add the trailing character, and reduce. That makes it the only place where an error can accumulate silently rather than being recomputed away, so the panel recomputes every window's hash from scratch and requires the two to agree — on this text the disagreement count is 0.

The arithmetic is exact, so the collisions are the same everywhere

The hashes are computed in arbitrary-precision integers, not in machine doubles. That matters more than it looks on a page whose subject is that two particular windows collide: if the modulus arithmetic overflowed or rounded, the collision would be a property of the reader's browser rather than of the text, and the three offsets printed above would not be checkable by hand. They are, and the worked example below does check one.

The material

One number per window, rolled forward, and what equality does not prove

The hash, the roll and its correctness, the collisions on this text listed exactly, and the cost of settling them.

Definition · The window hash

Fix a base b and a modulus q. For a string w of length m the hash is the value of w read as an m-digit number in base b, taken modulo q: H(w) = (w[0] b^(m−1) + w[1] b^(m−2) + ... + w[m−1]) mod q, where each character contributes its code point.

Theorem · The roll is correct

Let w = t[s..s+m−1] and w' = t[s+1..s+m]. Then H(w') = (b (H(w) − t[s] b^(m−1)) + t[s+m]) mod q, so each successive hash costs a constant number of arithmetic operations once b^(m−1) mod q is known.

Write H(w) without the reduction as S = sum over i of t[s+i] b^(m−1−i). Subtracting t[s] b^(m−1) removes the leading term, leaving sum over i ≥ 1 of t[s+i] b^(m−1−i).

Multiplying by b raises every remaining exponent by one, giving sum over i ≥ 1 of t[s+i] b^(m−i), which is the first m − 1 terms of w''s expansion. Adding t[s+m] b^0 completes it.

Reduction modulo q commutes with addition and multiplication, so performing it at each step gives the same residue as performing it at the end. The cost is one multiplication, one subtraction, one addition and one reduction, independent of m.

□

So the scan is n steps of constant arithmetic plus m character comparisons for each candidate. The panel counts the second part and prints it as characters compared verifying, because that is the part whose size depends on the text.

Example · Seven candidates, four matches, three collisions

The lab opens on the rain in spain stays mainly in the plain and the pattern ain, at base 256 and modulus 41. The pattern hashes to 36. Of the 41 windows, 7 hash to 36. Four are the real occurrences, at offsets 5, 14, 25 and 40. The other three are at offsets 33, 36 and 38, and their characters are the space followed by th, then e space p, then pla. None of those is ain and all of them hash to 36.

The panel prints those three in a table with their hashes beside the pattern's, so that a reader can copy one out and check it. The worked example below does exactly that for the first of them, in five lines of arithmetic.

What the collisions cost, and what the cost does not depend on

Each of the 7 candidates costs m = 3 character comparisons to settle, whether it turns out to be a match or not, so the verification bill is 21 comparisons. Nine of those — three collisions at three characters each — produce nothing. The panel reports both numbers, as characters compared verifying and wasted on collisions.

Nothing in the algorithm notices the waste. A collision is indistinguishable from a match until the characters are compared, which is why the comparison is unconditional and why an implementation that trusted the hash would be wrong on this very text, at three offsets, silently.

Exact arithmetic, and why it is not a detail here

At base 256 a three-character window is a number up to 256^3, about 16.7 million, which fits a double comfortably. At twelve characters it does not, and a rounded intermediate would change which windows collide. The kit computes every hash in arbitrary-precision integers, so the three offsets above are the same three on every machine, and a reader who checks one by hand and disagrees has found a bug rather than a rounding difference.

The same choice is what makes the panel's independent recomputation meaningful. Each window's rolled hash is compared with the same window hashed from its characters, and the count of disagreements is printed; on this text it is 0. If the arithmetic were approximate that check would be comparing two approximations and could pass while both were wrong.

Where the cost actually goes

Rabin–Karp's attraction is that the scan is arithmetic rather than comparison, so the work per window does not depend on m. Its exposure is that the number of candidates does depend on the modulus, and the modulus is a choice. Three collisions on 41 windows is a 7 per cent false-alarm rate on this text at this modulus, and the sibling lesson “Choosing a Modulus, and What the Sweep Says” runs the same text at every prime under 200 to show what that rate does as the choice moves.

Interactive

A rolling hash, and a collision you can read off the page

Equal hashes are not a match, and the verification is not optional

Pick a base and a modulus, and read the collisions off the table

Every bar is one window and its height is that window's hash, with the pattern's value drawn across. The upper table lists every window whose hash matched, marked as a real match or a collision, and every hash is an arbitrary-precision integer so the collisions are the same on every machine.

Worked example

The text

The pattern

The base

The modulus

Windows—

Hashes equal to the pattern's—

Real matches—

Collisions—

Characters compared verifying—

Wasted on collisions—

Primes under 200 that collide—

Largest of them—

The hash of a window is its characters read as digits in the chosen base, taken modulo the chosen modulus, and the next window is computed from this one by removing the leading digit and appending the trailing one. Equal hashes are NOT a match: the algorithm must compare the characters, and the count of times it had to is on the page. Lower the modulus until the collisions appear, then raise it and watch them go — and notice that they do not go monotonically.

Method

Hashing a window, rolling it, and never believing it

Compute one hash by hand, roll it once, and check a collision. Three short calculations settle what the page is about.

Compute the pattern's hash first, and keep it

ain is 97, 105, 110 in code points, so at base 256 it is 97 × 65536 + 105 × 256 + 110 = 6383982, and 6383982 mod 41 = 36. Every comparison on the page is against that one number.

Roll one window by hand

From the window at offset 0 to the window at offset 1: subtract the leading character's contribution, multiply by the base, add the new trailing character, reduce. Doing it once makes it obvious that the cost does not grow with m.

Verify a candidate before recording it

Compare the m characters. This is not a defensive extra; the panel's table has three rows where the hash agreed and the characters did not, and skipping the comparison would report all three as matches.

Check a collision by hand, at least once

Take offset 33, the window consisting of a space and th, and compute its hash from its three code points. Getting 36 is the moment the page stops being an assertion about hashing and becomes a fact about this text.

Hashes, rolls, and what equality establishes

Score 0 / 0

Choose the answer you can justify.

One collision, checked from its characters

The text is the rain in spain stays mainly in the plain, the pattern is ain, the base is 256 and the modulus is 41. Code points: space is 32, a is 97, e is 101, h is 104, i is 105, l is 108, n is 110, p is 112, t is 116.

the pattern a i n 97, 105, 110 97 x 65536 + 105 x 256 + 110 = 6383982 6383982 mod 41 = 36 offset 33 ' t h' 32, 116, 104 32 x 65536 + 116 x 256 + 104 = 2126952 2126952 mod 41 = 36 SAME compare characters: ' ' vs 'a' FAIL a collision windows = 41 hashes equal to 36 = 7 real matches offsets 5, 14, 25, 40 = 4 collisions offsets 33, 36, 38 = 3 characters compared verifying 7 x 3 = 21 wasted on the collisions 3 x 3 = 9 rolled hashes disagreeing with a fresh one = 0

Two three-character strings with nothing in common produced the same residue, and the only reason the algorithm did not report the space and th as an occurrence of ain is the comparison on the line below. That line is not an optimisation guard; it is where the correctness lives.

For a faded rehearsal, check offset 38, whose characters are pla — 112, 108, 97. The supplied first move is the base expansion: 112 × 65536 + 108 × 256 + 97. Reduce it modulo 41 and confirm 36, then say how many of the three collisions you would have caught by comparing only the first character.

Then change the modulus to 1000003 and count again. The candidates fall from 7 to 4 and the verification bill from 21 to 12; the matches do not move. Say why the match count cannot move however the modulus changes, and what that tells you about which of the two counters is measuring the algorithm and which is measuring the choice.

Common mistakes

Calling the verification an optimisation that can be skippedIt is the correctness argument. Without it the algorithm reports 7 positions on this text, of which 3 are wrong, and the failure is silent because a hash gives no signal of its own reliability. Every claim the page makes about the method's speed is a claim about the method with the comparison in it.

Reading a low collision count as a property of the hash functionThree on 41 windows is a property of this text, this base and this modulus together. The sibling lesson runs the same text and base at 46 different moduli and gets collision counts from 0 to 18, which is what it looks like when a number depends on a choice rather than on the algorithm.

Assuming a collision must share characters with the patternA residue is a residue. Offset 33 is a space followed by th and hashes to the same 36 as ain; they agree in no position. Checking only the first character would separate all three here and would not in general, which is why the comparison is over all m.

Check your understanding

✓

Finish when you can hash a window by hand, roll it once, and verify one collision from its code points.

You should be able to state the hash as a base expansion modulo q, prove the roll correct, say why its cost is independent of m, explain why equal hashes are one-sided evidence, compute a collision's residue from its characters, and say what the independent recomputation is protecting.

Note: Three collisions on 41 windows is one modulus's worth of evidence. “Choosing a Modulus, and What the Sweep Says” keeps this text and this base and runs every prime under 200, which turns “collisions are rare” into a count — and shows that the count does not fall as the modulus rises.