Java Collections: шпаргалка, которую стоит сохранить

Нужен список
Быстрый доступ по индексу → ArrayList
get      O(1)
add      O(1)*
insert   O(n)
remove   O(n)
Выбор по умолчанию для обычного списка.

Часто работаешь с началом/концом → ArrayDeque
addFirst/addLast   O(1)*
pollFirst/pollLast O(1)*
Лучше, чем LinkedList, когда нужен стек или deque.

Нужен поиск по ключу
Быстрый поиск → HashMap
get    O(1)*
put    O(1)*
remove O(1)*
Главный выбор для key → value.

Нужен порядок добавления → LinkedHashMap
HashMap + порядок
Может использоваться для LRU Cache.

Нужна сортировка ключей → TreeMap
get    O(log n)
put    O(log n)
remove O(log n)
Когда нужны:
firstKey()
lastKey()
floorKey()
ceilingKey()

Нужна уникальность → HashSet
add      O(1)*
contains O(1)*
remove   O(1)*
Внутри основан на HashMap.

Уникальность + сортировка → TreeSet
add      O(log n)
contains O(log n)
remove   O(log n)

Есть:
first()
last()
floor()
ceiling()
 
Всегда нужен min/max элемент → PriorityQueue
peek  O(1)
poll  O(log n)
offer O(log n)
Внутри — heap.
Используем в задачах:
Top K
Kth Largest
Merge K Sorted Lists
 
Нужна очередь → ArrayDeque
Deque<Integer> queue = new ArrayDeque<>();
offer()
poll()
peek()
Отличный выбор для BFS.
 
Нужна структура для алгоритмов:
BFS → ArrayDeque
DFS → ArrayDeque
Top K → PriorityQueue
Подсчет частот → HashMap
Поиск уникальных → HashSet
Сортированный поиск → TreeSet / TreeMap
LRU Cache → LinkedHashMap
Несколько потоков работают с Map → ConcurrentHashMap
Но:
ConcurrentHashMap ≠ "теперь весь код потокобезопасный"
Потокобезопасность отдельных операций не гарантирует атомарность вашей бизнес-операции.
Например:
if (!map.containsKey(key)) {
    map.put(key, value);
}
Это уже не одна атомарная операция.
Для таких случаев нужно смотреть в сторону:
putIfAbsent()
computeIfAbsent()
merge()
 
Как выбирать коллекцию за 10 секунд
Нужен index?
    ↓
ArrayList
 
Нужен key → value?
    ↓
HashMap
 
Key → value + порядок?
    ↓
LinkedHashMap
 
Key → value + сортировка?
    ↓
TreeMap
 
Уникальность?
    ↓
HashSet
 
Уникальность + сортировка?
    ↓
TreeSet
 
Min / Max по приоритету?
    ↓
PriorityQueue
 
Stack / Queue / Deque?
    ↓
ArrayDeque
 
Concurrent Map?
    ↓
ConcurrentHashMap
И 5 ловушек, которые любят на собеседованиях
1. LinkedList не означает "быстрее вставка".
Если сначала нужно найти позицию — поиск уже O(n).
2. HashMap не гарантирует порядок.
Нужен порядок → LinkedHashMap.
3. TreeMap не просто "отсортированный HashMap".
Это другая структура данных с O(log n) вместо среднего O(1).
4. PriorityQueue не хранит элементы полностью отсортированными.
Она гарантирует быстрый доступ к приоритетному элементу.
5. ConcurrentHashMap не делает сложную последовательность операций атомарной.
Для этого существуют специальные атомарные методы.
 
* — средняя/амортизированная сложность для обычных условий.
И главное правило:
Сначала определите главную операцию, которую нужно выполнять быстро. Потом выбирайте коллекцию.
Не:
"Я всегда использую ArrayList."
А:
"Мне нужен быстрый доступ по индексу → поэтому ArrayList."