Past exam question: 2078 Poush (Back), Q7
Open in the Padhaiko appQuestion
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:
- Separate Chaining (Open Hashing): Each bucket
HT[i]holds a linked list of all colliding keys mapping toi. Never runs out of space inside the table, though extra pointer memory is needed. - 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 (, , ):
- 52: (empty) slot 2.
- 77: (empty) slot 7.
- 26: (empty) slot 6.
- 44: (empty) slot 4.
- 33: (empty) slot 3.
- 91: (empty) slot 1.
- 81: (collision with
91):- : (empty) slot 5.
Final Hash Table:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Key | — | 91 | 52 | 33 | 44 | 81 | 26 | 77 | — | — |
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, —, —].