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

Пример:

java