✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-205

String 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

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.

Outgoing Character

The character leaving the current window.

Incoming Character

The character entering the next window.

Example or application

Text

ABCDE

Window Length

3

Windows

  • ABC

  • BCD

  • CDE

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

Initial Hash

O(m) time.

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