В Java: как HashMap обрабатывает коллизии хэш-кодов?

HashMap хранит несколько элементов с одинаковым хэш-кодом в одной корзине (bucket), используя связанный список или сбалансированное дерево.

Механизм обработки коллизий:

1. Вычисление индекса корзины: index = (n - 1) & hash, где n — размер массива корзин, hash — хэш ключа.
2. Разрешение коллизий внутри корзины:
   • Java 7 и ранее: Все элементы в одной корзине хранились в виде односвязного списка.
   • Java 8 и выше: При малом количестве коллизий используется односвязный список. Когда размер списка в корзине превышает порог TREEIFY_THRESHOLD (по умолчанию 8) и общее количество корзин превышает MIN_TREEIFY_CAPACITY (64), список преобразуется в красно-черное дерево (TreeNode). Это улучшает производительность поиска с O(n) до O(log n). При уменьшении размера дерева ниже UNTREEIFY_THRESHOLD (6) оно снова преобразуется в список.

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

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

Дополнительные процессы:

• Rehashing (перехеширование): Когда количество элементов превышает capacity * loadFactor (по умолчанию 0.75), массив корзин увеличивается вдвое, и все элементы перераспределяются по новым индексам.
• Поиск элемента: При вызове get(key) вычисляется хэш и индекс корзины, затем в найденной корзине последовательно (в списке) или бинарно (в дереве) ищется элемент с совпадающим ключом (проверяется equals()).