二次探测函数的证明

Question

如果有人能帮我解决这个问题，我将非常感激。问题是:考虑下面的哈希函数:h(k, i) = (h ' (k) + (1/2) (i + i^2)) mod m，其中对于某个正整数p m = 2^p。证明或否证对于任意k，探测序列是<0,1,2，…

Answer 1

是的。

假设h(k, i) = h(k, j)。
然后h'(k) + 1/2 * i * (i + 1) = h'(k) + 1/2 * j * (j + 1) (mod m) & lt; =>
1/2 * i * (i + 1) = 1/2 * j * (j + 1) (mod m) =>
i * (i + 1) = j * (j + 1) (mod 2m) & lt; => i * i - j * j + i - j = 0 (mod 2m) & lt; =>
(i - j) * (i + j + 1) = 0 (mod 2m)。第二项是奇数和2m = 2^(p + 1)，因此
i = j (mod 2m) => i = j (mod m)。