If M is prime, how to choose a and b to minimize collisions?
Also in books it is written that to find the empty slot while quadratic probing in (f(k)+j^2) % M, the hash table has to be at least half empty? Can someone provide me a proof of that?
+2
A:
There are some values for choosing a and b on wikipedia:
For prime M > 2, most choices of a and b will make f(k,j) distinct for j in [0,(M − 1) / 2]. Such choices include a = b = 1/2, a = b = 1, and a = 0,b = 1. Because there are only about M/2 distinct probes for a given element, it is difficult to guarantee that insertions will succeed when the load factor is > 1/2.
A proof for the guarantee of finding the empty slots is here or here.
tanascius
2009-09-16 12:52:55
avd
2009-09-16 13:14:00
I am not sure if I understand you correctly. They give the example of 2^m (in wikipedia m is n). But the next paragraph they are talking of a prime M > 2 (in wikipedia they write M as m). That is the paragraph I quoted.
tanascius
2009-09-16 13:27:22
I m saying that hash table size must be prime but if we 2^m then it wont be prime
avd
2009-09-16 14:01:13
Yes, it should be prime. In wikipedia they have two cases. And the second one is about prime sizes. That should be alright.
tanascius
2009-09-16 14:44:46