Понимаем многопоточность в Java через коллекции и атомики

1️⃣ HashMap / TreeMap / TreeSet (не потокобезопасные)

• Структура: массив бакетов + связные списки / деревья (для коллизий).
• Под капотом: при put/remove происходит модификация массива бакетов и, возможно, переупорядочивание цепочек.
• Проблема при многопоточности: два потока могут одновременно менять один бакет → corrupt структуры, потеря элементов, бесконечный цикл при итерации.

• Структура: красно-черное дерево.
• При вставке/удалении поток изменяет несколько узлов дерева.
• Одновременные изменения → структура дерева может сломаться, get/put/rebalance могут выбросить ConcurrentModificationException или повредить балансировку.

✅ Вывод: нужна внешняя синхронизация, иначе карта/множество легко портится.

2️⃣ SynchronizedMap / SynchronizedSortedMap / SynchronizedSortedSet

Под капотом: Все методы обёрнуты в synchronized (this) на объекте карты/сета. Любая операция блокирует всю карту/сет на время выполнения. Гарантирует целостность данных, но нет параллельной работы.

public V put(K key, V value) {
    synchronized (this) {
        return m.put(key, value);
    }
}

Чтение/запись → одна операция одновременно, что исключает race condition.

3️⃣ ConcurrentHashMap

Под капотом (Java 8+):

• Массив бакетов + узлы в деревьях для коллизий.
• Основная синхронизация:
  • get — полностью без блокировок.
  • put — CAS (Compare-And-Swap) на уровне бакета или synchronized на узле дерева, только если нужно.
  • Расширение таблицы (resize) частично синхронизировано на сегментах.
• Одновременные put/get на разные ключи — выполняются параллельно без блокировки всей карты.
• Race condition на значении: если это изменяемый объект внутри карты, CHM не синхронизирует его поля.

4️⃣ ConcurrentSkipListMap / ConcurrentSkipListSet

• Структура: Skip List (многослойный связный список).
• Операции используют lock-free алгоритмы + CAS.
• Каждый уровень списка частично блокируется или обновляется атомарно.
• Позволяет параллельные операции на разных ключах.
• Одновременные изменения одного ключа → race condition, если не использовать атомарные методы (compute, putIfAbsent).

5️⃣ AtomicInteger / AtomicReference / AtomicLong

• Используют CPU-инструкции CAS (Compare-And-Swap).
• Обновление атомарное и lock-free: одно и то же значение не потеряется при одновременных потоках.
• Пример:

  AtomicInteger ai = new AtomicInteger(0);
  ai.incrementAndGet(); // атомарно

• Без блокировок на уровне JVM или объекта — чистый CAS на CPU.

Collections.synchronizedSortedMap(new TreeMap<>())
Поток A: ─────[взял монитор]─────────────> работает
Поток B: ─────[ждёт, монитор занят]─────┐
Поток C: ─────[ждёт, монитор занят]─────┘

Level 3: 10 --------- 30 ---------------- 75 --------- 90
Level 2: 10 ---- 25 ---- 50 ---- 60 ---- 75 ---- 90
Level 1: 10  20  25  30  40  50  60  70  75  80  90

Поток A: вставляет 35
Поток B: вставляет 55
Поток C: читает 30

✔ Все три операции могут выполняться одновременно, потому что блокировки берутся только на маленькие сегменты списка.
✔ Порядок ключей сохраняется, субмапы работают.