PadhaikoAll subjects

Past exam question: 2065 Shrawan (Regular / Back), Q8

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

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:

  1. Separate Chaining: Each table index HT[i] stores a linked list of all keys hashing to i. Insertion prepends in , and lookup scans only the short bucket chain (expected where ).
  2. 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 .

All past exam questions for Data Structure and Algorithms