Clever Geek Handbook

Quadratic probing: (f (k) + a * j + b * j ^ 2)% M How to choose a and b?

If M is simple, how do we choose a and b to minimize conflicts?

Also in the books it is written that in order to find an empty slot when quadratic probing in (f (k) + j ^ 2)% M, the hashtable must be at least half empty? Can anyone provide me with proof of this?

+2


source to share


1 answer


There are several meanings for choosing a and b on wikipedia :

For a simple M> 2, most variants a and b will make f (k, j) different for j in [0, (M - 1) / 2]. This choice includes a = b = 1/2, a = b = 1 and a = 0, b = 1. Since there are only about M / 2 different probes per element, it is difficult to guarantee that inserts will be successful when the load factor is> 1/2.



The proof of the guarantee of finding empty slots is here or.

+2


source






More articles:


All Articles