Jak obsługiwana jest kolizja w HashMap, gdy różne klucze mają ten sam kod hash?

W Javie obsługa kolizji w HashMap, gdy kod hash jest taki sam, jest realizowana za pomocą łańcuchów (chaining). Oznacza to, że wszystkie elementy, których kod hash prowadzi do tego samego indeksu w tablicy bucketów, są przechowywane w liście powiązanej lub drzewie (od Java 8) w tym bucketcie.

Jeśli liczba elementów w łańcuchu stanie się wystarczająco duża (domyślnie więcej niż 8), lista powiązana jest przekształcana w zrównoważone drzewo (TreeNode), co poprawia wydajność wyszukiwania z O(n) do O(log n).

Przykład uproszczonej logiki wstawiania:

int bucketIndex = hash(key) % table.length;
Node<K,V> head = table[bucketIndex];
// Sprawdzamy, czy klucz już istnieje w łańcuchu
while (head != null) {
    if (head.key.equals(key)) {
        head.value = value; // aktualizujemy wartość
        return;
    }
    head = head.next;
}
// Jeśli klucza nie ma, dodaj nowy węzeł na początku listy
Node<K,V> newNode = new Node<>(key, value);
newNode.next = table[bucketIndex];
table[bucketIndex] = newNode;

W ten sposób HashMap skutecznie radzi sobie z kolizjami, utrzymując akceptowalną wydajność.