Как устроен HashMap в Java: вопросы собеседования

Как значение находит своё место

Ключ приходит в карту как объект, а корзину нужно выбрать числом — эту работу и делает hashCode. По числу выбирается корзина, а внутри корзины уже сравниваются ключи через equals. Отсюда следует то, что делает связку двух методов не формальностью, а условием работоспособности: hashCode решает, где искать, а equals — что именно нашли.

Из этого выводится самое неприятное последствие нарушенного контракта, и его стоит уметь показать на примере. Положили объект в карту, потом изменили у него поле, которое участвует в вычислении хеша, — и значение потерялось. Оно лежит в карте, оно не удалено, но искать его теперь будут в другой корзине. Тот же механизм объясняет, почему изменяемый объект — плохой ключ.

Коллизия — когда два разных ключа попадают в одну корзину — при этом не сбой, а нормальный режим. Гарантия javadoc сформулирована с оговоркой ровно про это: константное время get и put обещано при условии, что хеш-функция «должным образом рассеивает элементы по корзинам». Плохая хеш-функция никакого правила не нарушает — она просто съедает обещание производительности.

У этой оговорки есть предельный случай, на котором её смысл виден лучше всего: пусть hashCode всегда возвращает одно и то же число. Формально не сломается ничего — карта останется корректной, значения будут находиться. Но все ключи попадут в одну корзину, и поиск из константного превратится в перебор.

Что происходит при росте

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

Конструктор без аргументов создаёт карту с начальной ёмкостью 16 и коэффициентом загрузки 0.75. Ёмкость — это число корзин; коэффициент загрузки — мера того, насколько карте позволено заполниться, прежде чем ёмкость увеличится автоматически.

Дальше работает правило, которое стоит формулировать точно, потому что в пересказах оно часто съезжает: когда число записей превышает произведение коэффициента загрузки на текущую ёмкость, таблица перестраивается так, чтобы корзин стало примерно вдвое больше. Не «когда карта заполнилась», а именно при превышении произведения — то есть при 16 корзинах порог наступает на тринадцатой записи, а не на семнадцатой.

Почему именно 0.75 — тоже документировано, и это вопрос размена: «значение по умолчанию даёт хороший компромисс между временем и памятью», а более высокие значения уменьшают расход памяти, но увеличивают стоимость поиска. Полезное практическое следствие: если объём известен заранее, ёмкость лучше задать в конструкторе — перестройка большой карты не бесплатна.

Из перестроек следует ещё одно свойство, о котором спрашивают отдельно: порядок обхода не гарантирован и не обязан оставаться постоянным во времени. Это записано в документации прямо, и опираться на порядок нельзя даже в пределах одного запуска.

Где кончается контракт и начинается реализация

Разборы собеседований описывают превращение длинной корзины в дерево как часть ожидаемого ответа — не как экзотику, до которой доходят единицы. И здесь есть тонкость, которая делает ответ заметно сильнее: документация класса этого не описывает.

Javadoc HashMap говорит про ёмкость, коэффициент загрузки, перестройку и отсутствие гарантий порядка. Про то, что лежит внутри корзины, он не говорит ничего — только обещает константное время при хорошем рассеивании. Структура корзины остаётся деталью конкретной реализации, а не обязательством, на которое можно опереться.

Отсюда способ отвечать, который применим ко всем вопросам такого рода: назвать поведение, а следом — его статус. Не «внутри связный список, который превращается в дерево», а «документация обещает константное время при хорошем рассеивании; в реализации HotSpot длинная корзина перестраивается в дерево, но это деталь реализации, а не часть контракта». Второй ответ не длиннее первого и содержит на один уровень больше.

Практическая ценность различения не в педантичности. Контракт — это то, что переживёт смену версии; деталь реализации — то, что может измениться без предупреждения, и строить на ней логику программы нельзя.

Что именно ломается в двух потоках

Ответ «не потокобезопасна» закрывает вопрос только на словах: в разборах собеседований этот заход доходит до замены и её свойств, а не останавливается на факте. Начать стоит с формулировки документации, которая точнее привычной: карта должна синхронизироваться извне, если несколько потоков обращаются к ней одновременно и хотя бы один изменяет её структурно.

Термин «структурная модификация» документация определяет отдельно, и это различение стоит знать: структурная модификация — это добавление или удаление записей; замена значения у уже существующего ключа структурной модификацией не является.

Дальше — место, где привычное изложение расходится с первоисточником. ConcurrentModificationException часто подаётся как защитный механизм, который сообщит о проблеме. Javadoc говорит обратное, и почти дословно: гарантировать fail-fast невозможно, исключение бросается «на основе лучших усилий», и писать программу, корректность которой зависит от этого исключения, было бы неправильно — оно предназначено только для обнаружения ошибок.

ConcurrentHashMap решает задачу иначе и имеет свою цену, которую полезно назвать вместе с преимуществом:

• чтения не берут блокировку и не блокируются, а чтение отражает результат последнего завершённого обновления;
• итераторы слабо согласованы: они отражают состояние таблицы в некоторый момент и ConcurrentModificationException не бросают вовсе;
• у составных операций вроде putAll и clear конкурентное чтение может увидеть только часть изменений;
• size(), isEmpty() и containsValue() документация относит к методам, полезным, когда карта не изменяется конкурентно; иначе они годятся для мониторинга и оценки, но не для управления логикой;
• null не допускается ни как ключ, ни как значение — в отличие от HashMap.

И оговорка, без которой список читается неверно: конкурентная карта делает атомарной отдельную операцию, а не последовательность из двух. Пара «проверить и положить», написанная в два вызова, остаётся гонкой — для неё есть putIfAbsent и compute.