Vorbește despre coliziunile din HashMap.

Ocuparea în HashMap apare atunci când doi chei diferite au același cod hash. Acest lucru nu duce la pierderea datelor, dar afectează performanța.

La inserarea unui element:

1. Se apelează hashCode() al cheii.
2. Se calculează indexul coșului în array pe baza codului hash.
3. Dacă coșul este gol, elementul este inserat.
4. Dacă coșul conține deja elemente, se apelează equals() pentru fiecare element din coș cu noua cheie.
5. Dacă equals() returnează true, valoarea este actualizată.
6. Dacă equals() returnează întotdeauna false, se adaugă un nou element în coș.

Până la Android 7.0 (Nougat), HashMap folosea liste legate pentru rezolvarea coliziunilor. Cu multe coliziuni într-un coș, căutarea în listă devine O(n), unde n este numărul de elemente din coș.

Din Android 7.0 încolo, pentru coșurile cu multe coliziuni (pragul de 8 elemente), HashMap convertește automat lista legată într-un arbore roșu-negru (TreeNode). Căutarea în arbore are complexitatea O(log n), ceea ce îmbunătățește semnificativ performanța în cazurile cu multe coliziuni. Dacă numărul de elemente din coș scade din nou sub prag (6 elemente), arborele este reconvertit în listă legată.

O implementare bună a hashCode() și equals() pentru obiecte personalizate este cheia pentru minimizarea coliziunilor și asigurarea eficienței HashMap.

Exemplu:

@Override
public int hashCode() {
    // Exemplu de implementare bună a hashCode
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Exemplu de implementare corectă a equals
    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);
}