← вся теориятеория к собесу · Коллекции Java

HashMap в Java изнутри

HashMap изнутри: вопрос номер один

Запустил четыре потока, каждый кладёт по 50 000 записей в обычную HashMap. Ожидаемо 200 000, а в мапе оказалось 199 566. Повторил - 178 404. Ещё раз - 198 625. Тот же код с ConcurrentHashMap даёт ровно 200 000 каждый раз.

«Расскажи, как устроена HashMap» - самый частый вопрос Java-собесов вообще. Он удобен интервьюеру: за пять минут видно и знание структур данных, и понимание контрактов, и представление о многопоточности.

// Формулировки: «что происходит при put?», «зачем корзина превращается в дерево?», «почему нельзя HashMap из двух потоков?»

Путь put: ящики, цепочки, деревья

Внутри - массив ящиков. Когда кладёшь пару, берётся hashCode ключа, к нему подмешиваются старшие биты, и остаток от деления на размер массива даёт номер ящика. Внутри ящика идёт поиск ключа, равного по equals: нашли - заменили значение, не нашли - добавили узел. Чтение идёт тем же маршрутом.

Разные ключи иногда попадают в один ящик - это коллизия, и она законна. Узлы складываются в цепочку. С Java 8 длинная цепочка (от восьми узлов при размере массива от 64) перестраивается в красно-чёрное дерево, чтобы худший случай остался логарифмическим.

// Насколько это спасает, зависит от ключа. Я мерил на 20 000 ключах с одинаковым хешем: если ключ реализует Comparable, 20 000 поисков занимают 20,3 мс, если нет - 1609 мс. Дереву нужен порядок, иначе оно вырождается.

ящик: ячейка массива с цепочкой или деревом узлов
превращение в дерево: цепочка от 8 узлов становится красно-чёрным деревом

Расширение и политика null

Когда записей становится больше, чем размер массива умножить на коэффициент заполнения (по умолчанию 0,75), массив удваивается и ВСЕ записи раскладываются заново. Это заметно: два миллиона вставок в мапу с нуля заняли у меня 459 мс, а в мапу с заранее заданной ёмкостью - 245 мс. Почти вдвое, и это на ровном месте.

Про null. HashMap принимает один null-ключ и любое число null-значений, я проверил - работает. Отсюда неоднозначность: get вернул null, и это может значить «ключа нет» или «лежит null». Различает только containsKey, у меня он честно вернул true для ключа со значением null и false для отсутствующего.

// ConcurrentHashMap null не принимает вовсе - и ключ, и значение дают NullPointerException. Причина не в придирчивости: в конкурентной мапе неоднозначность «нет ключа или лежит null» неразрешима атомарно.

// Порядок обхода HashMap не определён. Я положил пять ключей, посмотрел порядок, добавил ещё двадцать - и те же пять вышли в другом порядке. Код, завязанный на «как обычно обходится», это бомба замедленного действия.

коэффициент заполнения: порог 0,75, после которого массив удваивается
containsKey: единственный способ отличить null-значение от отсутствия

Многопоточность: почему теряются записи

Замер из начала темы объясняется просто. Два потока читают один и тот же ящик, оба видят его старое состояние, оба записывают свой узел - и один затирает другого. Плюс расширение массива, которое в старых версиях умудрялось зациклить чтение навсегда. «Пока работает» держится до первой настоящей нагрузки.

ConcurrentHashMap решает это блокировками на уровне отдельных ящиков и атомарными операциями сравнения с обменом, а чтение идёт вообще без блокировок. В моём замере она не потеряла ни одной записи из двухсот тысяч.

Но потокобезопасность операций не равна атомарности их связок. Последовательность «проверил get, потом сделал put» - это гонка даже в ConcurrentHashMap: между двумя вызовами кто угодно успеет вклиниться. Для таких случаев есть атомарные putIfAbsent, merge и compute.

// Идиома, которую держат наизусть: map.computeIfAbsent(key, k -> new ArrayList<>()).add(x). Это мультимапа одной строкой, и в конкурентной версии она атомарна. Я проверил - два вызова подряд дают {a=[1, 2]}.

map.computeIfAbsent(key, k -> new ArrayList<>()).add(x);
// вместо: if (!map.containsKey(key)) map.put(key, new ArrayList<>());

ConcurrentHashMap: блокировки на уровне ящиков, чтение без блокировок
computeIfAbsent: атомарное «вычисли и положи, если нет»

Как отвечать: «Что происходит при put в HashMap?»

Берётся hashCode ключа, к нему подмешиваются старшие биты, и остаток от деления на размер массива даёт номер ящика. Если ящик пуст - кладётся новый узел. Если нет - идём по цепочке и ищем ключ, равный по equals: нашли - заменяем значение, не нашли - добавляем узел в конец. Цепочка от восьми узлов при размере массива от 64 перестраивается в красно-чёрное дерево, чтобы худший случай остался логарифмическим. Если после вставки записей стало больше, чем размер на коэффициент заполнения 0,75, массив удваивается и все записи раскладываются заново - это дорого, я мерил, два миллиона вставок с заранее заданной ёмкостью укладываются вдвое быстрее. Отсюда три практических вывода. Ключам нужны согласованные equals и hashCode. Ключи должны быть неизменяемыми, иначе запись теряется. И из нескольких потоков обычная HashMap не годится: я запускал четыре потока по 50 тысяч записей и стабильно недосчитывался тысяч - там нужна ConcurrentHashMap.

Сильный ответ: маршрут пройден целиком, от вычисления хеша через цепочку и дерево к расширению, с точными порогами, а в конце - мост в практику. Числа про потерянные записи и про экономию на предзаданной ёмкости показывают, что человек это проверял.

На чём валят

−Кладут в мапу изменяемый ключ. Правка поля после put теряет запись для чтения, а память она занимать продолжает.
−Читают get равный null как «ключа нет». Может лежать null-значение, различает только containsKey.
−Говорят «HashMap из нескольких потоков вроде работает». У меня четыре потока теряли по полтысячи записей из двухсот тысяч, а в худшем прогоне больше двадцати тысяч.
−Пишут проверку и вставку двумя вызовами в ConcurrentHashMap. Это гонка, атомарны только putIfAbsent, merge и compute.
−Полагаются на порядок обхода HashMap. Он меняется после расширения и между версиями.

Проверьте себя

Пять вопросов из банка по этой подтеме. Всего их 21, остальные разбираются в тренажёре.

#map_internals1 / 5
Что HashMap делает с длинным бакетом при большом числе коллизий (Java 8+)?
A)Сразу выбрасывает самые старые пары из бакета, удерживая его длину в пределах восьми элементов
B)Превращает список бакета в дерево при ≥8 узлах и таблице ≥64
C)Немедленно увеличивает load factor до 1.0, отключая дальнейшие расширения таблицы ради экономии
D)Ничего особенного не делает: бакет остаётся связным списком, и поиск в нём деградирует до O(n)
показать ответ и разбор
+B)Превращает список бакета в дерево при ≥8 узлах и таблице ≥64
// разбор: До Java 8 бакет был связным списком, и при массе коллизий поиск в нём деградировал до O(n). С Java 8, если в одном бакете накапливается ≥8 узлов И размер таблицы ≥64, список превращается в красно-чёрное дерево — поиск внутри бакета становится O(log n). При уменьшении (<6) дерево снова сворачивается в список. Это защита от атак/патологий на коллизиях.
#map_internals2 / 5
Что задаёт load factor (0.75) в HashMap?
A)Максимальное число элементов, которое HashMap вообще способен хранить, после чего он бросает исключение
B)Долю бакетов, которые остаются пустыми и не используются под данные
C)Порог заполненности, при котором таблица расширяется (resize)
D)Скорость, с которой старые записи автоматически удаляются из карты по мере добавления новых пар
показать ответ и разбор
+C)Порог заполненности, при котором таблица расширяется (resize)
// разбор: load factor — порог: когда число записей превышает capacity × 0.75, таблица удваивается и все элементы перераспределяются (rehash) — дорогая O(n) операция, но редкая. Значение 0.75 — компромисс между расходом памяти и вероятностью коллизий. Зная примерный размер заранее, задают начальную ёмкость, чтобы избежать многократных resize.
#map_internals3 / 5
Чем HashMap отличается от ConcurrentHashMap и Hashtable по потокобезопасности и null?
A)Все три потокобезопасны из коробки, а разница лишь в скорости хеширования ключей внутри
B)HashMap потокобезопасен через синхронизацию каждого метода, а ConcurrentHashMap — нет, он для одного потока
C)Hashtable — самый современный и быстрый вариант, его и рекомендуют вместо HashMap в новых проектах
D)HashMap — не потокобезопасен и допускает null-ключ; ConcurrentHashMap — потокобезопасен, без null
показать ответ и разбор
+D)HashMap — не потокобезопасен и допускает null-ключ; ConcurrentHashMap — потокобезопасен, без null
// разбор: HashMap не синхронизирован (быстрый, для одного потока), допускает один null-ключ и null-значения. Hashtable — старый, синхронизирует каждый метод глобальным замком (медленно), null запрещает. ConcurrentHashMap — современный потокобезопасный вариант с тонкой блокировкой (по бакетам/CAS), тоже без null (чтобы get==null однозначно значил «нет ключа»). В конкуренции берут ConcurrentHashMap, не Hashtable.
#map_internals4 / 5
Когда стоит взять TreeMap вместо HashMap?
A)Когда нужен отсортированный обход ключей или запросы по диапазону
B)Когда важнее всего скорость: TreeMap даёт строго O(1) на get, тогда как HashMap работает за O(log n)
C)Когда ключи могут быть null: TreeMap хранит null-ключи, а HashMap их принципиально не поддерживает
D)Когда карта очень большая: TreeMap тратит меньше памяти, потому что не резервирует запасные бакеты
показать ответ и разбор
+A)Когда нужен отсортированный обход ключей или запросы по диапазону
// разбор: TreeMap хранит ключи в красно-чёрном дереве отсортированными (по Comparable/Comparator), давая O(log n) на операции и навигацию по порядку: subMap/headMap/tailMap, firstKey/lastKey, ceiling/floor. HashMap быстрее (амортизированное O(1)), но порядка не держит. Берут TreeMap именно когда нужен порядок или диапазонные запросы, миксом — LinkedHashMap для порядка вставки.
#map_internals5 / 5
Что делает computeIfAbsent(key, k -> new ArrayList<>()) у Map?
A)Пересоздаёт значение заново и перезаписывает старое, даже если по ключу уже что-то лежало
B)Возвращает значение по ключу, а если его нет — создаёт, кладёт и возвращает
C)Возвращает значение, только если ключ отсутствует, иначе бросает исключение о повторной вставке
D)Проверяет наличие ключа, но само значение не сохраняет — его нужно затем положить отдельным put
показать ответ и разбор
+B)Возвращает значение по ключу, а если его нет — создаёт, кладёт и возвращает
// разбор: computeIfAbsent атомарно (для ConcurrentHashMap) решает частый паттерн «мультикарты»: если ключа нет — вычисляет значение переданной функцией, кладёт его и возвращает; если есть — возвращает существующее, функцию не вызывая. Убирает шаблон get→проверка на null→put. Пара к нему — getOrDefault (вернуть дефолт без вставки) и merge (для агрегаций).

дальше

Теорию прочитали. Навык ставится повторением

В Сеньорчике эта подтема идёт в ежедневных сессиях: движок возвращает её, пока ответы не станут уверенными, и ведёт прогресс отдельно по каждой подтеме. Теория внутри тоже бесплатна, лимит только на количество вопросов в день.

Открыть тренажёр Вся тема: Коллекции Java