Hogyan valósul meg a kollíziókezelés a HashMap-ben, amikor különböző kulcsok ugyanazzal a hash-kóddal rendelkeznek?

Java-ban a HashMap-ben az ütközések kezelése, amikor a hash-kódok megegyeznek, láncolással (chaining) valósul meg. Ez azt jelenti, hogy minden olyan elem, amelynek hash-kódja ugyanoda mutat a tömbben, egy összekapcsolt listában vagy (Java 8-tól kezdődően) egy fában tárolódik ebben a bucketben.

Ha a láncban lévő elemek száma elég nagy lesz (alapértelmezés szerint több mint 8), akkor a láncolt lista egy kiegyensúlyozott fára (TreeNode) alakul át, ami javítja a keresési teljesítményt O(n)ről O(log n)-re.

Egyszerűsített beszúrási logika példája:

int bucketIndex = hash(key) % table.length;
Node<K,V> head = table[bucketIndex];
// Ellenőrzi, hogy a kulcs már létezik-e a láncban
while (head != null) {
    if (head.key.equals(key)) {
        head.value = value; // érték frissítése
        return;
    }
    head = head.next;
}
// Ha a kulcs nem létezik, hozzáad egy új csomópontot a lista elejéhez
Node<K,V> newNode = new Node<>(key, value);
newNode.next = table[bucketIndex];
table[bucketIndex] = newNode;

Így a HashMap hatékonyan kezeli az ütközéseket, miközben elfogadható teljesítményt tart fenn.