Meséljen a HashMap-ben lévő ütközésekről.

A HashMap-ben ütközés akkor fordul elő, amikor két különböző kulcs ugyanazzal a hash-kóddal rendelkezik. Ez nem vezet adatvesztéshez, de befolyásolja a teljesítményt.

Elem beszúrásakor:

1. Meghívódik a hashCode() a kulcsnál.
2. A hash-kód alapján kiszámítódik a tömbben a kosár indexe.
3. Ha a kosár üres, az elem beszúrásra kerül.
4. Ha a kosár már tartalmaz elemeket, minden elemhez meghívódik az equals() a új kulccsal.
5. Ha az equals() true-t ad vissza, az érték frissül.
6. Ha az equals() mindig false-t ad vissza, egy új elem kerül a kosárba.

Android 7.0 (Nougat) előtt a HashMap láncolt listákat használt a kollíziók megoldására. Sok kollízió esetén a keresés a láncolt listában O(n), ahol n a kosárban lévő elemek száma.

Android 7.0-tól kezdve, ha egy kosárban sok kollízió van (küszöbérték 8 elem), a HashMap automatikusan átalakítja a láncolt listát egy piros-fekete fára (TreeNode). A keresés a fában O(log n) komplexitású, ami jelentősen javítja a teljesítményt sok kollízió esetén. Ha a kosárban lévő elemek száma ismét kevesebb lesz, mint a küszöb (6 elem), a fa visszaalakul láncolt listává.

Egy jó hashCode() és equals() implementáció a felhasználói objektumokhoz kulcsfontosságú a kollíziók minimalizálásához és a HashMap hatékonyságának biztosításához.

Példa:

@Override
public int hashCode() {
    // Jó hashCode implementáció példája
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Helyes equals implementáció példája
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    MyObject myObject = (MyObject) o;
    return field2 == myObject.field2 &&
           field1.equals(myObject.field1);
}