Past exam question: 2076 Baisakh (Back), Q10(b)
Open in the Padhaiko appWhat is the cause of collision in hashing and explain any one method for the collision resolution.
Solution
Cause of Collision in Hashing: A collision occurs when two distinct keys map to the same slot (). This is unavoidable by the Pigeonhole Principle because the key universe is vastly larger than the hash table size , so many keys must share the same modulo remainder or hash bucket.
Collision Resolution Method — Separate Chaining (Open Hashing): In separate chaining, each slot HT[i] () holds the head pointer of a linked list containing all keys that hash to index i.
- Insert(
k): Computei = h(k)and prepend/appendkto the linked list atHT[i]in time. - Search(
k): Computei = h(k)and linearly scan only the short list atHT[i]. - Delete(
k): LocatekinHT[i]and unlink its node.
Example: With and keys 12, 17, 22: all map to HT[2], forming chain HT[2] -> 12 -> 17 -> 22 -> NULL. No primary clustering or table-full limit occurs.
Collisions arise because the key universe far exceeds table size (Pigeonhole Principle). Separate chaining resolves collisions by storing a linked list at each bucket HT[h(k)] so multiple keys hashing to the same slot coexist without probing or clustering.