Hash collision - Definition and Overview

Hash collision is a term in computer programming for a situation that occurs when two distinct inputs into a hash function produce identical outputs.

In Searching

An efficient method of searching can be to calculate a hash value and then use it as an index into an array of data. Such a procedure can do a look up in the constant time required to compute the hash value and retrieve the data, unless a hash collision occurs. In the case of a hash collision some other method is necessary, since it indicates two inputs (search keys) map to the same location requiring disambiguation. Chaining is a method where all the data with the same hash value is searched by a different method. Alternately, when a hash collision occurs further entries in the hashed table being searched can be checked, either with the same hash value or with a secondary function, until either the correct entry is located or an unused location is reached.

In Cryptography

One desirable property of cryptographic hash functions is that it is computationally infeasible to find a collision. The value of a hash function can be used to certify an input is unchanged by publishing the value of the hash if it is impossible to find another reasonable input with the same hash value.

See also

• MD5CRK
• Birthday attack