Какова внутренняя структура HashMap?

Короткий ответ

HashMap внутри — это массив бакетов: массив узлов Node<K,V>[] table, где каждый узел хранит hash, key, value и ссылку next на следующий узел при коллизии. Индекс корзины вычисляется из hashCode() ключа, а коллизии разрешаются цепочками узлов.

Как это работает подробнее

По умолчанию создаётся 16 корзин, индекс вычисляется как (n - 1) & hash, где n — текущая длина массива. Когда число записей превышает ёмкость × load factor (по умолчанию 0,75), массив увеличивается примерно вдвое и записи перераспределяются по новым корзинам.

• Узел: хранит четыре поля — вычисленный хэш ключа, ключ, значение и ссылку next на следующий узел той же корзины.
• Коллизии: разные ключи с одним индексом выстраиваются в цепочку; с Java 8 цепочка длиннее 8 узлов превращается в красно-чёрное дерево, и худший случай поиска становится O(log n) вместо O(n).
• null: HashMap допускает один null-ключ — он попадает в корзину с индексом 0 без вызова hashCode — и сколько угодно null-значений.
• Потокобезопасность: класс не синхронизирован, при работе из нескольких потоков нужна внешняя синхронизация или ConcurrentHashMap.

Пример кода

HashMapDemo.javaКопировать

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
System.out.println(map.get("apple")); // 1
// индекс корзины: (n - 1) & hash, внутри цепочка узлов

Что использовать на практике

• Берите HashMap, когда нужна карта «ключ — значение» со средним доступом O(1) и порядок обхода не важен.
• Для равномерного распределения по корзинам ключи обязаны корректно переопределять equals и hashCode.
• В многопоточном коде вместо внешней синхронизации HashMap используйте ConcurrentHashMap.

Подводные камни

• Если переопределить только equals или только hashCode, равные ключи разъедутся по разным корзинам и элементы будут «теряться» из карты.
• Каждый resize дорог: начальную ёмкость и load factor стоит подбирать под ожидаемое число записей.
• Плохой hashCode (например, константа) собирает все узлы в одну корзину и вырождает операции в O(n).

Как отвечать на собеседовании

• Начните с «HashMap — это массив бакетов из узлов Node (hash, key, value, next)» → опишите вычисление индекса через hashCode и (n - 1) & hash → добавьте про цепочки коллизий и превращение длинных цепочек в красно-чёрное дерево с Java 8 → упомяните load factor 0,75 и resize → закончите тезисами про один null-ключ и отсутствие потокобезопасности.