Как устроен HashMap внутри: бакеты, коллизии, расширение и деревья с Java 8?
Проверила команда Сопровод · Обновлено
Короткий ответ
HashMap хранит записи в массиве бакетов. Номер бакета считается из hashCode() ключа: старшие биты хеша смешиваются с младшими, результат обрезается маской по размеру таблицы. Ключи с одним номером лежат в бакете цепочкой и различаются через equals(). Когда записей больше 0,75 от емкости, таблица удваивается. С Java 8 длинная цепочка превращается в красно-черное дерево.
Почему этот вопрос задают
HashMap есть почти в каждом сервисе, и от его устройства зависят скорость, память и баги с изменяемыми ключами. Middle должен объяснить, что происходит внутри put и get, своими словами.
Как рассуждать
- Опишите массив бакетов и то, как из
hashCode()получается номер бакета - Объясните коллизию: два ключа в одном бакете различаются через
equals() - Назовите порог расширения: при заполнении больше 0,75 таблица удваивается и записи переезжают
- Закончите деревьями с Java 8 и обоими условиями: длина цепочки и емкость от 64
Ответ с примером
Кеш профилей онлайн-игры держит в HashMap профили по нику. put берет hashCode() ключа, смешивает старшие 16 бит с младшими через h ^ (h >>> 16) и обрезает маской (n - 1). Емкость всегда степень двойки, поэтому маска заменяет деление с остатком. У ников «Aa» и «BB» одинаковый хеш 2112, и в таблице на 16 мест оба попадают в бакет 0. Коллизия ничего не теряет: в бакете лежит цепочка узлов, и get находит свой профиль через equals().
По умолчанию емкость 16 и коэффициент загрузки 0,75, поэтому на 13-й записи таблица удваивается до 32. Каждая запись остается в своем бакете или сдвигается ровно на 16 позиций. Если в бакете уже 8 записей и емкость не меньше 64, цепочка становится красно-черным деревом. Когда ключи различаются хешами или реализуют Comparable, поиск в нем занимает O(log n) вместо O(n).
public class Main {
public static void main(String[] args) {
Map<String, Profile> cache = new HashMap<>();
for (Profile p : List.of(new Profile("Aa", 12), new Profile("BB", 40))) {
cache.put(p.nick(), p);
int h = p.nick().hashCode(), bucket = (16 - 1) & (h ^ (h >>> 16));
System.out.println(p.nick() + ": hashCode " + h + ", бакет " + bucket);
}
System.out.println(cache.get("Aa") + " " + cache.get("BB"));
}
}
record Profile(String nick, int level) {}Aa: hashCode 2112, бакет 0 BB: hashCode 2112, бакет 0 Profile[nick=Aa, level=12] Profile[nick=BB, level=40]
Как ответить сильнее
Что добавит опытный кандидат
Что спросят следом
Доступно по подписке
Приемы опытных и готовые ответы
Частые ошибки
«
HashMapхранит записи в порядке добавления»Скажите, что порядок обхода зависит от хешей и меняется после расширения. Нужен порядок добавления — берите
LinkedHashMap, нужна сортировка по ключу —TreeMap«Дерево появляется, как только в бакете 8 элементов»
Добавьте второе условие: емкость таблицы не меньше 64. Маленькую таблицу
HashMapсначала удваивает, это дешевле дерева«
getиputвсегда работают за O(1)»Уточните: в среднем O(1) при хорошем
hashCode(). Дерево в бакете дает O(log n) при разных хешах или ключах сComparable, а само расширение таблицы стоит O(n)«Load factor 0,75 значит, что таблица заполняется на 75% и дальше не растет»
Поправьте: после порога таблица удваивается. 0,75 — компромисс между памятью и длиной цепочек, другое значение можно передать в конструктор
Сигналы для интервьюера
Сильный ответ
Считает номер бакета для конкретного ключа на доске и объясняет, что случится при 13-й вставке в таблицу на 16
Тревожный сигнал
Уверенно описывает бакеты и расширение, а сдвиг h >>> 16 в hash() считает лишней микрооптимизацией
Красный флаг
Уверен, что при коллизии новая запись затирает старую, и не упоминает equals() вовсе
Как еще могут спросить
- Как
HashMapнаходит бакет для ключа? - Что происходит в
HashMapпри коллизии хешей? - Когда
HashMapувеличивает размер таблицы? - Что изменилось в устройстве
HashMapв Java 8?











