Pastāstiet par sadursmēm HashMap.

HashMap rodas, kad divi dažādi atslēgas ir ar vienādu haškodu. Tas nerada datu zudumu, bet ietekmē veiktspēju.

Pievienojot elementu:

1. Izsauc hashCode() atslēgai.
2. Aprēķina baksta indeksu pēc haškoda masīvā.
3. Ja baksts ir tukšs, elements tiek pievienots.
4. Ja baksts jau satur elementus, katram elementam bakstā tiek izsaukts equals() ar jauno atslēgu.
5. Ja equals() atgriež true, vērtība tiek atjaunināta.
6. Ja equals() vienmēr atgriež false, jauns elements tiek pievienots bakstā.

Līdz Android 7.0 (Nougat), HashMap izmantoja sasaistītus sarakstus kolīziju risināšanai. Kad kolīziju skaits vienā bakstā palielinās, meklēšana sasaistītajā sarakstā kļūst par O(n), kur n ir elementu skaits bakstā.

No Android 7.0, bakstos ar daudz kolīziju (slieksnis 8 elementi), HashMap automātiski pārvērš sasaistīto sarakstu par sarkani- melnu koku (TreeNode). Koka meklēšana ir O(log n), kas ievērojami uzlabo veiktspēju lielam kolīziju skaitam. Ja baksta elements atkal samazinās zem sliekšņa (6 elementi), koks tiek atkal pārvērsts sasaistītā sarakstā.

Laba hashCode() un equals() realizācija lietotāja objektiem — atslēga minimālai kolīziju skaitam un HashMap efektivitātei.

Piemērs:

@Override
public int hashCode() {
    // Labs hashCode piemērs
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Pareizs equals piemērs
    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);
}