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

Как работает HashMap

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

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

Ответ

HashMap хранит пары ключ-значение в "корзинах" (buckets) на основе хэш-кода ключа. При добавлении элемента:

Вычисляется хэш ключа через hashCode()
По хэшу определяется индекс корзины: index = hash & (capacity - 1)
Если корзина пуста - элемент добавляется
При коллизии (одинаковый хэш) используется цепочка (в Java 8 при длине >8 переходит на красно-черное дерево)

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);  // hash("apple") -> индекс корзины
map.get("apple");     // быстрый доступ по хэшу

Особенности: