Course contentsShow
← Computer Science
Lesson 833 of 2,87219. Searching and SelectionFree lesson

Rabin-Karp: Collision Handling

Handle hash collisions in Rabin-Karp and understand worst-case behavior when multiple false positives occur.

Rabin-Karp: Collision Handling

You'll learn how Rabin-Karp deals with hash collisions and why they matter for performance.

In the Rabin-Karp algorithm, we use a rolling hash to quickly compare a pattern with substrings of text. But here's the catch: hash collisions can occur—two different strings might produce the same hash value. When our rolling hash matches the pattern's hash, we can't immediately declare victory; we might have a false positive.

The Collision Problem

Think of hash values like apartment numbers. Just because two people live in apartment 304 in different buildings doesn't mean they're the same person. Similarly, different strings can share the same hash value, especially when using modular arithmetic to keep hash values manageable.

How Rabin-Karp Handles Collisions

When the rolling hash of a substring matches the pattern's hash:

  1. Don't assume it's a match yet
  2. Verify character-by-character that the substring actually equals the pattern
  3. Only confirm a match if every character matches

This verification step is crucial. Without it, you'd report false matches.

Worst-Case Behavior

In the worst case, every position produces a hash collision. This forces character-by-character verification at every position, degrading performance to O(nm)—the same as the naive approach! This happens when:

  • The hash function is poorly chosen
  • The text and pattern conspire to produce many collisions
  • The modulus is too small

For example, if all substrings hash to the same value, you gain nothing from the rolling hash optimization.

Key Takeaway: Rabin-Karp must verify every hash match with character-by-character comparison to handle collisions correctly. While average performance is good, frequent collisions can degrade it to naive worst-case O(nm) time, making hash function choice critical.