Kā tiek īstenota elementu organizācija ar vienādu hash vērtību HashMap iekšienē?

Java, elementi ar vienādu hash vērtību (sadursmes) ir organizēti kā sasaistīts saraksts vai, no Java 8, kā līdzsvarots koks (TreeNode), kad ir daudz sadursmju.

Kad vairāki atslēgas ir ar vienādu hash kodu, tie tiek ievietoti vienā "kārbi" (bucket). Sākotnēji visi elementi šajā kārbā ir saistīti ar vienkāršu sasaistītu sarakstu. Ja viena kārbas elements pārsniedz noteiktu slieksni (parasti 8), saraksts tiek pārveidots par sarkano-melno koku, lai uzlabotu meklēšanas efektivitāti.

Vienkāršotas struktūras piemērs:

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

Tādējādi, sadursmju gadījumā, HashMap vispirms meklē elementu sarakstā vai kokā pēc atslēgas, salīdzinot atslēgas ar equals().