Идеальные хэш-функции

Question

Мне недавно дали домашнее задание, в котором спрашивали, можно ли при наличии списка ключей создать хеш-функцию, в которой нет коллизий. Проведя некоторые исследования, я обнаружил, что с учетом предварительно упорядоченного списка ключей возможны идеальные хэш-функции.

Однако я не совсем уверен, что сказать дальше. Может ли кто-нибудь дать мне несколько советов о том, как создаются идеальные хеш-функции, или что именно дает предопределенный список создателю хеш-функции, который обеспечивает идеальную функцию?

Спасибо за любую помощь.

Answer 1

Единственный способ избежать коллизий - это иметь отношение 1: 1 между ключом и значением хеш-функции.Диапазон значений хеш-функции должен быть по крайней мере таким же, как количество ключей, и функция отображения должна преобразовывать каждую клавишу в уникальное значение.Более подробная информация здесь: http://en.wikipedia.org/wiki/Perfect_hash