What is String Hashing and How Is It Used?
Learn how polynomial rolling hashes enable fast substring comparison, with real uses and how to answer this interview question well.
Expected Interview Answer
String hashing converts a string into a fixed-size numeric fingerprint using a polynomial rolling hash, typically computed modulo a large prime, so that two equal strings always hash to the same value and unequal strings almost always hash to different values, enabling O(1) substring comparison after O(n) preprocessing.
A polynomial hash treats a string as digits of a number in some base, computing hash(s) = s[0]*B^(n-1) + s[1]*B^(n-2) + ... + s[n-1] mod M for a chosen base B and modulus M, and this formulation lets you precompute prefix hashes and powers of B once in O(n), then answer “what is the hash of substring s[i..j]” in O(1) using prefix-hash subtraction. This underlies Rabin-Karp string matching, fast substring-equality checks in suffix-array construction, detecting duplicate substrings, and computing longest common extensions between two positions via binary search plus hash comparison. Because any fixed modulus admits adversarial inputs that collide, competitive and production use favors a large random prime modulus (or double hashing with two independent bases/moduli) chosen at runtime, and always verifies a hash match with a direct character comparison when correctness matters, not just speed. Double hashing reduces collision probability to roughly 1/(M1*M2), effectively eliminating practical collision risk.
- O(1) substring hash comparison after O(n) preprocess
- Powers Rabin-Karp and substring-equality checks
- Enables binary search for longest common extension
- Double hashing makes collisions practically negligible
AI Mentor Explanation
String hashing is like giving every possible spell of deliveries in an over a short numeric fingerprint computed from ball-by-ball outcomes, so two identical spells always produce the same fingerprint and different spells almost always produce different ones. Once you precompute a running fingerprint for the whole innings, checking whether any two overs had the exact same sequence of outcomes becomes an instant fingerprint comparison instead of replaying both overs ball by ball. Occasionally two genuinely different spells could coincidentally share a fingerprint, so a careful analyst always double-checks a fingerprint match against the actual ball log before declaring them identical. Using two independent fingerprint formulas at once makes an accidental coincidence astronomically unlikely.
Step-by-Step Explanation
Step 1
Choose base and modulus
Pick a base B larger than the alphabet size and a large prime modulus M (or two, for double hashing).
Step 2
Precompute prefix hashes and powers
Build prefix hash array and powers of B mod M in O(n), covering the whole string once.
Step 3
Answer substring hash queries in O(1)
Use prefix-hash subtraction: hash(s[i..j]) = (prefixHash[j+1] - prefixHash[i] * B^(j-i+1)) mod M.
Step 4
Verify on collision-sensitive matches
When hashes match and correctness matters, confirm with a direct substring comparison to rule out a rare collision.
What Interviewer Expects
- Explain the polynomial rolling hash formula and its O(1) substring query after O(n) preprocessing
- State the collision risk and why verification or double hashing matters
- Give real applications: Rabin-Karp, duplicate detection, longest common extension
- Know why a large random prime modulus is preferred over a small fixed one
Common Mistakes
- Using a small or fixed modulus vulnerable to adversarial collisions
- Skipping verification after a hash match when correctness is required
- Forgetting to precompute powers of the base, recomputing them per query
- Confusing string hashing with cryptographic hashing (different goals and guarantees)
Best Answer (HR Friendly)
“String hashing turns a string into a number so that comparing two strings becomes comparing two numbers, which is much faster than comparing characters one by one. I use it whenever I need fast substring comparisons at scale, like in Rabin-Karp search or detecting duplicate text, and I always verify a match directly when correctness really matters, since hash collisions are rare but possible.”
Code Example
class StringHasher:
def __init__(self, s, base=131, mod=1_000_000_007):
self.base = base
self.mod = mod
n = len(s)
self.prefix = [0] * (n + 1)
self.power = [1] * (n + 1)
for i, ch in enumerate(s):
self.prefix[i + 1] = (self.prefix[i] * base + ord(ch)) % mod
self.power[i + 1] = (self.power[i] * base) % mod
def substring_hash(self, i, j):
# hash of s[i:j], 0-indexed, half-open interval
length = j - i
return (self.prefix[j] - self.prefix[i] * self.power[length]) % self.mod
def has_duplicate_substring(s, length):
hasher = StringHasher(s)
seen = set()
for i in range(len(s) - length + 1):
h = hasher.substring_hash(i, i + length)
if h in seen:
return True
seen.add(h)
return FalseFollow-up Questions
- How would you defend against adversarial inputs designed to cause hash collisions?
- How does string hashing support binary-searching for the longest common extension?
- Why is double hashing preferred over a single hash function in competitive settings?
- How does string hashing compare to using a suffix array for substring comparison?
MCQ Practice
1. After O(n) preprocessing, how long does a substring hash query take with prefix hashing?
Prefix hash subtraction lets any substring hash be computed in O(1) once prefix hashes and powers of the base are precomputed.
2. Why is verification with a direct comparison recommended after a hash match?
Because hashing maps a large space of strings to a smaller numeric space, collisions are possible, so verification protects correctness.
3. What does double hashing (two independent bases/moduli) primarily achieve?
Combining two independent hash functions makes a coincidental collision on both simultaneously extremely unlikely, roughly the product of each collision probability.
Flash Cards
What formula underlies a polynomial rolling hash? — hash(s) = s[0]*B^(n-1) + s[1]*B^(n-2) + ... + s[n-1], computed mod M.
What is the time complexity of a substring hash query after preprocessing? — O(1), via prefix-hash subtraction.
Why should you verify a hash match with a direct comparison? — Because different strings can occasionally collide to the same hash value.
Name one classic use case of string hashing. — Rabin-Karp pattern matching, or fast duplicate/substring-equality detection.