Hash collision

In computer science, a hash collision or hash clash is when two distinct pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits.

Hash is typically used as a many-to-one function, with the number of potential inputs (size of input domain) much larger that the number of potential output values ("range"), making collisions inevitable ("pigeonhole principle"). For the cryptographic hash functions (CHFs), the output is a compact representative of particular input value used by data integrity algorithms to operate efficiently using this representative in place of the much larger input data. A collision violates the assumptions of integrity algorithms, so CHFs are designed to make finding a practical collision computationally infeasible (so-called collision resistance).

The typical uses of non-cryptographic hash functions (NCHFs) – like bloom filters, hash tables, count sketches – are less sensitive to collisions, so NCHFs require just the uniform distribution and avalanche properties. Still, collision resistance is an additional feature that is useful against hash flooding attacks; simple NCHFs, like the cyclic redundancy check (CRC), have essentially no collision resistance and thus cannot be used with an input open to manipulation by an attacker. Non-cryptographic applications employ multiple ways of handling the hash collisions when they occur.