Ako je organizovaná štruktúra prvkov s rovnakou hodnotou hash kódu v HashMap?

V Jave sú prvky s rovnakou hodnotou hash (kolízie) organizované vo forme prepojenej zoznamu alebo, od Java 8, vo forme vyváženého stromu (TreeNode), keď je veľa kolízií.

Keď niekoľko kľúčov má rovnaký hash kód, sú umiestnené do jednej "vedra" (bucket). Počiatočne sú všetky prvky v vedre prepojené jednoduchým prepojeným zoznamom. Ak počet prvkov v jednom vedre presiahne určitý prah (zvyčajne 8), zoznam sa premení na červeno-čierne stromové štruktúry na zvýšenie efektívnosti vyhľadávania.

Príklad zjednodušenej štruktúry:

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

Takto, pri kolíziách, HashMap najskôr hľadá prvok v zozname alebo v strome podľa kľúča, porovnávať kľúče pomocou equals().