PadhaikoAll subjects

Past exam question: 2072 Ashwin (Regular), Q11

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Searching Algorithms

Question

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 .

  1. Linear Probing: Probe sequence ().
    • Example: Insert 23, 33 into empty table: 23 slot 3; 33 collides at 3, probes (3+1)%10 = 4 slot 4.
  2. Quadratic Probing: Probe sequence (or ).
    • Example: Insert 23, 33, 43: 23 slot 3; 33 probes 3+1=4 slot 4; 43 probes 3+1=4 (occupied), then 3+4=7 slot 7. Avoids primary clustering.
  3. Double Hashing: Uses a second hash function for the probe step: (where ).
    • Example: With , , : insert 23, 33: 23 slot 3; 33 collides at 3, , probes (3 + 2) % 10 = 5 slot 5. Eliminates both primary and secondary clustering.
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).

All past exam questions for Data Structure and Algorithms