Может ли существовать идеальная хэш-функция без коллизий?

Что проверяют

Отличаете ли вы теорию от практики: на всём множестве возможных ключей коллизии неизбежны, а на заранее известном наборе их можно исключить полностью. Следом обычно спрашивают, как HashMap живёт с коллизиями и что меняется, если все ключи известны заранее.

Как отвечать

Ответ зависит от того, известны ли ключи.

Для произвольных входов нет. Это принцип Дирихле: hashCode() возвращает int, это 2³² значений, а строк бесконечно много. Пример: "Aa".hashCode() и "BB".hashCode() оба равны 2112. Даже у Integer.hashCode(), который возвращает само число, в таблице будут совпадения: индекс корзины считается как (n - 1) & hash, то есть от хэша остаются младшие биты.

Для фиксированного набора ключей да. Это и называется идеальным хэшированием:

• perfect hash function: для известного множества из n ключей строится функция без единой коллизии;
• minimal perfect hash: вдобавок отображает n ключей ровно в диапазон от 0 до n - 1, без пустых ячеек. Современные алгоритмы (CHD, BBHash, RecSplit) тратят на это несколько бит на ключ;
• где применяется: ключевые слова в компиляторах (утилита gperf), статические словари, индексы в read-only хранилищах. Цена: функция строится заранее, и новый ключ требует перестройки.

В Java близкий пример это EnumMap: индексом служит ordinal(), идеальный хэш по определению. А switch по строкам компилятор разворачивает в switch по hashCode() с последующим equals() именно потому, что коллизии возможны.

HashMap с ними справляется так: перемешивает старшие биты через h ^ (h >>> 16), хранит совпавшие ключи цепочкой, а при восьми элементах в корзине и ёмкости таблицы от 64 превращает цепочку в красно-чёрное дерево.

Где спотыкаются

Отвечают «нет, невозможно» и забывают про известный набор ключей, ради которого вопрос и задают.

Приводят SHA-256 или MD5 как «функции без коллизий». Криптографическая стойкость означает, что коллизию трудно найти, а не что её нет, и для хэш-таблиц такие функции слишком медленные.

Путают коллизию хэш-кодов и коллизию в корзине: разные hashCode() легко попадают в одну корзину после взятия младших битов.