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
avd
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
tanascius
source
to share