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.
Background Hash collisions can be unavoidable depending on the number of objects in a set and whether or not the bit string they are mapped to is long enough in length. When there is a set of n {\displaystyle n} objects, if n {\displaystyle n} is greater than | R | {\displaystyle |R|} , which in this case R {\displaystyle R} is the set of the hash values, a hash collision is guaranteed to occur. Another reason hash collisions are likely at some point in time stems from the idea of the birthday paradox in mathematics. This problem looks at the probability of a set of two randomly chosen people having the same birthday out of n {\displaystyle n} number of people. This idea has led to what has been called the birthday attack. The premise of this attack is that it is difficult to find a birthday that specifically matches your birthday or a specific birthday, but the probability of finding a set of any two people with matching birthdays increases the probability greatly. Bad actors can use this approach to make it simpler for them to find hash values that collide with any other hash value – rather than searching for a specific value. The impact of collisions depends on the application. When hash functions and fingerprints are used to identify similar data, such as homologous DNA sequences or similar audio files, the functions are designed so as to maximize the probability of collision between distinct but similar data, using techniques like locality-sensitive hashing. Checksums, on the other hand, are designed to minimize the probability of collisions between similar inputs, without regard for collisions between very different inputs. Instances where bad actors attempt to create or find hash collisions are known as collision attacks. In practice, security-related applications use cryptographic hash algorithms, which are designed to be long enough for random matches to be unlikely, fast enough that they can be used anywhere, and safe enough that it would be extremely hard to find collisions.
Collision resolution
In hash tables, since hash collisions are inevitable, hash tables have mechanisms of dealing with them, known as collision resolutions. Two of the most common strategies are open addressing and separate chaining. The cache-conscious collision resolution is another strategy that has been discussed in the past for string hash tables.
Open addressing
Cells in the hash table are assigned one of three states in this method – occupied, empty, or deleted. If a hash collision occurs, the table will be probed to move the record to an alternate cell that is stated as empty. There are different types of probing that take place when a hash collision happens and this method is implemented. Some types of probing are linear probing, double hashing, and quadratic probing. Open Addressing is also known as closed hashing.
Separate chaining
This strategy allows more than one record to be "chained" to the cells of a hash table. If two records are being directed to the same cell, both would go into that cell as a linked list. This efficiently prevents a hash collision from occurring since records with the same hash values can go into the same cell, but it has its disadvantages. Keeping track of so many lists is difficult and can cause whatever tool that is being used to become very slow. Separate chaining is also known as open hashing.
Cache-conscious collision resolution Although much less used than the previous two, Askitis & Zobel (2005) has proposed the cache-conscious collision resolution method in 2005. It is a similar idea to the separate chaining methods, although it does not technically involve the chained lists. In this case, instead of chained lists, the hash values are represented in a contiguous list of items. This is better suited for string hash tables and the use for numeric values is still unknown.
See also List of hash functions Universal one-way hash function Cryptography – Practice and study of secure communication techniques Universal hashing – Technique for selecting hash functions Perfect hash function – Hash function without any collisions Injective map – Function that preserves distinctnessPages displaying short descriptions of redirect targets
References
… excerpt ends here. Continue reading the full article.
