Rääkige HashMap-i kokkupõrgetest.

HashMap tekib, kui kaks erinevat võtit omavad sama hash-koodi. See ei põhjusta andmete kaotsiminekut, kuid mõjutab jõudlust.

Elementi lisamisel:

1. Kutsutakse välja hashCode() võtme jaoks.
2. Arvutatakse indeks kaussmasiivis hash-koodi põhjal.
3. Kui kauss on tühi, element lisatakse.
4. Kui kauss juba sisaldab elemente, kutsutakse equals() iga elemendi jaoks kausis uue võtmega.
5. Kui equals() tagastab true, uuendatakse väärtust.
6. Kui equals() alati tagastab false, lisatakse uus element kausile.

Android 7.0 (Nougat)-ni kasutas HashMap kolizioonide lahendamiseks seotud nimekirju. Kui kolizioonide arv ühes kausis suureneb, muutub otsing seotud nimekirjas O(n)-ks, kus n on elementide arv kausis.

Alates Android 7.0, suurte kolizioonide (lävend 8 elementi) puhul HashMap automaatselt teisendab seotud nimekirja punavärvi-mustaks puuks (TreeNode). Puu otsing on O(log n), mis oluliselt parandab jõudlust suure kolizioonide arvu korral. Kui kausi elementide arv langeb uuesti alla lävendi (6 elementi), muudetakse puu tagasi seotud nimekirjaks.

Hea hashCode() ja equals() realiseerimine kasutajaobjektidele on võtmetähtsusega kolizioonide minimeerimiseks ja HashMap tõhususe tagamiseks.

Näide:

@Override
public int hashCode() {
    // Hea hashCode näide
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Õige equals näide
    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);
}