PadhaikoAll subjects

Past exam question: 2078 Poush (Back), Q7

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

Briefly explain different types of collision resolution techniques. Consider a hash table of size 10. Using quadratic probing, insert the keys 52, 77, 26, 44, 33, 91 and 81 into the table. (Take C1 = 1 and C2 = 3)

Solution

Types of Collision Resolution Techniques:

  1. Separate Chaining (Open Hashing): Each bucket HT[i] holds a linked list of all colliding keys mapping to i. Never runs out of space inside the table, though extra pointer memory is needed.
  2. Open Addressing (Closed Hashing): All elements reside directly in the array; upon collision at , probe sequence searches for the next empty slot:
    • Linear Probing: (suffers primary clustering).
    • Quadratic Probing: (eliminates primary clustering).
    • Double Hashing: (avoids both primary and secondary clustering).

Quadratic Probing Trace (, , ):

Final Hash Table:

Index0123456789
Key—91523344812677——
Answer:

Collision resolution uses separate chaining or open addressing (linear probing, quadratic probing, double hashing). With , the keys occupy slots: [—, 91, 52, 33, 44, 81, 26, 77, —, —].

All past exam questions for Data Structure and Algorithms