Как подбирается хэш-функция для снижения количества коллизий

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

Понимаете ли вы, как хэш превращается в номер корзины в HashMap, и умеете ли написать hashCode(), который не сваливает все ключи в одну корзину. Следом почти всегда спрашивают про контракт equals и hashCode и про то, что происходит в корзине при коллизиях.

Как отвечать

Начните с устройства HashMap:

• индекс корзины: (n-1) & hash, где n это ёмкость, всегда степень двойки. В индекс попадают только младшие биты;
• перемешивание: поэтому HashMap сначала делает h ^ (h >>> 16), чтобы старшие биты тоже влияли на индекс;
• коллизии: элементы одной корзины лежат списком, а с Java 8, когда их становится больше восьми при ёмкости от 64, список превращается в красно-чёрное дерево. Худший поиск падает с O(n) до O(log n), особенно если ключи реализуют Comparable.

Отсюда требования к своему hashCode():

• те же поля, что в equals: равные объекты обязаны давать равный хэш, иначе ключ «пропадёт» из мапы;
• некоммутативное смешивание: классическая схема 31 * result + field.hashCode(). Простая сумма полей даёт одинаковый хэш для (1, 2) и (2, 1);
• неизменяемые поля: если поле ключа поменялось после вставки, объект окажется не в той корзине;
• готовые средства: Objects.hash(...), у record метод генерируется автоматически.

Вне коллекций, для шардирования или фильтров Блума, берут некриптографические MurmurHash3 или xxHash, в Guava это Hashing.murmur3_128(). Криптографические хэши вроде SHA-256 нужны там, где важна стойкость к подбору, а не скорость.

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

Советуют SHA-256 «для хорошего распределения» в хэш-таблице. Он заметно медленнее, а таблице важны скорость и равномерность младших битов, а не криптостойкость.

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

Возвращают из hashCode() константу или хэш одного поля с малым числом значений. Мапа тогда деградирует до одной переполненной корзины.