Pasakokite apie susidūrimus HashMap.

HashMap susidaro, kai du skirtingi raktai turi tą patį maišos kodą. Tai nesukelia duomenų praradimo, bet veikia našumą.

Pridedant elementą:

1. Iškviečiamas hashCode() raktui.
2. Apskaičiuojamas bako indeksas pagal maišos kodą masyve.
3. Jei bakas tuščias, elementas įdedamas.
4. Jei bakas jau turi elementų, kiekvienam elementui bakelyje iškviečiama equals() su nauju raktu.
5. Jei equals() grąžina true, reikšmė atnaujinama.
6. Jei equals() visada grąžina false, į bakelį pridedamas naujas elementas.

Iki Android 7.0 (Nougat), HashMap naudojo susietus sąrašus kolizijų sprendimui. Kai kolizijų skaičius viename bakelyje didėja, paieška susietame sąraše tampa O(n), kur n — elementų skaičius bakelyje.

Nuo Android 7.0, bakeliuose su daug kolizijų (slenkstis 8 elementai), HashMap automatiškai paverčia susietą sąrašą į raudonai-juodą medį (TreeNode). Medžio paieška yra O(log n), kas žymiai pagerina našumą esant daug kolizijų. Jei bakelio elementų skaičius vėl sumažėja žemiau slenksčio (6 elementai), medis vėl paverčiamas į susietą sąrašą.

Geras hashCode() ir equals() įgyvendinimas naudotojo objektams — raktas minimaliai kolizijai ir HashMap efektyvumui.

Pavyzdys:

@Override
public int hashCode() {
    // Geras hashCode pavyzdys
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Teisingas equals pavyzdys
    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);
}