The quadratic probing strategy has a clustering problem related to the way it looks for open…
The quadratic probing strategy has a clustering problem related to the way it looks for open slots. Namely, when a collision occurs at bucket h(k), it checks buckets A[(h(k) + j2) mod N], for j = 1,2,…, N − 1.
a. Show that j2 mod N will assume at most (N + 1)/2 distinct values, for N prime, as j ranges from 1 to N − 1. As a part of this justification, note that j2 mod N = (N − j)2 mod N for all j.
b .A better strategy is to choose a prime N such that N mod 4 = 3 and then to check the bucketsA[(h(k) ± j2) mod N] as j ranges from 1 to (N − 1)/2, alternating between plus and minus. Show that this alternate version is guaranteed to check every bucket in A.