A hash collision happens when distinct keys or substrings produce the same hash value or index. In Rabin–Karp, matching hashes are only a signal to compare the actual characters: equal hashes do not prove equal strings. section 4.1 section 1.4.1
Collisions matter because they can:
- Create spurious matches that require character-by-character verification. section 4.1
- Degrade Rabin–Karp from average linear time to O(n × m) when collisions are frequent. section 4.4
- Slow hash-map operations from near O(1) to worst-case O(N) with a poorly designed hash function. section 1.4.1
A simple hash can confuse anagrams
A hash that adds character values gives “ACT” and “CAT” the same value. A better rolling hash using positional powers reduces this collision, but Rabin–Karp still verifies characters whenever hashes match. section 4.1 section 4.4
Figure 4.4 Two substrings previously with a simple hash function yield the same hash value. When the hash function is changed using powers of 10, the same two substrings yield different hash values. This reduces the problem of collision.
Compare how positional powers distinguish substrings that collide under a simpler hash. section 4.1





