Смущает вычисление последовательности проб в двойном хешировании

Question

Я знаю, что в Double Hashing,

h1(key) = key mod 11
h2(key) = 7 - (key mod 7)

h1 представляет начало в местоположении h1(ключ), h2 представляет размер шага.

Но я не знаю, как решить для последовательности проб.

Например, если ключ 14,

Можете ли вы объяснить мне, почему ответ 3,10,6,2,9,5,1,8,4,0,

Answer 1

В вашем примере размер таблицы равен 11 (позиции пронумерованы от 0 до 10). Размер шага - это число, которое нужно добавить к текущей позиции, чтобы получить следующую позицию (модуль размера таблицы).

h1 = 14 mod 11 = 3
h2 = 7 - (14 mod 7) = 7 - 0 = 7

Итак, первая позиция, назовите это p, 3, как указано h1, Каждая последующая позиция, p' дан кем-то --

p' = (p + h2) mod table_size

для этого примера

p' = (p + 7) mod 11

Итак, вторая позиция -

(3 + 7) mod 11 = 10 mod 11 = 10

и третий -

(10 + 7) mod 11 = 17 mod 11 = 6

и так далее.