Ako je implementované spracovanie kolízií v HashMap pri rôznych kľúčoch s rovnakým hash kódom?

V Java, spracovanie kolízií v HashMap, keď sú hash kódy rovnaké, je implementované pomocou chaining (reťazenia). To znamená, že všetky prvky, ktorých hash kód smeruje na rovnaký index v poli bucketov, sú uložené v prepojenej zozname alebo strome (od Java 8) v tomto bucketu.

Ak sa počet prvkov v reťazci stane dostatočne veľký (predvolene viac ako 8), prepojený zoznam sa premení na vyvážené stromové (TreeNode), čo zlepšuje výkon vyhľadávania z O(n) na O(log n).

Príklad zjednodušenej logiky vkladania:

int bucketIndex = hash(key) % table.length;
Node<K,V> head = table[bucketIndex];
// Kontrola, či už kľúč existuje v reťazci
while (head != null) {
    if (head.key.equals(key)) {
        head.value = value; // aktualizácia hodnoty
        return;
    }
    head = head.next;
}
// Ak kľúč neexistuje, pridá sa nový uzol na začiatok zoznamu
Node<K,V> newNode = new Node<>(key, value);
newNode.next = table[bucketIndex];
table[bucketIndex] = newNode;

Týmto spôsobom HashMap efektívne zvláda kolízie a zachováva prijateľný výkon.