Kā HashMap realizē sadursmju apstrādi, ja dažādiem atslēgām ir vienāds hash kods?

Java, ja HashMap sadursmju apstrāde, kad ir vienādi hash kodi, tiek īstenota, izmantojot chaining (ķēdēšanu). Tas nozīmē, ka visi elementi, kuru hash kods noved pie tā paša indeksa masīvā, tiek glabāti sasaistītā sarakstā vai kokā (no Java 8) šajā bucket.

Ja elementu skaits ķēdē kļūst pietiekami liels (pēc noklusējuma vairāk nekā 8), sasaistītais saraksts tiek pārveidots līdzsvarotā kokā (TreeNode), kas uzlabo meklēšanas veiktspēju no O(n) uz O(log n).

Vienkāršots ievietošanas piemērs:

int bucketIndex = hash(key) % table.length;
Node<K,V> head = table[bucketIndex];
// Pārbauda, vai atslēga jau eksistē ķēdē
while (head != null) {
    if (head.key.equals(key)) {
        head.value = value; // atjaunot vērtību
        return;
    }
    head = head.next;
}
// Ja atslēga nav, pievieno jaunu mezglu sākumā
Node<K,V> newNode = new Node<>(key, value);
newNode.next = table[bucketIndex];
table[bucketIndex] = newNode;

Tādējādi HashMap efektīvi pārvalda sadursmes, saglabājot pieņemamu veiktspēju.