Использует ли HashMap в Java связный список для разрешения коллизий?

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

Как это работает:

1. Элементы (узлы Node<K,V>) с одинаковым индексом бакета (рассчитанным как hash(key) & (n-1)) помещаются в один и тот же бакет.
2. Изначально они хранятся как узлы односвязного списка.
3. При поиске по ключу происходит итерация по этому списку и сравнение ключей через equals().

Важная оптимизация в Java 8+: Когда количество элементов в одном бакете превышает определенный порог (TREEIFY_THRESHOLD = 8) и общее количество бакетов достаточно велико (MIN_TREEIFY_CAPACITY = 64), односвязный список преобразуется в красно-черное дерево (TreeNode). Это улучшает худший случай производительности поиска с O(n) до O(log n).

Пример, иллюстрирующий коллизию:

Map<String, Integer> map = new HashMap<>(16);
// Предположим, что hash("key1") & 15 == hash("key2") & 15 (коллизия)
map.put("key1", 100); // Добавляется первый Node в бакет
map.put("key2", 200); // Добавляется второй Node, ссылающийся на первый (Node.next)

Таким образом, HashMap комбинирует скорость прямого доступа по индексу (массив бакетов) и гибкость связного списка (или дерева) для обработки коллизий.