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

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

Агар шумораи элементҳо дар зандурафтан ба андозаи кофӣ калон шавад (аз пешфарз бештар аз 8), рӯйхати пайваст ба дарахти мувозинатёфтар (TreeNode) табдил меёбад, ки иҷрои ҷустуҷӯро аз O(n) ба O(log n) беҳтар мекунад.

Маслиҳати соддакардашудаи воридкунӣ:

int bucketIndex = hash(key) % table.length;
Node<K,V> head = table[bucketIndex];
// Санҷед, ки оё калид аллакай дар зандурафтан ҳаст
while (head != null) {
    if (head.key.equals(key)) {
        head.value = value; // навсозии арзиш
        return;
    }
    head = head.next;
}
// Агар калид вуҷуд надошта бошад, як навъро ба оғози рӯйхати пайваст илова кунед
Node<K,V> newNode = new Node<>(key, value);
newNode.next = table[bucketIndex];
table[bucketIndex] = newNode;

Тавре ки мебинем, HashMap ба самаранокӣ бо коллизияҳо кор мекунад ва дар ҳоле ки иҷрои қобили қабулро нигоҳ медорад.