Concurrent collections

Collections.synchronizedMap(new HashMap<>()) wraps every method in a lock. It is correct and it is slow, and it still does not make if (!map.containsKey(k)) map.put(k, v) safe, because that is two calls. The concurrent collections in java.util.concurrent solve both problems: fine-grained or lock-free internals, and compound operations as single atomic methods. Knowing which methods are atomic is the entire skill, and knowing how ConcurrentHashMap is built underneath is what tells you which methods are safe to be slow inside.

#ConcurrentHashMap

The workhorse. Reads are lock-free; writes lock a single bin. Any number of threads can read and write different keys with no contention.

ConcurrentHashMap<String, Session> sessions = new ConcurrentHashMap<>();
 
sessions.putIfAbsent(id, s);                                       // atomic
sessions.computeIfAbsent(id, key -> createSession(key));          // atomic per key; fn runs at most once
sessions.compute(id, (key, old) -> old == null ? fresh() : old.touch());
sessions.merge(id, 1, Integer::sum);                               // atomic counter
sessions.remove(id, expectedValue);                                // conditional remove
sessions.replace(id, oldValue, newValue);                          // conditional replace

computeIfAbsent is the one to know. The mapping function runs under the bin lock, exactly once per absent key, and other threads asking for the same key wait for it — so a cache built on it never computes the same value twice. Two consequences: the function must be short and must not touch the same map (recursive computeIfAbsent on the same map throws IllegalStateException: Recursive update since Java 9, and could livelock before), and it must not block on I/O for long, because the bin is locked and every other key in that bin waits too.

#Under the hood: how the map is built

The Java 8 rewrite of ConcurrentHashMap replaced the old sixteen "segments" with a design that locks as little as possible:

• The table is a volatile Node[], sized to a power of two, indexed by the spread hash exactly as HashMap does. Reads walk the bin with volatile loads and take no lock at all.
• An empty bin is filled with a CAS on the array slot. Two threads inserting different keys into an empty bin: one CAS wins, the other retries and finds the bin non-empty.
• A populated bin is locked with synchronized on its first node while a write walks or modifies the chain. That is the "bin lock", and it is why the map's contention is per-bin, not per-map: with a million-entry table and a few dozen writers, two writers almost never want the same bin.
• Long bins become trees at eight entries, as in HashMap, so a bad hash degrades to O(log n).
• Resizing is cooperative. When the table must grow, a writer that notices starts a transfer; other writers that arrive at a bin already moved (marked by a ForwardingNode) help move the next stripe of bins instead of waiting. Reads during a resize follow the forwarding node into the new table. There is no moment when the map is unavailable.
• size() is a LongAdder. Counts live in striped CounterCells updated per insert and summed on read, so size() and mappingCount() are estimates while writes are in flight, and never a point of contention.
• computeIfAbsent on an empty bin places a ReservationNode in the slot with a CAS and holds its lock while the function runs, which is the mechanism behind "exactly once per key" and behind the rule that the function must not re-enter the map.

What is not atomic:

if (!map.containsKey(k)) map.put(k, v);     // two calls; use putIfAbsent
Integer n = map.get(k); map.put(k, n + 1);  // read then write; use merge
map.size();                                 // an estimate while writes are in flight

Iteration is weakly consistent: it never throws ConcurrentModificationException, reflects some state at or after the iterator's creation, and may or may not show concurrent updates. No null keys or values — get returning null must mean absent, because with concurrent writers there is no atomic way to distinguish "mapped to null" from "removed".

ConcurrentHashMap.newKeySet() is the concurrent Set. ConcurrentSkipListMap/Set are the sorted versions (O(log n), lock-free, built on CAS over a skip list).

#Walkthrough: the cache that stalled every key

A service cached exchange rates: rates.computeIfAbsent(ccy, c -> rateClient.fetch(c)), with fetch a 30 ms HTTP call. It ran for a year. Then the rate provider had an incident and fetch took 12 seconds.

1. A request for EUR finds no entry, takes bin 41's lock, and calls fetch. It holds the lock for 12 seconds.
2. EUR hashes to bin 41; so do INR, KRW and nineteen other currencies in a 64-bin table. Every request for any of them, cached or not, now blocks on synchronized(head) for bin 41, because a read of a populated bin does not lock but a computeIfAbsent always does.
3. Sixty request threads pile up on bin 41 within seconds. The dump shows them BLOCKED (on object monitor) at ConcurrentHashMap.computeIfAbsent, waiting for <0x…> (a ConcurrentHashMap$ReservationNode) or a Node.
4. The other 43 bins are fine, so a third of the currencies work and two thirds time out, which looks like a data-dependent bug and is a hashing coincidence.
5. The fix: never do I/O inside computeIfAbsent. Store a CompletableFuture<Rate> as the value (computeIfAbsent(c, k -> supplyAsync(() -> fetch(k), pool))), so the bin lock is held for the microsecond it takes to create the future and waiting happens outside the map; or use a cache built for this (Caffeine), whose loading is per-key and lock-free.

computeIfAbsent's exactly-once guarantee is bought with a bin lock. That is the right trade for a cheap function and the wrong one for a slow one.

#CopyOnWriteArrayList

Every write copies the whole backing array and swaps it into a volatile field; reads see an immutable snapshot with no locking, and iterators hold the array they started with. Iteration never throws and never sees a concurrent change.

Right for: listener lists, subscriber sets, configuration read on every request and changed once an hour. Wrong for: anything written more than occasionally — a 10,000-element list appended to in a loop is 10,000 full copies, 400 MB of garbage for 40 KB of data. If you find CopyOnWriteArrayList in a hot write path, it is the bug.

#Blocking queues

The producer–consumer hand-off, done for you:

BlockingQueue<Job> queue = new ArrayBlockingQueue<>(1_000);       // bounded: on purpose
 
// producer
if (!queue.offer(job, 100, MILLISECONDS)) reject(job);            // backpressure, not OOM
// consumer
Job j = queue.take();                                              // blocks until available
Job j = queue.poll(1, SECONDS);                                    // or gives up

put/take block; offer/poll with a timeout bound the wait; add/remove throw. ArrayBlockingQueue is one ReentrantLock and two Conditions (the bounded buffer from the locks lesson, exactly); LinkedBlockingQueue uses two locks, one per end, so a producer and a consumer never contend, and it is optionally bounded (unbounded by default — the pool lesson explains why that is a problem). PriorityBlockingQueue orders by priority and is unbounded; DelayQueue releases elements when their delay expires; SynchronousQueue has no capacity and hands each element directly from a put to a take. LinkedTransferQueue and ConcurrentLinkedQueue (non-blocking, unbounded, CAS-based) round out the set.

#Latches, barriers and semaphores

Not collections, but the same package, the same AQS underneath, and the same happens-before guarantees:

• CountDownLatch(n) — await() blocks until countDown() has been called n times. One-shot. "Wait for these N workers to finish initialising."
• CyclicBarrier(n) — n threads each call await(); all proceed together; reusable. "Every phase of the simulation waits for every thread."
• Semaphore(permits) — acquire()/release(). A bulkhead: "at most 10 concurrent calls to this downstream." tryAcquire(timeout) turns saturation into a fast failure.
• Phaser — a barrier with dynamic membership; rarely needed.

Semaphore slots = new Semaphore(10);
if (!slots.tryAcquire(200, MILLISECONDS)) throw new TooBusyException();
try { return client.call(); } finally { slots.release(); }

#The wrapper collections

Collections.synchronizedList/Map/Set lock every call on the wrapper object. They are the right choice only when you need a thread-safe version of a specific implementation the concurrent package lacks (a synchronised LinkedHashMap, say). Iterating them requires locking on the wrapper manually — the one thing people forget — or you get ConcurrentModificationException under load.

#Choosing

#Try it yourself

map.merge(k, 1, Integer::sum);                       // 1
map.put(k, map.getOrDefault(k, 0) + 1);              // 2
map.computeIfPresent(k, (key, v) -> v + 1);          // 3
if (map.get(k) == null) map.put(k, 1);               // 4
map.compute(k, (key, v) -> v == null ? 1 : v + 1);   // 5

#Misconceptions

• "A concurrent map makes my code thread-safe." It makes each method atomic. Two methods in a row are a race, on any map.
• "computeIfAbsent is a free cache." It is exactly-once per key because it holds the bin's lock while your function runs. A slow function stalls every key in that bin.
• "ConcurrentHashMap locks the whole map on write." It CASes an empty bin and locks one bin's head node otherwise; since Java 8 there are no segments and no global lock, and resizes are cooperative.
• "CopyOnWriteArrayList is the thread-safe ArrayList." It is the thread-safe list for data that is read constantly and written almost never; each write copies everything.
• "size() is wrong under load." It is an estimate by design, computed from striped counters so that inserts never contend on a count.

#Going deeper

• ConcurrentHashMap source, the class comment: Doug Lea's own design notes, the most instructive comment in the JDK.
• ConcurrentHashMap.putVal, computeIfAbsent, transfer and addCount: the CAS on an empty bin, the bin lock, the cooperative resize, the striped count.
• ArrayBlockingQueue and LinkedBlockingQueue source, for one-lock versus two-lock queues.
• Caffeine's design documentation, for what a loading cache does that computeIfAbsent cannot.
• Java Concurrency in Practice, chapter 5.