@TrumpDonald

Как при двойном хэшировании последовательность проб является перестановкой?

Добрый день, я не могу понять. Допустим есть двойное хэширование h(k,i)=(h1(k)+i*h2(k)) mod n. Есть утверждение что последовательность проб соответствующих ключу k, является перестановкой множества {0,1,...,n-1} тогда и только тогда, когда h2(k) взаимно просто с n. Приведите пожалуйста хотя бы 1 пример что бы утверждение было верно.
  • Вопрос задан
  • 42 просмотра
Решения вопроса 1
longclaps
@longclaps
Чего уж проще. Пусть n==2^t, так обычно и бывает. Тогда h2(k)==2*k+1 - нечетное число, завсегда взаимно простое с n.
Подставьте и проверьте.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Яндекс Москва
от 100 000 до 300 000 руб.
от 120 000 руб.
Globus Москва
от 150 000 до 200 000 руб.
18 авг. 2019, в 20:16
6000 руб./за проект
18 авг. 2019, в 19:05
2000 руб./за проект
18 авг. 2019, в 19:00
1500 руб./за проект