Разкажете за колизиите в HashMap.

Колизия в HashMap възниква, когато два различни ключа имат еднакъв хеш код. Това не води до загуба на данни, но влияе на производителността.

При добавяне на елемент:

1. Извиква се hashCode() на ключа.
2. Изчислява се индексът на кофата в масива въз основа на хеш кода.
3. Ако кофата е празна, елементът се добавя.
4. Ако кофата вече съдържа елементи, се извиква equals() за всеки елемент в кофата с новия ключ.
5. Ако equals() върне true, стойността се актуализира.
6. Ако equals() винаги връща false, новият елемент се добавя към кофата.

До Android 7.0 (Nougat), HashMap използваше свързани списъци за решаване на колизии. При голям брой колизии в един коф, търсенето в списъка става O(n), където n е броят на елементите в кофата.

От Android 7.0 нататък, за кофове с голям брой колизии (праг 8 елемента), HashMap автоматично преобразува свързания списък в червено-черено дърво (TreeNode). Търсенето в дървото има сложност O(log n), което значително подобрява производителността при много колизии. Ако броят на елементите в кофата отново стане по-малък от прага (6 елемента), дървото се преобразува обратно в свързан списък.

Добра реализация на hashCode() и equals() за потребителски обекти е ключът към минимизиране на колизиите и осигуряване на ефективност на HashMap.

Пример:

@Override
public int hashCode() {
    // Пример за добра реализация на hashCode
    int result = 17;
    result = 31 * result + field1.hashCode();
    result = 31 * result + field2;
    return result;
}

@Override
public boolean equals(Object o) {
    // Пример за правилна реализация на 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);
}