Задать вопрос
@TrumpDonald

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

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

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

Похожие вопросы