@TrumpDonald

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

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

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

Войти через центр авторизации
Похожие вопросы