PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q9

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

What is collision? What are the techniques used for collision resolution in hashing? Insert the keys: 62, 37, 36, 44, 67, 91, 82, and 31 using quadratic probing method. The hash function is: h(key) = key % 10 (where 10 is the table size).

Solution

Collision and Collision Resolution Techniques: A collision occurs when a hash function maps two or more distinct keys to the same hash table slot ( for ).

Main collision resolution techniques:

  1. Separate Chaining (Open Hashing): Each table slot stores a linked list of all keys hashing to that index.
  2. Open Addressing (Closed Hashing): All keys reside inside the table array; collisions probe subsequent slots via:
    • Linear Probing:
    • Quadratic Probing: (or )
    • Double Hashing:

Quadratic Probing Trace (, ):

Final Hash Table:

Index0123456789
Key—9162824431363767—
Answer:

A collision happens when distinct keys hash to the same index; it is resolved via separate chaining or open addressing (linear probing, quadratic probing, double hashing). Inserting 62, 37, 36, 44, 67, 91, 82, 31 via quadratic probing yields:

All past exam questions for Data Structure and Algorithms