Коллизии

Когда разные ключи получают один хеш

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

record Key(int value) {
    @Override
    public int hashCode() {
        return 1;
    }
}

Map<Key, String> map = new HashMap<>();
map.put(new Key(10), "ten");
map.put(new Key(20), "twenty");

Оба ключа имеют одинаковый hashCode(), но они не равны друг другу. Корректная хеш-таблица обязана сохранить обе записи и при поиске различить их по самим ключам.

Два основных способа обработки

Один подход — цепочки (separate chaining): каждая корзина может содержать несколько записей. После перехода в нужную корзину таблица сравнивает ключ с находящимися там ключами. Если распределение хорошее, таких сравнений остаётся мало.

Другой подход — открытая адресация: все записи находятся прямо во внутреннем массиве, а при занятой позиции алгоритм по определённому правилу ищет другую свободную позицию. У этих подходов разные детали реализации, но цель одна — не потерять записи, которые претендуют на одно место.

Почему важна заполненность таблицы

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

При хорошем распределении и контролируемой загрузке операции остаются ожидаемо близкими к O(1). Если множество ключей постоянно попадает в одно место, объём работы растёт и в худшем случае может приблизиться к O(n).