Computer Science
Explainer
Hash collisions: chaining vs open addressing
Two different keys, one slot. What does the hash table do?
Quick check · tap an answer to continue
Lesson notes
Key points
- A collision happens when two different keys hash to the same index, which is unavoidable when keys outnumber slots.
- Separate chaining stores every colliding key in a linked list attached to that slot.
- Open addressing instead keeps everything in the array, probing the next free slot, as in linear probing.
- Both slow down as the load factor, items divided by slots, grows, so tables resize when it gets too high.
Definitions
- Collision
- When h(k1) mod m equals h(k2) mod m for two different keys k1 and k2.
Takeaway: Chaining uses lists; open addressing probes for another slot.
Quick check: Linear probing handles a collision by...
- Trying the next free slot
- Adding a linked list
- Deleting the old key
Linear probing is open addressing: it steps to i+1, i+2 until a free slot.
CollisionChainingOpen addressingLoad factor
Lessons like this, for your syllabus.
Short narrated study videos written for your course, level and exam. Free to start.
Get lessons for your own syllabus