Collision Handling

By the end, you can

• Explain why collisions are inevitable using the pigeonhole principle.
• Describe how separate chaining resolves a collision and why it tolerates α > 1.
• Trace a linear probing sequence, including wrap-around, and identify the landing slot.
• Explain primary clustering and state why linear probing suffers from it.
• Trace a quadratic probing sequence and state the conditions that guarantee a slot is found.
• Distinguish primary from secondary clustering and explain which probing strategies avoid each.
• Trace a double-hashing probe sequence and explain why h₂ must never be zero.
• Explain why blanking a deleted slot breaks open-addressing search and how tombstones fix it.
• Calculate the load factor and interpret what it implies for expected probe cost.
• Compare the four strategies by their trade-offs in memory, cache locality, and clustering behavior.