Что происходит при коллизиях в HashMap?

Question

Коллизия в HashMap возникает, когда разные ключи попадают в один и тот же бакет.В этом случае элементы хранятся вместе внутри одного бакета.Поиск нужного значения выполняется с помощью сравнения ключей через equals().При небольшом количестве коллизий производительность остаётся высокой.Большое число коллизий ухудшает скорость операций.

YeaHub · Accepted Answer

Коллизии — это нормальная часть работы хеш-таблиц, и HashMap умеет с ними корректно справляться.Что такое коллизияКоллизия — это ситуация, при которой:hashCode() у разных ключей совпадаетвычисляется одинаковый индекс бакетаВажно:совпадение hashCode() не означает, что ключи равныокончательное сравнение выполняется через equals()Как HashMap хранит элементы при коллизииАлгоритм следующий:вычисляется бакет по hashCode()в бакете хранится несколько элементовпри поиске перебираются элементы бакетаиспользуется equals() для сравнения ключейУпрощённо:if (node.hash == hash && key.equals(node.key)) {
    return node.value;
}
Последствия коллизийувеличивается время поискавозрастает нагрузка на equals()возможна деградация производительностиВыводКоллизии неизбежны, но при корректной реализации hashCode() и equals() они редко становятся проблемой.