Povězte o kolizích v HashMap.

Kolize v HashMap nastává, když dva různé klíče mají stejný hash kód. To nezpůsobí ztrátu dat, ale ovlivní výkon.

Při vkládání prvku:

1. Zavolá se hashCode() klíče.
2. Vypočítá se index koše v poli na základě hash kódu.
3. Pokud je koš prázdný, prvek se vloží.
4. Pokud koš již obsahuje prvky, volá se equals() pro každý prvek v koši s novým klíčem.
5. Pokud equals() vrátí true, hodnota se aktualizuje.
6. Pokud equals() vždy vrací false, nový prvek se přidá do koše.

Do Android 7.0 (Nougat) HashMap používala spojové seznamy k řešení kolizí. Při velkém počtu kolizí v jednom koši je hledání v seznamu O(n), kde n je počet prvků v koši.

Od Android 7.0 dále, pro koše s velkým počtem kolizí (práh 8 prvků), HashMap automaticky převádí spojový seznam na červenou-černou strom (TreeNode). Vyhledávání ve stromu má složitost O(log n), což výrazně zlepšuje výkon při velkém počtu kolizí. Pokud počet prvků v koši opět klesne pod práh (6 prvků), strom se zpět převede na spojový seznam.

Dobrá implementace hashCode() a equals() pro vlastní objekty je klíčem ke snížení kolizí a zajištění efektivity HashMap.

Příklad:

@Override
public int hashCode() {
    // Příklad dobré implementace hashCode
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Příklad správné implementace 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);
}