Open Addressing vs Separate Chaining in Hash Tables
💡 Concept Name
Collision Resolution — Strategies to handle hash collisions in hash tables, mainly through open addressing and separate chaining.
📘 Quick Intro
When two keys map to the same index in a hash table—a collision—resolving it efficiently is vital. Open addressing searches for the next free slot, while separate chaining maintains a list of entries per index.
🧠 Analogy / Short Story
Picture a parking lot:
- Open Addressing: If your assigned spot is taken, you drive forward to find the next empty space.
- Separate Chaining: If your spot is full, you park behind the existing car, forming a line (like a linked list).
🔧 Technical Explanation
- 🔁 Open Addressing: All entries reside within the hash table array itself; collisions cause probing for alternate slots.
- 🪢 Separate Chaining: Each bucket in the array holds a linked list or another collection of items hashing to that slot.
- ⚡ Performance: Open addressing shines with low load factors; separate chaining excels when the table is densely filled.
- 🧠 Memory Use: Open addressing uses less memory but may suffer clustering; chaining uses extra memory for pointers.
- 🔄 Load Factor Sensitivity: Open addressing performance deteriorates faster as load factor grows compared to chaining.
🎯 Purpose & Use Case
- ✅ Choose open addressing to save memory and maintain speed when collisions are rare.
- ✅ Choose separate chaining when expecting lots of collisions or variable data sizes.
💻 Real Code Example
// Separate chaining example using Dictionary>
var hashTable = new Dictionary<int, List<string>>();
int hash = "John".GetHashCode() % 10;
if (!hashTable.ContainsKey(hash))
hashTable[hash] = new List<string>();
hashTable[hash].Add("John");
❓ Interview Q&A
Q1: What is a hash collision?
A: When two different keys produce the same hash value in a hash table.
Q2: Why do hash collisions occur?
A: Because the hash function maps a large key space into a smaller fixed-size array.
Q3: What are common techniques to resolve collisions?
A: Separate chaining and open addressing.
Q4: How does separate chaining work?
A: By storing collided elements in a linked list or bucket at the same array index.
Q5: What is open addressing?
A: Finding another empty slot within the hash table array via probing methods.
Q6: Name some probing techniques in open addressing.
A: Linear probing, quadratic probing, and double hashing.
Q7: What is the drawback of linear probing?
A: It can cause clustering, leading to performance degradation.
Q8: How does double hashing improve collision resolution?
A: By using a second hash function to calculate probe steps, reducing clustering.
Q9: What happens when the load factor of a hash table is high?
A: The chances of collisions increase, decreasing performance.
Q10: How can resizing help with collisions?
A: Increasing the table size reduces collisions and improves efficiency.
📝 MCQs
Q1. What is a hash collision?
- Two keys map to different hashes
- Two keys map to same hash
- Keys are equal
- Hash table overflow
Q2. Why do collisions happen?
- Keys are equal
- Hash function compresses keys
- Keys are hashed randomly
- Hash table is empty
Q3. Which are common collision resolution methods?
- Linear search
- Separate chaining and open addressing
- Sorting
- Rehashing only
Q4. How does separate chaining resolve collisions?
- Overwrite data
- Linked list at array index
- Skip insertion
- Resize table
Q5. What is open addressing?
- Use linked lists
- Find empty slot via probing
- Double hashing only
- Ignore collisions
Q6. Which probing method causes clustering?
- Quadratic probing
- Double hashing
- Linear probing
- Random probing
Q7. How does double hashing reduce clustering?
- Uses third hash
- Uses second hash for step size
- Uses fixed step
- No clustering effect
Q8. What happens when load factor is high?
- Less collisions
- More collisions
- No change
- Table shrinks
Q9. How does resizing help collision resolution?
- Increases collisions
- Lowers load factor
- Slows down
- No effect
Q10. Which data structure is used in separate chaining?
- Array
- Linked list
- Stack
- Queue
💡 Bonus Insight
Advanced hybrid techniques like Robin Hood hashing and cuckoo hashing merge the benefits of both approaches, pushing collision resolution to new efficiency levels.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!