證明二次探測函數

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)。