What is a hash collision and why do collisions happen?

beginner

← All Arrays, Strings & Hash Tables questions

Re-explain

A hash collision happens when two different keys land in the same bucket. It happens because a hash function squeezes a huge space of possible keys into a small, finite number of buckets.

There are far more possible keys than slots, so by the pigeonhole principle some keys must share a slot. Even a great hash function cannot avoid this. It can only make collisions rare and evenly spread. Poor functions make it worse by clustering keys together.

Collisions are normal, not a bug, so every hash table has a plan for them. Common approaches store the clashing entries in a small list per bucket, or probe for the next open slot. Handling them well is what keeps lookups near O(1) instead of degrading.

Rewriting in plainer words…

This answer doesn't lend itself to a diagram - it reads best . No credits were charged.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·

What should the new diagram focus on?

Guided practice for Arrays, Strings & Hash Tables One question at a time. Answer out loud, get graded, see what you missed.

How well did you know this?

AI:

Saved in this browser - sign in to keep your review list.

How should your speech become text?

Listening… your words appear above as you speak - tap Stop when you're done.

Recording · cr - tap Stop & transcribe when you're done.

Transcribing with AI…

Voice:

Keep going - a few more words and AI can grade it.

Interview lens How interviewers actually use this question

Likely follow-ups

What is the difference between separate chaining and open addressing? Say where clashing entries live in each scheme, then compare deletes, memory use and how each behaves as the table fills up.
Two different keys sit in the same bucket. How does the map know which entry belongs to which key? Point to comparing the stored hash and then checking key equality, and say why a matching hash alone does not prove two keys are equal.
When do collisions push hash table lookups from O(1) toward O(n)? Cover a weak hash or a high load factor piling keys into a few buckets, and what resizing or a better hash does about it.
Could an attacker choose keys that all collide? How would you defend against that? Name the attack and one defense, such as a hash seeded with a secret random value or a balanced tree inside crowded buckets.
With a 64-bit hash, how many keys can you store before two share the same full hash value? Use the birthday bound. Collisions become likely near the square root of the hash space, far sooner than its size suggests.

What you can say

A hash collision is when two different keys end up in the same bucket of a hash table.
It happens because the hash function maps a huge space of possible keys onto a small, fixed number of buckets.
There are far more possible keys than slots, so by the pigeonhole principle some keys have to share one.
Even a great hash function can't avoid that, but it keeps collisions rare and evenly spread, while a poor one clusters keys together.
So collisions are normal, and every hash table plans for them, either with a small list per bucket or by probing for the next open slot.
How well the table handles them decides whether lookups stay near O(1) or degrade as buckets fill up.

Weak answers to avoid

Treats collisions as a bug to eliminate With more possible keys than slots, no hash function for arbitrary keys can avoid them. Say they are normal and that every table has a plan for them.
Says what a collision is, never why The question asks why. Name the squeeze from a huge key space into a few buckets and the pigeonhole principle, not just two keys sharing a slot.
Confuses a collision with a duplicate key Inserting the same key twice updates one entry. A collision is two different keys sharing a bucket, and the table must keep both.
Stops at the definition, no handling or cost Mention per-bucket lists or probing for the next open slot, and that handling collisions well is what keeps lookups near O(1).

Interview lens

Likely follow-ups, what you can say, and the weak answers to avoid.

Want a quick review of the fundamentals? See the Arrays, Strings & Hash Tables cheatsheet.

← Back to all Arrays, Strings & Hash Tables questions

Pro · $10/mo

74 of 85 Arrays, Strings & Hash Tables answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

Full answers + code
AI explanations, simpler or deeper
1,000 AI credits / month
Cancel anytime

Get Pro → See plans & pricing →