algorithm - 证明二次探测函数

Question

如果有人可以帮助解决这个问题，我将不胜感激。问题是：考虑以下哈希函数：h(k, i) = (h'(k) + (1/2) (i + i^2 )) mod m，其中 m = 2^p 表示某个正整数页。证明或反驳对于任何 k，探针序列是 <0, 1, 2, ...,m – 1> 的排列

Answer 1

是的。

让我们假设h(k, i) = h(k, j).
然后h'(k) + 1/2 * i * (i + 1) = h'(k) + 1/2 * j * (j + 1) (mod m)<=>
1/2 * i * (i + 1) = 1/2 * j * (j + 1) (mod m)=>
i * (i + 1) = j * (j + 1) (mod 2m)<=> i * i - j * j + i - j = 0 (mod 2m)<=>
(i - j) * (i + j + 1) = 0 (mod 2m)。第二项是奇数2m = 2^(p + 1)，因此
i = j (mod 2m)=> i = j (mod m)。