algorithm - 二次プロービング関数の証明

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)。第 2 項は奇数であり2m = 2^(p + 1)、したがって
i = j (mod 2m)=>i = j (mod m)です。