证明二次探测函数

Question

如果有人能够帮助解决这个问题，我将非常感激。问题是： 考虑以下散列函数：对于某些正数，h（k，i）=（h'（k）+（1/2）（i + i^2））mod m，其中m = 2^p整数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)。