Hogyan valósul meg az elemek szervezése ugyanazzal a hash-kóddal a HashMap-ben?

Java-ban a HashMap elemei, amelyek ugyanazzal a hash-kóddal rendelkeznek (ütközések), láncolt listaként vagy, Java 8-tól kezdve, kiegyensúlyozott fákként (TreeNode) vannak szervezve, ha sok ütközés fordul elő.

Amikor több kulcs ugyanazt a hash-kódot kapja, egy "kád" (bucket) alá kerülnek. Kezdetben minden elem a kádon belül egy egyszerű láncolt listával van összekötve. Ha egy kádon belüli elemek száma meghalad egy bizonyos küszöbértéket (általában 8), a listát vörös-fekete fára alakítják át a keresés hatékonyságának növelése érdekében.

Egyszerűsített szerkezet példája:

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

Így ütközés esetén a HashMap először a listában vagy a fában keresi meg az elemet a kulcs alapján, azokat az equals() metódussal összehasonlítva.