Hash Collision

In Turkish: Hash Çakışması
Pronunciation: HASH kuh-LIZH-un

Updated October 3, 20262 min read

In short

A hash collision is two different inputs sharing a hash value or bucket, which hash tables must handle and cryptographic hashes must make infeasible to find.

What is a hash collision?

A hash table maps a huge range of possible keys onto a limited number of buckets, so some keys must share a bucket, by the pigeonhole principle. Collisions come sooner than intuition suggests: the birthday paradox shows that with just 23 people, the chance that two share a birthday is over 50%. Good hash functions spread keys evenly, but collisions remain normal.

There are two main ways to handle them. Separate chaining stores a small list in each bucket, so colliding keys sit side by side. Open addressing stores everything in the array itself and, on a collision, probes for another free slot, for example the next one in line, which is linear probing. Either way, tables track their load factor, how full they are, and grow and rehash when it gets too high, keeping lookups O(1) on average.

Collisions also matter for security. If attackers can predict a hash function, they can send many keys that collide on purpose, turning O(1) lookups into O(n) and slowing a server to a crawl, an attack known as hash flooding. That is why languages such as Python and Rust randomize their string hashing. For cryptographic hashes, finding any collision is a break: MD5 and SHA-1 are considered broken because practical collisions were found.

A common misconception is that a good hash function has no collisions. Any function that maps unlimited inputs to a fixed-size output must have them. What matters is that they are rare, evenly spread and, for cryptographic uses, infeasible to find on purpose.

Key takeaways

A collision is when different inputs share a hash value or bucket.
Collisions are unavoidable and come early, as the birthday paradox shows.
Hash tables handle them with chaining or open addressing and resize by load factor.
Predictable hashes allow hash flooding attacks; languages randomize them.
Practical collisions break cryptographic hashes such as MD5 and SHA-1.

Example

Separate chaining in a tiny hash table (Python)python

class ChainedHashTable:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])     # colliding keys share the bucket's list

    def get(self, key):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return None

table = ChainedHashTable(size=2)        # tiny on purpose, so collisions happen
for word in ["apple", "banana", "cherry"]:
    table.put(word, len(word))
print(table.buckets)

Readers ask

How do hash tables handle collisions?

With separate chaining, where each bucket holds a list of entries, or open addressing, where a colliding entry is placed in another free slot found by probing. Resizing the table when it gets full keeps collisions rare.

Why is a hash collision a problem for MD5 and SHA-1?

Cryptographic hashes are used for signatures and integrity checks. If an attacker can create two different files with the same hash, a signature on one is also valid for the other, so these algorithms can no longer be trusted for security.

What is the birthday paradox?

The surprising fact that in a group of 23 people there is more than a 50% chance two share a birthday. It shows that collisions appear long before a hash space is close to full.