Хеш-функции

Что делает хеш-функция

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

Для корректной работы важна детерминированность: пока ключ не изменился, один и тот же ключ должен давать один и тот же хеш. Иначе после добавления записи таблица не сможет понять, в какой области искать её при следующем обращении.

Равные ключи и одинаковый hashCode

В Java хеширующие коллекции используют методы equals() и hashCode(). Если два объекта равны по equals(), их hashCode() должен быть одинаковым. Обратное неверно: одинаковый хеш ещё не означает, что объекты равны.

String first = new String("java");
String second = new String("java");

System.out.println(first.equals(second));
System.out.println(first.hashCode() == second.hashCode());

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

Хорошее распределение важнее уникальности

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

После получения хеша таблице всё равно нужно преобразовать его в допустимый индекс. Для простого примера можно использовать Math.floorMod(hash, capacity): этот метод корректно работает и с отрицательными хешами.