Opowiedz o kolizjach w HashMap.

Kolizja w HashMap występuje, gdy dwa różne klucze mają ten sam kod hash. Nie prowadzi to do utraty danych, ale wpływa na wydajność.

Przy wstawianiu elementu:

1. Wywoływana jest metoda hashCode() klucza.
2. Obliczany jest indeks kubełka w tablicy na podstawie kodu hash.
3. Jeśli kubełek jest pusty, element jest wstawiany.
4. Jeśli kubełek już zawiera elementy, dla każdego elementu w kubełku wywoływana jest metoda equals() z nowym kluczem.
5. Jeśli equals() zwraca true, wartość jest aktualizowana.
6. Jeśli equals() zawsze zwraca false, nowy element jest dodawany do kubełka.

Do Android 7.0 (Nougat), HashMap używał list powiązanych do rozwiązywania kolizji. Przy dużej liczbie kolizji w jednym kubełku, wyszukiwanie w liście powiązanej staje się O(n), gdzie n to liczba elementów w kubełku.

Od Android 7.0, dla kubełków z dużą liczbą kolizji (próg 8 elementów), HashMap automatycznie zamienia listę powiązaną na drzewo czerwono-czarne (TreeNode). Wyszukiwanie w drzewie ma złożoność O(log n), co znacznie poprawia wydajność przy dużej liczbie kolizji. Jeśli liczba elementów w kubełku ponownie spadnie poniżej progu (6 elementów), drzewo jest zamieniane z powrotem na listę powiązaną.

Dobra implementacja hashCode() i equals() dla obiektów użytkownika jest kluczowa dla minimalizacji kolizji i zapewnienia efektywności HashMap.

Przykład:

@Override
public int hashCode() {
    // Przykład dobrej implementacji hashCode
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Przykład poprawnej implementacji 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);
}