concept · INFO-CS-ADS-205String Hashing and Rolling Hash
Learn how strings can be converted into numerical hash values and how rolling hashes update those values efficiently when a fixed-size window moves across text.
Explanation
Overview
String Hashing converts a string into a numerical value using a hash function. Rolling Hash is a technique that allows the hash of a new string window to be calculated from the previous window's hash without recomputing the entire value. These methods are useful for efficient substring comparison and pattern searching.
Key concepts
Hash functions; Polynomial hashing; Modular arithmetic; Rolling hash; Sliding window; Hash collisions
Variables
s: The input string.; m: The length of the string or current window.; B: The polynomial hash base.; M: The modulus used to limit hash values.; H(s): The hash value of string s.; outgoingCharacter: The character leaving the current window.
Complexity
initialHash: O(m) time.; rollingUpdate: O(1) arithmetic operations per window, assuming fixed-size integer arithmetic.; allWindows: O(n) time after initialization for a text of length n.; space: O(1) auxiliary space for a single rolling window.; collisionHandling: Exact equality may require O(m) character verification when hashes match.
Example
text: ABCDE; windowLength: 3; windows: ABC; BCD; explanation: The algorithm first calculates the hash of ABC. When the window moves to BCD, it removes the contribution of A, shifts the remaining polynomial value, and adds D. It repeats the process to calculate the hash of CDE.; result: Each next window hash can be calculated efficiently without hashing every character again.
Pseudocode
function rollingHash(text, patternLength, base, mod):
m = patternLength
hash = calculateHash(text[0 to m - 1])
power = base^(m - 1) mod mod
for i = 0 to length(text) - m:
process(hash, i)
if i < length(text) - m:
outgoing = value(text[i])
incoming = value(text[i + m])
hash = ((hash - outgoing * power) * base + incoming) mod mod
hash = (hash + mod) mod mod
Applications
Rabin-Karp pattern matching.; Duplicate substring detection.; Plagiarism detection.; Text comparison.; Competitive programming.; Large-scale string processing.
Variables
M
The length of the string or current window.
B
The polynomial hash base.
M
The modulus used to limit hash values.
H(s)
The hash value of string s.
Outgoing Character
The character leaving the current window.
Incoming Character
The character entering the next window.
Example or application
Explanation
The algorithm first calculates the hash of ABC. When the window moves to BCD, it removes the contribution of A, shifts the remaining polynomial value, and adds D. It repeats the process to calculate the hash of CDE.
Result
Each next window hash can be calculated efficiently without hashing every character again.
Definition
String Hashing converts a string into a numerical value using a hash function. Rolling Hash is a technique that allows the hash of a new string window to be calculated from the previous window's hash without recomputing the entire value. These methods are useful for efficient substring comparison and pattern searching.
Mathematical Representation
Polynomial Hash
H(s) = (s[0] × B^(m-1) + s[1] × B^(m-2) + ... + s[m-1]) mod M.
Rolling Hash
H_next = ((H_current - outgoingCharacter × B^(m-1)) × B + incomingCharacter) mod M.
Hashing Approach
Assign a numerical value to each character.
Choose a base and modulus.
Calculate the initial polynomial hash.
Remove the contribution of the outgoing character when the window moves.
Shift the remaining hash by multiplying it by the base.
Add the incoming character.
Apply the modulus to keep the hash within the selected range.
When comparing strings, verify actual characters if an exact match is required.
Pseudocode
function rollingHash(text, patternLength, base, mod):
m = patternLength
hash = calculateHash(text[0 to m - 1])
power = base^(m - 1) mod mod
for i = 0 to length(text) - m:
process(hash, i)
if i < length(text) - m:
outgoing = value(text[i])
incoming = value(text[i + m])
hash = ((hash - outgoing * power) * base + incoming) mod mod
hash = (hash + mod) mod mod
Complexity
Rolling Update
O(1) arithmetic operations per window, assuming fixed-size integer arithmetic.
All Windows
O(n) time after initialization for a text of length n.
Space
O(1) auxiliary space for a single rolling window.
Collision Handling
Exact equality may require O(m) character verification when hashes match.
Key Concepts
Hash functions
Polynomial hashing
Modular arithmetic
Rolling hash
Sliding window
Hash collisions
Substring comparison
Advantages
Updates fixed-length window hashes efficiently.
Supports fast expected-time pattern matching.
Can compare many substrings using precomputed hash information.
Is useful for duplicate detection and text comparison.
Forms the basis of the Rabin-Karp algorithm.
Limitations
Different strings can produce the same hash value.
Hash parameters must be selected carefully.
A single hash may have a non-negligible collision risk for some workloads.
Exact matching may require direct character verification.
Modular arithmetic and overflow handling must be implemented correctly.
Applications
Rabin-Karp pattern matching.
Duplicate substring detection.
Plagiarism detection.
Text comparison.
Competitive programming.
Large-scale string processing.
Related Topics
Rabin-Karp Algorithm
Naive Pattern Matching
Suffix Arrays
Hash Tables
Pattern Matching
Practice Question
Why is rolling hash faster than recalculating the hash of every substring independently?
Practice Answer
It updates the previous window's hash by removing the outgoing character and adding the incoming character, requiring constant-time arithmetic per shift.
Learning Objectives
Explain the central idea and purpose of string hashing and rolling hash.
Identify the assumptions, inputs, and conditions relevant to string hashing and rolling hash.
Evaluate an application of string hashing and rolling hash for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- String Algorithms and Pattern Matching
Suggest a correction or source · More in Algorithms & Data Structures