Past exam question: 2065 Shrawan (Regular / Back), Q8
Open in the Padhaiko appQuestion
What is collision? Explain any two methods of collision resolution with reference to hashing.
Solution
Hash Collision: A collision occurs when two distinct keys map to the same slot index () in a finite hash table.
Two Collision Resolution Methods:
- Separate Chaining: Each table index
HT[i]stores a linked list of all keys hashing toi. Insertion prepends in , and lookup scans only the short bucket chain (expected where ). - Linear Probing (Open Addressing): All keys live inside the table array. On collision at , slots are probed sequentially until an empty slot is found. Simple and cache-friendly, though susceptible to primary clustering.
Answer:
A collision happens when for . Separate chaining resolves it via per-bucket linked lists, whereas linear probing resolves it by scanning subsequent array slots .