Расскажите о коллизиях в 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);
}