Как е реализирана обработката на колизии в HashMap при различни ключове с еднакъв хеш код?

В Java обработката на колизии в HashMap, когато хеш кодовете са еднакви, се реализира чрез chaining (верижна връзка). Това означава, че всички елементи, чиито хеш код води до един и същи индекс в масива с bucket-ове, се съхраняват в свързан списък или дърво (от Java 8 нататък) в този bucket.

Ако броят на елементите в веригата стане достатъчно голям (по подразбиране повече от 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 ефективно се справя с колизиите, като запазва приемлива производителност.