Коллекции Java изнутри

Вопрос «как устроен HashMap» задают почти всегда, от junior до senior. Разница только в глубине: junior называет корзины и equals/hashCode, senior рассказывает про деревья в корзинах, resize и почему HashMap не для многопоточности.

Иерархия

• Collection: List (порядок, индексы, дубли), Set (без дублей), Queue/Deque (очереди).
• Map стоит отдельно: пары ключ-значение, не наследует Collection.

Задача	Брать
список с доступом по индексу	ArrayList
стек, очередь, дек	ArrayDeque
множество без порядка	HashSet
порядок вставки	LinkedHashSet / LinkedHashMap
отсортированные ключи, поиск ближайшего	TreeSet / TreeMap
приоритеты	PriorityQueue (двоичная куча)

ArrayList

Внутри массив Object[]. get(i) O(1), add в конец амортизированно O(1): когда массив заполнен, создаётся новый в 1.5 раза больше и старый копируется. Вставка и удаление в середине O(n) из-за сдвига. Если размер известен, задайте ёмкость: new ArrayList<>(n).

LinkedList двусвязный список: вставка по готовому узлу O(1), но get(i) O(n), а каждый узел это отдельный объект с двумя ссылками, кеш процессора страдает. На практике ArrayList или ArrayDeque почти всегда быстрее.

HashMap

Массив корзин (table), размер степень двойки, по умолчанию 16. Путь put(key, value):

1. hash = key.hashCode() ^ (h >>> 16): старшие биты подмешиваются к младшим.
2. Индекс корзины (n - 1) & hash.
3. Корзина пуста: кладём узел. Иначе идём по цепочке и ищем ключ через hash == и equals. Нашли: заменяем значение, нет: добавляем в конец.
4. В цепочке стало 8 узлов, и таблица не меньше 64: цепочка превращается в красно-чёрное дерево (поиск O(log n) вместо O(n)). Если таблица меньше 64, вместо этого она расширяется.
5. Размер превысил capacity * loadFactor (0.75): таблица удваивается, узлы раскладываются заново.

Ключ null допустим (один, в корзине 0). Порядок обхода не гарантирован и меняется после resize. HashMap не потокобезопасен: при параллельной записи теряются данные. Для потоков ConcurrentHashMap (он, кстати, не принимает null ни в ключах, ни в значениях).

HashSet это HashMap, где элементы хранятся как ключи, а значение одна общая заглушка.

TreeMap и LinkedHashMap

TreeMap красно-чёрное дерево: операции O(log n), ключи отсортированы по compareTo или Comparator, есть floorKey, ceilingKey, headMap, subMap. Равенство ключей определяет компаратор, а не equals.

LinkedHashMap хеш-таблица плюс двусвязный список узлов: обход в порядке вставки. С флагом accessOrder = true и переопределённым removeEldestEntry это готовый LRU-кеш.

Итераторы и изменение коллекции

Итераторы ArrayList, HashMap и других обычных коллекций fail-fast: если коллекцию структурно изменили не через итератор, следующий next() бросит ConcurrentModificationException. Удалять при обходе нужно через iterator.remove() или list.removeIf(...).

for (String s : list) {
    if (s.isEmpty()) list.remove(s);   // CME
}
list.removeIf(String::isEmpty);         // правильно

Неизменяемые коллекции

• List.of, Set.of, Map.of (Java 9): неизменяемые, не принимают null, Set.of и Map.of падают на дублях.
• Arrays.asList(arr): фиксированный размер, set можно, add/remove бросают UnsupportedOperationException, а изменения пишутся в исходный массив.
• Collections.unmodifiableList(list): обёртка-представление, изменения исходного списка через неё видны.
• Java 21 добавила SequencedCollection: getFirst(), getLast(), reversed() у списков, деков и LinkedHashSet.

Частые ошибки

• Удаление в foreach и ConcurrentModificationException.
• Изменяемый объект как ключ HashMap.
• LinkedList «потому что вставка O(1)».
• list.remove(1) на List<Integer>: удаляется элемент по индексу 1, а не значение 1.

Что спросят на собесе

• Как устроен HashMap: hash, корзины, коллизии, resize, деревья.
• Сложность операций ArrayList и LinkedList, что выбрать.
• Чем отличаются HashMap, LinkedHashMap и TreeMap.
• Что такое fail-fast итератор и как удалить элемент во время обхода.
• Как сделать LRU-кеш на стандартных коллекциях.