Что такое коллизия в хеш-таблицах?

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

Пример коллизии в Java:

String a = "FB";
String b = "Ea";
// Алгоритм хеширования строк дает одинаковый результат:
System.out.println(a.hashCode()); // 2236
System.out.println(b.hashCode()); // 2236
// При добавлении в HashMap оба ключа попадут в одну корзину (bucket).

Способы разрешения коллизий:

• Метод цепочек (Chaining): Элементы с одинаковым хеш-кодом хранятся в одной корзине в виде связного списка или сбалансированного дерева. Это подход, используемый в HashMap.
• Открытая адресация (Open Addressing): При коллизии элемент помещается в следующую свободную ячейку таблицы согласно алгоритму проб (линейное, квадратичное probing).

Как Java HashMap обрабатывает коллизии (Java 8+):

1. Элементы в корзине хранятся как связный список.
2. При достижении определенного порога элементов в списке (TREEIFY_THRESHOLD = 8) и при достаточном размере таблицы, список преобразуется в красно-черное дерево для обеспечения производительности O(log n) в худшем случае.
3. При уменьшении количества элементов дерево преобразуется обратно в список.

Важно для корректной работы:

• Методы equals() и hashCode() должны быть согласованы: если a.equals(b) == true, то a.hashCode() == b.hashCode().
• Обратное утверждение не обязательно: одинаковые хеш-коды не означают равенство объектов.