Доказательство квадратичной функции зондирования

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