Многопоточность и коллекции JVM

Процесс представляет собой запущенную программу со своей памятью; потоки работают внутри процесса, делят его кучу, и у каждого есть свой стек. Поток JVM всегда находится в одном из шести состояний: NEW, RUNNABLE, BLOCKED, WAITING, TIMED_WAITING или TERMINATED. На Android: каждое приложение работает в отдельном Linux-процессе, порождённом от Zygote, со своим рантаймом ART. Необработанное исключение в любом из его потоков убивает весь процесс. **NEW и TERMINATED**: поток создан, но не запущен, и поток завершился. start() срабатывает один раз; повторный вызов бросает IllegalThreadStateException. **RUNNABLE**: поток выполняется или готов выполняться. Поток внутри нативного кода или блокирующего чтения из сокета тоже показывает RUNNABLE. **BLOCKED**: поток ждёт входа в блок synchronized, который держит другой поток. **WAITING и TIMED_WAITING**: поток ждёт, пока другой поток что-то сделает, в wait(), join() или LockSupport.park(). Поток, ждущий ReentrantLock, припаркован, поэтому показывает WAITING, а не BLOCKED. С таймаутом (sleep, wait(ms), join(ms)) состояние будет TIMED_WAITING.

У каждого потока свой стек кадров вызовов с локальными переменными, параметрами и ссылками; все объекты лежат в одной куче, общей для всех потоков. Локальный Int принадлежит только своему потоку, а любой объект, до которого могут добраться два потока, становится общим и требует синхронизации. Стек: один на поток, по кадру на каждый вызов, освобождается при возврате. Его размер фиксируется при старте потока, поэтому бесконечная рекурсия заканчивается StackOverflowError. Куча: объекты, массивы и строки со всеми их полями, ею управляет GC. Примитивное поле живёт внутри своего объекта, а упакованный Int? тоже является объектом. Ссылки: val user в функции хранит ссылку в кадре, а сам User лежит в куче. Передав его другому потоку, вы делите объект, а не копию. Захват в Kotlin: локальный var, захваченный лямбдой, переносится в кучу внутри Ref.IntRef, поэтому лямбды, работающие на нескольких потоках, получают на нём гонку данных, как на обычном поле. Захваченный val просто копируется. На собеседованиях «Java memory model» может означать это устройство памяти или, строго говоря, правила видимости (happens-before), которые решают, когда один поток видит записи другого.

Через голый Thread, HandlerThread со своим Looper, ExecutorService плюс Handler главного потока или AsyncTask, который упаковывал эту пару. AsyncTask объявлен устаревшим в API 30: он приводил к утечкам Activity, терял результаты при повороте и вёл себя по-разному на разных версиях Android. **Thread: самый простой вариант, и им никто не владеет: нет отмены, нет пути обратно в UI. HandlerThread**: фоновый поток с Looper; Runnable, отправленные в его Handler, выполняются по одному, по порядку. **Executor плюс Handler(Looper.getMainLooper()): работа выполняется в пуле, результат отправляется в главный поток. Что было не так с AsyncTask**: написанный как inner-класс, он держал Activity, пока не закончится doInBackground. После поворота onPostExecute попадал в уничтоженную Activity или результат терялся. Меняющиеся правила выполнения: с Android 1.6 задачи шли параллельно, а с 3.0 снова последовательно. С тех пор все задачи приложения делят одну очередь, так что одна медленная задача тормозит все остальные. Сегодня: корутины в viewModelScope с withContext(Dispatchers.IO) и WorkManager для работы, которая должна пережить экран.

ArrayList устроен как растущий массив: get(i) за O(1), добавление в конец за амортизированное O(1), вставка или удаление в середине за O(n). LinkedList представляет собой цепочку узлов: O(1) на обоих концах, но O(n), чтобы дойти до индекса. На практике ArrayList всё равно выигрывает: один компактный массив хорошо ложится в кеш процессора. Рост: заполненный ArrayList выделяет массив в 1,5 раза больше и копирует в него элементы. Копирование редкое, поэтому добавление в среднем остаётся O(1); ArrayList(expectedSize) позволяет его избежать. **Середина ArrayList**: add(i, x) и removeAt(i) сдвигают хвост одним System.arraycopy, быстрым копированием памяти, так что O(n) остаётся дешёвым и для тысяч элементов. **O(1)-вставка в LinkedList условна**: она верна, только если ListIterator уже стоит в нужном месте. add(i, x) сначала проходит i узлов, и почти на каждом вероятен промах кеша. Память: каждый элемент LinkedList хранится в отдельном объекте-узле с заголовком и тремя ссылками, против одной ячейки-ссылки в массиве ArrayList, и это добавляет работы GC. Квадратичная ловушка: for (i in list.indices) list[i] на LinkedList проходит цепочку при каждом get, всего O(n²); итерируйтесь через for (x in list).

HashMap даёт поиск в среднем за O(1) без определённого порядка, LinkedHashMap вдобавок сохраняет порядок вставки, а TreeMap держит ключи отсортированными за O(log n) на операцию. Множества устроены так же. mapOf, mutableMapOf, setOf и mutableSetOf в Kotlin возвращают связанные версии. **HashMap, HashSet** (hashMapOf(), hashSetOf()): самые быстрые и экономные; порядок обхода следует раскладке по бакетам и может поменяться после ресайза. **LinkedHashMap, LinkedHashSet**: каждая запись ещё и связана с соседями (две лишние ссылки) ради стабильного порядка вставки. С accessOrder = true каждый get переносит запись в конец, и на этом строится LRU-кеш. **TreeMap, TreeSet** (sortedMapOf(), sortedSetOf(), toSortedMap()): красно-чёрное дерево, упорядоченное по compareTo или Comparator, с запросами по диапазону вроде ceilingKey и headMap. sortedMapOf типизирован как SortedMap, поэтому для методов навигации объявляйте TreeMap. Выбор: только поиск, HashMap; стабильный порядок для UI или JSON, LinkedHashMap; сортированный вывод или «следующий ключ после X», TreeMap.

HashMap хранит массив бакетов: hashCode ключа выбирает бакет, а equals находит запись внутри него. Ключи из одного бакета образуют связный список, который после 8 записей превращается в красно-чёрное дерево, а массив удваивается, когда мапа заполнена на 75%. Поиск ключа Индекс: hash = h xor (h ushr 16), затем hash and (capacity - 1). Ёмкость всегда равна степени двойки (по умолчанию 16); сдвиг подмешивает старшие биты в младшие, которые и выбирают бакет. Внутри бакета: сравнивается сохранённый хеш, затем ссылка, затем equals. У равных ключей должны быть равные хеш-коды, иначе поиск уйдёт в другой бакет. **null**: допускается один ключ null (хеш 0, бакет 0) и сколько угодно значений null; ConcurrentHashMap отвергает и то, и другое. Коллизии Записи одного бакета связаны в цепочку, поэтому поиск в нём стоит O(k) для k записей. Бакет, в котором стало больше 8 записей, превращается в красно-чёрное дерево с поиском за O(log k), но только если в таблице хотя бы 64 бакета; таблица поменьше вместо этого расширяется. Дерево, в котором осталось 6 записей или меньше, снова превращается в список. Ресайз Когда размер превышает capacity * loadFactor (12 для стандартных 16 и 0,75), массив удваивается и все записи переезжают: запись остаётся на индексе i или уходит на i плюс старая ёмкость, и решает это один бит её хеша. Ресайз стоит O(n), но случается редко, поэтому put остаётся амортизированным O(1).

Happens-before определяет в Java Memory Model, когда один поток обязан увидеть записи другого; без такого ребра JIT и процессор могут кешировать или переставлять их. synchronized даёт взаимоисключение и видимость, @Volatile видимость одного поля, AtomicInteger атомарное чтение-изменение-запись. Рёбра, на которые вы опираетесь: unlock happens-before следующего lock того же монитора; запись в volatile-поле happens-before последующих чтений этого поля; Thread.start() happens-before действий нового потока, а они happen-before возврата из join(). Рёбра транзитивны: всё, что записано до ребра, видно после него. **synchronized(lock) { }** или @Synchronized: внутри только один поток за раз, и следующий поток, захвативший тот же объект, видит всё, что было записано до unlock. **@Volatile**: каждое чтение видит последнюю запись, а объект, полностью построенный до volatile-записи, безопасно публикуется потоку, который прочитал новую ссылку. Атомарным count++ от этого не становится: здесь два действия, чтение и запись, и потоки вклиниваются между ними. **AtomicInteger, AtomicReference**: семантика volatile плюс атомарные incrementAndGet и compareAndSet, сделанные на процессорной инструкции compare-and-swap вместо блокировки. Правило: один писатель и флаг или замена ссылки, @Volatile; один счётчик, атомик; несколько полей, которые меняются вместе, блокировка.

running объявлено обычным полем, поэтому ничто не гарантирует, что рабочий поток вообще увидит запись главного: компилятор может прочитать поле один раз до цикла и вечно крутиться на этой копии. Пометьте его @Volatile, и каждая проверка будет читать текущее значение. Почему так происходит: между записью в stop() и чтением в цикле нет ребра happens-before, поэтому Java Memory Model разрешает компилятору считать running неизменным внутри цикла, который ни разу не синхронизируется. Интерпретатор перечитывает поле, а код после JIT-компиляции может и не перечитывать, поэтому баг зависит от того, когда скомпилируется цикл. На десктопной JVM HotSpot этот цикл продолжает крутиться и после stop(). Как работает исправление: volatile-чтение нельзя закешировать или вынести из цикла, а volatile-запись happens-before каждого последующего чтения поля, так что цикл увидит false на следующей проверке. Всё, что главный поток записал до stop(), тоже станет видно рабочему. **Почему @Volatile достаточно: один поток пишет, другой только читает; для общего счётчика понадобился бы атомик. Другие варианты**: AtomicBoolean или interrupt() с проверкой isInterrupted, который заодно будит поток, заблокированный в sleep или take(). В корутине ту же задачу решает отмена с ensureActive().

Поток просят остановиться, и он останавливается сам: interrupt() лишь выставляет флаг целевому потоку. Блокирующие вызовы вроде sleep, wait, join и BlockingQueue.take реагируют на него, бросая InterruptedException; код, который никогда не блокируется, должен сам проверять isInterrupted. **Не Thread.stop()**: он убивал поток в произвольной точке и отпускал его блокировки, оставляя объекты изменёнными наполовину. Он объявлен устаревшим, а на Android бросает UnsupportedOperationException. Флаг сбрасывается, когда бросается исключение: после catch поток выглядит так, будто его никто не просил остановиться. Никогда не глотайте его: пустой catch превращает просьбу в ничто, и ни shutdownNow(), ни отменённый runInterruptible уже не остановят этот поток. Дайте исключению подняться выше или восстановите флаг через Thread.currentThread().interrupt() и выйдите. В Kotlin эту ошибку сделать легко: проверяемых исключений нет, поэтому широкий catch (e: Exception) вокруг Thread.sleep молча проглатывает прерывание. Что игнорирует прерывания: чтение из классического java.net.Socket и поток, ждущий входа в synchronized. Закройте сокет из другого потока или берите ReentrantLock через lockInterruptibly().

Все три реентерабельны: поток, который держит блокировку, может взять её повторно и не заблокировать сам себя. ReentrantLock добавляет то, чего нет у synchronized: tryLock с таймаутом, прерываемое ожидание, честность (fairness) и несколько условий. ReentrantReadWriteLock пускает много читателей сразу, но только одного писателя. Реентерабельность: блокировка считает захваты для потока-владельца, поэтому один @Synchronized-метод, вызывающий другой на том же объекте, просто увеличивает счётчик; каждому lock() нужен свой unlock(). Корутинный Mutex не реентерабелен: у него нет потока-владельца. **synchronized: отпускается автоматически, даже при исключении, но ждущий поток не может выйти по таймауту или по прерыванию. ReentrantLock**: tryLock(100, TimeUnit.MILLISECONDS) сдаётся вместо вечного ожидания, а lockInterruptibly() реагирует на interrupt(). ReentrantLock(true) работает честно (FIFO) ценой пропускной способности. newCondition() даёт отдельные очереди ожидания. Отпускайте в finally; withLock { } из Kotlin делает это за вас. **ReentrantReadWriteLock: окупается только при частых долгих чтениях и редких записях. Блокировку на чтение нельзя повысить до блокировки на запись: попытка взять запись, держа чтение, заканчивается deadlock. Производительность**: synchronized без конкуренции стоит дёшево в современных рантаймах (ART использует thin locks), поэтому выбирайте ReentrantLock ради возможностей, а не ради скорости.

Поток 1 держит a и ждёт b, поток 2 держит b и ждёт a: из этого цикла не выйдет ни один, и так возникает deadlock (взаимная блокировка). Чтобы его не было, достаточно сломать любое из четырёх условий; обычное решение: брать блокировки в одном глобальном порядке, здесь по id счёта. Четыре условия, нужные одновременно: взаимное исключение, удержание и ожидание (держать одну блокировку, запрашивая другую), отсутствие вытеснения (никто не может отнять блокировку) и циклическое ожидание. Порядок блокировок разрывает цикл: если каждый поток сначала берёт меньший id, поток 2 тоже начинает с a и просто ждёт своей очереди. **tryLock с таймаутом ломает удержание и ожидание: если вторая блокировка занята, отпустите первую, подождите случайное время и повторите. Без случайной паузы два потока могут бесконечно повторять попытки в такт, и так получается livelock. Не вызывайте чужой код, держа блокировку: слушатель или метод другого компонента может взять свои блокировки в обратном порядке. Скопируйте нужное, отпустите блокировку, потом вызывайте. Диагностика**: дамп потоков или ANR-трейс, если замешан главный поток, показывает оба потока в Blocked, и каждый ждёт монитор, который держит другой.

Берите BlockingQueue: put блокируется, пока очередь полна, take блокируется, пока она пуста, а всю синхронизацию делает библиотека. wait/notify служат примитивом под ней, и wait() должен стоять в цикле while, потому что поток может проснуться, когда его условие всё ещё ложно. Зачем цикл: wait() может вернуться без всякого notify (ложное пробуждение, spurious wakeup), а после notifyAll элемент может первым забрать другой потребитель. Перепроверяйте условие после каждого пробуждения: while (items.isEmpty()) lock.wait(). Держите монитор: wait и notify нужно вызывать внутри synchronized на том же объекте, иначе они бросают IllegalMonitorStateException. wait() отпускает этот монитор на время ожидания и снова берёт его перед возвратом. **notifyAll вместо notify**: notify будит одного произвольного ждущего, возможно производителя, когда нужен был потребитель, и сигнал теряется. В Kotlin: у Any нет wait и notify, поэтому блокировкой должен быть java.lang.Object (private val lock = Object()), и компилятор об этом предупреждает. Какая очередь: ArrayBlockingQueue(capacity) ограничена, поэтому быстрый производитель ждёт, а не забивает память; LinkedBlockingQueue() по умолчанию не ограничена; offer и poll с таймаутом перестают ждать через заданное время.

Пул держит потоки живыми и кормит их задачами из очереди, так что за создание потока вы платите один раз. Три фабрики возвращают один и тот же ThreadPoolExecutor с разными настройками: n потоков и неограниченная очередь, сколько угодно потоков без очереди или один поток и неограниченная очередь. **Как решает execute**: потоков меньше corePoolSize, запустить новый; иначе положить задачу в очередь; очередь полна, добавить потоки до maximumPoolSize; дальше отклонить (стандартная AbortPolicy бросает RejectedExecutionException). **newFixedThreadPool(n)**: n потоков и LinkedBlockingQueue без предела. При перегрузке очередь растёт до OutOfMemoryError. **newCachedThreadPool()**: ни одного core-потока, до Int.MAX_VALUE потоков, SynchronousQueue, которая ничего не хранит, простаивающие потоки завершаются через 60 с. Подходит для коротких всплесков; лавина медленных задач породит по потоку на каждую задачу. **newSingleThreadExecutor(): один поток, задачи в порядке отправки: простой способ сериализовать доступ к файлу или базе данных. Ограничьте хоть что-то**: соберите ThreadPoolExecutor сами с ArrayBlockingQueue и политикой вроде CallerRunsPolicy, которая притормаживает производителя, выполняя задачу в его потоке. **submit прячет ошибки**: исключение лежит внутри Future до вызова get(); при execute оно доходит до обработчика необработанных исключений, и на Android приложение падает.

synchronizedMap оборачивает каждый вызов в одну блокировку, и все потоки стоят к ней в очереди. ConcurrentHashMap блокирует только бакет, в который пишет, а читает без блокировок. CopyOnWriteArrayList копирует весь массив при каждой записи, поэтому чтение и обход никогда не блокируются и никогда не видят изменение на полпути. **Collections.synchronizedMap(map)**: корректна для отдельных вызовов, но одна блокировка на всё, и обход не защищён: держите synchronized(map) { } вокруг цикла, иначе он может бросить ConcurrentModificationException. **ConcurrentHashMap**: get не берёт блокировку; put кладёт узел в пустой бакет через CAS или блокирует только первый узел этого бакета, так что писатели в разные бакеты друг друга не ждут. Итераторы слабо согласованы: ConcurrentModificationException не будет, но изменения, сделанные во время цикла, могут попасть в обход, а могут и нет. Ключи и значения null не допускаются. Составные действия всё равно дают гонку: if (!map.containsKey(k)) map[k] = v состоит из двух атомарных вызовов с зазором между ними. Используйте собственные атомарные методы мапы: putIfAbsent, computeIfAbsent, compute, merge. **CopyOnWriteArrayList**: каждый add или remove копирует массив, что стоит O(n) и даёт мусор; обход идёт по снимку. Подходит для списков слушателей, которые меняются редко, а обходятся на каждом событии; не подходит для всего, что часто пишется.

getOrPut работает по схеме «проверить, потом действовать»: читает мапу и при промахе запускает загрузку и сохраняет результат через putIfAbsent. Два потока, промахнувшиеся одновременно, оба запускают загрузку, поэтому пользователь скачивается дважды, а сохраняется только один из результатов. **Что гарантирует ConcurrentHashMap**: атомарен каждый её собственный вызов. getOrPut в Kotlin представляет собой функцию-расширение, которая вызывает get, а затем putIfAbsent, и сетевой вызов идёт между ними; его документация предупреждает, что функция значения по умолчанию может выполниться, даже если ключ уже есть. **Почему не просто computeIfAbsent(id) { api.loadUser(it) }: он запускает загрузку один раз на ключ, но держит блокировку бакета весь запрос: записи других ключей в этот бакет ждут сеть. Исправление**: кешируйте работу, а не результат. computeIfAbsent за микросекунды кладёт Lazy; первый .value запускает загрузку, остальные вызовы с тем же id ждут на этом Lazy, который по умолчанию синхронизирован, а другие id не блокируются вовсе. Ошибки: если загрузка бросает исключение, Lazy остаётся неинициализированным, и следующий вызов повторит запрос, а не закеширует ошибку. В корутинах: та же идея с Deferred<User> из scope.async { }; удаляйте запись при ошибке, потому что упавший Deferred бросает исключение вечно.

Compare-and-set выполняется одной атомарной операцией процессора: записать новое значение, только если в поле всё ещё лежит ожидаемое, и сообщить, получилось ли. Атомики крутят её в цикле (прочитать, вычислить, CAS, повторить), поэтому ни один поток не блокируется, но при конкуренции попытки тратятся впустую, а один CAS покрывает одну переменную. Как это работает updateAndGet { } читает текущее значение, вычисляет новое и вызывает compareAndSet(old, new); если другой поток успел раньше, он читает снова и повторяет. Поэтому он может выполнить вашу лямбду несколько раз: в ней не должно быть побочных эффектов. На ARM64 ART компилирует CAS в пару эксклюзивных загрузки и сохранения (LDAXR/STLXR): сохранение не проходит, если другое ядро успело записать значение. Поле объявлено volatile, поэтому атомики дают и happens-before. Где они перестают помогать Конкуренция: когда много потоков одновременно обновляют один счётчик, большинство CAS не проходят, а кеш-линия скачет между ядрами. LongAdder раскладывает счёт по нескольким ячейкам и суммирует их при чтении: гораздо быстрее для статистики с частыми записями, но чтение не даёт снимка. ABA: CAS проходит, если значение успело смениться с A на B и обратно на A, как будто ничего не менялось. С неизменяемыми объектами и GC это случается редко, а с переиспользуемыми узлами или повторно выданными id вполне реально. AtomicStampedReference добавляет к значению номер версии. Несколько полей: два атомика, обновлённые один за другим, вместе не атомарны, и читатель может увидеть новый count со старым total. Сложите оба в один неизменяемый объект и меняйте его одним CAS или возьмите блокировку.

Записи молча пропадают: два put в один бакет перезаписывают ссылки друг друга, запись во время ресайза попадает в старый массив, а size расходится с реальным числом записей. Если блокировать только писателей, у читателей всё равно нет ребра happens-before, и get может вернуть null для ключа, который в мапе есть. Гонка писателей Потерянные записи: оба потока читают одну и ту же голову бакета и привязывают к ней свой узел; вторая привязка затирает первую. Четыре потока, кладущие по 50 000 разных ключей, за один прогон могут потерять от нескольких записей до десятков тысяч, причём без всякого исключения. Ресайз: поток, переваливший через порог, строит новый массив и переносит записи; put в старый массив в это время теряется, а два потока, расширяющие мапу одновременно, могут опубликовать каждый свой массив. Порча структуры: size увеличивается простым ++; сломанный бакет-дерево может бросить ClassCastException изнутри HashMap или оставить поток крутиться на 100% CPU. Почему блокировки только на put мало У читателя, который обходит блокировку, нет ребра happens-before с писателем: он может увидеть новый массив раньше, чем в него перенесли записи, или узел, поля которого ещё не видны. Поэтому get во время ресайза может не найти существующий ключ, а обход может пропустить записи или бросить ConcurrentModificationException. Исправления Любой доступ под одной и той же блокировкой, включая чтение и обход; или ConcurrentHashMap с его атомарными методами; или ограничить мапу одним потоком; или публиковать неизменяемую мапу через @Volatile-поле и заменять её при каждом изменении.

ThreadLocal даёт каждому потоку свою копию значения: она хранится в мапе внутри объекта Thread, а ключом служит сам ThreadLocal. Потоки пула не умирают, поэтому значение, которое никто не удалил, остаётся живым и достаётся следующей задаче на этом потоке; корутина, возобновившаяся на другом потоке, его теряет. Как он хранится У каждого Thread есть ThreadLocalMap; get() смотрит в мапу текущего потока, поэтому блокировки не нужны. Ключи хранятся как слабые ссылки на ThreadLocal, значения как сильные. Пулы: утечки и устаревшие значения Поток пула живёт столько же, сколько пул, поэтому значение, которое выставили и не удалили, остаётся достижимым вместе со всем, на что оно ссылается. Даже когда сам ThreadLocal уже стал мусором, его значение лежит в мапе, пока какое-нибудь следующее обращение на этом потоке не вычистит устаревшую ячейку. Следующая задача на этом потоке читает request id или транзакцию предыдущей. Выставляйте значение внутри try и вызывайте remove() в finally. Внутри корутин После приостановки корутина может возобновиться на другом потоке Dispatchers.Default или IO, где значения нет или оно принадлежит другой корутине. threadLocal.asContextElement(value) кладёт значение в контекст корутины: оно устанавливается при каждом возобновлении, а прежнее значение потока восстанавливается при каждой приостановке. Элемент не отслеживает записи: set() внутри корутины пропадёт после следующей приостановки. Меняйте значение через withContext(threadLocal.asContextElement(newValue)).