math - 二次探测 : (f(k) + a*j + b*j^2) % M, 如何选择a和b？

Question

如果 M 是质数，如何选择 a 和 b 以最小化碰撞？

书上也写到，要在 (f(k)+j^2) % M 中进行二次探测时找到空槽，哈希表必须至少有一半是空的？有人可以向我提供证明吗？

Answer 1

在 wikipedia 上选择 a 和 b 有一些值:

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.

保证找到空槽的证明是here或 here .