证明二次探测函数
Proof the quadratic probing function
如果有人能帮助解决这个问题，我将不胜感激。问题是：
考虑以下哈希函数：h(k, i) = (h'(k) + (1/2) (i + i^2 )) mod m，其中 m = 2^p 对于某个正整数p.证明或反驳对于任何 k，探测序列是 <0, 1, 2, ...,m – 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).
如果有人能帮助解决这个问题，我将不胜感激。问题是： 考虑以下哈希函数：h(k, i) = (h'(k) + (1/2) (i + i^2 )) mod m，其中 m = 2^p 对于某个正整数p.证明或反驳对于任何 k，探测序列是 <0, 1, 2, ...,m – 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).