Bloodika's Java Understanding

This is my personal engineering map of how Java actually works below the surface — not API docs, not beginner tutorials. Everything here is about what the JVM is doing when your code runs: how memory is laid out, how garbage is found and reclaimed, how threads coordinate, and how every major collection structure is implemented in terms of raw data structures. If you’ve been writing Java for a while and want to truly own the platform, this is the reference.

1. The JVM — Your Code’s Universe

The Java Virtual Machine is a specification, not a single piece of software. HotSpot (the implementation used by both Oracle JDK and OpenJDK) is what almost everyone runs in production. HotSpot compiles bytecode to native machine code at runtime using JIT, manages all memory, and implements the threading model. Everything that follows is about HotSpot’s behavior.

1.1 Class Loading Subsystem

Before any code runs, the JVM must load the .class files it needs. The class loading process has three phases: loading, linking, and initialization.

Loading reads the binary .class format from a source (filesystem, JAR, network, database — anything). The delegation model governs which classloader does the work:

The Bootstrap ClassLoader is written in native C++ and is part of the JVM itself. It loads the core JDK classes: java.lang.*, java.util.*, etc. You cannot reference it from Java code — String.class.getClassLoader() returns null because of this.

The Platform ClassLoader (called Extension ClassLoader in Java 8) loads classes from the JDK’s extension mechanism and the module system’s bootstrap modules.

The Application ClassLoader loads your application’s classes from the classpath or module path.

Delegation: when any classloader receives a load request for a class, it first asks its parent to load it. Only if the parent (and its parent, up to Bootstrap) cannot find the class does the current loader try itself. This prevents application code from shadowing java.lang.String or other core classes.

Custom ClassLoaders: used in every Java EE / Jakarta EE application server, OSGi containers, and frameworks like Spring that do bytecode manipulation. A URLClassLoader takes an array of URLs and loads from those. Because class identity in the JVM is (classloader, fully-qualified-name), the same .class file loaded by two different classloaders produces two distinct and mutually incompatible types.

The following demonstrates this: two loaders each load the same class file, and instanceof fails across the boundary even though the bytecode is identical.

URLClassLoader loaderA = new URLClassLoader(new URL[]{classDir}, null);
URLClassLoader loaderB = new URLClassLoader(new URL[]{classDir}, null);
Class<?> fromA = loaderA.loadClass("com.example.Widget");
Class<?> fromB = loaderB.loadClass("com.example.Widget");
Object instance = fromA.getDeclaredConstructor().newInstance();
System.out.println(fromA == fromB);
System.out.println(fromA.isInstance(instance));
System.out.println(fromB.isInstance(instance));

This prints false, true, false. The two Class objects are not == even though they describe the same source code, and an instance created from loaderA’s version fails fromB.isInstance().

Linking has three sub-phases:

Verification confirms the bytecode is well-formed and type-safe — no stack underflows, no illegal type coercions. This is the JVM’s security gate.

Preparation allocates memory for the class’s static fields and sets them to default zero values (0, false, null). The actual values are not set yet.

Resolution replaces symbolic references in the constant pool (string-based names of classes, methods, fields) with direct pointers into memory. This can be eager (at load time) or lazy (on first use).

Initialization runs the class’s static initializer blocks and sets static fields to their declared values. This happens exactly once per classloader, and is guaranteed to be thread-safe (the JVM holds a lock internally during initialization, which is why double-checked locking with uninitialized static fields was historically broken).

1.2 Runtime Data Areas

The JVM spec defines six memory regions that the JVM manages:

The Heap is where all object instances and arrays live. All threads share the heap. The GC manages this area. It is the largest and most complex region.

The Method Area (implemented as Metaspace since Java 8, which replaced PermGen) stores per-class data: the runtime constant pool, field and method descriptors, method bytecode, and JIT-compiled native code pointers. Metaspace lives in native (off-heap) memory and expands automatically. -XX:MaxMetaspaceSize caps it; the default is unlimited, bounded only by the OS.

The Java Stack is per-thread. Each method invocation pushes a stack frame; return pops it. Stack depth is bounded by -Xss (default 512KB to 1MB depending on platform). StackOverflowError is thrown when this limit is exceeded.

A method that recurses without a base case exhausts the stack:

static void overflow() {
    overflow();
}

Each call to overflow() pushes a new frame onto the thread’s stack. With no base case the stack grows until it exceeds -Xss, at which point the JVM throws StackOverflowError. The depth at which this happens varies with frame size and the JVM’s internal overhead per frame.

The Program Counter (PC) Register is per-thread and holds the address of the currently executing JVM instruction. For native methods it is undefined.

The Native Method Stack is per-thread and supports JNI (native) method calls.

The Code Cache is separate from the heap: it stores JIT-compiled native machine code. Bounded by -XX:ReservedCodeCacheSize (default 240MB in recent JDKs). When full, JIT stops compiling — look for CodeCache is full. Compiler has been disabled. in logs.

1.3 Bytecode & the Execution Engine

A .class file is a binary container. The first four bytes are always 0xCAFEBABE (the magic number). Then: major/minor version numbers, the constant pool, access flags, class/superclass/interfaces, fields, methods, and attributes.

The JVM is a stack-based virtual machine: instructions operate on an operand stack (local to each stack frame) rather than named registers. This makes bytecode compact and portable across CPU architectures.

Key bytecode instruction categories:

• Load/store: iload_0 (push local slot 0 as int), astore_1 (pop reference into slot 1), ldc (load constant from pool)
• Arithmetic: iadd, lmul, dsub, irem (remainder)
• Comparison & branching: if_icmplt (branch if int comparison), lookupswitch, tableswitch
• Object operations: new, getfield, putfield, getstatic, putstatic, checkcast, instanceof
• Method invocations:
  • invokevirtual: virtual dispatch on class methods (polymorphism)
  • invokeinterface: interface method dispatch
  • invokespecial: constructors, super.method(), private methods (non-virtual)
  • invokestatic: static methods
  • invokedynamic: user-defined dispatch, used for lambdas, method references, and Groovy/Kotlin/Scala features
• Array operations: newarray, aaload, aastore, arraylength
• Stack manipulation: dup, pop, swap
• Control flow: goto, jsr/ret (legacy, subroutines in old class files), athrow, return variants

javap -c disassembles a .class file into its bytecode. For a method that adds one to an int parameter:

public int increment(int);
  Code:
     0: iload_1
     1: iconst_1
     2: iadd
     3: ireturn

iload_1 pushes the first parameter (slot 0 is this; slot 1 is the int) onto the operand stack. iconst_1 pushes the integer literal 1. iadd pops both values, adds them, and pushes the result. ireturn returns the top of the operand stack to the caller. The entire method compiles to four one-byte instructions.

1.4 JIT Compilation & Tiered Compilation

The interpreter runs bytecode instruction-by-instruction. This is correct and starts immediately but is slow (typically 10–50× slower than native code). The JIT compiler translates hot bytecode to native machine code.

HotSpot’s tiered compilation (enabled by default since Java 8) has five levels:

Level 0 is the interpreter. Every method starts here.

Level 1 is C1 (client compiler) compilation with no profiling. Fast compilation, moderate code quality. Used for trivial methods.

Level 2 is C1 with limited profiling (invocation counters). Very fast to compile.

Level 3 is C1 with full profiling: method invocation counts, branch-taken frequencies, receiver type profiles (which concrete class was passed at a call site). This data is used by Level 4.

Level 4 is C2 (server compiler) compilation. Uses the Level 3 profiles to make aggressive speculative optimizations:

• Method inlining: the single most impactful optimization. A method call is replaced with the body of the called method, eliminating dispatch overhead and enabling further optimizations inside the inlined body.
• Escape analysis: if an object never escapes the current method (not returned, not passed to other threads), the JVM can allocate it on the stack instead of the heap (scalar replacement), eliminating GC pressure entirely.
• Lock elision: if an object never escapes, synchronization on it can be removed entirely.
• Loop unrolling: replicate the loop body N times to reduce branch overhead and enable SIMD vectorization.
• Speculative devirtualization: if profiling shows 99% of calls at a virtual call site go to one concrete type, emit a fast-path check for that type and fall through to the general dispatch only otherwise.
• Constant folding and propagation: compute compile-time-known expressions at compile time.
• Dead code elimination: remove code on paths that profiling shows never execute.
• Vectorization (SIMD): map array operations to SSE/AVX instructions.

Deoptimization: C2’s speculative optimizations can become wrong. When a new subclass is loaded that breaks a devirtualization assumption, HotSpot deoptimizes: the native frame is converted back to interpreted frames and re-execution continues in the interpreter. This is transparent to the application but causes a brief stall.

You can see compilation activity with -XX:+PrintCompilation. A ! in the output means deoptimization occurred. An s means method is synchronized. A % means OSR (on-stack replacement) — re-compiling a method while it is already running (for long-running loops).

A typical -XX:+PrintCompilation output:

    224   34     3       java.lang.String::hashCode (49 bytes)
    227   35     4       java.lang.String::hashCode (49 bytes)
    230   34     3       java.lang.String::hashCode (49 bytes)   made not entrant

Column 1 is milliseconds since JVM start. Column 2 is a compile ID. Column 3 is the tier (3 = C1 with full profiling, 4 = C2). The third line shows the C1 compilation becoming made not entrant — the JVM has replaced it with the C2 version and old callers will deoptimize the next time they return.

2. Memory Architecture — Where Every Byte Lives

2.1 Heap Structure: Young vs Old Generation

The generational hypothesis underlies most Java GC design: most objects die young. The heap is split into regions that exploit this.

Young Generation (typically ~33% of total heap by default, controlled by -XX:NewRatio):

• Eden space: almost all new object allocations happen here via TLAB (see §2.4). Eden is large — objects fill it up between Minor GCs.
• Survivor 0 (S0) and Survivor 1 (S1): small spaces (default 1/8 of Young Gen each, -XX:SurvivorRatio). At any time, one survivor is the “from” space (holds objects from previous Minor GC) and one is the “to” space (empty, ready to receive survivors from the next Minor GC). They swap roles each Minor GC.

Old Generation (Tenured): objects that survive enough Minor GCs get promoted here. The threshold is MaxTenuringThreshold (default 15 for Serial/Parallel, adaptive for G1). An object also promotes early if it is too large for the survivor space (promotion to Old Gen directly from Eden).

A Minor GC collects only the Young Generation. It is stop-the-world but usually short (milliseconds) because the Young Gen is small. A Major GC collects the Old Generation (sometimes requiring a concurrent cycle first). A Full GC collects the entire heap (Young + Old + Metaspace).

Large object allocation: objects larger than a threshold (-XX:PretenureSizeThreshold for Serial/Parallel, or 50% of a G1 region for G1) bypass Young Gen and are allocated directly in Old Gen (or a Humongous region in G1). This avoids copying them multiple times during Minor GCs, but they put pressure on Old Gen.

2.2 Metaspace

Metaspace replaced PermGen in Java 8. PermGen was a fixed-size heap region that caused OutOfMemoryError: PermGen space in applications that loaded many classes (common in hot-deploy scenarios). Metaspace is native memory — it expands automatically and is bounded by MaxMetaspaceSize (default: unlimited, so it grows until the OS says no).

Metaspace stores: class metadata (field names/types, method signatures, access flags), method bytecode, the runtime constant pool, and vtables (virtual method dispatch tables). It does not store interned strings (those are on the heap since Java 7).

Class metadata is freed when a class becomes unreachable — this requires the class’s classloader to become unreachable. In application servers that load a new version of your app without restarting, if old classloaders accumulate (Metaspace leak), watch for OutOfMemoryError: Metaspace. Tools: Java Flight Recorder, VisualVM, or -XX:+TraceClassLoading/-XX:+TraceClassUnloading.

2.3 Object Memory Layout

Every Java object on the heap has a fixed-layout object header followed by instance fields, followed by alignment padding.

Object header (on 64-bit HotSpot with compressed oops):

• Mark word (8 bytes): multipurpose. When unlocked: stores identity hash code (31 bits) + GC age (4 bits, for generational promotion threshold) + lock state bits (3 bits). When locked: contains a pointer to the lock record on the owning thread’s stack, or a pointer to an inflated monitor object. In ZGC: stores colored pointer metadata.
• Class pointer (4 bytes with -XX:+UseCompressedOops, enabled by default for heaps < 32GB; 8 bytes otherwise): pointer into Metaspace to this object’s class metadata.

Total header: 12 bytes (compressed) or 16 bytes (uncompressed).

Instance fields: the JVM is free to reorder fields for optimal alignment. HotSpot’s field ordering heuristic is: longs and doubles (8 bytes), ints and floats (4 bytes), shorts and chars (2 bytes), bytes and booleans (1 byte), then object references (4 or 8 bytes). Parent class fields come before child class fields.

Padding: objects are aligned to 8-byte boundaries. An object with a 12-byte header and one int field = 12 + 4 = 16 bytes (no padding needed). An object with a 12-byte header and one byte field = 12 + 1 = 13 bytes → padded to 16 bytes.

This means the minimum possible object size in HotSpot is 16 bytes. A class with no fields: 12-byte header + 4 bytes padding = 16 bytes. Keep this in mind when reasoning about memory usage: new Object() = 16 bytes; new Integer(42) = 16 bytes; int = 42 = 0 bytes on heap (stack/register).

Arrays have an extra 4-byte length field in the header: array header = 12 (mark+class) + 4 (length) = 16 bytes, then the elements contiguously. A new int[10] = 16 + 40 = 56 bytes.

You can inspect object layouts with the JOL (Java Object Layout) tool:

System.out.println(ClassLayout.parseClass(MyClass.class).toPrintable());

2.4 TLAB — Thread-Local Allocation Buffers

Allocating objects requires claiming space on the heap. Naive approach: every thread does a CAS on a shared “next free pointer” in Eden. This creates contention at the allocation site.

HotSpot solves this with TLABs. Each thread owns a private chunk of Eden. Within its TLAB, a thread allocates by simply bumping a pointer — a single pointer increment, no synchronization. This is extremely fast (comparable to stack allocation).

When a thread’s TLAB fills up, it requests a new one from Eden. This is the only point that requires coordination. TLABs are sized dynamically (by the JVM) based on allocation rate and Eden size.

If an object is too large to fit in the TLAB, it is allocated directly in Eden using a CAS on the global Eden pointer — still lock-free but slower.

TLABs are refilled at each Minor GC (Eden is cleared). Use -XX:+PrintTLAB to observe TLAB statistics.

2.5 Stack Frames

Each method invocation creates a stack frame on the calling thread’s Java stack. The frame contains:

Local variable array: slots 0 through N-1. For instance methods, slot 0 is always this. Parameters follow. Local variables declared inside the method get further slots. long and double take two consecutive slots. The size is fixed at compile time and stored in the method’s Code attribute.

Operand stack: the working area for bytecode instructions. Instructions push and pop values here. Maximum depth is also fixed at compile time.

Reference to runtime constant pool: allows the method to look up class/field/method references.

Return address (in HotSpot’s interpreter): where to jump after this method returns.

When the method returns (normally or via exception), the frame is popped and the thread’s stack shrinks. Local references become unreachable. Objects they pointed to may now be eligible for collection (assuming no other live references).

2.6 Off-Heap Memory

Several mechanisms place data outside the managed heap:

Direct ByteBuffers (ByteBuffer.allocateDirect(n)) allocate native memory via malloc. The ByteBuffer object itself is on the heap, but holds a native address. When the ByteBuffer becomes unreachable and is GC’d, a Cleaner (registered via PhantomReference) fires and free()s the native memory. Direct buffers are ideal for I/O — data can be passed directly to OS syscalls without copying through the Java heap (zero-copy). Monitored via java.lang.management.BufferPoolMXBean.

ByteBuffer direct = ByteBuffer.allocateDirect(1024 * 1024);
direct.putInt(0, 42);
int value = direct.getInt(0);

The write and read happen in native memory — no GC-managed heap copy is involved. When direct becomes unreachable, the JVM’s Cleaner thread calls free() on the native pointer on the next GC cycle. Unlike heap memory, this reclamation is not automatic or predictable — explicit cleaner.clean() or keeping track of the MappedByteBuffer lifecycle is necessary for long-lived buffers.

Memory-Mapped Files (FileChannel.map()) map a file region into virtual address space. The OS handles page faults on access. Very efficient for large files with random access patterns.

sun.misc.Unsafe.allocateMemory(n): raw malloc. Must be freed manually with freeMemory(). Used internally by off-heap data structure libraries (Chronicle Map, Netty’s PooledByteBuf). You are now responsible for all memory management.

Foreign Memory API (Java 22+ stable): MemorySegment / Arena provide a safe, structured alternative to Unsafe for off-heap allocation. Arenas support explicit lifecycle management and automatic cleanup when the arena is closed.

2.7 The Code Cache

JIT-compiled native code lives in the Code Cache, a contiguous native memory region. It is divided (since Java 9) into three segmented heaps:

• Non-method code: JVM stubs, interpreter, runtime support code
• Profiled code: Level 2/3 C1 code (expected to be deoptimized later)
• Non-profiled code: Level 1 C1 and Level 4 C2 code (long-lived compiled methods)

Default size is 240MB (varies by JDK). Set with -XX:ReservedCodeCacheSize. Monitor usage with -XX:+PrintCodeCache or JMX.

When the Code Cache fills, JIT compilation stops entirely. Symptoms: latency spikes, log message CodeCache is full. Compiler has been disabled. This is a serious production issue.

3. Garbage Collection — The Full Picture

3.1 Reachability & GC Roots

GC’s job is to find live objects and reclaim everything else. Live = reachable from a GC root. GC roots are the starting points of the reachability graph:

• Every local variable and parameter in every active stack frame across all threads
• Every static field of every loaded class
• Every JNI global reference (native code holding Java objects)
• All active monitor objects (synchronized blocks)
• Objects in the finalization queue
• JVM internal references (class objects, string interning table, etc.)

Reachability analysis (tracing GC): starting from all roots, the GC traverses reference fields transitively, marking each object it reaches as live. When traversal completes, all unmarked objects are unreachable → garbage.

The alternative to tracing is reference counting: each object holds a count of references to it; when count hits zero, collect. Java does not use reference counting (except optionally in some off-heap libraries) because it cannot handle cycles: if A references B and B references A but neither is referenced from roots, both counts are > 0 but both objects are garbage.

A WeakReference lets you observe this directly — the referent has no strong reference keeping it alive, so the GC can collect it at any time:

WeakReference<byte[]> ref = new WeakReference<>(new byte[1024 * 1024]);
System.out.println(ref.get() != null);
System.gc();
System.out.println(ref.get());

After System.gc(), the byte array is eligible for collection and ref.get() returns null. Note that System.gc() only suggests a collection — the JVM may defer it. Under memory pressure it is guaranteed to happen before OutOfMemoryError.

3.2 Reference Types

Java has four reference strengths, controlled by the java.lang.ref package:

Strong reference (default): Object o = new Object(). The GC will never collect an object while any strong reference to it exists.

Soft reference (SoftReference<T>): the GC may collect the referent if it needs memory. Soft references are guaranteed to be cleared before an OutOfMemoryError is thrown. The JVM uses a policy (related to the most recent GC time and SoftRefLRUPolicyMSPerMB) to decide when to clear them. Use for heap-bounded caches: if the heap gets full, cache entries are freed automatically.

SoftReference<byte[]> cache = new SoftReference<>(loadExpensiveData());
byte[] data = cache.get();
if (data == null) {
    data = loadExpensiveData();
    cache = new SoftReference<>(data);
}

Weak reference (WeakReference<T>): cleared at any GC cycle once no strong or soft references exist. A WeakHashMap uses weak keys — when a key is no longer strongly reachable, its entry is removed automatically. Use for canonicalizing mappings and observer/listener patterns where the listener should not prevent the subject from being collected.

A ReferenceQueue lets you detect exactly when a weak reference is cleared:

ReferenceQueue<Object> queue = new ReferenceQueue<>();
WeakReference<Object> weak = new WeakReference<>(new Object(), queue);
System.gc();
Reference<?> enqueued = queue.poll();
System.out.println(enqueued == weak);

After the GC collects the anonymous new Object(), it enqueues weak into queue. queue.poll() returns it non-null, and enqueued == weak is true. This is the mechanism underlying WeakHashMap’s automatic key expiry.

Phantom reference (PhantomReference<T>): get() always returns null. The reference is enqueued in a ReferenceQueue after the object is finalized and before its memory is reclaimed. The only use is detecting when an object has been collected so you can perform post-mortem cleanup (like freeing associated native memory). This replaced finalize().

Cleaner API (Java 9+, java.lang.ref.Cleaner): modern, simpler replacement for PhantomReference. Register an object + a Runnable cleanup action. The Cleaner runs the action when the object becomes phantom-reachable. Used internally by DirectByteBuffer.

Cleaner cleaner = Cleaner.create();
Object resource = new Object();
cleaner.register(resource, () -> System.out.println("native memory freed"));
resource = null;
System.gc();

The Runnable runs in the Cleaner’s own daemon thread after resource becomes phantom-reachable. Unlike finalize(), the cleanup action cannot access the object (it was already collected), and it cannot resurrect it. The Cleaner thread is separate from the application, so a slow cleanup does not block GC progression.

Finalization (deprecated Java 18, removed in Java 21+): objects with a finalize() method cannot be immediately collected — they are enqueued in the finalizer queue and finalized by a background Finalizer thread first. This adds 1+ GC cycles of latency before reclamation, the finalizer thread can become a bottleneck, and finalize() can resurrect the object by storing this somewhere. Avoid it.

3.3 Write Barriers, Card Tables & Remembered Sets

Generational GC only collects Young Gen during a Minor GC. But old objects can hold references to young objects. The GC must track these cross-generation pointers or risk collecting live young objects.

Card table: the heap is divided into 512-byte cards. Each card has a corresponding byte in the card table. When any reference field within a card’s range is written (i.e., obj.field = ref), the JVM’s write barrier marks that card as dirty. During Minor GC, the GC scans dirty cards to find old-to-young pointers (they are additional roots for the young-gen collection).

Remembered Sets (RSets): G1 uses a per-region RSet instead of a global card table. Each region’s RSet records which other regions contain pointers into it. This lets G1 collect individual regions without scanning the entire heap.

A write barrier is a small piece of code the JVM inserts before or after every reference store. For G1 it is a post-write barrier that updates the RSet and also supports the SATB (snapshot-at-the-beginning) invariant for concurrent marking. Write barriers add ~3–10% throughput overhead for write-heavy code.

SATB (Snapshot-At-The-Beginning): during concurrent marking, G1 must ensure it does not miss live objects. SATB means: at the start of marking, take a logical snapshot of the live set. Any reference that is overwritten during marking (object previously referenced from the graph is now unreferenced because someone stored a new value) is logged in SATB buffers so the GC can still trace the original target. This prevents the GC from mistakenly collecting an object that was live at mark-start but appeared unreachable due to concurrent mutation.

3.4 Stop-The-World Pauses

A stop-the-world (STW) pause halts all application threads. During a pause, no application code runs, latency spikes, and GC does its work safely. The JVM uses safepoints to stop threads: each thread periodically checks a flag (safepoint poll), and when the JVM requests a pause, threads halt at their next safepoint. Compiled methods have safepoint polls at loop back edges and method returns. Interpreted methods check at each bytecode. Threads in native code are considered “already at safepoint” because they don’t touch the Java heap.

Time to Safepoint (TTSP): the delay between the JVM requesting a stop and all threads reaching safepoints. If one thread is in a long native call or a tight compiled loop without a safepoint poll (can happen with very long loops containing no method calls), TTSP can be large. -XX:+PrintSafepointStatistics shows this.

Modern low-pause collectors (ZGC, Shenandoah) minimize STW to sub-millisecond by doing almost all work concurrently. Serial/Parallel GC do all GC work in STW.

3.5 Serial GC

-XX:+UseSerialGC. Single-threaded for both Minor and Major GC. Suitable only for small, single-CPU applications or short-lived CLIs. No concurrency, no parallelism.

Minor GC: mark + copy from Eden+S0 to S1. Objects exceeding MaxTenuringThreshold (default 15) are promoted to Old Gen.

Major GC: mark-sweep-compact of Old Gen. Single thread. Can cause seconds-long pauses on large heaps.

java -XX:+UseSerialGC -Xms64m -Xmx64m -jar app.jar

The heap is intentionally small and fixed — Serial GC’s pause times are proportional to heap size, so keeping the heap small keeps pauses short.

3.6 Parallel GC

-XX:+UseParallelGC. Default in Java 8; still used in batch/throughput-focused workloads. Maximizes throughput at the cost of potentially long STW pauses.

Minor GC: parallel copy (multiple GC threads work simultaneously on different parts of Young Gen). Configured by -XX:ParallelGCThreads (default = CPU count).

Major/Full GC: parallel mark-sweep-compact of Old Gen. Still STW, but all GC threads work in parallel.

-XX:GCTimeRatio=99 sets target: GC should take at most 1/(1+99) = 1% of time. -XX:MaxGCPauseMillis sets a pause target (ergonomics tries to meet it by adjusting heap sizes). -XX:+UseAdaptiveSizePolicy (default on) auto-tunes Eden, Survivor, and Old Gen sizes based on GC statistics.

java -XX:+UseParallelGC -Xmx8g -XX:ParallelGCThreads=16 -XX:GCTimeRatio=19 -jar batch.jar

GCTimeRatio=19 targets at most 1/(1+19) = 5% of wall time in GC. The 16-thread parallel collector saturates all CPUs during a pause to finish as quickly as possible, making it ideal for throughput-oriented batch jobs where total time matters more than individual pause length.

3.7 CMS — Concurrent Mark Sweep (Legacy)

-XX:+UseConcMarkSweepGC. Removed in Java 14. Designed to minimize Old Gen pause times by doing most marking concurrently. Understanding CMS is historically important because G1, ZGC, and Shenandoah all evolved from CMS ideas.

CMS phases:

Initial Mark (STW): mark directly reachable objects from GC roots. Very fast.

Concurrent Mark: trace the live object graph from the initial mark results, running concurrently with the application. Mutator threads are running and modifying the graph. CMS uses a tri-color marking algorithm (white = not seen, gray = found but not fully traced, black = fully traced). Concurrently modified objects are tracked via write barriers.

Concurrent Preclean: concurrently re-processes cards dirtied during Concurrent Mark.

Final Remark (STW): short pause to finish tracing objects modified since the start of Concurrent Mark. This is the second STW and its duration was CMS’s Achilles’ heel — under heavy write traffic it could be unexpectedly long.

Concurrent Sweep: reclaim garbage concurrently. No compaction — CMS leaves free space in-place (free lists). This means: memory fragmentation accumulates over time, and if there isn’t enough contiguous space for a large allocation, CMS falls back to a Full GC with compaction.

Concurrent Reset: reset internal data structures.

CMS weaknesses: concurrent mode failure (Old Gen too full before marking completes → Full GC), fragmentation, high write-barrier overhead. G1 was designed to fix these.

CMS was removed in Java 14. For historical reference, its launch flags were:

java -XX:+UseConcMarkSweepGC -Xmx4g -XX:CMSInitiatingOccupancyFraction=70
    -XX:+UseCMSInitiatingOccupancyOnly -jar app.jar

CMSInitiatingOccupancyFraction=70 triggered the concurrent cycle when Old Gen reached 70% full — lower values meant more frequent but less risky marking cycles.

3.8 G1 GC — The Modern Default

-XX:+UseG1GC. Default since Java 9. G1 (Garbage First) is designed to balance throughput and pause times, and to predictably meet a pause-time goal.

Region-based heap: instead of contiguous Young/Old spaces, G1 divides the heap into equal-sized regions (1MB to 32MB, power of 2, auto-selected or set via -XX:G1HeapRegionSize). The total number of regions is up to 2048. Each region is dynamically assigned a role: Eden, Survivor, Old, or Humongous.

Humongous regions: objects larger than 50% of a region size are “humongous” and allocated directly in Old Gen (actually in a contiguous span of regions). Humongous allocations can trigger a concurrent marking cycle immediately. Frequent humongous allocations (e.g., large byte arrays) can cause performance issues.

The Remembered Set (RSet) for each region records which other regions contain references into it. Maintained by post-write barriers. RSets allow G1 to collect a region without scanning the whole heap — only regions in its RSet need to be checked for cross-region pointers.

Young GC (Evacuation Pause, STW): all application threads stop. Live objects from Eden + Survivor regions are copied (evacuated) to new Survivor or Old regions. Empty regions are immediately reclaimed. Duration is typically 5–50ms. Happens frequently (every time Eden fills).

Concurrent Marking Cycle: triggered when heap occupancy exceeds InitiatingHeapOccupancyPercent (IHOP, default 45%). This is what allows G1 to select old regions for collection in the subsequent Mixed GC.

Phases of the Concurrent Marking Cycle:

Initial Mark (STW, piggybacked on Young GC): marks GC roots. Also sets the TAMS (top-at-mark-start) pointer in each region to the current allocation top — objects allocated above TAMS during marking are considered implicitly live and will not be mistakenly collected.

Concurrent Root Region Scan (concurrent): scans Survivor regions from the Initial Mark for references into Old Gen. Must complete before the next Young GC.

Concurrent Mark (concurrent): traces the live object graph using SATB. SATB write barriers log overwritten references so they are not lost. The GC computes live bytes per region during this phase.

Remark (STW, short): finalizes marking. Processes remaining SATB buffers. Processes reference objects (soft, weak, etc.).

Cleanup (mostly STW): accounts live bytes per region (from Concurrent Mark). Sorts regions by GC efficiency (live data / total region size — regions with less live data are cheaper to collect). Identifies completely empty old regions and immediately frees them. The STW part of Cleanup is very short.

Mixed GC: after the Concurrent Marking Cycle, G1 runs Mixed Collections. A Mixed GC is like a Young GC but also includes a selection of old regions (the cheapest to collect based on live-data ratios). Mixed GCs continue until Old Gen occupancy drops below G1HeapWastePercent (default 5%). -XX:G1MixedGCLiveThresholdPercent=85 controls which old regions are eligible (only those with ≤85% live data). -XX:G1MixedGCCountTarget=8 sets how many mixed GC rounds to spread the work over.

Evacuation failure: during a Young or Mixed GC, if there’s not enough room in to-space for all live objects, an evacuation failure occurs. The GC falls back to keeping objects in-place (marks them with a special bit) and eventually a Full GC occurs. Signs: (to-space exhausted) in GC logs. Causes: heap too small, Old Gen filling too fast, or Humongous objects choking available regions.

Full GC: serial (Java 9) or parallel (Java 10+) mark-sweep-compact of the entire heap. Triggered when G1 cannot reclaim space fast enough. A rare Full GC is usually fine; frequent Full GC means tuning is needed.

A typical G1 production configuration:

java -XX:+UseG1GC -Xmx8g -XX:MaxGCPauseMillis=100
     -XX:InitiatingHeapOccupancyPercent=35
     -Xlog:gc*:file=gc.log:time,uptime,level,tags
     -jar app.jar

MaxGCPauseMillis=100 tells G1 to target 100ms pauses. IHOP=35 starts concurrent marking earlier than the default 45%, giving G1 more time to finish marking before Old Gen fills and forcing a Full GC. The -Xlog line writes detailed GC logs for offline analysis.

Key G1 tuning flags:

3.9 ZGC — Sub-Millisecond Pauses

-XX:+UseZGC. Production-ready since Java 15. ZGC targets pause times under 1ms regardless of heap size (tested with heaps up to 16TB). It achieves this through two key innovations: colored pointers and load barriers.

Colored pointers: on 64-bit Linux, only 48 bits of a pointer are actually used for addressing (256TB of virtual address space). ZGC uses 4 of the remaining bits to store per-pointer GC metadata:

• Marked0 / Marked1: alternating bits indicate whether the referenced object has been marked live in the current GC cycle (the bit that means “marked” flips each cycle to avoid clearing all marks).
• Remapped: indicates whether this pointer has been updated to reflect the object’s current location after relocation.
• Finalizable: indicates the object is only reachable via a finalizer.

Every pointer in the heap thus carries state about the GC’s knowledge of where its object is. This is unique — in other collectors, GC state is stored in the objects themselves (mark word).

ZGC uses multi-mapping to implement colored pointers: the same physical memory page is mapped at 3 different virtual addresses (one per valid colored-pointer bit pattern). This way, a colored pointer with any valid bit combination still points to the correct physical page.

Load barriers: ZGC inserts a barrier on every reference load from the heap (when you read a reference field). The barrier checks the pointer’s color bits. If the pointer is “bad” (e.g., the object has been relocated but this pointer still has the old address, indicated by the Remapped bit being clear), the barrier:

1. Looks up the new address in the forwarding table (a hash map from old address to new address).
2. Updates the pointer in-place (heals it) so future loads don’t hit the slow path.
3. Returns the corrected pointer.

This means application threads cooperate in pointer healing concurrently with the GC — no STW needed for relocation from the application’s perspective.

ZGC Phases:

Pause Mark Start (STW, ~0.5–1ms): enumerate and mark GC roots.

Concurrent Mark: trace the live object graph, updating colored pointer bits to “marked.”

Pause Mark End (STW, ~0.5–1ms): process remaining marking work.

Concurrent Prepare for Relocation: select relocation sets (regions to compact), build relocation tables.

Pause Relocate Start (STW, ~0.5–1ms): relocate GC roots.

Concurrent Relocate: move live objects from relocation set regions to new regions, updating the forwarding table. Load barriers in application code heal stale pointers on demand.

Concurrent Remap (overlapped with next cycle’s marking): update all remaining stale pointers. Because load barriers heal pointers lazily, some stale pointers may still exist in the heap; the Remap phase cleans them all up.

Key ZGC flags:

-XX:+UseZGC
-XX:ZCollectionInterval=0
-XX:ZAllocationSpikeTolerance=2.0
-XX:SoftMaxHeapSize=<n>g
-Xlog:gc*:file=gc.log:time,uptime,level,tags

ZGC does not support generational collection until Java 21 (Generational ZGC, -XX:+ZGenerational). Without generational mode, all objects are treated equally — short-lived objects are reclaimed in the next relocation, but ZGC doesn’t specifically optimize for them.

A production ZGC configuration on Java 21+:

java -XX:+UseZGC -XX:+ZGenerational -Xms4g -Xmx16g
     -XX:SoftMaxHeapSize=12g
     -Xlog:gc*:file=gc.log:time,uptime,level,tags
     -jar app.jar

SoftMaxHeapSize=12g lets ZGC try to keep heap usage under 12GB while allowing burst to 16GB. Generational mode (-XX:+ZGenerational) adds young-generation optimization, significantly improving throughput for short-lived object workloads compared to non-generational ZGC.

3.10 Shenandoah GC

-XX:+UseShenandoahGC. Red Hat’s concurrent collector, available in OpenJDK since Java 12. Like ZGC, targets ultra-low pauses through concurrent compaction. Different technique: Brooks forwarding pointers.

Brooks pointers: every Shenandoah object has an extra word at the beginning (before the regular object header) called the forwarding pointer. Initially it points to the object itself. When the object is relocated (moved to a new address), the forwarding pointer is atomically updated to point to the new location. A load barrier checks if the forwarding pointer == the current address; if not, the object has moved and the barrier returns the new address.

Unlike ZGC’s colored pointers (metadata stored in the pointer), Shenandoah’s metadata is stored in the object header, which means it works on 32-bit platforms and does not require multi-mapping. The trade-off is the extra word per object (~8 bytes overhead per object).

Shenandoah Phases:

Init Mark (STW): scan GC roots.

Concurrent Mark: trace the live object graph. Uses SATB (same as G1/CMS).

Final Mark (STW): drain SATB queues, finish marking.

Concurrent Cleanup: free regions with no live objects.

Concurrent Evacuation: copy live objects from the collection set to new regions concurrently with application threads. Brooks pointers in the old copies are updated to point to new copies. Load barriers in mutator code resolve stale references.

Init Update References (STW, very brief): flip a flag to start the reference update phase.

Concurrent Update References: scan the entire heap and update all stale pointers (pointers to old addresses) to the new addresses.

Final Update References (STW): update GC roots to new addresses. Free collection set regions.

Shenandoah modes: adaptive (default, tunes heuristics based on allocation rate), static (collect at fixed intervals), compact (collect as aggressively as possible), passive (no concurrent GC, STW only — for testing).

java -XX:+UseShenandoahGC -XX:ShenandoahGCHeuristics=adaptive
     -Xmx8g -Xlog:gc*:file=gc.log:time,uptime,level,tags
     -jar app.jar

The adaptive heuristic adjusts the collection interval based on the measured allocation rate, aiming to start evacuation early enough to finish before the heap fills. Switch to compact mode for the most aggressive possible heap reclamation at the cost of more CPU time spent collecting.

3.11 Epsilon GC — The No-Op Collector

-XX:+UseEpsilonGC. Performs no garbage collection. The heap fills up and when it’s full, the JVM throws OutOfMemoryError.

Use cases: very short-lived tools where GC overhead is unwanted, performance baselines (what is GC overhead vs none?), or applications that carefully manage memory lifetime through scoped arenas and guarantee no heap growth.

java -XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC
     -Xms512m -Xmx512m -jar cli-tool.jar

The heap is fixed at 512MB because there is no GC to reclaim it. -Xms == -Xmx avoids heap expansion overhead. Epsilon is useful for measuring raw allocation throughput or for CLI tools that allocate a bounded, predictable amount and exit before the heap fills.

3.12 GC Tuning Flags Reference

Heap sizing:

-Xms<size>          Initial heap size
-Xmx<size>          Maximum heap size
-Xmn<size>          Young generation size (Serial, Parallel)
-XX:NewRatio=n      Old:Young ratio (default 2 = Old is 2x Young)
-XX:SurvivorRatio=n Eden:Survivor ratio (default 8 = Eden is 8x each Survivor)
-XX:MaxTenuringThreshold=n  Promotion age threshold (0-15)

GC selection:

-XX:+UseSerialGC
-XX:+UseParallelGC
-XX:+UseG1GC
-XX:+UseZGC
-XX:+UseShenandoahGC
-XX:+UseEpsilonGC

GC diagnostics:

-Xlog:gc*:file=gc.log:time,uptime,level,tags
-XX:+HeapDumpOnOutOfMemoryError
-XX:HeapDumpPath=/path/to/dump.hprof
-XX:+PrintSafepointStatistics
-XX:+UnlockDiagnosticVMOptions

Metaspace:

-XX:MetaspaceSize=<size>       Initial Metaspace size (triggers first GC)
-XX:MaxMetaspaceSize=<size>    Cap (default: unlimited)

3.13 Reading GC Logs

Enable with: -Xlog:gc*:file=gc.log:time,uptime,level,tags

Young GC in G1:

[1.234s][info][gc] GC(5) Pause Young (Normal) (G1 Evacuation Pause) 48M->12M(256M) 8.234ms

This means: at 1.234s, GC event #5, a normal Young GC caused by evacuation pressure. Heap went from 48MB to 12MB used (out of 256MB total). Pause was 8.234ms.

Concurrent Cycle in G1:

[5.100s][info][gc] GC(12) Concurrent Mark Cycle
[5.101s][info][gc] GC(12) Pause Young (Concurrent Start) 128M->64M(512M) 14.2ms
[5.102s][info][gc] GC(12) Concurrent Mark
[5.240s][info][gc] GC(12) Concurrent Mark 138.5ms
[5.241s][info][gc] GC(12) Remark
[5.244s][info][gc] GC(12) Pause Remark 2.3ms
[5.245s][info][gc] GC(12) Cleanup
[5.246s][info][gc] GC(12) Pause Cleanup 1.1ms
[5.247s][info][gc] GC(12) Concurrent Mark Cycle 147.3ms

Full GC (bad news):

[30.000s][info][gc] GC(99) Pause Full (G1 Compaction Pause) 480M->120M(512M) 2345.678ms

A 2.3-second Full GC. Root cause: heap too small, Humongous allocations filling Old Gen, or evacuation failures. Action: increase -Xmx, reduce allocation rate, increase IHOP, or investigate what is filling Old Gen.

Things to watch in GC logs:

• Pause duration: consistently above MaxGCPauseMillis? Heap may be too small or IHOP too high.
• to-space exhausted / to-space overflow: evacuation failures → impending Full GC.
• Any Pause Full: investigate immediately.
• GC frequency: if Minor GC happens every second or faster, Eden is too small.
• Heap after GC grows over time: memory leak — objects are accumulating in Old Gen.

4. Concurrency — The Deep End

4.1 The Java Memory Model (JMM)

Modern CPUs have multi-level caches (L1, L2, L3), write buffers, and perform instruction reordering for performance. Two threads running on different cores can see completely different “views” of memory unless the JVM (and CPU) apply appropriate memory barriers.

The JMM does not specify the underlying CPU instructions. Instead, it defines happens-before (HB) relationships: if action A happens-before action B, then B is guaranteed to see all changes made by A.

HB rules:

• Program order: within a single thread, every action happens-before every subsequent action in that thread (but the CPU can reorder them as long as the single-thread result is preserved).
• Monitor unlock: an unlock on a monitor happens-before every subsequent lock of that same monitor.
• volatile write: a write to a volatile variable happens-before every subsequent read of that variable.
• Thread start: a call to Thread.start() on a thread happens-before any action in that thread.
• Thread termination: all actions in a thread happen-before another thread returns from join() on that thread.
• Object construction: the completion of a constructor happens-before the finalize() method of that object.
• Transitivity: if A HB B and B HB C, then A HB C.

Without a HB relationship, the JMM makes no guarantees. A data race (two threads accessing the same variable without synchronization, at least one writing) is undefined behavior in the JMM sense — you can observe stale values, partial writes, or even values that never existed (due to compiler reordering).

Safe publication: publishing an object from one thread so that other threads can correctly see its fully initialized state requires either:

• Publishing via a volatile field or AtomicReference
• Publishing via the final field of a properly constructed object (final fields are guaranteed visible after the constructor completes)
• Publishing within a synchronized block
• Publishing via static initializers (initialized by the class loader under the class init lock)

The most common publication bug: a reference to an object is made visible to other threads before the object’s fields are fully initialized.

A data race on a non-volatile field is the most common JMM violation:

boolean ready = false;
int value = 0;

void writer() {
    value = 42;
    ready = true;
}

void reader() {
    while (!ready) {}
    System.out.println(value);
}

Without volatile, the compiler and CPU may reorder the two writes in writer(). The reader may see ready == true before value == 42, printing 0. Declaring both fields volatile establishes a happens-before edge from the ready write to the ready read, which by transitivity also covers the value write — the reader is then guaranteed to see 42.

4.2 Thread Lifecycle & States

A Java thread is a java.lang.Thread wrapping an OS thread (for platform threads) or a JVM-managed fiber (for virtual threads, §4.11).

Thread states (Thread.State enum):

NEW: created but start() not yet called.

RUNNABLE: thread is executing or ready to execute. Note: a thread doing blocking I/O is RUNNABLE from the JVM’s perspective (it’s in a native syscall which the JVM can’t distinguish from CPU work).

BLOCKED: waiting to acquire a monitor lock (synchronized). Thread is parked and will be woken when the lock becomes available.

WAITING: waiting indefinitely for another thread to perform a specific action. Caused by Object.wait(), Thread.join(), or LockSupport.park(). Requires an explicit notify()/notifyAll() or unpark().

TIMED_WAITING: like WAITING but with a timeout. Caused by Thread.sleep(), Object.wait(timeout), Thread.join(timeout), LockSupport.parkNanos().

TERMINATED: thread has finished executing.

Thread lifecycle transitions:

new Thread() → NEW .start() → RUNNABLE (OS schedules it) Thread acquires CPU → executing synchronized lock contested → BLOCKED Lock released → RUNNABLE Object.wait() → WAITING notify() called → BLOCKED (still needs to re-acquire the monitor) sleep(n) → TIMED_WAITING Timeout / interrupt → RUNNABLE

The following demonstrates two distinct wait states:

Object lock = new Object();

Thread sleeping = new Thread(() -> {
    try { Thread.sleep(10_000); } catch (InterruptedException e) {}
});

Thread waiting = new Thread(() -> {
    synchronized (lock) {
        try { lock.wait(); } catch (InterruptedException e) {}
    }
});

sleeping.start();
waiting.start();
Thread.sleep(100);
System.out.println(sleeping.getState());
System.out.println(waiting.getState());

sleeping.getState() is TIMED_WAITING (sleeping with a deadline). waiting.getState() is WAITING (indefinite wait inside a monitor). A thread competing to enter a synchronized block would show BLOCKED — that is the only state exclusive to lock contention.

4.3 synchronized & Intrinsic Locks

Every Java object has an associated intrinsic lock (also called a monitor). synchronized uses it.

synchronized(obj) { ... }: acquire obj’s lock, execute the block, release the lock (even if an exception is thrown).

synchronized instance method = synchronized(this) implicitly.

synchronized static method = synchronized(MyClass.class) — locks on the Class object.

Lock states in HotSpot (encoded in the mark word):

Biased locking (removed in Java 21): an object’s lock can be biased toward a specific thread. Once biased, that thread can acquire the lock with a single pointer comparison (no CAS, no atomic). Eliminates overhead when only one thread ever uses a lock. On contention (another thread tries to acquire), the JVM must revoke the bias — this requires a safepoint. Biased locking was disabled by default in Java 15 (-XX:-UseBiasedLocking) and removed in Java 21 after profiling showed that modern workloads with thread pools made it rarely beneficial.

Thin lock (lightweight): when a second thread first contends for a lock, the JVM uses CAS to replace the mark word with a pointer to a lock record allocated on the owning thread’s stack. If CAS succeeds, the thread holds the lock. If the same thread re-acquires (recursion), a counter in the lock record is incremented. The thin lock avoids OS involvement. When a third thread tries to acquire a thin-locked object, the lock inflates.

Fat lock (heavyweight/inflated): a monitor object is allocated (on the heap or in a special area). The monitor contains: the owning thread, a count for reentrant locks, and an OS-level mutex + condition variable (or pthread_mutex_t on Linux, CRITICAL_SECTION on Windows). Blocked threads park themselves by calling pthread_cond_wait. This is expensive but correct for contended scenarios.

Monitor operations:

wait(): releases the lock, suspends the thread in a wait set. Must be called from within synchronized. notify(): moves one thread from the wait set to the entry set (it will contend for the lock when it wakes up). notifyAll(): moves all waiting threads to the entry set.

Classic pattern:

synchronized (queue) {
    while (queue.isEmpty()) {
        queue.wait();
    }
    return queue.poll();
}

Use while, never if, because of spurious wakeups — a thread can wake up from wait() without notify() being called.

4.4 volatile — Visibility & Ordering

A volatile field guarantees two things:

Visibility: every read of a volatile field sees the most recent write, from any thread. The JVM ensures the value is not stale (no CPU cache reuse across threads without synchronization).

Ordering: a volatile write acts as a release (all writes before it are visible to anyone who subsequently sees this write), and a volatile read acts as an acquire (all subsequent reads are ordered after seeing the volatile). On x86, a volatile write emits a mfence or lock add [mem], 0 instruction (full memory barrier). On ARM, explicit dmb (data memory barrier) instructions are emitted.

What volatile does NOT do: atomicity for compound actions. volatile long and volatile double read/write are atomic (guaranteed by the JMM). But counter++ on a volatile int is not atomic — it is still read-increment-write: three separate operations.

Use volatile for: one-time state transitions (a volatile boolean started flag), safely publishing an immutable object (store a fully-initialized object reference to a volatile field), double-checked locking with the instance field:

private volatile MyService instance;

public MyService getInstance() {
    if (instance == null) {
        synchronized (this) {
            if (instance == null) {
                instance = new MyService();
            }
        }
    }
    return instance;
}

Without volatile, the JVM could publish the reference before the object is fully constructed (instruction reordering).

4.5 java.util.concurrent.locks

ReentrantLock: a lock with explicit lock() / unlock() calls. Backed by AbstractQueuedSynchronizer (AQS).

AQS is the workhorse of java.util.concurrent. It maintains:

• An int state field (semantics defined by subclass: ReentrantLock uses 0=unlocked, N=locked N times by same thread)
• A CLH-variant queue of waiting threads (doubly-linked list of Node objects, each containing a thread reference and a wait status)

On lock(): if state == 0, CAS to 1 and record current thread as owner (fast path). Otherwise, enqueue in the AQS queue and call LockSupport.park() (suspend the thread). On unlock(): decrement state; if 0, wake the next queued thread via LockSupport.unpark().

Advantages over synchronized:

• tryLock(): returns immediately with false if lock is not available — avoids deadlock
• tryLock(timeout, unit): waits up to timeout
• lockInterruptibly(): throws InterruptedException if interrupted while waiting
• Fairness mode (new ReentrantLock(true)): grants lock to the longest-waiting thread — predictable latency at the cost of throughput

The tryLock idiom replaces a blocking synchronized block with a bounded wait:

ReentrantLock lock = new ReentrantLock();

if (lock.tryLock(100, TimeUnit.MILLISECONDS)) {
    try {
        doWork();
    } finally {
        lock.unlock();
    }
} else {
    handleLockTimeout();
}

The finally block is essential — unlike synchronized, ReentrantLock does not release automatically when an exception escapes the critical section. Omitting it leaves the lock permanently held by the current thread.

ReentrantReadWriteLock: separate read (shared) and write (exclusive) locks. Multiple readers can hold simultaneously; a writer gets exclusive access. Used for shared data structures read frequently but written rarely. Read lock does not block other readers; write lock blocks all. Risk: read starvation of writers — if readers arrive continuously, a writer may wait forever. Fairness mode addresses this.

ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
Map<String, String> cache = new HashMap<>();

String read(String key) {
    rwLock.readLock().lock();
    try { return cache.get(key); }
    finally { rwLock.readLock().unlock(); }
}

void write(String key, String value) {
    rwLock.writeLock().lock();
    try { cache.put(key, value); }
    finally { rwLock.writeLock().unlock(); }
}

Any number of threads may be inside read() simultaneously. A thread calling write() blocks until all active readers have released, and new readers block until the write completes. The underlying HashMap is unsafe for concurrent access — the lock is what makes this correct.

StampedLock (Java 8+): a more flexible read-write lock.

Modes:

• Write lock: exclusive, like ReadWriteLock
• Read lock: shared, like ReadWriteLock
• Optimistic read: no actual lock acquired; just reads a stamp. After reading, call validate(stamp) — if no write happened since the stamp was obtained, the read is valid. If invalid, retry with a real read lock. Excellent for read-dominant scenarios.

StampedLock lock = new StampedLock();

long stamp = lock.tryOptimisticRead();
double x = this.x;
double y = this.y;
if (!lock.validate(stamp)) {
    stamp = lock.readLock();
    try {
        x = this.x;
        y = this.y;
    } finally {
        lock.unlockRead(stamp);
    }
}
return Math.sqrt(x * x + y * y);

StampedLock is NOT reentrant. Do not call readLock() while holding a writeLock() or vice versa without releasing first.

LockSupport: the fundamental low-level primitive. LockSupport.park() suspends the current thread; LockSupport.unpark(thread) wakes a specific thread. Unlike Object.wait(), park() does not require holding a monitor, and unpark() can be called before park() — the thread will not block when it next calls park() (the permit is pre-granted). This makes LockSupport deadlock-free for implementing higher-level abstractions.

4.6 Atomic Operations & CAS

Compare-And-Swap (CAS): an atomic CPU instruction (CMPXCHG on x86, LDREX/STREX on ARM) that atomically reads a memory location, compares to an expected value, and if equal, swaps to a new value. Returns a boolean indicating success.

java.util.concurrent.atomic provides:

• AtomicInteger, AtomicLong, AtomicBoolean
• AtomicReference<T>: atomic reference swap
• AtomicIntegerArray, AtomicLongArray, AtomicReferenceArray
• AtomicIntegerFieldUpdater, AtomicLongFieldUpdater, AtomicReferenceFieldUpdater: apply atomic operations to a volatile field of an existing class without boxing

All of these use sun.misc.Unsafe internally (or VarHandle in newer JDKs) for CAS.

CAS loop (the basic idiom):

int current;
int updated;
do {
    current = value.get();
    updated = current + delta;
} while (!value.compareAndSet(current, updated));

If CAS fails (another thread changed the value), re-read and retry. This is optimistic locking — assumes contention is rare, avoids lock overhead.

The ABA problem: thread reads A, another thread changes A→B→A, first thread’s CAS(expected=A, new=C) succeeds — but the value was B in between. For reference types where identity matters, this can cause bugs (e.g., in lock-free linked lists). Solution: AtomicStampedReference<T> pairs the reference with an integer stamp (version counter); CAS checks both value and stamp.

LongAdder / LongAccumulator: when many threads increment the same counter, CAS contention becomes a bottleneck (many retries). LongAdder maintains an array of Cell objects (one per CPU or active thread, to reduce false sharing). Each thread increments its cell. sum() aggregates all cells. Significantly higher throughput than AtomicLong under contention.

LongAdder counter = new LongAdder();
IntStream.range(0, 1_000_000).parallel().forEach(i -> counter.increment());
System.out.println(counter.sum());

Under parallel load, each thread mostly increments its own Cell without contending. Compare with an AtomicLong under the same load — the CAS retry loop creates a memory bottleneck that worsens linearly with thread count. LongAdder scales near-linearly instead. The trade-off is that sum() is not atomic: it reflects the count at some point during the summation, not a precise snapshot.

The ABA problem is subtle: AtomicStampedReference pairs the reference with a version counter to catch it:

AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);

int[] stamp = {0};
String val = ref.get(stamp);

ref.compareAndSet("A", "B", 0, 1);
ref.compareAndSet("B", "A", 1, 2);

boolean succeeded = ref.compareAndSet("A", "C", stamp[0], stamp[0] + 1);
System.out.println(succeeded);

The final CAS fails (false) even though the value is "A" again, because the stamp has advanced from 0 to 2. The original stamp (0) no longer matches. Without the stamp, the CAS would succeed — silently applying a change based on a stale read that missed two intermediate writes.

VarHandle (Java 9+): typed references to fields or array elements with configurable memory ordering semantics. Replaces Unsafe for structured accesses. Supports getOpaque, getAcquire, getVolatile, compareAndSet, compareAndExchange, getAndSet, and getAndAdd — each with different memory ordering guarantees.

4.7 Thread Pools & ExecutorService

Never create threads directly in production code. Use a pool.

ThreadPoolExecutor: the core class. Takes:

• corePoolSize: minimum threads kept alive even when idle
• maximumPoolSize: maximum threads
• keepAliveTime + unit: how long idle threads above core survive before termination
• workQueue: a BlockingQueue<Runnable> to hold pending tasks
• threadFactory: how to create threads (set names, daemon flag, priority)
• rejectedExecutionHandler: what to do when queue is full and max threads reached

Queue choices and their implications:

LinkedBlockingQueue (unbounded by default): tasks queue up indefinitely. maximumPoolSize is effectively unused — the pool never creates threads beyond corePoolSize because the queue never fills. This is what Executors.newFixedThreadPool() uses — the unbounded queue means unbounded memory usage under sustained overload.

ArrayBlockingQueue(n) (bounded): once full, new tasks are handled by rejectedExecutionHandler. Forces the pool to grow toward maximumPoolSize.

SynchronousQueue (zero-capacity): each submit() must hand off directly to an idle thread; if none available, a new thread is created (up to max) or rejected. This is what Executors.newCachedThreadPool() uses — threads are created on demand.

PriorityBlockingQueue: tasks with higher priority (lowest comparator value) run first.

Rejected execution policies:

AbortPolicy (default): throws RejectedExecutionException. CallerRunsPolicy: runs the task in the calling thread. Natural back-pressure mechanism. DiscardPolicy: silently drops the task. DiscardOldestPolicy: drops the oldest queued task and retries submission.

A ThreadPoolExecutor with a bounded queue and back-pressure via CallerRunsPolicy:

ThreadPoolExecutor pool = new ThreadPoolExecutor(
    4, 8,
    60, TimeUnit.SECONDS,
    new ArrayBlockingQueue<>(100),
    Executors.defaultThreadFactory(),
    new ThreadPoolExecutor.CallerRunsPolicy()
);

With a bounded ArrayBlockingQueue(100), the pool first fills the queue, then creates new threads up to maximumPoolSize (8). Once both are saturated, CallerRunsPolicy runs the task in the submitting thread — this naturally slows down the producer without dropping work or throwing exceptions.

ForkJoinPool: designed for divide-and-conquer tasks (recursively split into subtasks). Uses work-stealing: each thread has a deque; when its own deque is empty, it steals tasks from the tail of another thread’s deque. This eliminates contention and maximizes CPU utilization for tree-structured workloads.

ForkJoinPool.commonPool() is the shared pool used by:

• Parallel streams (stream.parallel())
• CompletableFuture async methods (when no executor specified)
• ForkJoinTask.fork() when called outside an explicit pool

The common pool’s parallelism = Runtime.getRuntime().availableProcessors() - 1. Override with -Djava.util.concurrent.ForkJoinPool.common.parallelism=N. Be careful: blocking inside the common pool starves all parallel streams application-wide.

StructuredTaskScope (Java 21+, preview → standard in Java 24): structured concurrency API for scoped parallel execution:

try (var scope = new StructuredTaskScope.ShutdownOnFailure()) {
    Subtask<User> user = scope.fork(() -> fetchUser(id));
    Subtask<Orders> orders = scope.fork(() -> fetchOrders(id));
    scope.join().throwIfFailed();
    return new Profile(user.get(), orders.get());
}

When the scope exits, all subtasks are guaranteed to be done (or cancelled). Avoids the “task escaping scope” problem of CompletableFuture.

4.8 CompletableFuture

CompletableFuture<T> represents a value that may not be available yet. It can be completed externally (complete(value), completeExceptionally(ex)) or by chaining transformations.

Stages: each method like thenApply / thenAccept / thenRun returns a new CompletableFuture that completes when the previous stage completes.

thenApply(Function<T,U>): transform the result. Runs in the thread that completes the previous stage (could be the caller’s thread or a pool thread).

thenApplyAsync(Function<T,U>): always runs in the ForkJoinPool common pool (or a specified executor). Avoids blocking the completing thread.

thenCompose(Function<T, CompletableFuture<U>>): flatMap — chain futures without nesting. Use when your transform itself returns a future.

thenCombine(CompletableFuture<U>, BiFunction<T,U,V>): waits for both futures and combines their results.

thenAccept(Consumer<T>): consume the result, no return value.

thenRun(Runnable): run an action after completion, ignoring the result.

exceptionally(Function<Throwable, T>): recover from an exception, provide an alternative value.

handle(BiFunction<T, Throwable, U>): always runs (on success or failure), receives result (or null) and exception (or null).

whenComplete(BiConsumer<T, Throwable>): observe but cannot change the outcome.

allOf(CompletableFuture<?>...): completes when all complete. Returns CompletableFuture<Void>.

anyOf(CompletableFuture<?>...): completes when the first one completes.

Exception propagation: if stage A throws, stage B (which depends on A) completes exceptionally unless B uses exceptionally or handle. The exception propagates through all dependent stages until caught.

Completion thread: by default, when A.thenApply(fn) is registered, and A is already complete, fn runs in the current thread. If A is not yet complete, fn runs in whichever thread completes A. This can be surprising: fn might run in a thread pool thread inside a library you don’t control. Use thenApplyAsync to ensure it runs in a controlled pool.

join() vs get(): both block until complete. get() throws checked ExecutionException; join() throws unchecked CompletionException. In lambdas, join() is more convenient.

A typical async pipeline — each stage runs in the common ForkJoinPool, errors are recovered, and the whole chain is non-blocking until join():

CompletableFuture.supplyAsync(() -> fetchUserId())
    .thenComposeAsync(id -> fetchUserProfile(id))
    .thenApplyAsync(profile -> enrich(profile))
    .exceptionally(ex -> Profile.empty())
    .thenAcceptAsync(profile -> render(profile))
    .join();

thenComposeAsync flattens a future-returning function, avoiding CompletableFuture<CompletableFuture<Profile>>. If fetchUserId() throws, exceptionally intercepts and provides a fallback so thenAcceptAsync still runs. Using Async variants throughout ensures each stage is dispatched to a pool thread instead of running in whatever thread completed the prior stage.

4.9 Synchronizers

CountDownLatch: one-shot. Initialize with a count. Any thread calls await() to block. When countDown() is called count times, all awaiters are released. Cannot be reset. Use for: wait for N services to start, wait for N tasks to complete.

CountDownLatch ready = new CountDownLatch(3);
for (int i = 0; i < 3; i++) {
    new Thread(() -> {
        initService();
        ready.countDown();
    }).start();
}
ready.await();
System.out.println("all 3 services ready");

The main thread blocks at await() until all three initService() calls have called countDown(). The latch cannot be reset; create a new one for each operation.

CyclicBarrier: N threads each call await(); all block until N have arrived, then all proceed simultaneously. Can be reused (hence “cyclic”). Optional barrier action runs when all arrive. Use for: parallel simulated steps (all threads compute phase 1, then all proceed to phase 2 together).

CyclicBarrier barrier = new CyclicBarrier(3, () -> mergeResults());
for (int i = 0; i < 3; i++) {
    new Thread(() -> {
        computePartialResult();
        barrier.await();
    }).start();
}

All three threads block at barrier.await() until all have called it. Then mergeResults() runs once, and all three threads proceed simultaneously. After mergeResults() returns, the barrier resets and can be used again for a second phase.

Semaphore: integer permits. acquire() blocks until a permit is available and takes one. release() returns a permit. Can exceed initial permits. Use for: rate limiting, connection pools, bounded concurrency.

Semaphore pool = new Semaphore(5);

void useResource() throws InterruptedException {
    pool.acquire();
    try {
        callExternalService();
    } finally {
        pool.release();
    }
}

At most 5 threads can be inside callExternalService() simultaneously. The sixth caller blocks at acquire() until one of the five calls release(). The finally block is mandatory — a missed release() permanently reduces the permit count.

Phaser: flexible barrier for variable-phase parallel algorithms. Threads register() and arriveAndAwaitAdvance() for each phase. Threads can deregister. Phases advance automatically. Supports tiered (tree of Phasers) for scalable barrier coordination.

Exchanger: two threads exchange objects at a synchronization point. One thread calls exchange(item) and blocks; when the other calls exchange(item), both get each other’s item. Use for: producer-consumer pipelines passing buffers back and forth.

BlockingQueue implementations:

ArrayBlockingQueue: bounded, backed by circular array, fair or non-fair mode. LinkedBlockingQueue: optionally bounded (default unbounded), backed by linked nodes, separate put and take locks for higher concurrency. PriorityBlockingQueue: unbounded, elements ordered by comparator. DelayQueue: elements must implement Delayed; elements only become takeable after their delay expires. Use for: scheduled task processing. LinkedTransferQueue: producers can optionally wait for a consumer to receive their item (transfer() vs put()). SynchronousQueue: zero capacity, every put must match a take. Used for direct handoff.

4.10 ThreadLocal

ThreadLocal<T> gives each thread its own independent instance of T. Reads and writes are local to the current thread — no synchronization needed.

Internally, each Thread object has a ThreadLocal.ThreadLocalMap field: a custom hash map from ThreadLocal instances to values. The map uses weak keys (so unused ThreadLocal instances can be GC’d), but the values are strong references.

ThreadLocal memory leak: if a ThreadLocal is used in a thread pool and its remove() is never called, the value survives as long as the thread lives (which for pooled threads is forever). Symptom: heap grows, Old Gen fills with objects from previous requests. Fix: always call remove() in a finally block after each task:

try {
    context.set(buildContext(request));
    processRequest(request);
} finally {
    context.remove();
}

InheritableThreadLocal: child threads inherit values from their parent thread at the time of creation. Virtual threads (§4.11) do NOT automatically inherit from their carrier thread.

Use cases: request-scoped context (user ID, correlation ID, locale, transaction), per-thread connection management (JDBC in thread-per-request servers), per-thread SimpleDateFormat instances (which are not thread-safe).

4.11 Virtual Threads — Project Loom

Traditional platform threads (1:1 with OS threads) are expensive:

• Each costs ~1MB of reserved stack memory
• Context switching is a kernel operation
• Practical limit: a few thousand per JVM

Virtual threads (Java 21, Thread.ofVirtual()) are JVM-managed, extremely lightweight:

• Heap-allocated (stack grows dynamically on the heap, can be tiny)
• Context switching is pure JVM work (no kernel involvement)
• Can create millions

Thread vt = Thread.ofVirtual().start(() -> {
    String data = httpClient.get("https://api.example.com/data");
    process(data);
});

ExecutorService executor = Executors.newVirtualThreadPerTaskExecutor();
executor.submit(() -> blockingDatabaseQuery());

Mounting and unmounting: a virtual thread runs on a carrier thread (a real OS thread, part of ForkJoinPool). When the virtual thread would block (I/O, Thread.sleep(), LockSupport.park()), the JVM unmounts it from the carrier — the carrier thread is now free to run another virtual thread. When the blocking operation completes, the virtual thread is rescheduled and mounts on any available carrier.

Pinning: a virtual thread cannot be unmounted when it is:

• Inside a synchronized block or method (because the intrinsic lock is stored in the carrier thread’s state)
• Executing a native method or foreign function

When pinned, the carrier thread is blocked for the duration. Use ReentrantLock instead of synchronized in virtual-thread-heavy code to avoid pinning.

Debugging: -Djdk.tracePinnedThreads=full prints a stack trace whenever a virtual thread pins its carrier.

Virtual threads are not faster than platform threads for CPU-bound work. They excel at I/O-bound workloads where threads spend most of their time waiting — the ability to have thousands of concurrent blocking calls without consuming OS threads is the win.

Structured Concurrency and Scoped Values (Java 21+) were designed alongside virtual threads to provide first-class support for fine-grained parallel task management and context propagation without ThreadLocal leaks.

5. Collections — Under the Hood

5.1 ArrayList — The Workhorse

ArrayList<E> is backed by an Object[]. The array is the “backing array” or “capacity”; the logical “size” is the number of actual elements.

Construction: new ArrayList<>() creates an empty array (actually a shared empty array constant). The first add() allocates with capacity 10. new ArrayList<>(n) pre-allocates capacity n (important optimization when you know approximate size).

Growth: when size == capacity, a new array is allocated with capacity = oldCapacity + (oldCapacity >> 1) — that’s the original capacity plus half of it, giving approximately 1.5× growth. Then Arrays.copyOf() (which calls System.arraycopy()) copies all elements. This is O(n) for the resize operation, but amortized O(1) for add() since resizes happen with exponentially decreasing frequency.

add(E) at end: amortized O(1).

add(int index, E): shifts all elements from index to size-1 right by one using System.arraycopy(). O(n).

remove(int index): shifts elements left. O(n).

remove(Object o): linear scan + shift. O(n).

get(int index): array indexing. O(1).

contains(Object o): linear scan. O(n).

sort(): Arrays.sort() with TimSort — stable, O(n log n).

Iteration: the Iterator has a modCount check — if the list is structurally modified during iteration (via anything other than the iterator’s own remove()), it throws ConcurrentModificationException. This is fail-fast behavior.

The classic mistake — modifying the list during a for-each loop:

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
    if (s.equals("b")) list.remove(s);
}

This throws ConcurrentModificationException because the for-each desugars to an Iterator that checks modCount on each next(), and list.remove() increments modCount. The correct approach is removeIf, which is specifically designed for this:

list.removeIf(s -> s.equals("b"));

Pre-sizing avoids all growth copies when the final size is known:

List<String> result = new ArrayList<>(rows.size());
for (Row row : rows) {
    result.add(row.getName());
}

Without new ArrayList<>(rows.size()), a 1,000-element list triggers ~11 copy-and-grow cycles as capacity progresses through 10 → 15 → 22 → … → 1000+.

ArrayList vs. array: ArrayList has ~2% overhead per element (boxed elements, array header) versus a raw int[]. For performance-critical number arrays, use primitive arrays or IntStream.

5.2 LinkedList — When and Why

LinkedList<E> is a doubly-linked list. Each element is a Node<E> object:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

The LinkedList itself holds references to first and last nodes, and a size.

addFirst() / addLast(): O(1) — just pointer manipulation.

removeFirst() / removeLast(): O(1).

get(int index): O(n) — must traverse from first or last (whichever is closer). LinkedList is NOT suitable as a random-access list.

add(int index, E): O(n) to find the node, O(1) to insert. No shifting.

Memory: each Node object costs ~24 bytes (header 16 + item ref 4 + next 4 + prev 4 → 28, padded to 32 bytes with uncompressed oops, or ~24 with compressed). An ArrayList storing references costs ~4 bytes per element (compressed reference in backing array). For 1 million elements, LinkedList costs ~24MB; ArrayList costs ~4MB. Plus LinkedList destroys CPU cache locality.

Use LinkedList when: you need O(1) add/remove at both ends AND you never need random access. ArrayDeque is almost always a better Deque implementation.

Both LinkedList and ArrayDeque implement Deque, but the memory layout is completely different:

Deque<String> linked = new LinkedList<>();
Deque<String> array  = new ArrayDeque<>();

linked.addLast("a");
linked.addFirst("b");
String head = linked.pollFirst();

array.addLast("a");
array.addFirst("b");
head = array.pollFirst();

Both produce the same result, but ArrayDeque stores elements in a circular Object[] — cache-friendly, no per-element heap allocation. Each LinkedList element is a separate Node object (~32 bytes), scattered across the heap. For 1 million elements, LinkedList uses ~32MB; ArrayDeque uses ~8MB, and iteration is ~5× faster due to sequential memory access.

LinkedList as Deque: implements Deque<E>, so you can use it as a stack (push/pop from head) or queue (add to tail, remove from head). But ArrayDeque is typically 2–10× faster due to cache locality.

5.3 HashMap — Buckets, Hashing, Trees

HashMap<K,V> is the most important collection in Java. Understanding its internals is essential.

Backing structure: Node<K,V>[] table — an array of “buckets.” Each bucket holds a linked list (or, after Java 8, a red-black tree) of entries with the same bucket index.

Hashing: to compute a bucket index from a key, HashMap does:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Then bucket index = hash & (n - 1) where n is table.length (always a power of 2). The XOR with the high 16 bits improves distribution for small table sizes (where only low bits of the hash matter for indexing).

Collision resolution: two keys can have the same bucket index (hash collision). Colliding entries form a linked list at that bucket. Lookup scans the chain comparing with .equals().

Tree-ification (Java 8+): when a single bucket’s chain grows to 8 entries (TREEIFY_THRESHOLD = 8) AND the table has at least 64 slots (MIN_TREEIFY_CAPACITY = 64), the chain is converted to a red-black tree (TreeNode<K,V> — HashMap.Node with left/right/parent/red fields). This makes worst-case lookup O(log n) instead of O(n) per bucket, which matters when many keys hash to the same bucket (e.g., hostile keys in untrusted input). Tree degrades back to linked list when it shrinks to 6 entries (UNTREEIFY_THRESHOLD = 6).

Capacity and load factor: default initial capacity = 16, load factor = 0.75. When size > capacity * loadFactor (i.e., 12 entries in a capacity-16 map), the table doubles in size and all entries are rehashed. The new capacity is always a power of 2. Rehashing uses the existing hash values: an entry whose (hash & oldCapacity) bit is 0 stays in the same bucket index; otherwise it moves to oldIndex + oldCapacity. This is clever — no full rehash required.

Null keys: stored in bucket 0 (hash = 0). Only one null key is allowed.

Null values: allowed. Check with containsKey() before using get() if null is a valid value (since get() returns null for both “not found” and “found null value”).

The null ambiguity is a common source of bugs:

Map<String, String> map = new HashMap<>();
map.put(null, "nullKey");
map.put("key", null);

System.out.println(map.get(null));
System.out.println(map.get("key"));
System.out.println(map.get("missing"));
System.out.println(map.containsKey("key"));
System.out.println(map.containsKey("missing"));

get("key") and get("missing") both return null but mean completely different things. containsKey("key") is true; containsKey("missing") is false. Whenever null is a meaningful stored value, always use containsKey() to distinguish “found null” from “absent.”

Not thread-safe: concurrent modification causes undefined behavior (possible infinite loop during resize in Java 6 — fixed in Java 8, but data loss is still possible). Use ConcurrentHashMap or explicit synchronization.

Iteration order: insertion order is NOT guaranteed. Use LinkedHashMap for that.

HashMap.Entry is Map.Entry: the iterator returns Map.Entry<K,V> which gives getKey() and getValue(). entrySet().iterator() is the most efficient way to iterate both keys and values.

5.4 LinkedHashMap — Ordered Hash

Extends HashMap. Adds a doubly-linked list running through all entries, maintaining either insertion order or access order.

Each entry is LinkedHashMap.Entry<K,V> which extends HashMap.Node<K,V> with before and after pointers. The LinkedHashMap itself holds head and tail references.

Insertion order (default): entries are returned in the order they were first inserted. Re-inserting an existing key does not change its position.

Access order (new LinkedHashMap<>(16, 0.75f, true)): the most recently accessed entry (via get() or put()) moves to the tail. This enables a simple LRU cache by overriding removeEldestEntry():

Map<K, V> lruCache = new LinkedHashMap<>(capacity, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
};

When removeEldestEntry() returns true, the eldest (head, i.e., least recently accessed) entry is automatically removed.

Iteration is O(n) and in order. Memory overhead over HashMap: two extra references (before, after) per entry.

5.5 TreeMap — The Red-Black Tree

TreeMap<K,V> maintains keys in sorted order. Backed by a red-black tree (self-balancing binary search tree). Keys must either implement Comparable<K> or you must supply a Comparator<K>.

Red-black tree properties:

1. Every node is red or black.
2. The root is black.
3. All null leaf nodes (NIL nodes) are black.
4. Red nodes cannot have red children (no two consecutive reds on any path).
5. All paths from any node to its NIL descendants contain the same number of black nodes.

These invariants guarantee the tree height is at most 2 log₂(n+1), ensuring O(log n) for get/put/remove.

Rotation operations (left-rotate, right-rotate) and recoloring maintain balance after insertions and deletions. The implementation is complex but O(log n) amortized.

Operations:

put(K,V), get(K), remove(K): O(log n) — BST search + balancing.

firstKey(), lastKey(): O(log n) — walk to leftmost/rightmost.

ceilingKey(K): smallest key ≥ K. O(log n).

floorKey(K): largest key ≤ K. O(log n).

higherKey(K): smallest key > K. O(log n).

lowerKey(K): largest key < K. O(log n).

subMap(K from, K to): a live view of keys in [from, to). O(1) to get the view; operations within are O(log n).

headMap(K to), tailMap(K from): live sub-views. O(1) to create.

The navigation methods make range queries on sorted data clean and efficient:

TreeMap<Integer, String> prices = new TreeMap<>();
prices.put(10, "cheap");
prices.put(25, "mid");
prices.put(50, "premium");
prices.put(100, "luxury");

System.out.println(prices.ceilingKey(20));
System.out.println(prices.floorKey(30));
System.out.println(prices.higherKey(25));
System.out.println(prices.subMap(10, true, 50, false));

ceilingKey(20) returns 25 (smallest key ≥ 20). floorKey(30) returns 25 (largest key ≤ 30). higherKey(25) returns 50 (strictly greater). subMap(10, true, 50, false) returns a live view containing keys 10 and 25 — writes to this view are reflected in the original map and vice versa.

NavigableMap interface: TreeMap implements NavigableMap<K,V> which adds all the ceiling/floor/higher/lower navigation operations. descendingMap() returns a reverse-ordered view.

5.6 Sets

HashSet<E>: backed by a HashMap<E, PRESENT> where PRESENT is a static dummy object. add(e) calls map.put(e, PRESENT). Same performance as HashMap (O(1) amortized for add/contains/remove). No ordering guarantee.

LinkedHashSet<E>: backed by a LinkedHashMap. Maintains insertion order. O(1) for add/contains/remove.

TreeSet<E>: backed by a TreeMap. Sorted order. O(log n) for add/contains/remove. Implements NavigableSet.

EnumSet<E extends Enum<E>>: specialized set for enum types. Backed by a single long bitmask (RegularEnumSet) or long[] (JumboEnumSet). Extremely compact and fast — set operations are bitwise.

enum Day { MON, TUE, WED, THU, FRI, SAT, SUN }

EnumSet<Day> weekdays = EnumSet.range(Day.MON, Day.FRI);
EnumSet<Day> weekend  = EnumSet.complementOf(weekdays);
System.out.println(weekdays.contains(Day.SAT));
System.out.println(EnumSet.copyOf(weekend));

weekdays is stored as a single long with bits 0–4 set (MON through FRI). complementOf flips all 7 bits, yielding a long with bits 5–6 set (SAT, SUN). contains() is a single bitwise AND. For sets of up to 64 enum constants, every operation is O(1) with no heap allocation.

CopyOnWriteArraySet<E>: backed by CopyOnWriteArrayList. Thread-safe. Good for rarely-modified sets with frequent iteration.

5.7 Queue, Deque & ArrayDeque

Queue<E> interface: offer(e) / add(e) (add to tail), poll() / remove() (remove from head), peek() / element() (inspect head without removing). add/remove/element throw exceptions; offer/poll/peek return null/false.

Deque<E> interface: double-ended queue. Adds offerFirst/offerLast, pollFirst/pollLast, peekFirst/peekLast. Can be used as both Queue (FIFO) and Stack (LIFO).

ArrayDeque<E>: backed by a circular Object[]. Head and tail indices wrap around. No null elements allowed. Amortized O(1) for all head/tail operations. Capacity doubles when full.

ArrayDeque is the recommended replacement for both Stack (legacy class, synchronized, slow) and LinkedList when used as a queue or deque. For most use cases, ArrayDeque is 2–10× faster than LinkedList due to cache-friendly memory layout.

Stack behavior with ArrayDeque:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
int top = stack.pop();

push(e) = addFirst(e), pop() = removeFirst(), peek() = peekFirst().

5.8 PriorityQueue — The Binary Heap

PriorityQueue<E> is a min-heap: poll() always removes the smallest element (according to natural ordering or a provided Comparator). For a max-heap: new PriorityQueue<>(Comparator.reverseOrder()).

Binary heap structure: conceptually a complete binary tree where each parent ≤ its children (min-heap). Stored as an array: node at index i has children at 2i+1 and 2i+2; parent at (i-1)/2.

offer(e) (add): append to end of array, then sift up — swap with parent while smaller than parent. O(log n).

poll() (remove min): take root (index 0), move last element to root, then sift down — swap with the smaller child while larger than the smaller child. O(log n).

peek(): return array[0]. O(1).

contains(o): linear scan. O(n).

remove(o): find then sift up or down. O(n).

Heapify (building from n elements): call siftDown from index (n/2 - 1) to 0. O(n) — counterintuitively linear because most nodes are near the bottom and need little sifting.

PriorityQueue is NOT thread-safe. Use PriorityBlockingQueue for concurrent scenarios.

Iteration order from iterator() is NOT sorted — the iterator traverses the backing array. To consume in sorted order, repeatedly call poll().

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.addAll(List.of(5, 1, 8, 3));
System.out.println(minHeap.poll());
System.out.println(minHeap.poll());

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.addAll(List.of(5, 1, 8, 3));
System.out.println(maxHeap.poll());

minHeap.poll() yields 1, then 3. maxHeap.poll() yields 8. The backing array is not fully sorted — it satisfies only the heap property (each parent ≤ its children for a min-heap). Printing the array directly shows elements in heap order, not sorted order.

5.9 Concurrent Collections

ConcurrentHashMap<K,V>: the thread-safe alternative to HashMap. In Java 7, it used segment locking (16 segments, each an independent locked hash table). In Java 8, it was redesigned:

Reads are entirely lock-free — the table is volatile Node<K,V>[] and individual nodes have volatile V val fields. Reads use no synchronization.

First element in an empty bucket: inserted via CAS on the table slot. No lock.

Subsequent elements in a bucket: synchronized(firstNode) — lock is per-bucket, not per-segment. Contention only on hash collision in the same bucket. Bin-level locking instead of segment-level means much lower contention.

Tree bins: when a bin becomes a red-black tree (TreeBin), the TreeBin itself has an internal ReentrantReadWriteLock-style mechanism for concurrent tree access (reads can be concurrent within a tree bin; writes are exclusive).

size() uses baseCount + a CounterCell[] array (striped counters similar to LongAdder) to avoid hot-spot contention on the size field.

Atomic compound operations: compute(k, fn), computeIfAbsent(k, fn), computeIfPresent(k, fn), merge(k, v, fn) — all performed atomically on a single key.

ConcurrentHashMap<String, List<String>> index = new ConcurrentHashMap<>();

void addToIndex(String word, String docId) {
    index.computeIfAbsent(word, k -> new ArrayList<>()).add(docId);
}

computeIfAbsent atomically checks whether word exists and, if not, calls the function and inserts the result — all under a single bucket-level lock. Two threads calling addToIndex("hello", ...) simultaneously are guaranteed exactly one ArrayList is created, not two. Note that add(docId) after the call is not atomic — if concurrent adds to the list matter, use CopyOnWriteArrayList or a different structure.

CopyOnWriteArrayList<E>: every write (add, remove, set) copies the entire backing array. Reads are unsynchronized (read a stable snapshot). iterator() never throws ConcurrentModificationException and always sees the snapshot at the time the iterator was created. Write is O(n) for each mutation. Best for very small lists that are read far more than written (classic example: event listener lists).

CopyOnWriteArrayList<Runnable> listeners = new CopyOnWriteArrayList<>();
listeners.add(() -> System.out.println("listener 1"));

for (Runnable listener : listeners) {
    listener.run();
    listeners.add(() -> System.out.println("added during iteration"));
}
System.out.println(listeners.size());

The loop iterates over the snapshot from the moment it started — it fires listener 1 but does not see the listener added mid-iteration. After the loop, listeners.size() is 2. No ConcurrentModificationException is thrown even though a write happened during iteration.

ConcurrentSkipListMap<K,V> and ConcurrentSkipListSet<E>: sorted concurrent collections backed by a skip list (a probabilistic data structure with O(log n) average for all operations). Thread-safe alternative to TreeMap / TreeSet without external locking. The skip list uses CAS for lock-free concurrent updates.

BlockingQueue implementations for producer-consumer (see §4.9): ArrayBlockingQueue, LinkedBlockingQueue, SynchronousQueue, PriorityBlockingQueue, DelayQueue, LinkedTransferQueue.

5.10 The equals() & hashCode() Contract

This contract is fundamental to how HashMap, HashSet, and all hash-based collections work.

The contract:

If a.equals(b) is true, then a.hashCode() == b.hashCode() MUST be true.

The converse is not required: a.hashCode() == b.hashCode() does NOT imply a.equals(b) (hash collisions are expected).

Consequences of violating the contract:

If you override equals() but not hashCode(), two “equal” objects can end up in different buckets in a HashMap. Looking up one of them will not find the other. Your map silently fails.

If you override hashCode() inconsistently (returns different values for the same object state), objects you put in the map cannot be found later.

Rules for a correct hashCode():

• Must return the same value for the same object across multiple calls during one JVM execution (unless fields used in equals() change).
• Equal objects must have equal hash codes.
• Unequal objects should ideally have different hash codes (for performance), but it is not required.

Implementing hashCode(): use Objects.hash(field1, field2, ...). Java 7+ style. Internally calls Arrays.hashCode(new Object[]{field1, field2, ...}) using the polynomial: result = 31 * result + (field == null ? 0 : field.hashCode()). The prime 31 is chosen because it is odd (avoids power-of-2 information loss), and 31 * i == (i << 5) - i (JIT can optimize the multiplication).

Comparator vs Comparable:

Comparable<T> is implemented by a class to define its natural ordering. compareTo(T other) returns negative/zero/positive. Should be consistent with equals() (though not strictly required — TreeMap considers two keys with compareTo() == 0 to be the same key even if equals() returns false).

Comparator<T> is an external ordering strategy, passed to collections. Allows multiple sort orders for the same class. Comparator.comparing(Person::getAge).thenComparing(Person::getName) chains comparators.

Records and equals/hashCode: Java 16+ records automatically generate equals(), hashCode(), and toString() based on all record components. This is the safest way to get a correct implementation.

record Point(int x, int y) {}

Point(1, 2).equals(Point(1, 2)) is true. Point(1, 2).hashCode() == Point(1, 2).hashCode() is true. No boilerplate.

Quick Reference: Choosing the Right Collection

Quick Reference: Choosing the Right GC

Quick Reference: Concurrency Primitives