Hash collision
|
|
In computer science, a hash collision is a situation that occurs when two distinct inputs into a hash function produce identical outputs.
Most hash functions have potential collisions, but with good hash functions they occur less often than with bad ones. In certain specialized applications where a relatively small number of possible inputs are all known ahead of time it is possible to construct a perfect hash function which maps all inputs to different outputs.
In searching
Main article: hash table.
An efficient method of searching can be to process a lookup key using a hash function, then take the resulting hash value and then use it as an index into an array of data. The resulting data structure is called a hash table. As long as different keys map to different indexes, lookup can be performed in constant time. When multiple lookup keys are mapped to identical indexes, however, a hash collision occurs. The most popular ways of dealing with this are chaining (building a linked list of values for each array index), and open addressing (searching other array indexes nearby for an empty space).
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 signed value of the hash if it is not feasible to produce a collision. Feasible in this context refers to any method which is faster than a brute-force birthday attack.