Collection API

• Set
• HashSet
• LinkedHashSet
• TreeSet
• List
• ArrayList
• LinkedList
• Vector
• Stack
• Queue
• PriorityQueue
• LinkedList (Queue)
• ArrayDeque (Queue)
• Deque
• ArrayDeque
• LinkedList (Deque)
• Map
• HashMap
• LinkedHashMap
• TreeMap
• Hashtable
• WeakHashMap
• Начальная ёмкость и сложность операций
• Iterator vs Enumeration
• fail-fast vs fail-safe

Термин	Описание
Collection	Объект-контейнер, хранящий набор элементов
Collections	Утилитный класс (java.util.Collections) со статическими методами: sort, shuffle, min, max, reverse и др.
java.util.Collection	Корневой интерфейс Java Collections Framework

Set

Set — коллекция без дубликатов. Порядок зависит от реализации.

Set (интерфейс)
 ├── HashSet        — неупорядоченный, O(1) операции
 ├── LinkedHashSet  — порядок добавления, O(1)
 └── TreeSet        — отсортированный, O(log n)

HashSet

• Хранит элементы с помощью HashMap внутри (ключ — элемент, значение — Object)
• Не гарантирует порядок
• Допускает null
• Операции add, remove, contains — O(1)

LinkedHashSet

• Расширяет HashSet
• Сохраняет порядок добавления элементов (двусвязный список внутри)
• Операции — O(1)

TreeSet

• Реализует SortedSet / NavigableSet
• Хранит элементы в отсортированном порядке (по возрастанию)
• Основан на красно-чёрном дереве (Red-Black Tree)
• Операции add, remove, contains — O(log n)
• Не допускает null
• Требует, чтобы элементы реализовывали Comparable или передать Comparator

---

Характеристика	HashSet	LinkedHashSet	TreeSet
Основа	HashMap	HashSet + связный список	Red-Black Tree
Порядок	❌	Порядок добавления	Сортировка
null	✅	✅	❌
add	O(1)	O(1)	O(log n)
remove	O(1)	O(1)	O(log n)
contains	O(1)	O(1)	O(log n)
Когда использовать	Максимальная скорость без порядка	Нужен предсказуемый порядок	Нужны сортировка и range-запросы

HashSet vs TreeSet: если нужна сортировка — TreeSet; если нужна скорость — HashSet.

List

List — упорядоченная коллекция, допускает дубликаты. Элементы доступны по индексу.

List (интерфейс)
 ├── ArrayList   — динамический массив, O(1) get
 ├── LinkedList  — двусвязный список, O(1) add/remove на концах
 └── Vector      — устаревший; synchronized ArrayList
       └── Stack — LIFO (устаревший; используй Deque)

ArrayList

• Внутри — динамический массив объектов
• При переполнении создаётся массив в 1.5 раза больше, старые элементы копируются
• Начальная ёмкость по умолчанию — 10

Операция	Сложность	Комментарий
get(i)	O(1)	Прямой доступ по индексу
add (конец)	O(1) амортизированно	Иногда O(n) при расширении
add(i, e)	O(n)	Сдвиг элементов
remove(i)	O(n)	Сдвиг элементов
contains	O(n)	Линейный поиск
size	O(1)

LinkedList

• Внутри — двусвязный список
• Реализует и List, и Deque
• Нет прямого доступа по индексу — итерация до нужного элемента

Операция	Сложность	Комментарий
get(i)	O(n)	Обход с начала или конца
add (конец/начало)	O(1)
add(i, e)	O(n)	Поиск позиции
remove (первый/последний)	O(1)
remove(i)	O(n)	Поиск позиции

Vector

• Устаревшая реализация списка на базе динамического массива
• Почти то же, что ArrayList, но методы synchronized
• Обычно проигрывает ArrayList по производительности из-за лишней синхронизации

Stack

• Устаревший класс для модели LIFO
• Наследуется от Vector
• Методы: push, pop, peek
• В современном коде вместо него предпочтительнее Deque / ArrayDeque

---

Характеристика	ArrayList	LinkedList	Vector	Stack
Основа	Динамический массив	Двусвязный список	Синхронизированный массив	Vector + LIFO API
get(i)	O(1)	O(n)	O(1)	O(1)
Добавление	O(1)* в конец	O(1) на концах, O(n) по индексу	O(1)* в конец	push: O(1)*
Удаление	O(n) по индексу	O(1) на концах, O(n) по индексу	O(n) по индексу	pop: O(1)*
contains	O(n)	O(n)	O(n)	O(n)
Потокобезопасность	❌	❌	✅	✅
Когда использовать	Частый доступ по индексу	Частые операции на концах	Почти никогда, только legacy	Почти никогда, лучше ArrayDeque

Queue

Queue — очередь по модели FIFO (First In First Out).

Queue (интерфейс)
 ├── PriorityQueue  — элементы извлекаются по приоритету
 ├── LinkedList     — обычная FIFO-очередь
 └── ArrayDeque     — быстрая очередь на массиве (через Deque)

PriorityQueue

• Основана на heap (по умолчанию min-heap)
• Элементы извлекаются не в порядке добавления, а по приоритету
• peek() возвращает минимальный элемент
• offer / poll — O(log n), peek — O(1)
• null не допускается

LinkedList (Queue)

• Может использоваться как обычная FIFO-очередь
• Добавление в хвост и удаление из головы — O(1)
• Хранит элементы в порядке вставки
• Допускает null

ArrayDeque (Queue)

• Основан на циклическом массиве
• Обычно быстрее LinkedList для очереди и стека
• Операции на концах — O(1)
• null не допускается

---

Характеристика	PriorityQueue	LinkedList	ArrayDeque
Основа	Heap	Двусвязный список	Циклический массив
Порядок извлечения	По приоритету	FIFO	FIFO
offer	O(log n)	O(1)	O(1)
poll	O(log n)	O(1)	O(1)
peek	O(1)	O(1)	O(1)
contains	O(n)	O(n)	O(n)
null	❌	✅	❌
Когда использовать	Нужен приоритет	Простая очередь и legacy API	Предпочтительный FIFO в памяти

Deque

Deque — двусторонняя очередь. Позволяет добавлять и удалять элементы с обоих концов и может работать и как Queue (FIFO), и как Stack (LIFO).

Deque (интерфейс)
 ├── ArrayDeque
 └── LinkedList

ArrayDeque

• Предпочтительная замена Stack
• Основан на циклическом массиве
• Быстрые операции на обоих концах: O(1)
• null не допускается

LinkedList (Deque)

• Реализует Deque через двусвязный список
• Операции на концах — O(1)
• По памяти тяжелее, чем ArrayDeque
• Допускает null

---

Характеристика	ArrayDeque	LinkedList
Основа	Циклический массив	Двусвязный список
addFirst / addLast	O(1)	O(1)
pollFirst / pollLast	O(1)	O(1)
peekFirst / peekLast	O(1)	O(1)
contains	O(n)	O(n)
null	❌	✅
Когда использовать	Стек и двусторонняя очередь по умолчанию	Нужен Deque и API списка одновременно

ArrayDeque vs Stack: ArrayDeque — предпочтительная замена Stack (быстрее, нет синхронизации) ArrayDeque vs LinkedList: ArrayDeque быстрее для большинства операций

Какая коллекция реализует FIFO? → LinkedList, ArrayDeque

Для хранения примитивного типа byte: - byte[] — обычный массив (8 бит / 1 байт на элемент) - ByteArrayOutputStream — для потока байт

Map

Map — структура «ключ → значение». Ключи уникальны.

Map (интерфейс)
 ├── HashMap        — неупорядоченный, O(1), допускает null
 │     └── LinkedHashMap  — порядок добавления/доступа
 ├── TreeMap        — отсортирован по ключу, O(log n)
 ├── Hashtable      — устаревший, synchronized, не допускает null
 └── WeakHashMap    — ключи — WeakReference

HashMap

• Самая популярная реализация Map
• Основан на массиве bucket'ов + цепочках / деревьях при коллизиях
• В среднем put, get, remove — O(1)
• Допускает один null-ключ и несколько null-значений

Структура HashMap

HashMap: массив bucket'ов (Node[])

index 0: [ Node(key1, val1) → Node(key5, val5) ]   ← коллизия: цепочка
index 1: [ Node(key2, val2) ]
index 2: null
index 3: [ Node(key3, val3) ]
...
index N: [ Node(key4, val4) ]

При длине цепочки ≥ 8 → цепочка превращается в Red-Black Tree (Java 8+)
При длине дерева ≤ 6 → обратно в цепочку

Как работает HashMap

1. Вычисляется hashCode() ключа
2. Хэш дополнительно перемешивается
3. По хэшу вычисляется индекс bucket'а
4. В bucket'е ищется совпадение по equals()
5. Если ключ найден, значение обновляется; иначе создаётся новый узел

Параметры HashMap

Параметр	Значение по умолчанию	Описание
initialCapacity	16	Начальное число bucket'ов
loadFactor	0.75	При заполнении > 75% — resize (×2)
threshold	capacity × loadFactor	Порог для расширения

При capacity=16 и loadFactor=0.75 → расширение при 12 элементах

Что важно помнить про HashMap

• Коллизия не ломает карту: элементы попадают в одну корзину
• Если equals() == true, значение по ключу обновляется
• При плохой хэш-функции производительность может деградировать
• С Java 8 длинные цепочки превращаются в дерево и работают быстрее

LinkedHashMap

• Наследуется от HashMap
• Сохраняет порядок вставки или порядок доступа (accessOrder=true)
• Подходит для реализации LRU-кэша через removeEldestEntry()
• Сложность операций в среднем остаётся O(1)

TreeMap

• Реализует SortedMap / NavigableMap
• Основан на Red-Black Tree
• Хранит элементы отсортированными по ключу
• get, put, remove — O(log n)
• null-ключи не допускаются

Hashtable

• Устаревшая синхронизированная реализация Map
• Не допускает ни null-ключи, ни null-значения
• В современном коде обычно заменяется на ConcurrentHashMap или Collections.synchronizedMap(...)

WeakHashMap

• Хранит ключи как WeakReference
• Если на ключ больше нет strong-ссылок, запись может быть удалена сборщиком мусора
• Удобен для кэшей и метаданных, жизненный цикл которых должен следовать за ключом
• Допускает null-ключ и null-значения

---

Характеристика	HashMap	LinkedHashMap	TreeMap	Hashtable	WeakHashMap
Основа	Хэш-таблица	HashMap + связный список	Red-Black Tree	Хэш-таблица	Хэш-таблица + weak keys
Порядок	❌	Порядок вставки / доступа	Сортировка по ключу	❌	❌
null ключ	✅ (один)	✅	❌	❌	✅
null значения	✅	✅	✅	❌	✅
get / put	O(1)	O(1)	O(log n)	O(1)	O(1)
remove	O(1)	O(1)	O(log n)	O(1)	O(1)
Потокобезопасность	❌	❌	❌	✅	❌
Когда использовать	Общий случай	Нужен предсказуемый порядок или LRU	Нужны сортировка и range-запросы	Legacy synchronized map	Кэш с автоочисткой по GC

---

Начальная ёмкость и сложность операций

Начальная ёмкость по умолчанию

Коллекция	Начальная ёмкость
ArrayList	10
HashMap	16
HashSet	16
LinkedList	— (узлы создаются динамически)
ArrayDeque	16
PriorityQueue	11
Hashtable	11
StringBuilder	16

Сводная таблица сложностей

Коллекция	get	add	remove	contains	Порядок
ArrayList	O(1)	O(1)*	O(n)	O(n)	Индекс
LinkedList	O(n)	O(1)	O(1)**	O(n)	Порядок вставки
HashSet	—	O(1)	O(1)	O(1)	❌
LinkedHashSet	—	O(1)	O(1)	O(1)	Порядок вставки
TreeSet	—	O(log n)	O(log n)	O(log n)	Сортировка
HashMap	O(1)	O(1)	O(1)	O(1)	❌
LinkedHashMap	O(1)	O(1)	O(1)	O(1)	Порядок вставки
TreeMap	O(log n)	O(log n)	O(log n)	O(log n)	По ключу
PriorityQueue	O(1) peek	O(log n)	O(log n)	O(n)	По приоритету
ArrayDeque	O(1) peek	O(1)	O(1)	O(n)	Порядок вставки

• * — амортизированно (иногда O(n) при расширении)
• ** — O(1) если есть ссылка на узел; O(n) при поиске по значению

---

Iterator vs Enumeration

	Iterator	Enumeration
Методы	hasNext(), next(), remove()	hasMoreElements(), nextElement()
Удаление	✅ remove()	❌
Применение	Все современные коллекции	Устаревшие (Vector, Hashtable)

• Iterable — интерфейс с методом iterator(); реализация позволяет использовать for-each
• Iterator — интерфейс для обхода коллекции
• for-each — синтаксический сахар над Iterator; нельзя удалять через цикл — используй iterator.remove()

fail-fast vs fail-safe

	fail-fast	fail-safe
Как работает	Бросает ConcurrentModificationException при изменении во время итерации	Работает на копии коллекции
Примеры	ArrayList, HashMap, HashSet	CopyOnWriteArrayList, ConcurrentHashMap