Collision Resolution Overview
What you'll learn: When two keys hash to the same slot in a hash table, you need a strategy to handle the conflict—this lesson introduces the two main approaches.
Why Collision Resolution Matters
You've learned that collisions happen when different keys produce the same hash value. But a hash table can't just ignore collisions—it needs a systematic way to still store and retrieve all the data correctly. Think of it like two people showing up with tickets for the same seat at a theater: you need a policy to resolve the situation fairly and efficiently.
The Two Main Strategies
There are two fundamental approaches to handling collisions:
1. Chaining (Separate Chaining)
In chaining, each slot in the hash table holds a collection (often a linked list) of all elements that hash to that location. When a collision occurs, you simply add the new element to that slot's collection.
Analogy: Imagine each mailbox can hold multiple letters stacked together. If two letters arrive for the same box number, you just stack them inside.
2. Open Addressing
In open addressing, every slot holds at most one element. When a collision occurs, you systematically search ("probe") for the next available empty slot according to some rule, and place the element there.
Analogy: If a parking spot is taken, you follow a specific pattern to find the next empty spot—maybe the next space over, or perhaps jumping by some fixed interval.
Choosing Between Them
Both strategies have tradeoffs. Chaining keeps colliding items together but requires extra memory for the data structures (like linked list nodes). Open addressing uses only the array itself but requires careful management of probe sequences and deletions.
Key Takeaway: The two main collision resolution strategies are chaining (storing multiple items per slot using a secondary structure) and open addressing (probing for alternative slots within the array itself).