Свойства хеш-функций

Тимофей: Не любая функция годится на роль хеш-функции. Сейчас я расскажу, какими свойствами должна обладать хорошая хеш-функция.
Как мы выяснили, эта функция принимает на вход данные и выдаёт число, которое соответствует индексу в массиве.
А зачем нужны хеш-функции?
Гоша: Чтобы быстро искать, добавлять и удалять данные.
Например, нужно выяснить стоимость товара в магазине. Кажется, если функция будет вычислять это значение дольше, чем мы могли бы найти информацию без её использования, смысла в её применении нет.
image
Поэтому хеш-функция обладает такими свойствами:
  1. Детерминизм. Для одного и того же ключа функция всегда должна возвращать одинаковое значение.
  2. Эффективность. Хеш-функция должна вычисляться достаточно быстро.
  3. Ограниченность. Результат вычисления функции должен принадлежать определённому диапазону, который соответствует размеру хеш-таблицы.
  4. Равномерность. Данные должны быть распределены по хеш-таблице равномерно. То есть каждое выходное значение равновероятно.
  5. Лавинность. При незначительном изменении входных данных выходное значение должно меняться значительно.
  6. Необратимость. Невозможно восстановить ключ по значению функции. При регистрации на сайте пользователь вводит свой пароль, к которому применяется хеш-функция. Полученное значение записывается в базу данных. Каждый раз, когда пользователь вводит пароль, к нему применяется та же функция, а результат сравнивается с записью в базе данных. Если злоумышленник получит доступ к данным в базе, он не должен иметь возможность восстановить пароль.
Следствия из перечисленных свойств:
  • Для близких значений функция не должна возвращать близкие результаты.
  • В значениях функции не должно образовываться кластеров, то есть множеств близко расположенных друг к другу точек.
Решите задачу N: https://contest.yandex.ru/contest/19095/problems/N