Hash collision
= Hash collision
{title2=$x\ne y,\ h(x)=h(y)$}
A hash collision is a <function collision> of a <hash function> $h:U\to B$: two distinct <inputs> $x,y\in U$ have the same <output>, $h(x)=h(y)$. Repeating the same <input> is not a <hash collision>. Unequal hash values prove the keys differ; equal hash values only identify candidates that might be equal. This makes a <hash function> useful as a compact filter before comparing the original data.
Here is a deliberately simple example using <modular arithmetic>. Let $h(k)=k\bmod16$ for nonnegative <integer> keys, and let a four-bucket <hash table> use the further bucket index $b(k)=h(k)\bmod4$. For keys $2,6,18$, the hash values are $2,6,2$, while all three bucket indices are $2$. Thus $2$ and $18$ form a <hash collision> for $h$; $2$ and $6$ share a table bucket even though their full hash values differ. Always specify which <function> is being compared: a table collision concerns the bucket-index <function>, which may discard more information than the original <hash function>.
\Image[/hash-collision-key-identity.png]
{title=A shared hash value and a shared table bucket discard different distinctions}
{description=Constructed <integer> keys $2,6,18$ pass through $h(k)=k\bmod16$ and $b(k)=h(k)\bmod4$. Orange highlights the <hash collision> between $2$ and $18$; blue key $6$ joins them only after bucket reduction. <Separate chaining> retains all three keys. This is a toy calculation, not a measured workload or a <cryptographic hash function>.}
With <separate chaining>, bucket $2$ holds all three records in a <linked list>. A search for $18$ visits that bucket and compares the stored keys until it finds $18$; a search for $34$ visits the same bucket but rejects every stored key. A <hash collision> changes the search work, while key comparison preserves correctness. Storing only one record per hash value would incorrectly merge distinct keys. This is the purpose of collision handling in a <hash table>.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 8: Hashing I>{ref}
The <pigeonhole principle> explains inevitability: if a <hash function> has only $M$ possible <outputs>, any $M+1$ distinct <inputs> contain a <hash collision>. In particular, a <function> whose <domain of a function> is larger than its finite <codomain> cannot be an <injective function>. This is an existence statement; it gives neither an efficient way to find the pair nor a <probability> for a smaller collection of keys. A particular small collection might have no <hash collision> at all.
For a <cryptographic hash function>, <collision resistance> asks that finding any two distinct messages with equal full digests be computationally infeasible under the specified model and resources. It does not mean that <hash collisions> do not exist. <Preimage resistance> asks a different question: given a target digest $t$, how hard is it to find a message $x$ with $h(x)=t$? The collision finder may choose both messages and their common digest; the <preimage> finder is given the digest in advance. These definitions distinguish two search tasks, independently of how a <hash table> stores records.https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-107r1.pdf[Quynh Dang, NIST SP 800-107 Revision 1 (2012), section 3.1 and section 4.1, definitions of collision and preimage resistance]{ref}