Как реализована обработка коллизий в HashMap при одинаковых хэш-кодах различных ключей?

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

Если количество элементов в цепочке становится достаточно большим (по умолчанию больше 8), связный список преобразуется в сбалансированное дерево (TreeNode), что улучшает производительность поиска с O(n) до O(log n).

Пример упрощённой логики вставки:

int bucketIndex = hash(key) % table.length;
Node<K,V> head = table[bucketIndex];
// Проверяем, есть ли ключ в цепочке
while (head != null) {
    if (head.key.equals(key)) {
        head.value = value; // обновляем значение
        return;
    }
    head = head.next;
}
// Если ключа нет, добавляем новый узел в начало списка
Node<K,V> newNode = new Node<>(key, value);
newNode.next = table[bucketIndex];
table[bucketIndex] = newNode;

Таким образом, HashMap эффективно справляется с коллизиями, сохраняя приемлемую производительность.