I would really appreciate if someone could help solve this problem. The question is: Consider the following hash function: h(k, i) = (h’(k) + (1/2) (i + i^2 )) mod m, where m = 2^p for some positive integer p. Prove or disprove that for any k, the probe sequence is a permutation of <0, 1, 2, ...,m – 1>
Yes, it is.
Let's assume that h(k, i) = h(k, j)
.
Then 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)
. The second term is odd and 2m = 2^(p + 1)
, thus i = j (mod 2m)
=> i = j (mod m)
.