Concurrent Collections — Don’t Reinvent Them

Every time you were about to wrap a HashMap in synchronized, Doug Lea already did it better. The java.util.concurrent collections are among the most engineered code in the JDK: they use lock striping, CAS, and lock-free algorithms to give you thread safety without collapsing throughput. This file covers what each one is, when to reach for it, and where the sharp edges are.

One principle above all others: do not synchronize a whole collection when you can pick a concurrent one instead. Collections.synchronizedMap is a museum piece.

---

1. ConcurrentHashMap — The One You’ll Use Most

The workhorse. Highly concurrent reads (essentially lock-free), fine-grained locking on writes (per bin, roughly).

ConcurrentHashMap<String, User> users = new ConcurrentHashMap<>();

users.put("alice", alice);
User u = users.get("alice");
users.remove("alice", alice);   // atomic compare-and-remove

Key atomic operations you should reach for:

Method	Semantics
putIfAbsent(k, v)	Sets only if key absent. Returns old value or null.
computeIfAbsent(k, f)	If absent, computes and stores. Atomic.
computeIfPresent(k, f)	If present, remaps. Atomic.
compute(k, f)	Always applies the function. Atomic.
merge(k, v, f)	Combines with existing (great for counters and grouping).
replace(k, oldV, newV)	Atomic CAS.

Canonical counter pattern:

map.merge(key, 1L, Long::sum);   // atomic ++; correct even under contention

⚠️ The computeIfAbsent pinning trap (Java 21+): the remapping function runs while holding a bin lock. If the function blocks on I/O, virtual threads pin their carrier (until Java 24). Also — don’t recursively call computeIfAbsent on the same map from inside the mapping function; you’ll deadlock the bin. Netflix documented a real production outage from this.

Also:

• Iterators are weakly consistent: they reflect state at some point after iteration began, and do not throw ConcurrentModificationException. They may or may not see updates made during iteration.

• Size returned by size() is a snapshot estimate — don’t use it for correctness invariants.

• No null keys or values. Ever. This is a design choice to disambiguate “not present” from “present with null.”

---

2. CopyOnWriteArrayList — Read-Almost-Only

Every write copies the entire backing array. Reads are lock-free and see a consistent snapshot.

List<Listener> listeners = new CopyOnWriteArrayList<>();
listeners.add(newListener);          // O(n) copy
for (Listener l : listeners) l.on(); // no locking, iterates a snapshot

When it fits:

• Event listener lists, observer lists, subscription lists.

• Read-to-write ratio > ~50:1.

• Small collections (< ~1000 elements).

When it’s a disaster:

• Anything that grows to tens of thousands with frequent writes. Every add is O(n) and allocates a fresh array.

• Hot paths that call add/remove in a loop.

There is also CopyOnWriteArraySet for the same trade-off with set semantics.

---

3. BlockingQueue — The Producer-Consumer Backbone

BlockingQueue extends Queue with two blocking operations: put(e) waits if full, take() waits if empty. These are the primitive that lets producers and consumers hand off work safely without you writing lock/condition code.

The four you should recognize

Implementation	Bounded?	Notes
ArrayBlockingQueue	Yes (fixed at construction)	Backed by a circular array. Single lock. Best when you want a hard ceiling.
LinkedBlockingQueue	Optional (bounded if you pass capacity, unbounded by default)	Two locks (head/tail). Higher throughput than ArrayBQ when producers/consumers don’t interfere.
SynchronousQueue	Zero capacity	Hand-off queue. Every put waits for a matching take. Basis of newCachedThreadPool.
PriorityBlockingQueue	Unbounded	Heap-ordered by natural order or Comparator. Not FIFO.

Always pick a bounded queue in production. Unbounded queues turn transient slowdowns into permanent OOMs. The whole point of backpressure is that the queue is allowed to push back on producers.

Canonical producer-consumer

BlockingQueue<Job> queue = new ArrayBlockingQueue<>(1024);

// Producer thread:
queue.put(job);              // blocks if full

// Consumer thread:
while (!Thread.currentThread().isInterrupted()) {
    Job j = queue.take();    // blocks if empty
    process(j);
}

Compare with the by-hand Condition version in file 02: BlockingQueue is nine lines shorter and correct on the first try.

---

4. ConcurrentSkipListMap and ConcurrentSkipListSet — Sorted Concurrent

When you need TreeMap-like sorted access from many threads. Implemented with skip lists (a probabilistic balanced structure) so operations are O(log n) with no global lock.

ConcurrentSkipListMap<Long, Event> byTimestamp = new ConcurrentSkipListMap<>();
Event e = byTimestamp.firstEntry().getValue();
SortedMap<Long, Event> recent = byTimestamp.tailMap(now - 60_000);

When to use:

• You need concurrent access AND sorted-range views (headMap, tailMap, firstKey).

• You’re implementing time-window aggregations, priority stores, or leader boards with concurrent updates.

Otherwise, ConcurrentHashMap is faster — don’t pay for sorting you won’t use.

---

5. ConcurrentLinkedQueue and ConcurrentLinkedDeque — Lock-Free, Non-Blocking

Unlike BlockingQueue, these never block. poll() returns null on empty. Based on the Michael-Scott non-blocking queue algorithm.

Use when:

• You need a work queue and you’d rather spin/back-off than block. Rare in application code.

• You’re implementing a lock-free algorithm and need a building block.

Don’t use for producer-consumer — a BlockingQueue gives you the same guarantees with clearer backpressure.

---

6. Deprecated / Legacy Wrappers — Avoid

Old	Modern replacement
Hashtable	ConcurrentHashMap
Vector	ArrayList (unsynchronized) or CopyOnWriteArrayList
Stack	Deque (ArrayDeque single-threaded, ConcurrentLinkedDeque concurrent)
Collections.synchronizedMap(...)	ConcurrentHashMap
Collections.synchronizedList(...)	Reconsider; if truly needed, external lock with narrow scope

Seeing Hashtable in code review is a signal that no one has read this file. All of the above use a single global lock, so any two threads touching the collection serialize completely.

---

7. Producer-Consumer Patterns — Full Recipes

Multiple producers, multiple consumers, bounded backpressure

BlockingQueue<Job> queue = new ArrayBlockingQueue<>(2048);

ExecutorService producers = Executors.newFixedThreadPool(4);
for (int i = 0; i < 4; i++) {
    producers.submit(() -> {
        while (!Thread.currentThread().isInterrupted()) {
            Job j = readNextJob();
            queue.put(j);              // blocks under load — that's the point
        }
        return null;
    });
}

ExecutorService consumers = Executors.newFixedThreadPool(8);
for (int i = 0; i < 8; i++) {
    consumers.submit(() -> {
        while (!Thread.currentThread().isInterrupted()) {
            Job j = queue.take();
            try { process(j); }
            catch (Exception e) { log.error("job failed", e); }
        }
        return null;
    });
}

Graceful shutdown with a poison pill

Blocking on take() complicates shutdown — the consumer is asleep. Two patterns:

1. Interrupt-driven: consumers.shutdownNow() sends interrupts. take() throws InterruptedException. Handle it, break.

2. Poison pill: put a sentinel object on the queue. Consumers exit when they see it. Simpler when you need FIFO drain semantics.

---

8. Decision Table

Need	Use
Concurrent map	ConcurrentHashMap
Sorted concurrent map	ConcurrentSkipListMap
Read-mostly list (listeners)	CopyOnWriteArrayList
Producer-consumer with backpressure	ArrayBlockingQueue (bounded)
Handoff channel (thread pools)	SynchronousQueue
Priority-ordered work	PriorityBlockingQueue
Lock-free FIFO (rare)	ConcurrentLinkedQueue
Snapshot iteration required	CopyOnWriteArrayList or copy from ConcurrentHashMap.values()

---

⚠️ What Most People Get Wrong

They iterate a ConcurrentHashMap and treat the iterator like a HashMap’s — assuming it’s a consistent snapshot. It isn’t. It’s a weak snapshot. If you need a real snapshot, copy: new HashMap<>(concurrentMap) under whatever consistency you actually need.

They also treat size() as authoritative on any concurrent collection. It’s an estimate. Never write if (map.size() < CAP) map.put(...) — that’s a race. Use putIfAbsent and check the return, or bound the map with a proper cache (Caffeine, coming in Phase 07).

And they reach for Collections.synchronizedMap(new HashMap<>()) out of muscle memory, when ConcurrentHashMap is one import away and 10-100× faster under contention.

---

Return to README.md · Next: 05_virtual_threads_project_loom.md