Hoe wordt de organisatie van elementen met dezelfde hash-waarde binnen HashMap gerealiseerd?

In Java worden elementen met dezelfde hash-waarde (botsingen) in HashMap georganiseerd als een gekoppelde lijst of, vanaf Java 8, als een gebalanceerde boom (TreeNode) wanneer er veel botsingen zijn.

Wanneer meerdere sleutels dezelfde hash-code hebben, worden ze in één "emmer" (bucket) geplaatst. Aanvankelijk zijn alle elementen in de emmer verbonden via een eenvoudige gekoppelde lijst. Als het aantal elementen in één emmer een bepaalde drempel overschrijdt (meestal 8), wordt de lijst omgezet in een rood-zwart boom om de zoek efficiëntie te verbeteren.

Voorbeeld van een vereenvoudigde structuur:

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

Zo zoekt HashMap bij botsingen eerst in de lijst of in de boom naar het element op basis van de sleutel, waarbij de sleutels worden vergeleken met equals().