Что такое коллизия хеш-кодов и как она обрабатывается?

Question

Коллизия возникает, когда разные ключи имеют одинаковый hashCode().
Это нормальная ситуация для хеш-таблиц.
HashMap хранит такие элементы в одной корзине.
Для различения используется equals().
Начиная с Java 8, длинные цепочки оптимизируются деревьями.

YeaHub · Accepted Answer

Хеш-функция отображает бесконечное множество ключей в ограниченное количество значений, поэтому коллизии неизбежны.Что такое коллизияОпределение:Коллизия — это ситуация, когда два разных объекта возвращают одинаковый hashCode().Пример:key1.hashCode() == key2.hashCode()
key1.equals(key2) == false
Как HashMap обрабатывает коллизииПосле попадания в одну корзину:Элементы хранятся в виде списка.При поиске выполняется последовательный вызов equals().Оптимизация в Java 8+Если:В одной корзине становится слишком много элементов.Ключи реализуют Comparable.Тогда структура:преобразуется из спискав сбалансированное дерево (красно-черное)Это улучшает сложность:с O(n)до O(log n)Почему коллизии допустимыВажно:Минимизировать количество коллизий.Никогда не нарушать контракт equals/hashCode.Краткий выводКоллизии — нормальная часть работы хеш-таблиц, а HashMap эффективно справляется с ними через списки и деревья.