PadhaikoAll subjects

Past exam question: 2076 Baisakh (Back), Q10(b)

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

What 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.

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.

Answer:

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.

All past exam questions for Data Structure and Algorithms