liveBook · Manning

Hash collision

As explained in Algorithms Every Programmer Should Know

A hash collision occurs when distinct keys produce the same hash index or hash value.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines collisions, demonstrates weak and improved string hashes, and traces verification and worst-case costs.
Examples
Uses ACT and CAT to show an anagram collision and contrasts simple addition with positional powers.
What you can do after
Diagnose weak hashing by recognizing spurious hits, checking matching strings, and considering performance degradation.
How it connects
Connects collisions to Rabin–Karp, rolling hashes, hash functions, sliding windows, and hash maps.

Also explained in

Compare how 6 books explain hash collision →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.