Past exam question: 2072 Ashwin (Regular), Q11
Open in the Padhaiko appQuestion
How a linear probing, quadratic probing and double hashing techniques are used to resolve collision? Explain with suitable example.
Solution
Three Open Addressing Collision Resolution Techniques: Assume a hash table of size with primary hash .
- Linear Probing: Probe sequence ().
- Example: Insert
23, 33into empty table:23slot3;33collides at3, probes(3+1)%10 = 4slot4.
- Example: Insert
- Quadratic Probing: Probe sequence (or ).
- Example: Insert
23, 33, 43:23slot3;33probes3+1=4slot4;43probes3+1=4(occupied), then3+4=7slot7. Avoids primary clustering.
- Example: Insert
- Double Hashing: Uses a second hash function for the probe step: (where ).
- Example: With , , : insert
23, 33:23slot3;33collides at3, , probes(3 + 2) % 10 = 5slot5. Eliminates both primary and secondary clustering.
- Example: With , , : insert
Answer:
All three are open-addressing schemes probing until an empty slot is found: linear probing steps by (simple, suffers primary clustering), quadratic probing steps by (eliminates primary clustering), and double hashing steps by (eliminates both primary and secondary clustering).