Author: Ramesh Vankayala

Introduction

In Part 1, we learned a simple rolling hash using the sum of ASCII values.

Hash = ASCII1 + ASCII2 + ASCII3

Although this helps us understand the concept, it is not suitable for real-world applications because many different strings can produce the same hash.

Example:

ABC

65 + 66 + 67 = 198

CAB

67 + 65 + 66 = 198

Different strings, same hash.

This is called a Hash Collision.

To reduce collisions, the Rabin-Karp algorithm uses Polynomial Rolling Hash.

Why Do We Need Polynomial Hashing?

Think of a vehicle registration number.

KA01AB1234

If we only added all digits together, many different registration numbers would produce the same total.

Instead, every position contributes differently.

The same idea is applied in polynomial hashing.

Characters appearing at different positions receive different weights.

Polynomial Hash Formula

The hash of a string is calculated as:

[
Hash = s_0 \times p^{m-1}

s_1 \times p^{m-2}
...
s_{m-1} \times p^0
]

Where

Symbol	Meaning
s	Character value
p	Base (31, 53, or 256 are common choices)
m	Length of the string

Example

String

ABC

ASCII values

Character	ASCII
A	65
B	66
C	67

Assume

Base = 31

Weights

Character	Weight
A	31²
B	31¹
C	31⁰

Step-by-Step Calculation

31² = 961

31¹ = 31

31⁰ = 1

Character	Formula	Value
A	65 × 961	62,465
B	66 × 31	2,046
C	67 × 1	67

Final Hash

62465 + 2046 + 67

=64578

Unlike the simple ASCII sum, changing the order of the characters now changes the hash.

Why Choose Base 31?

Interviewers often ask:

"Why is the base usually 31?"

Reasons:

It is a prime number.
It distributes hash values well.
It reduces collisions.
Multiplication by 31 is computationally efficient.
Java's String.hashCode() also uses 31.

What is Modulo Arithmetic?

Imagine calculating the hash for a string with one million characters.

The number becomes extremely large.

Eventually, integer overflow occurs.

To avoid this, we keep the hash within a fixed range.

Instead of storing

98765432123456789

we store

98765432123456789 % 1,000,000,007

Why 1,000,000,007?

This number is frequently used because:

It is prime.
It fits within 32-bit integer calculations.
It minimizes collisions.
It is efficient for modular arithmetic.

Rolling Hash Formula

Suppose

ABCDE

Window size

Current window

ABC

Next window

BCD

Instead of recalculating the entire polynomial hash, we update it.

Conceptually:

Remove contribution of A

↓

Shift remaining characters

↓

Add D

This is why each window update is O(1).

Java Example

public class PolynomialHash {

    static final int BASE = 31;

    public static long calculateHash(String s) {

        long hash = 0;

        for (int i = 0; i < s.length(); i++) {
            hash = hash * BASE + s.charAt(i);
        }

        return hash;
    }

    public static void main(String[] args) {

        String s = "ABC";

        System.out.println(calculateHash(s));

    }
}

Output

Rabin–Karp Algorithm

The complete algorithm follows these steps:

Pattern

↓

Calculate Pattern Hash

↓

Calculate First Window Hash

↓

Compare Hashes

↓

Different?

↓

Move Window

↓

Update Hash

↓

Compare Again

↓

Hash Match?

↓

Compare Characters

↓

Substring Found

Why Verify Characters?

Even polynomial hashes can collide.

Suppose

Hash(Window)

=

Hash(Pattern)

This does not guarantee the strings are identical.

Therefore, after a hash match, compare each character.

Hash Match

↓

Character Comparison

↓

Equal?

↓

Substring Found

Complexity

Operation	Complexity
Pattern Hash	O(m)
First Window Hash	O(m)
Sliding Window Updates	O(n)
Average Overall	O(n + m)
Worst Case (many collisions)	O(n × m)

Where:

n = length of the text
m = length of the pattern

Common Interview Questions

1. Why is Rabin–Karp faster than brute force?

Because it compares hash values instead of comparing every character in every window.

2. What is a Hash Collision?

Two different strings generating the same hash value.

3. Why verify characters after hash matching?

Because equal hashes do not always mean equal strings.

4. Why use modulo?

To prevent integer overflow and keep hash values within a manageable range.

5. Why is 31 commonly chosen?

Prime number
Better distribution
Lower collision probability
Used by Java's String.hashCode()

6. Where is Rabin–Karp used?

Search engines
Plagiarism detection
DNA sequence matching
Virus signature scanning
Text editors
Log analysis
Malware detection
Duplicate document detection

Interview Summary

A strong interview answer should include these points:

Start with the brute-force solution and its O(n × m) complexity.
Explain that hashing converts a string into a number.
Introduce polynomial hashing to reduce collisions.
Explain rolling hash for O(1) window updates.
Mention modulo arithmetic to avoid overflow.
Discuss hash collisions and character verification.
Conclude that Rabin–Karp has an average time complexity of O(n + m).

Key Takeaways

Polynomial hashing is significantly more reliable than a simple ASCII sum.
Rolling hash avoids recomputing every window from scratch.
Modulo arithmetic prevents overflow and keeps hashes manageable.
Rabin–Karp combines rolling hash with character verification to efficiently solve substring search problems.
Understanding these concepts provides a solid foundation for advanced string algorithms such as KMP, suffix arrays, suffix automata, and string indexing.

A great follow-up article would be Part 3: "Rolling Hash Dry Run with Java Debugger", where every iteration is shown in a table with:

windowStart
windowEnd
oldHash
newHash
outgoing character
incoming character
hash comparison
character verification
decision (move/found)

This format is especially effective for interview preparation because it makes the algorithm's execution easy to visualize.

rameshvanka

Friday, 31 July 2026

Rolling Hash in Java (Hash Collision Solving) – Part 2: Polynomial Hashing, Modulo Arithmetic, and Rabin–Karp (Interview Guide)