Past exam question: 2078 Chaitra (Regular), Q9
Open in the Padhaiko appQuestion
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:
- Separate Chaining (Open Hashing): Each table slot stores a linked list of all keys hashing to that index.
- 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 (, ):
- 62: (empty) slot 2.
- 37: (empty) slot 7.
- 36: (empty) slot 6.
- 44: (empty) slot 4.
- 67: (collision). (empty) slot 8.
- 91: (empty) slot 1.
- 82: (collision). (empty) slot 3.
- 31: (collision). (occupied); (empty) slot 5.
Final Hash Table:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Key | — | 91 | 62 | 82 | 44 | 31 | 36 | 37 | 67 | — |
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:
- Slots
0..9:[—, 91, 62, 82, 44, 31, 36, 37, 67, —].