Rozprávajte o kolíziách v HashMap.

Kolízia v HashMap nastáva, keď dva rôzne kľúče majú rovnaký hash kód. To nevedie ku strate dát, ale ovplyvňuje výkon.

Pri vkladaní prvku:

1. Zavolá sa hashCode() kľúča.
2. Vypočíta sa index koša v poli na základe hash kódu.
3. Ak je kôš prázdny, prvok sa vloží.
4. Ak kôš už obsahuje prvky, pre každý prvok v koši sa volá equals() s novým kľúčom.
5. Ak equals() vráti true, hodnota sa aktualizuje.
6. Ak equals() vždy vráti false, nový prvok sa pridá do koša.

Do Android 7.0 (Nougat), HashMap používala spojené zoznamy na riešenie kolízií. Pri veľkom počte kolízií v jednom koši sa vyhľadávanie v zozname stáva O(n), kde n je počet prvkov v koši.

Od Android 7.0, pre koše s veľkým počtom kolízií (práh 8 prvkov), HashMap automaticky konvertuje spojený zoznam na červenú-čiernu strom (TreeNode). Vyhľadávanie v strome má zložitosť O(log n), čo výrazne zlepšuje výkon pri veľkom počte kolízií. Ak počet prvkov v koši opäť klesne pod práh (6 prvkov), strom sa opäť konvertuje na spojený zoznam.

Dobrá implementácia hashCode() a equals() pre vlastné objekty je kľúčom k minimalizácii kolízií a zabezpečeniu efektívnosti HashMap.

Príklad:

@Override
public int hashCode() {
    // Príklad dobrej implementácie hashCode
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Príklad správnej implementácie 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);
}