Cum este realizată organizarea elementelor cu aceeași valoare de hash în interiorul HashMap?

În Java, elementele cu aceeași valoare de hash (coliziuni) în HashMap sunt organizate sub formă de listă legată sau, începând cu Java 8, sub formă de arbore echilibrat (TreeNode) atunci când există un număr mare de coliziuni.

Când mai multe chei au același cod de hash, acestea sunt plasate într-un "coș" (bucket). Inițial, toate elementele din coș sunt legate printr-o listă simplă. Dacă numărul de elemente dintr-un coș depășește un prag determinat (de obicei 8), lista este transformată într-un arbore roșu-negru pentru a crește eficiența căutării.

Exemplu de structură simplificată:

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

Astfel, în caz de coliziuni, HashMap caută mai întâi elementul în listă sau în arbore după cheie, comparând cheile cu ajutorul metodei equals().