Чӣ гуна ташкилоти унсурҳо бо арзиши ҳамон хеш дар дохили HashMap амалӣ мешавад?

Дар Java, элементҳо бо арзиши hash-и якхела (ҷаллобӣ) дар HashMap ташкил карда мешаванд, ё ҳамчун рӯйхати пайвастшуда ё, аз Java 8, ҳамчун дарахти мувозинатшуда (TreeNode) вақте ки шумораи ҷаллобӣ зиёд аст.

Вақте ки чанд калид кодекси hash-и якхела доранд, онҳо дар як "қуттӣ" (bucket) ҷойгир мешаванд. Аввал, ҳамаи элементҳо дар қуттӣ тавассути рӯйхати пайвастшудаи оддӣ пайваст шудаанд. Агар шумораи элементҳо дар як қуттӣ аз ҳадди муайян (одатан 8) зиёд шавад, рӯйхат ба дарахти сурх-сиёҳ барои беҳтар кардани самаранокии ҷустуҷӯ табдил дода мешавад.

Масали соддакардашудаи структура:

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

Бинобар ин, дар ҳолатҳои ҷаллобӣ, HashMap аввал дар рӯйхат ё дар дарахт тавассути калид меҷӯяд, ки калидҳоро тавассути equals() муқоиса мекунад.