Jak zorganizowana jest struktura elementów z tym samym wartością hasza w HashMap?

W Javie elementy o tym samym kodzie hash (kolizje) w HashMap są organizowane w postaci listy powiązanej lub, od Java 8, w postaci zrównoważonego drzewa (TreeNode) przy dużej liczbie kolizji.

Gdy kilka kluczy ma ten sam kod hash, umieszcza się je w jednym "wiadrze" (bucket). Początkowo wszystkie elementy w wiadrze są powiązane przez prostą listę powiązaną. Jeśli liczba elementów w wiadrze przekracza określony próg (zwykle 8), lista ta jest przekształcana w czerwono-czarne drzewo, aby zwiększyć wydajność wyszukiwania.

Przykład uproszczonej struktury:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // ...
}

W ten sposób, w przypadku kolizji, HashMap najpierw szuka elementu na liście lub w drzewie po kluczu, porównując klucze za pomocą equals().