Jak je organizována struktura prvků se stejnou hodnotou hashe uvnitř HashMap?

V Javě jsou prvky s identickým hodnotou hash (kolize) organizovány ve formě spojovaného seznamu nebo, od Java 8, ve formě vyváženého stromu (TreeNode), pokud je mnoho kolizí.

Když několik klíčů má stejný hash kód, jsou umístěny do jedné "koše" (bucket). Zpočátku jsou všechny prvky v koši spojeny jednoduchým spojovaným seznamem. Pokud počet prvků v koši přesáhne určitý práh (obvykle 8), seznam se přemění na červeno-černý strom pro zvýšení efektivity hledání.

Příklad zjednodušené struktury:

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

Tímto způsobem HashMap při kolizích nejprve hledá prvek v seznamu nebo stromu podle klíče, porovnávající klíče pomocí equals().