Kako je organizovana struktura elemenata sa istom vrednošću heš-a unutar HashMap?

U Javi, elementi sa istim hash vrednostima (kolizije) u HashMap organizovani su u obliku povezane liste ili, od Java 8 nadalje, u obliku uravnoteženog stabla (TreeNode) kada postoji mnogo kolizija.

Kada više ključeva ima isti hash kod, oni se smeštaju u jednu "kantu" (bucket). U početku, svi elementi u kanti su povezani jednostavnom povezanim listom. Ako broj elemenata u jednoj kanti pređe određeni prag (obično 8), lista se pretvara u crveno-crno stablo radi povećanja efikasnosti pretraživanja.

Primer pojednostavljene strukture:

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

Na ovaj način, pri kolizijama, HashMap prvo traži element u listi ili stablu po ključu, upoređujući ključeve pomoću metode equals().