Hash collisions: When two keys want the same place

In short: A collision occurs when two different keys are mapped to the same slot in a hash table; methods such as chaining resolve it.

In more detail: A hash table uses a hash function to compute a position in an array from a key. Because there are more possible keys than slots, two keys inevitably sometimes hit the same slot. This is unavoidable (pigeonhole principle) and must be handled so that both values can be found.

In Depth

Chaining (separate chaining)

Each slot (“bucket”) contains a small list. If two keys land in the same bucket, both are in the list, and the search compares the keys there. This is simple and robust; Java’s HashMap works this way (for long lists it converts them to trees).

Open addressing

All entries live directly in the array. If a slot is occupied, another is sought: linear probing tries the next slot, quadratic probing larger jumps, double hashing uses a second hash function for the step size. Deleted entries must be marked (“tombstone”) so that search chains do not break. It saves pointers but is slow when the array is almost full.

The load factor

The load factor is entries divided by slots. The fuller, the more collisions. It is usual to enlarge the table at about 0.75 (usually doubling) and redistribute all entries (rehashing). This keeps the average effort for insertion and search constant (O(1) on average).

Good hash functions and attacks

A good function distributes keys evenly and is fast. An attacker who knows the hash function and table can generate many keys that all collide and cripple the application with O(n) accesses (“hash flooding”). Countermeasures are randomly initialised hash functions (SipHash) or trees in long buckets.

See also: HashMap, Hashing, Big O notation, Bloom filter and trie