Что такое коллизия в HashMap — пример ответа на собеседовании Android Разработчик

Что такое коллизия в HashMap

«Что такое коллизия в HashMap» — вопрос из категории Алгоритмы и структуры данных, который задают на 23% собеседований Android Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Алгоритмы и структуры данных Вероятность: 23% Категория: Android Разработчик

Ответ

Коллизия в HashMap возникает, когда разные ключи имеют одинаковый хеш-код или разные хеш-коды, но попадают в одну и ту же корзину (bucket). В Java HashMap разрешает коллизии через цепочку (каждый bucket — это связный список или дерево, если элементов много) или открытую адресацию (в некоторых реализациях).

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("Aa", 1); // Хеш-код "Aa" = 2112
map.put("BB", 2); // Хеш-код "BB" = 2112 → коллизия!

При коллизии HashMap добавляет элемент в список/дерево внутри bucket. При поиске сначала находится bucket по хеш-коду, затем ключи сравниваются через equals().