THE ROLLING HASH — a dart

THE ROLLING HASH slide the window, update in O(1) — drop the old, add the new

To search a long text for a pattern, Rabin-Karp hashes a sliding window and compares hashes instead of characters. The trick is that when the window slides one step, you do not rehash from scratch: you subtract the contribution of the character leaving, shift the base, and add the character entering — an O(1) update instead of O(w). The window hash carries its state forward across the slide, so a whole-text scan drops from O(nw) to O(n). It powers substring search, rsync’s block matching, and plagiarism detection.

THE TECHNIQUE h’ = (h − old·B^(w−1))·B + new — O(1) slide

The demo hashes a 3-wide window, then rolls it one step by dropping the high term and adding the new char — the rolled hash equals a fresh recompute: live demo

HISTORY & CREDIT Rabin & Karp · 1987

“Every window must be hashed from its characters.” — only the first; each next window is one subtract, one shift, one add. cited

the window hash · h = Σ cᵢ · B^(w−1−i) — a positional polynomial in base B.
the roll · h’ = (h − c₀·B^(w−1))·B + cₙₑ₣ — drop, shift, add: O(1).
1987 · Michael Rabin & Richard Karp — hashing for fast substring search.

A window hash that walks the text one cheap update at a time — state carried across the slide, never rebuilt. incremental

RECOMMEND FOR I-13 the O(1) slide, on the compiler

On the canonical compiler, the rolled hash of window [2,5,9] (2086) equals a fresh recompute of the same window:

$ i13 run zd_rollinghash.i13 # roll [7,2,5]->[2,5,9] RUN OK · 132 step(s) · peak stack 8 · call depth 4 h0 = 6794 -- hash of window [7,2,5] h1_roll = 2086 -- rolled: (h0 - 7*B^2)*B + 9 h1_recompute = 2086 -- fresh hash of [2,5,9] match = 1

Recommend as a NULL — incremental recomputation, i.e. resource. The rolling hash returns exactly the value a from-scratch hash would (i13 prints 2086 both ways); the only difference is that it updates in O(1) by carrying window state forward. That is the resource axis (B40) — a cheaper mechanism for the same pinned output. It brushes conserve-remainder (state carried across a seam) but conserves no lost quantity; it merely avoids recomputation. NULL.