Java Concurrency & Collections

A process is a running program with its own memory; threads run inside a process, share its heap and each have their own stack. A JVM thread is always in one of six states: NEW, RUNNABLE, BLOCKED, WAITING, TIMED_WAITING or TERMINATED. On Android: each app is a Linux process forked from Zygote, with its own ART runtime. An uncaught exception on any of its threads kills the whole process. **NEW and TERMINATED**: created but not started, and finished. start() works once; a second call throws IllegalThreadStateException. **RUNNABLE**: running or ready to run. A thread inside native code or a blocking socket read also reports RUNNABLE. **BLOCKED**: waiting to enter a synchronized block that another thread holds. **WAITING and TIMED_WAITING**: waiting for another thread to act, in wait(), join() or LockSupport.park(). A thread waiting for a ReentrantLock is parked, so it shows WAITING, not BLOCKED. With a timeout (sleep, wait(ms), join(ms)) the state is TIMED_WAITING.

Each thread has its own stack of call frames holding locals, parameters and references; every object lives on the one heap all threads share. A local Int belongs to its thread alone, while any object two threads can reach is shared and needs synchronization. Stack: one per thread, one frame per call, freed on return. Its size is fixed when the thread starts, so runaway recursion ends in StackOverflowError. Heap: objects, arrays and strings with all their fields, managed by the GC. A primitive field lives inside its object, and a boxed Int? is an object too. References: val user in a function is a reference in the frame, and the User it points to is on the heap. Passing it to another thread shares the object, not a copy. Kotlin capture: a local var captured by a lambda is moved to the heap inside a Ref.IntRef, so lambdas running on several threads race on it as on a field. A captured val is simply copied. In interviews "Java memory model" can mean this layout or, strictly, the visibility rules (happens-before) that decide when one thread sees another's writes.

With a raw Thread, a HandlerThread that has its own Looper, an ExecutorService plus a main-thread Handler, or AsyncTask, which bundled that pair. AsyncTask was deprecated in API 30: it leaked Activities, lost results on rotation and behaved differently across Android versions. **Thread: the simplest, and nobody owns it: no cancellation, no way back to the UI. HandlerThread**: a background thread with a Looper; Runnables posted to its Handler run one at a time, in order. **Executor plus Handler(Looper.getMainLooper()): the work runs on a pool, the result is posted to the main thread. What went wrong with AsyncTask**: written as an inner class, it held the Activity until doInBackground finished. After a rotation, onPostExecute reached the destroyed Activity or the result was lost. Changing execution rules: tasks ran in parallel from Android 1.6 and serially again from 3.0. Since then every task in the app shares one queue, so one slow task stalls all the others. Today: coroutines in viewModelScope with withContext(Dispatchers.IO), and WorkManager for work that must outlive the screen.

ArrayList is a resizable array: get(i) is O(1), appending is amortised O(1), inserting or removing in the middle is O(n). LinkedList is a chain of nodes: O(1) at both ends, O(n) to reach an index. ArrayList still wins in practice: one compact array suits the CPU cache. Growth: a full ArrayList allocates an array 1.5 times larger and copies into it. The copy is rare, so appending stays O(1) on average; ArrayList(expectedSize) avoids it. **The middle of an ArrayList**: add(i, x) and removeAt(i) shift the tail with one System.arraycopy, a fast memory move, so O(n) stays cheap for thousands of elements. **LinkedList's O(1) insert is conditional**: it holds only when a ListIterator already stands at the spot. add(i, x) first walks i nodes, with a likely cache miss on each. Memory: every LinkedList element is a separate node object with a header and three references, against one reference slot in the ArrayList array, and more work for the GC. The quadratic trap: for (i in list.indices) list[i] on a LinkedList walks the chain on every get, O(n²) in total; iterate with for (x in list) instead.

HashMap gives O(1) average lookups in no defined order, LinkedHashMap also keeps insertion order, and TreeMap keeps keys sorted at O(log n) per operation. The sets mirror them. Kotlin's mapOf, mutableMapOf, setOf and mutableSetOf return the linked versions. **HashMap, HashSet** (hashMapOf(), hashSetOf()): the fastest and leanest; iteration follows the bucket layout and can change after a resize. **LinkedHashMap, LinkedHashSet**: every entry is also linked to its neighbours (two extra references) for a stable insertion order. With accessOrder = true, every get moves the entry to the end, the basis of an LRU cache. **TreeMap, TreeSet** (sortedMapOf(), sortedSetOf(), toSortedMap()): a red-black tree ordered by compareTo or a Comparator, with range queries such as ceilingKey and headMap. sortedMapOf is typed as SortedMap, so declare a TreeMap for the navigation methods. Choosing: lookups only, HashMap; a stable order for UI or JSON, LinkedHashMap; sorted output or "the next key after X", TreeMap.

HashMap keeps an array of buckets: the key's hashCode picks a bucket and equals finds the entry inside it. Keys that share a bucket form a linked list, which turns into a red-black tree past 8 entries, and the array doubles once the map is 75% full. Finding a key Index: hash = h xor (h ushr 16), then hash and (capacity - 1). The capacity is a power of two (16 by default); the shift mixes the high bits into the low ones that choose the bucket. Inside the bucket: compare the stored hash, then the reference, then equals. Equal keys must have equal hash codes, or the lookup goes to another bucket. **null**: one null key (hash 0, bucket 0) and any number of null values are allowed; ConcurrentHashMap rejects both. Collisions Entries in one bucket are chained, so a lookup there costs O(k) for k entries. A bucket that grows past 8 entries becomes a red-black tree with O(log k) lookups, but only in a table of at least 64 buckets; a smaller table is resized instead. A tree that shrinks to 6 entries or fewer turns back into a list. Resizing When the size passes capacity * loadFactor (12 for the default 16 and 0.75), the array doubles and every entry moves: it stays at index i or goes to i plus the old capacity, decided by one bit of its hash. A resize is O(n) but rare, so put stays amortised O(1).

Happens-before is the Java Memory Model's rule for when one thread must see another's writes; without that edge the JIT and CPU may cache or reorder them. synchronized gives exclusion plus visibility, @Volatile visibility for one field, AtomicInteger atomic read-modify-write. The edges you rely on: an unlock happens-before the next lock of the same monitor; a volatile write happens-before later reads of that field; Thread.start() happens-before the new thread's actions, which happen-before join() returns. Edges are transitive: whatever was written before an edge is visible after it. **synchronized(lock) { }** or @Synchronized: one thread at a time inside, and the next thread to lock the same object sees everything written before the unlock. **@Volatile**: every read sees the latest write, and an object fully built before a volatile write is safely published to the thread that reads the new reference. It does not make count++ atomic: that is a read and a write, and threads interleave between them. **AtomicInteger, AtomicReference**: volatile semantics plus atomic incrementAndGet and compareAndSet, done with a CPU compare-and-swap instead of a lock. Rule of thumb: one writer and a flag or a reference swap, @Volatile; one counter, an atomic; several fields that change together, a lock.

running is a plain field, so nothing guarantees the worker ever sees the main thread's write: the compiler may read it once before the loop and spin on that copy forever. Marking it @Volatile makes every check read the current value. Why it happens: the write in stop() and the read in the loop share no happens-before edge, so the Java Memory Model lets the compiler treat running as unchanged inside a loop that never synchronizes. Interpreted code rereads the field and JIT-compiled code may not, so the bug depends on when the loop gets compiled. On a desktop HotSpot JVM this loop keeps spinning after stop(). How the fix works: a volatile read cannot be cached or moved out of the loop, and a volatile write happens-before every later read of the field, so the loop sees false on its next check. Anything the main thread wrote before stop() becomes visible to the worker as well. **Why @Volatile is enough: one thread writes, the other only reads; a shared counter would need an atomic. Other fixes**: an AtomicBoolean, or interrupt() with an isInterrupted check, which also wakes a thread blocked in sleep or take(). In a coroutine, cancellation with ensureActive() does the job.

You ask it to stop and it stops itself: interrupt() only sets a flag on the target thread. Blocking calls such as sleep, wait, join and BlockingQueue.take react by throwing InterruptedException; code that never blocks has to check isInterrupted on its own. **Not Thread.stop()**: it killed a thread at an arbitrary point and released its locks with objects half-updated. It is deprecated, and on Android it throws UnsupportedOperationException. The flag is cleared when the exception is thrown: after the catch, the thread looks as if nobody had asked it to stop. Never swallow it: an empty catch turns the request into nothing, so shutdownNow() or a cancelled runInterruptible can no longer stop that thread. Let the exception propagate, or restore the flag with Thread.currentThread().interrupt() and return. Kotlin makes the mistake easy: there are no checked exceptions, so a broad catch (e: Exception) around Thread.sleep catches the interrupt without a word. What ignores interrupts: a classic java.net.Socket read and a thread waiting to enter synchronized. Close the socket from another thread, or take a ReentrantLock with lockInterruptibly().

All three are reentrant: a thread that holds the lock can take it again without blocking itself. ReentrantLock adds what synchronized lacks: tryLock with a timeout, interruptible waiting, fairness and several conditions. ReentrantReadWriteLock admits many readers at once but only one writer. Reentrant: the lock counts holds per owner thread, so one @Synchronized method calling another on the same object just raises the count; each lock() needs its own unlock(). A coroutine Mutex is not reentrant: it has no owner thread. **synchronized: released automatically, even on an exception, but a waiting thread cannot time out or be interrupted. ReentrantLock**: tryLock(100, TimeUnit.MILLISECONDS) gives up instead of waiting forever, and lockInterruptibly() reacts to interrupt(). ReentrantLock(true) is fair (FIFO) at a throughput cost. newCondition() gives separate wait queues. Unlock in finally; Kotlin's withLock { } does that for you. **ReentrantReadWriteLock: pays off only for frequent, long reads and rare writes. A read lock cannot be upgraded: taking the write lock while holding the read lock deadlocks. Performance**: an uncontended synchronized is cheap on modern runtimes (ART uses thin locks), so choose ReentrantLock for its features, not for speed.

Thread 1 holds a and waits for b, thread 2 holds b and waits for a: a cycle neither can leave, which is a deadlock. Breaking any of its four conditions prevents it; the usual fix is to take locks in one global order, here by account id. The four conditions, all needed at once: mutual exclusion, hold and wait (keep one lock while asking for another), no preemption (nobody can take a lock away) and circular wait. Lock ordering breaks the cycle: if every thread locks the lower id first, thread 2 also starts with a and simply waits its turn. **tryLock with a timeout breaks hold and wait: if the second lock is busy, release the first, pause for a random moment and retry. Without the random pause, two threads can keep retrying in step: a livelock. Never call foreign code while holding a lock: a listener or another component's method may take its own locks in the opposite order. Copy what you need, release, then call. Diagnosis**: a thread dump, or the ANR trace when the main thread is involved, shows both threads Blocked, each waiting to lock a monitor held by the other.

Use a BlockingQueue: put blocks while the queue is full, take blocks while it is empty, and the library does the locking. wait/notify is the primitive underneath, and wait() must sit in a while loop because a thread can wake up while its condition is still false. Why a loop: wait() may return without any notify (a spurious wakeup), and after notifyAll another consumer may take the item first. Recheck the condition after every wakeup: while (items.isEmpty()) lock.wait(). Hold the monitor: wait and notify must be called inside synchronized on the same object, or they throw IllegalMonitorStateException. wait() releases that monitor while waiting and takes it back before returning. **notifyAll over notify**: notify wakes one arbitrary waiter, maybe a producer when a consumer was needed, and the signal is lost. In Kotlin: Any has no wait or notify, so the lock must be a java.lang.Object (private val lock = Object()), and the compiler warns about it. Which queue: ArrayBlockingQueue(capacity) is bounded, so a fast producer waits instead of filling memory; LinkedBlockingQueue() is unbounded by default; offer and poll with a timeout stop waiting after a while.

A pool keeps threads alive and feeds them tasks from a queue, so you pay for creating a thread once. The three factories are one ThreadPoolExecutor with different settings: n threads and an unbounded queue, unlimited threads and no queue, or one thread and an unbounded queue. **How execute decides**: below corePoolSize, start a thread; otherwise queue the task; queue full, add threads up to maximumPoolSize; then reject (the default AbortPolicy throws RejectedExecutionException). **newFixedThreadPool(n)**: n threads and a LinkedBlockingQueue with no limit. Under overload the queue grows until OutOfMemoryError. **newCachedThreadPool()**: no core threads, up to Int.MAX_VALUE, a SynchronousQueue that stores nothing, idle threads stop after 60 s. Fine for short bursts; a flood of slow tasks gets one thread per task. **newSingleThreadExecutor(): one thread, tasks in submission order: a simple way to serialise access to a file or a database. Bound something**: build the ThreadPoolExecutor yourself with an ArrayBlockingQueue and a policy such as CallerRunsPolicy, which slows the producer by running the task on its thread. **submit hides failures**: the exception waits inside the Future until get(); with execute it reaches the uncaught exception handler, which on Android crashes the app.

synchronizedMap wraps every call in one lock, so all threads queue for it. ConcurrentHashMap locks only the bucket being written and reads without locking. CopyOnWriteArrayList copies its whole array on every write, so reads and iteration never lock and never see a change midway. **Collections.synchronizedMap(map)**: correct per call, but one lock for everything, and iteration is not covered: hold synchronized(map) { } around the loop, or it can throw ConcurrentModificationException. **ConcurrentHashMap**: get takes no lock; put CASes a node into an empty bucket or locks just that bucket's first node, so writers to different buckets do not wait for each other. Iterators are weakly consistent: no ConcurrentModificationException, but changes made during the loop may or may not show. No null keys or values. Compound actions still race: if (!map.containsKey(k)) map[k] = v is two atomic calls with a gap between them. Use the map's own atomic methods: putIfAbsent, computeIfAbsent, compute, merge. **CopyOnWriteArrayList**: every add or remove copies the array, O(n) plus garbage; iteration walks a snapshot. Right for listener lists, written rarely and iterated on every event; wrong for anything written often.

getOrPut is check-then-act: it reads the map and, on a miss, runs the loader and stores the result with putIfAbsent. Two threads that miss at the same moment both run the loader, so the user is fetched twice and only one of the results is kept. **What ConcurrentHashMap guarantees**: each of its own calls is atomic. Kotlin's getOrPut is an extension made of a get and a putIfAbsent with the network call between them; its docs warn that the default value function may run even if the key is already there. **Why not plain computeIfAbsent(id) { api.loadUser(it) }: it runs the loader once per key, but holds that bucket's lock for the whole request: writes to other keys in the bucket wait for the network. The fix**: cache the work, not the result. computeIfAbsent stores a Lazy in microseconds; the first .value runs the load, other callers for the same id wait on that Lazy, which is synchronized by default, and other ids are not blocked at all. Failures: if the load throws, the Lazy stays uninitialised, so the next call retries instead of caching the error. With coroutines: the same idea with Deferred<User> from scope.async { }; remove the entry when it fails, because a failed Deferred rethrows forever.

Compare-and-set is one atomic hardware operation: write the new value only if the field still holds the expected one, and report whether it did. Atomics loop on it (read, compute, CAS, retry), so no thread blocks, but contention means wasted retries and one CAS covers one variable. How it works updateAndGet { } reads the current value, computes a new one and calls compareAndSet(old, new); if another thread got there first, it reads again and retries. So it may run your lambda several times: keep it free of side effects. On ARM64, ART compiles a CAS to an exclusive load and store (LDAXR/STLXR): the store fails if another core wrote the value in between. The field is volatile, so atomics also give happens-before. Where it stops helping Contention: when many threads hammer one counter, most CAS attempts fail and the cache line bounces between cores. LongAdder spreads the count over several cells and sums them on read: much faster for write-heavy statistics, but a read is not a snapshot. ABA: a CAS succeeds if the value went from A to B and back to A in between, as if nothing had changed. With immutable objects and a GC it rarely bites; it does with reused nodes or recycled ids. AtomicStampedReference pairs the value with a version number. Several fields: two atomics updated one after the other are not atomic together, so a reader can see the new count with the old total. Put both into one immutable object and swap it in a single CAS, or use a lock.

Entries silently disappear: two puts into one bucket overwrite each other's link, a write during a resize lands in the old array, and size drifts from the real count. Locking only the writers still leaves readers without a happens-before edge, so get can return null for a key that is there. Writers racing Lost entries: both threads read the same bucket head and link their node to it; the second link replaces the first. Four threads putting 50,000 distinct keys each can lose anything from a few entries to tens of thousands in one run, with no exception. Resize: the thread that crosses the threshold builds a new array and moves entries across; a put into the old array meanwhile is lost, and two threads resizing at once can each publish their own array. Corruption: size is a plain ++; a broken treeified bucket can throw ClassCastException from inside HashMap or leave a thread spinning at 100% CPU. Why locking only put fails A reader that skips the lock has no happens-before edge with the writer: it may see the new array before entries were moved into it, or a node whose fields are not yet visible. So get during a resize can miss an existing key, and iteration can skip entries or throw ConcurrentModificationException. The fixes Every access under the same lock, reads and iteration included; or ConcurrentHashMap with its atomic methods; or confine the map to one thread; or publish an immutable map through a @Volatile field and replace it on every change.

ThreadLocal gives each thread its own copy of a value, stored in a map inside the Thread object and keyed by the ThreadLocal. Pool threads never die, so a value nobody removes stays alive and the next task on that thread sees it; a coroutine that resumes on another thread loses it. How it is stored Each Thread has a ThreadLocalMap; get() looks in the current thread's map, so no locking is needed. Keys are weak references to the ThreadLocal, values are strong. Pools: leaks and stale values A pool thread lives as long as the pool, so a value that is set and never removed stays reachable, along with everything it references. Even after the ThreadLocal itself is garbage, its value stays in the map until a later access on that thread happens to clean the stale slot. The next task on that thread reads the previous task's request id or transaction. Set the value inside try and call remove() in finally. Inside coroutines After a suspension a coroutine may resume on another thread of Dispatchers.Default or IO, where the value is missing or belongs to another coroutine. threadLocal.asContextElement(value) puts the value into the coroutine context: it is installed on every resume and the thread's previous value is restored on every suspend. The element does not track writes: a set() inside the coroutine is gone after the next suspension. Change the value with withContext(threadLocal.asContextElement(newValue)).