Java Concurrent Collections

Java Concurrent Collections high concurrency java.util.concurrent

Коллекция	Структура данных	Синхронизация	Свойства
🗺️ Map impl ConcurrentMap / ConcurrentNavigableMap
ConcurrentHashMap	Node<K,V>[] table (buckets) 📘 как в HashMap	Blocking lock‑stripping на бакеты CAS	weakly consistent Замена Hashtable
ConcurrentSkipListMap	Skip list из нод (головные узлы, башни)	Lock‑free CAS	weakly consistent sorted
🧩 Set impl NavigableSet / Set
ConcurrentSkipListSet	ConcurrentSkipListMap	Lock‑free CAS	weakly consistent sorted
CopyOnWriteArraySet	CopyOnWriteArrayList	Blocking (writes) copy on write	only reads high concurrency snapshot iterator Хорош для маленьких наборов
📋 List impl List
CopyOnWriteArrayList	Object[] array 📘 как в ArrayList	Blocking (writes) copy on write	only reads high concurrency snapshot iterator Хорош для маленьких наборов
⏳ Queue / Deque (non‑blocking) impl Queue / Deque
ConcurrentLinkedQueue	Linked nodes (Michael‑Scott queue) 📘 как в LinkedList (FIFO)	Lock‑free CAS (M&S algorithm)	weakly consistent unbounded Высокая пропускная способность
ConcurrentLinkedDeque	Linked nodes (double‑ended) 📘 как в LinkedList (LIFO и FIFO)	Lock‑free CAS	weakly consistent
🔒 BlockingQueue (producer‑consumer) impl BlockingQueue
ArrayBlockingQueue	Circular array (fixed capacity) 📘 как в ArrayDeque, но с ограничением размера	Blocking ReentrantLock+ Condition	weakly consistent bounded fairness (no starvation) Подходит для небольших данных, где важно предсказуемое время работы. Часто используется в пулах потоков
LinkedBlockingQueue	Linked nodes (optionally bounded) 📘 как в LinkedList	Blocking Two ReentrantLocks(takeLock/putLock) + Condition	weakly consistent optionally‑bounded По умолчанию неограниченная. Производительней ArrayBlockingQueue. Часто используется в пулах потоков
PriorityBlockingQueue	Object[] queue (binary heap) 📘 как в PriorityQueue	Blocking ReentrantLock+ CASдля увеличения ёмкости массива (ожидающие — yield() в цикле)	weakly consistent priority (sorted) unbounded Итерация без гарантий порядка и актуальности
SynchronousQueue Rendezvous (встреча) потоков. Потоки находятся в состоянии ожидания (LockSupport.park()) и каждый держит объект для передачи	TransferQueue/TransferStack. Хранят waiter (поток) и item (объект). 🎯 нет аналога — передача объекта «из рук в руки» между встретившимися потоками	Wait‑free CAS	Каждый put ждёт take. Часто используется в пулах потоков (e.g., CachedThreadPool)

CAS (Compare-And-Swap)атомарная процессорная операция, которая проверяет, совпадает ли текущее значение в памяти с ожидаемым, и если да, то заменяет его на новое. Другие потоки не будут заблокированы (что было бы дорого), а будут пытаться, пока не получится. Дешевая (но не бесплатная).

Lock‑strippingблокировка части коллекции (бакетов/узлов).

Weakly consistentитераторы не бросают ConcurrentModificationException, а отражают состояние на момент обхода с возможными параллельными изменениями.

Copy on writeзапись: 1) блокировка 2) копирование массива 3) изменение копии 4) установка ссылки на новый массив 5) разблокировка. Читатели не блокируются. Они видят либо старый массив, либо новый целиком, но никогда не промежуточное состояние. Записывать в 1 момент может только кто-то один.

Snapshot iteratorитератор работает с копией коллекции (создается для каждого итератора). Поэтому не вызывает ConcurrentModificationException.

Progress Guarantees в многопоточном программировании

	Имя	Проблема	Гарантия	Типичная реализация в JDK
	Blocking	Блокировка при зависании держателя, Deadlock, Livelock, Starvation	Никаких	Мониторы (`synchronized`, `ReentrantLock`)
Non‑blocking	Obstruction‑Free	Livelock	Любой поток гарантированно завершит свою операцию за конечное число шагов, если он останется один (остальные приостановлены)	Почти нет в JDK
	Lock‑free	Starvation	Хотя бы один поток в системе продвигается	CAS
	Wait‑free	Никаких	Каждый поток завершит операцию за конечное число шагов	Сложная. Потоки могут помогать друг другу. Пример: `SynchronousQueue`

Как это соотносится с нашими коллекциями? Гарантия, указанная для коллекции в блоке «Синхронизация», будет осуществима, если все потоки будут работать только с этой коллекцией (и больше ни с какими другими многопоточными сущностями).