От чего зависит сложность полной итерации по HashMap, если число записей невелико относительно ёмкости таблицы?
Полная итерация по HashMap зависит не только от числа записей, но и от текущей ёмкости внутренней таблицы: её сложность — O(capacity + size). Итератор последовательно проверяет все бакеты, включая пустые, поэтому чрезмерно большая ёмкость замедляет обход даже при неизменном количестве элементов.
Хеш-таблицы создавались для быстрого доступа к элементу по ключу: хеш ключа указывает на бакет, где находится запись. Чтобы сохранить близкое к постоянному время поиска, таблица резервирует свободное пространство и расширяется при росте заполненности.
Эта оптимизация выгодна для операций поиска и вставки, но создаёт компромисс для итерации. Обход должен проверить всю таблицу бакетов, а не только занятые позиции.
Представим карту с несколькими сотнями записей и очень большой заранее заданной ёмкостью. Поиск отдельного ключа может оставаться быстрым, но полный обход карты будет проверять множество пустых бакетов.
Это особенно заметно в задачах сериализации, построения отчётов и периодического сканирования кэшей. Ошибка возникает, когда ёмкость выбирают с большим запасом для редких пиков роста, а затем ожидают, что итерация будет зависеть только от фактического числа записей.
Внутри HashMap есть массив бакетов. Каждый бакет может быть пустым либо содержать одну или несколько записей; при большом числе коллизий в современных реализациях цепочка записей может преобразовываться в дерево.
Итератор проходит массив бакетов от начала до конца. Для пустого бакета он не возвращает элемент, но сам факт проверки занимает время. Для занятого бакета дополнительно обходятся находящиеся в нём записи, поэтому суммарная оценка выражается как O(capacity + size).
Размер — количество записей, а ёмкость — длина внутреннего массива бакетов. Удаление элементов обычно уменьшает размер, но не обязано автоматически уменьшать ёмкость таблицы. Публичный контракт HashMap не предоставляет операции «сжать текущую таблицу».
Практический вывод: не следует без причины задавать огромную начальную ёмкость. Её выбирают с учётом ожидаемого размера, допустимого коэффициента загрузки и стоимости возможных расширений. Точная внутренняя стратегия расширения относится к реализации, поэтому полагаться на детали конкретной версии JDK как на общий API-контракт не следует.
Сервис хранит несколько тысяч временных объектов в карте, но при запуске резервирует ёмкость, рассчитанную на десятки миллионов записей. Операции поиска работают приемлемо, однако каждый периодический обход карты начинает потреблять заметное процессорное время.
Рассматривались два варианта. Первый — оставить большую ёмкость: он снижает вероятность расширений при пиковом росте, но сохраняет дорогую итерацию и расход памяти. Второй — создавать новую карту подходящего размера и переносить записи: это уменьшает стоимость последующих обходов, но требует временной дополнительной памяти, пересчёта размещения записей и кратковременной работы по копированию.
Был выбран второй вариант для завершённых циклов накопления, поскольку карта редко достигает пикового размера, а полные обходы выполняются часто. Если бы требовался порядок вставки и преимущественно обход всех записей, альтернативой мог бы стать LinkedHashMap: он обычно обходит элементы за время, зависящее от размера, но требует дополнительной памяти для связей и меняет семантику порядка итерации.
get?Ожидаемая сложность поиска в HashMap обычно близка к O(1) при корректных hashCode, equals и приемлемом распределении хешей. Большое количество пустых бакетов напрямую не заставляет get просматривать их все: хеш вычисляется и используется для перехода к одному предполагаемому бакету. Однако чрезмерная ёмкость увеличивает потребление памяти и может ухудшать локальность доступа к данным.
Обычное удаление уменьшает число записей, но не обязано уменьшать внутренний массив бакетов. Поэтому карта может остаться большой и продолжать иметь стоимость полной итерации, связанную с прежней ёмкостью. Если нужно действительно уменьшить таблицу, обычно создают новую карту подходящего размера и переносят в неё актуальные записи, учитывая стоимость копирования и изменение ссылочной идентичности объекта карты.
LinkedHashMap хранит дополнительные связи между записями и может проходить элементы по этой связной структуре, поэтому стоимость итерации обычно пропорциональна числу записей, а не полной ёмкости хеш-таблицы. Компромисс — дополнительные ссылки, большее потребление памяти и наличие определённого порядка итерации, которого HashMap не обещает. Выбор оправдан, если обходы часты, карта может быть разреженной, а затраты памяти и порядок элементов приемлемы.