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

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

Как обрабатываются коллизии в HashMap? Основной механизм — метод цепочек (chaining). Элементы с одинаковым хешем хранятся в одной ячейке в виде структуры данных:

• До Java 8 — связный список.
• В Java 8 и выше — при достижении определенного порога коллизий (TREEIFY_THRESHOLD) список преобразуется в сбалансированное красно-черное дерево для восстановления производительности поиска до O(log n).

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

Map<String, Integer> map = new HashMap<>();
// Строки "Aa" и "BB" имеют одинаковый хеш-код 2112
map.put("Aa", 1); // hash("Aa") = 2112
map.put("BB", 2); // hash("BB") = 2112 -> КОЛЛИЗИЯ! Оба ключа попадут в один бакет.

Как избежать проблем с коллизиями?

1. Корректно переопределять equals() и hashCode(). Контракт между этими методами обязателен: если a.equals(b) == true, то a.hashCode() == b.hashCode().
2. Выбирать подходящую реализацию Map. Например, LinkedHashMap сохраняет порядок вставки, а TreeMap обеспечивает сортировку по ключам, но их производительность при частых коллизиях может отличаться.