В практической задаче коллекция постепенно растёт. Как объяснить амортизированную сложность вызовов put, несмотря на редкое расширение внутренней таблицы?
import java.util.HashMap;
import java.util.Map;
Map<Integer, String> data = new HashMap<>(4);
for (int i = 0; i < 1_000_000; i++) {
data.put(i, "value");
}
Для последовательности вставок в обычный HashMap средняя амортизированная сложность put составляет O(1). Отдельное расширение таблицы может стоить O(n), потому что элементы перераспределяются по новой таблице, но такие операции происходят редко, поэтому их стоимость распределяется между большим числом дешёвых вставок.
Хеш-таблица должна сохранять быстрый доступ, но фиксированный размер приводит к росту числа коллизий по мере добавления элементов. Увеличение таблицы позволяет поддерживать разумную загрузку и не допускать систематического ухудшения обычных операций.
Идея амортизированного анализа возникла как способ оценивать не стоимость одного редкого события, а суммарную стоимость длинной последовательности операций. Для динамических структур это важнее оценки отдельного расширения.
Внутри HashMap элементы распределяются по бакетам таблицы на основе хеша ключа. Когда число элементов достигает порога, связанного с ёмкостью таблицы и коэффициентом загрузки, таблица расширяется.
При расширении нужно создать массив большего размера и заново определить положение существующих записей. Поэтому конкретный вызов put может внезапно занять время, пропорциональное текущему числу элементов, хотя большинство вставок выполняется за постоянное ожидаемое время.
Пусть перед расширением в таблице находится n элементов. Расширение требует обработать эти элементы, поэтому его стоимость можно оценить как O(n). Однако между расширениями происходит примерно пропорциональное числу элементов количество обычных вставок.
Если таблица увеличивается примерно вдвое, суммарная стоимость перераспределений за n вставок образует геометрическую сумму: 1 + 2 + 4 + ... + n, то есть O(n). Деление этой суммарной стоимости на n операций даёт амортизированную стоимость O(1) на вставку.
Коэффициент загрузки задаёт компромисс. Меньшая загрузка уменьшает вероятность коллизий и обычно ускоряет операции, но требует больше памяти и более ранних расширений. Большая загрузка экономит память, однако может увеличить число коллизий и фактическое время работы.
У стандартного HashMap коэффициент загрузки по умолчанию равен 0,75. Конкретная вставка всё равно может быть дороже из-за коллизии, пользовательского hashCode() или расширения; амортизированная оценка не означает гарантированное время для каждого вызова.
Если ключи имеют патологически плохое распределение хешей, средняя оценка может перестать описывать ситуацию. В современных реализациях Java длинные цепочки коллизий при выполнении условий реализации могут преобразовываться в сбалансированные деревья, но это не отменяет требований к корректным equals() и hashCode().
Пример из вопроса создаёт карту с малой начальной ёмкостью, поэтому она будет многократно расширяться. Итоговая асимптотика последовательности вставок остаётся амортизированно O(n), но заранее заданная подходящая начальная ёмкость может уменьшить число перераспределений и временные пики.
Сервис загружает около пяти миллионов идентификаторов в HashMap, после чего выполняет только поиск. Вариант с конструктором без параметров прост, но вызывает серию расширений во время загрузки: растут паузы, число обращений к памяти и объём временной работы сборщика мусора.
Можно выбрать слишком большую начальную ёмкость. Это уменьшит число расширений, но увеличит расход памяти и может ухудшить локальность доступа. Можно оставить стандартную настройку, однако стоимость расширений будет оплачена в критической фазе загрузки.
Практичное решение — оценить ожидаемое число элементов и передать начальную ёмкость с запасом, учитывая коэффициент загрузки, например ceil(ожидаемое_число / 0.75). Реализация округлит внутреннюю ёмкость согласно своим правилам, а карта будет реже расширяться; результатом станут более предсказуемое время загрузки и меньшие временные пики при допустимом расходе памяти.
put выполняется за O(1)?Нет. Амортизированная оценка относится к суммарной стоимости последовательности операций. Отдельная вставка во время расширения может иметь стоимость O(n), а коллизия или вычисление пользовательского хеша также способны увеличить стоимость конкретного вызова.
При геометрическом росте размеры перераспределяемых таблиц образуют последовательность вроде 1, 2, 4, 8. Сумма всех предыдущих размеров меньше следующего размера в постоянное число раз, поэтому за n вставок все расширения вместе требуют O(n) работы, а не O(n²).
Если она слишком мала, карта чаще расширяется и перераспределяет записи. Если она чрезмерно велика, сразу выделяется больше памяти, часть которой может не использоваться, а операции могут хуже использовать кэш процессора. Начальную ёмкость следует оценивать по ожидаемому числу элементов и коэффициенту загрузки, оставляя запас для роста, но не резервируя заведомо избыточный объём.