Как устроен 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.