liveBook · Manning

False positive

As explained in Algorithms Every Programmer Should Know

A spurious hit is an invalid candidate match caused by different strings producing the same hash value.

In Rabin–Karp string matching, a false positive (or spurious hit) occurs when different substrings produce the same hash. A matching hash is only a candidate: compare the characters to confirm it. section 4.1

Anagrams collide

With a hash that simply adds character values, “ACT” and “CAT” receive the same hash despite being different strings. That collision creates a false positive; a positional hash can reduce such collisions, but matching hashes still require character-by-character verification. section 4.4 section 4.1

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 a simple hash gives two substrings the same value and how positional powers give them different values. section 4.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines collisions, demonstrates weak and improved hashes, and links frequent collisions to worst-case O(n × m) performance.
Examples
Uses “ACT” and “CAT” to show how an addition-based hash creates a false positive.
What you can do after
Diagnose false candidate matches by checking whether different substrings share a hash and verifying matching hashes character by character.
How it connects
Connects hash collisions to Rabin–Karp, rolling hash, and character-by-character string comparison.

Also explained in

Compare how 26 books explain false positive →

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.