Course contentsShow
← Computer Science
Lesson 412 of 2,87210. Hash TablesFree lesson

Polynomial Rolling Hash for Strings

Computing string hashes as polynomial evaluations: h(s) = s[0]*p^(n-1) + s[1]*p^(n-2) + ... + s[n-1].

Polynomial Rolling Hash for Strings

You'll learn: How to compute a single numeric hash value for a string by treating it as a polynomial expression.


The Core Idea

The basic string hashing approach you learned earlier (like summing character values) has a big problem: it produces the same hash for anagrams. "abc" and "cab" would collide constantly!

Polynomial rolling hash solves this by making position matter. We treat the string as coefficients of a polynomial, where each character's position gives it a different "weight."

The formula is:

h(s) = s[0] × p^(n-1) + s[1] × p^(n-2) + ... + s[n-1]

Where:

  • s[i] is the numeric value of character at position i (like ASCII value)
  • p is a prime number base (commonly 31 or 53)
  • n is the string length

Why This Works

Think of it like place values in our number system. In decimal, "123" means 1×100 + 2×10 + 3×1. Each digit's position changes its contribution. Similarly, 'a' at position 0 contributes much more (p^(n-1)) than 'a' at the last position.

For string "abc" with p=31:

h = 'a'×31² + 'b'×31¹ + 'c'×31⁰
h = 97×961 + 98×31 + 99×1
h = 93,217 + 3,038 + 99 = 96,354

String "cab" would give a completely different hash because each character appears at different positions with different weights.

The word "rolling" hints at an optimization you'll learn later: you can update the hash efficiently when sliding through a string.

Key Takeaway: Polynomial rolling hash computes h(s) = s[0]*p^(n-1) + s[1]*p^(n-2) + ... + s[n-1], giving each character a position-dependent weight to minimize collisions between similar strings.