Под капотом ArrayList и HashMap: capacity, load factor и O(n)→O(1)
«HashMap даёт O(1)» и «ArrayList даёт O(1) по индексу» — фразы, которые многие повторяют на автомате. За ними стоят условия и граничные случаи, и если их не знать, можно получить O(n) там, где ждали O(1), и недоумевать, почему сервис тормозит под нагрузкой. Разберём две главные коллекции Java под капотом.
ArrayList: один массив на всё
Внутри ArrayList — это Object[] (массив ссылок на объекты) плюс счётчик size. Никаких узлов и ссылок, как в связном списке. Отсюда свойства:
O(1) по индексу. Обращение list.get(5) — это просто array[5], доступ к элементу массива по смещению. Мгновенно.
Амортизированное O(1) добавления в конец. list.add(x) кладёт элемент в array[size] и инкрементирует size. Но массив имеет фиксированную длину — capacity. Когда место заканчивается, ArrayList создаёт новый массив в 1.5 раза больше и копирует туда старые элементы через System.arraycopy.
Почему при этом add остаётся O(1) «в среднем»? Потому что копирование случается редко. Если добавили N элементов, суммарно было скопировано примерно N + N/1.5 + N/(1.5²) + ... — это геометрическая прогрессия, в сумме ~3N. Делим на N операций — получаем O(1) в среднем (amortized). Одна редкая операция дорогая, но размазанная по всем — дёшево.
O(n) вставки в середину. list.add(0, x) — это сдвиг всех N элементов вправо через тот же System.arraycopy. Дорого. Если часто вставляете в начало — нужен ArrayDeque или, в некоторых случаях, LinkedList (хотя последний тоже имеет свои подводные камни).
Capacity против size. size — сколько элементов фактически. capacity — длина внутреннего массива (всегда ≥ size). Если знаете примерный размер заранее, задайте его через new ArrayList<>(expectedSize) — это уберёт несколько ресайзов и копирований на старте:
// Часто видим так:
List<User> result = new ArrayList<>(); // capacity = 10
for (int i = 0; i < 10000; i++) result.add(load(i)); // ~14 ресайзов
// Лучше, если знаем порядок:
List<User> result = new ArrayList<>(10_000); // один аллокации, ноль ресайзов
HashMap: бакеты и хеши
Внутри HashMap — массив бакетов (buckets). Каждый бакет — начало цепочки элементов. Алгоритм поиска:
- Посчитать
hashCode()ключа. - По хешу определить индекс бакета:
index = (n - 1) & hash(n — длина массива, операция&вместо%работает только потому, что длина массива всегда степень двойки). - Пройти по цепочке в бакете, сравнивая ключи через
equals().
Когда цепочка короткая — это O(1): хеширование, поиск бакета, сравнение с парой элементов. Когда все элементы сваливаются в один бакет (коллизия) — цепочка растёт и поиск становится O(n).
Load factor и порог расширения. HashMap держит loadFactor (по умолчанию 0.75) и threshold = capacity * loadFactor. Когда size превышает threshold, массив бакетов удваивается (×2) и все элементы перераспределяются (rehash). Поэтому HashMap на самом деле резервирует больше памяти, чем содержит элементов — она держит массив «полупустым», чтобы цепочки оставались короткими.
Красно-чёрное дерево на коллизиях. Начиная с Java 8, если в бакете скопилось больше 8 элементов и ключи реализуют Comparable, цепочка превращается в сбалансированное красно-чёрное дерево. Поиск в нём — O(log n) вместо O(n). Это спасает от вырождения производительности при плохом hashCode() или при хеш-коллизионных атаках (когда злоумышленник намеренно создаёт ключи с одинаковым хешем, чтобы положить сервер). Обратное превращение в цепочку происходит, когда в бакете остаётся меньше 6 элементов.
Что ломает «O(1)»
Плохой hashCode. Если у класса-ключа все объекты возвращают один и тот же хеш — все элементы попадают в один бакет, и HashMap деградирует до O(n) (или O(log n) благодаря дереву). Самый грустный случай — hashCode всегда возвращает константу. Чуть лучше, но всё ещё плохо — хеш, зависящий только от части полей.
Свой equals, несовместимый с hashCode. Контракт: если a.equals(b), то обязательно a.hashCode() == b.hashCode(). Нарушение — и HashMap кладёт «равные» ключи в разные бакеты, найти ничего нельзя. IDE и record генерируют согласованную пару автоматически — одна из причин, почему records так удобны как ключи.
Мутация ключа после вставки. Если положили в мапу ключ, а потом изменили поле, участвующее в hashCode — хеш изменится, и HashMap больше не найдёт элемент по этому ключу. Он останется в бакете по старому хешу, но путь к нему потерян. Immutable-ключи (через record или final-класс) — это не красота, а защита от такого класса багов.
ConcurrentModificationException. Если итерироваться по коллекции и параллельно её модифицировать — вылетит исключение. Это fail-fast-поведение, придуманное, чтобы не молча отдавать повреждённые данные. Для конкурентного доступа есть ConcurrentHashMap (сегментированные блокировки, позже — CAS-операции на бакетах).
ConcurrentHashMap — короткое слово
Если несколько потоков пишут в один HashMap — undefined behaviour (пропавшие элементы, бесконечные циклы в дереве на старых версиях Java, повреждённая структура). ConcurrentHashMap решает это не через одну глобальную блокировку (как устаревший Hashtable), а через мелкогранулярные блокировки: раньше — по сегментам, сейчас — на уровне отдельного бакета (CAS-операции, synchronized только на первом элементе бакета при коллизии). Параллельная запись работает без глобальных пауз.
Практические следствия
| Когда | Что выбрать | Почему |
|---|---|---|
| Известен порядок размера | new ArrayList<>(size) | Без ресайзов |
| Частые вставки в начало/середину | ArrayDeque или пересмотр структуры | O(n) у ArrayList |
| Ключ — изменяемый объект | Сделать immutable (record) | Иначе ключ «потеряется» |
| Параллельная запись | ConcurrentHashMap | Не HashMap, не Hashtable |
| Большие объёмы с риском коллизий | Не пишите свой hashCode вслепую | Используйте record или генерацию IDE |
Короткое summary
ArrayList — это массив плюс амортизированный анализ: добавление в конец O(1) «в среднем», по индексу O(1) честно, вставка в середину O(n). HashMap — бакеты по хешу с порогом расширения (0.75) и деревом на длинных коллизиях (с Java 8). «O(1)» держится только при хорошем hashCode и immutable-ключах — иначе можно получить O(n). Мутация ключа и конкурентный доступ без ConcurrentHashMap — два самых частых способа наступить.
Что почитать
- OpenJDK source:
java.util.HashMap— код с комментариями про treeification и пороги. - Java Object hashCode() contract — Javadoc — оригинал контракта
equals/hashCode. - «Java Performance» (Scott Oaks) — про накладные расходы коллекций и выбор под workload.