Skip to main content

Rolling Hash

Learn Rolling Hash (Strings, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

What is a Rolling Hash? A rolling hash updates a window's hash in O(1) as the window slides by one position, instead of recomputing from scratch (which would be O(k) per slide, O(n·k) overall). It's the "sliding window" idea applied to string hashing, and it's the engine behind Rabin-Karp pattern matching. To slide a window of size k forward by one character: remove the outgoing character's contribution, shift everything, then add the incoming character.

More lessons in Strings