What is a Collision

A collision happens when two different keys produce the same bucket index in a hash map. Since the hash function maps a potentially infinite set of keys into a finite number of buckets, collisions are inevitable — not a bug, but a mathematical certainty.

How it works

Consider a hash map with 8 buckets. Two keys that produce hash codes 11 and 19 both map to bucket 3 (since 11 % 8 = 3 and 19 % 8 = 3). The hash map needs a strategy to store both pairs in the same bucket.

Chaining — each bucket holds a linked list (or small dynamic array). When a collision occurs, the new entry is appended to that list. To look up a key, hash it, jump to the bucket, then scan the chain comparing keys until a match is found.

bucket 3: → ["alice": 42] → ["dave": 17] → null

Open addressing — all entries live directly in the array. When a collision occurs, the hash map probes the next available slot using a probing sequence (linear, quadratic, or double hashing). Lookup follows the same probe sequence until it finds the key or an empty slot.

bucket 3: ["alice": 42]
bucket 4: ["dave": 17]   ← placed here because 3 was occupied

Each approach has tradeoffs. Chaining handles high load gracefully but uses more memory (pointers) and suffers from cache misses. Open addressing has better cache locality but degrades sharply as the array fills up — long probe chains form, turning O(1) into O(n).

Both approaches depend on the load factor (entries / buckets). When the load factor exceeds a threshold (typically 0.75), the hash map resizes — allocates a larger array and rehashes every key. Resizing is O(n) but happens rarely enough that the average cost per operation remains O(1).

Why it matters

Collisions are the reason hash maps are O(1) on average rather than O(1) guaranteed. Understanding collision resolution explains why hash maps occasionally resize, why a bad hash function destroys performance, and why the load factor threshold exists.

See How Hash Maps Work for the full collision resolution walkthrough.