Wie ist die Organisation der Elemente mit demselben Hash-Wert innerhalb von HashMap implementiert?

In Java werden Elemente mit demselben Hash-Wert (Kollisionen) in HashMap in Form einer verketteten Liste organisiert oder, ab Java 8, bei vielen Kollisionen in Form eines balancierten Baums (TreeNode).

Wenn mehrere Schlüssel denselben Hash-Code haben, werden sie in eine "Korb" (bucket) gelegt. Anfangs sind alle Elemente im Korb durch eine einfach verkettete Liste verbunden. Überschreitet die Anzahl der Elemente in einem Korb einen bestimmten Schwellenwert (normalerweise 8), wird die Liste in einen Rot-Schwarz-Baum umgewandelt, um die Sucheffizienz zu erhöhen.

Beispiel für eine vereinfachte Struktur:

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

Auf diese Weise sucht HashMap bei Kollisionen zunächst im Listeneintrag oder im Baum nach dem Element anhand des Schlüssels, wobei die Schlüssel mittels equals() verglichen werden.