Что такое идеальная хэш-функция и зачем она нужна
Что проверяют
Знаете ли вы, что «идеальная хэш-функция» это точный термин, а не синоним хорошей. Проверяют заодно, представляете ли вы, где она применима, и понимаете ли устройство обычной хэш-таблицы, в том числе в рантайме Go.
Как отвечать
Идеальная хэш-функция это функция, которая на заранее известном фиксированном множестве ключей не даёт ни одной коллизии, то есть инъективна на этом множестве. Минимальная идеальная раскладывает n ключей ровно по n ячейкам, без пустот.
Ключевое условие одно: множество ключей известно целиком заранее и не пополняется. Для произвольного потока ключей такой функции не существует, входов больше, чем значений хэша, и коллизии неизбежны.
Зачем нужна: исчезают цепочки и пробирование, поиск это одно вычисление и одно обращение в память, а худший случай совпадает со средним. Применяют для ключевых слов языка в лексере, статических справочников, зашитых в бинарник, таблиц кодов и словарей только для чтения. Строят генераторами на этапе сборки, известны схема с двухуровневым хэшированием, дающая линейную память и константу в худшем случае, и современные алгоритмы вроде CHD.
В Go стоит добавить контекст: встроенная map берёт случайное зерно хэша на каждую таблицу, что защищает от подбора коллизий и делает порядок обхода намеренно перемешанным, так что подставить свою функцию туда нельзя. Для маленького фиксированного набора строк дешевле switch или сгенерированная таблица.
Где спотыкаются
Пересказывают свойства хорошей хэш-функции: равномерность, скорость, лавинный эффект. Это другое: идеальность определена относительно конкретного множества ключей, а не сама по себе.
Тянут в ответ криптографию. Стойкость к поиску прообраза и к коллизиям относится к криптографическим хэшам, к идеальному хэшированию отношения не имеет, и для таблиц такие функции неоправданно дороги.
Забывают про цену и границы. Построение требует всего набора ключей и заметного времени, а добавление ключа означает перестроение таблицы. И считают, что ключи можно не хранить: если на вход придёт ключ вне множества, функция вернёт валидный индекс чужой ячейки, поэтому сравнение ключа всё равно нужно.