JAVA-240 · Lesson 5 of 12 · 22 min
Thread-safe collections
▶ Video coming soon A video version of this lesson is on the way.
Monday, February 7, 2028. OrderDesk will keep three kinds of shared data: a stock table from part code to the number on the shelf, a list of things that happened during the run, and a queue of orders waiting to be picked. Hamza's first instinct is to wrap each one in synchronized methods. Ingrid stops him. "Somebody has already written those classes, tested them on machines with a hundred cores, and made them faster than anything you or I will write in an evening," she says. Tonight is about java.util.concurrent's collections: what they guarantee, what they do not, and how to use their atomic methods so that check-then-act races cannot happen.
Ordinary collections are not thread-safe
ArrayList, HashMap, HashSet and the other everyday collections are designed for one thread at a time. When two threads change one at once, anything can happen: lost elements, a wrong size, an exception deep inside the library, or in older Java versions, a HashMap stuck in an endless loop. The program below lets four threads add 10,000 items each to one ArrayList. It is a listing with three real runs, because its result changes every time.
import java.util.*;
public class Main {
public static void main(String[] args) throws InterruptedException {
List<Integer> log = new ArrayList<>();
int[] failures = new int[1];
Thread[] ts = new Thread[4];
for (int i = 0; i < 4; i++) {
ts[i] = new Thread(() -> {
for (int n = 0; n < 10_000; n++) {
try {
log.add(n);
} catch (RuntimeException e) {
synchronized (failures) { failures[0]++; }
}
}
});
ts[i].start();
}
for (Thread t : ts) t.join();
System.out.println("expected 40000 items, got " + log.size() + " (" + failures[0] + " adds threw)");
}
}What this code does
Four threads add to one ordinary ArrayList with no protection, and each catches any exception the list throws while it is being changed by another thread. The final size is usually less than 40,000, and some adds may even throw ArrayIndexOutOfBoundsException from inside ArrayList. None of this is a fault in ArrayList: it was never meant to be shared without a lock.
$ javac Main.java
$ java Main
expected 40000 items, got 35487 (0 adds threw)
$ java Main
expected 40000 items, got 36668 (0 adds threw)
$ java Main
expected 40000 items, got 33189 (1 adds threw)What this code does
These are three real runs of the program above on the same computer. The numbers differ from run to run, which is exactly the point: the output of a racy program cannot be predicted.
There are two ways out. The first is a synchronized wrapper: Collections.synchronizedList, synchronizedMap and synchronizedSet return a view whose every method locks one shared lock. That fixes single operations, but it leaves two traps. Iterating over the wrapper is not atomic, so you must hold the wrapper's lock yourself for the whole loop, and a check followed by an action, such as if (!map.containsKey(k)) map.put(k, v), is still a race. The second way, which this lesson recommends, is to use the collections designed for concurrency in java.util.concurrent.
ConcurrentHashMap
ConcurrentHashMap is the workhorse. Many threads can read it at once, and threads that update different keys rarely get in each other's way, because the map locks only the small part of itself that holds a key while changing it. Its reads never block. It does not allow null keys or values, which removes the question of whether get returned null because the key is missing or because its value is null.
Its real strength is its atomic compound methods. Each of these does a check and an action as one step, for one key, so the races of lesson 3 cannot happen:
| Method | What it does atomically |
|---|---|
| putIfAbsent(k, v) | Puts v only if k has no value; returns the existing value or null |
| computeIfAbsent(k, f) | If k is missing, computes a value with f, stores and returns it |
| compute(k, f) | Replaces the value for k with f(k, old value), or removes it if f returns null |
| merge(k, v, f) | Puts v if k is missing, otherwise replaces the value with f(old, v) |
| replace(k, old, new) | Changes the value to new only if it is still old, like compare-and-set |
Counting is the classic use. Four threads each read a quarter of a day's orders and add up how many of each part was ordered. With merge, adding one to a part's count is a single atomic step, even when two threads count the same part at the same moment.
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
public class Main {
public static void main(String[] args) throws InterruptedException {
String[] codes = {"TUBE-700x25", "PAD-ROAD", "CHAIN-11", "TUBE-700x25", "BELL", "PAD-ROAD", "TUBE-700x25", "CABLE-BRAKE"};
Map<String, Integer> ordered = new ConcurrentHashMap<>();
Thread[] counters = new Thread[4];
for (int t = 0; t < 4; t++) {
int part = t;
counters[t] = new Thread(() -> {
for (int n = 0; n < 25_000; n++) {
String code = codes[(part * 25_000 + n) % codes.length];
ordered.merge(code, 1, Integer::sum);
}
});
counters[t].start();
}
for (Thread t : counters) t.join();
new TreeMap<>(ordered).forEach((code, n) -> System.out.println(code + " " + n));
}
}BELL 12500 CABLE-BRAKE 12500 CHAIN-11 12500 PAD-ROAD 25000 TUBE-700x25 37500
What this code does
Four threads count 100,000 order lines between them into one ConcurrentHashMap, using merge to add 1 to a part's count atomically. Main prints the counts through a TreeMap copy so they come out sorted by part code; iterating a hash map directly would give an order that is not guaranteed. The counts add up to exactly 100,000 on every run.
computeIfAbsent is the safe way to create something the first time a key is used. OrderDesk keeps a list of order numbers for each repair day, and the first booking on a day must create that day's list exactly once, however many threads book at the same moment:
import java.util.*;
import java.util.concurrent.*;
public class Main {
public static void main(String[] args) throws InterruptedException {
Map<String, Queue<Integer>> byDay = new ConcurrentHashMap<>();
String[] days = {"Sat Apr 15", "Sun Apr 16", "Sat Apr 22"};
Thread[] bookers = new Thread[3];
for (int t = 0; t < 3; t++) {
int first = t * 100;
bookers[t] = new Thread(() -> {
for (int order = first; order < first + 100; order++) {
String day = days[order % days.length];
byDay.computeIfAbsent(day, d -> new ConcurrentLinkedQueue<>()).add(order);
}
});
bookers[t].start();
}
for (Thread t : bookers) t.join();
for (String day : days) System.out.println(day + ": " + byDay.get(day).size() + " bookings");
System.out.println("lists created: " + byDay.size());
}
}Sat Apr 15: 100 bookings Sun Apr 16: 100 bookings Sat Apr 22: 100 bookings lists created: 3
What this code does
Three threads book 300 orders across three repair days. computeIfAbsent creates a day's queue only the first time the day is seen, atomically, so two threads can never each create their own queue and lose one. The queues themselves are thread-safe ConcurrentLinkedQueue objects, because several threads add to the same day's queue.
Two cautions about the compute family. The function you pass runs while the map holds the lock for that key, so it must be short and must never touch the same map, or the program may deadlock or throw. And the map's size and iteration are weakly consistent: they reflect the map at some moment during the call, which may already be out of date when you use the answer. Iterating a ConcurrentHashMap while other threads change it never throws ConcurrentModificationException, but it may or may not show the changes made during the loop.
Copy-on-write lists and sets
CopyOnWriteArrayList takes a different approach. Every change, add, set or remove, makes a fresh copy of the whole underlying array and swaps it in. Readers and iterators work on whatever array was current when they started, without any locking, and can never see a half-made change or throw ConcurrentModificationException. The cost is that every write copies the entire list, so it suits lists that are read constantly and changed rarely. The classic case is a list of listeners or subscribers.
import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;
public class Main {
public static void main(String[] args) {
List<String> notifyList = new CopyOnWriteArrayList<>(List.of("counter screen", "picking printer"));
int sent = 0;
for (String listener : notifyList) {
sent++;
if (listener.equals("counter screen")) notifyList.add("owner's phone");
}
System.out.println("notified during the loop: " + sent);
System.out.println("listeners now: " + notifyList);
}
}notified during the loop: 2 listeners now: [counter screen, picking printer, owner's phone]
What this code does
A new listener is added in the middle of a loop over the list, which would throw ConcurrentModificationException with an ArrayList. With a CopyOnWriteArrayList the loop keeps walking the copy it started with, so it notifies the two original listeners. The new listener is in the list afterwards and will be notified the next time.
Its companion, CopyOnWriteArraySet, does the same for sets. Neither belongs anywhere that changes often: a list of every order processed on a Saturday would be copied hundreds of times.
Concurrent queues
java.util.concurrent has a family of queues for passing work between threads. ConcurrentLinkedQueue is a lock-free queue: offer adds at the tail and poll removes from the head, and poll returns null when the queue is empty instead of waiting. BlockingQueue implementations such as ArrayBlockingQueue and LinkedBlockingQueue add methods that wait: put waits while the queue is full, and take waits while it is empty. Blocking queues are the heart of the producer-consumer designs of lesson 10, so here is just a first look.
import java.util.concurrent.*;
public class Main {
public static void main(String[] args) throws InterruptedException {
BlockingQueue<String> toPick = new ArrayBlockingQueue<>(10);
Thread web = new Thread(() -> {
try {
for (int i = 1; i <= 5; i++) toPick.put("order " + (1000 + i));
toPick.put("END");
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
});
web.start();
int picked = 0;
while (true) {
String order = toPick.take();
if (order.equals("END")) break;
System.out.println("picking " + order);
picked++;
}
web.join();
System.out.println(picked + " orders picked");
}
}picking order 1001 picking order 1002 picking order 1003 picking order 1004 picking order 1005 5 orders picked
What this code does
A web thread puts five orders into a bounded blocking queue, followed by a special END marker, while main takes orders off the other end and picks them. take waits whenever the queue is empty, so main never sees a missing order and never spins. Because a single queue keeps its first-in, first-out order and there is only one taker, the orders always come out in the order they went in.
| Class | Ordering | Waits when empty or full? | Typical use |
|---|---|---|---|
| ConcurrentLinkedQueue | First in, first out | No: poll returns null | Lock-free hand-off where waiting is not needed |
| ArrayBlockingQueue | First in, first out, fixed capacity | Yes: put and take wait | Producer-consumer with a firm limit |
| LinkedBlockingQueue | First in, first out, optional capacity | Yes | Executor work queues, pipelines |
| PriorityBlockingQueue | By priority | take waits when empty; never full | Urgent repairs before routine ones |
| ConcurrentSkipListMap | Sorted by key | No | A thread-safe TreeMap, such as bookings by time |
Choosing a collection
Hamza puts together a short guide for OrderDesk's three structures. The stock table, read and updated by every order, becomes a ConcurrentHashMap, and every change to it goes through compute or merge so that each reservation is atomic. The event log, written by every thread and read once at the end, becomes a ConcurrentLinkedQueue. The queue of incoming orders becomes a LinkedBlockingQueue so that the picking threads can wait for work. Notifications to the counter screen go in a CopyOnWriteArrayList of listeners.
Ingrid adds one more rule. A thread-safe collection makes each of its own methods safe, but it cannot make your sequence of calls safe. Code that calls get and then put on a ConcurrentHashMap is still a check-then-act race, exactly as in lesson 3. Use the map's single atomic method that does what you need, or, when a rule spans two structures, such as moving a part from stock to an order, use a lock or design the data so one atomic update covers the rule.
// Still a race: another thread can change the count between get and put.
Integer left = stock.get(code);
if (left != null && left > 0) {
stock.put(code, left - 1);
}
// Safe: one atomic step for this key.
stock.computeIfPresent(code, (k, n) -> n > 0 ? n - 1 : n);What this code does
The first version calls two methods that are each thread-safe, but another thread can reserve the same part between them, so two orders can take the last one. The second version does the check and the change inside one computeIfPresent call, which the map runs atomically for that key. Telling whether this order got the part needs a little more care, as the exercise shows.
Try it yourself
Count the parts
Three threads each go through the same list of 6 order lines 10,000 times and count how often each part code appears, using ConcurrentHashMap.merge. Print the counts sorted by code.
The program should print BELL 10000, CHAIN-11 20000 and PAD-ROAD 30000.
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
public class Main {
public static void main(String[] args) throws InterruptedException {
List<String> lines = List.of("PAD-ROAD", "CHAIN-11", "PAD-ROAD", "BELL", "CHAIN-11", "PAD-ROAD");
Map<String, Integer> counts = new ConcurrentHashMap<>();
Thread[] ts = new Thread[3];
// each thread: 10,000 passes over lines, counting with merge
for (Thread t : ts) if (t != null) t.join();
new TreeMap<>(counts).forEach((k, v) -> System.out.println(k + " " + v));
}
}Try it yourself
Reserve with compute
The stock map holds 4 chains. Eight threads each try to reserve one chain. Use compute so the check and the decrement happen atomically, and count successful reservations in an AtomicInteger by checking, inside the compute function, whether a chain was left. (The function runs once per call for a ConcurrentHashMap.)
The program should print reserved: 4 and chains left: 0.
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
public class Main {
public static void main(String[] args) throws InterruptedException {
Map<String, Integer> stock = new ConcurrentHashMap<>(Map.of("CHAIN-11", 4));
AtomicInteger reserved = new AtomicInteger();
Thread[] ts = new Thread[8];
for (int i = 0; i < 8; i++) {
ts[i] = new Thread(() -> {
// reserve one CHAIN-11 atomically and count it
});
ts[i].start();
}
for (Thread t : ts) t.join();
System.out.println("reserved: " + reserved.get());
System.out.println("chains left: " + stock.get("CHAIN-11"));
}
}Common mistakes
MistakeSharing an ArrayList or HashMap between threads without a lock.
InsteadUse a concurrent collection, or guard every access with one lock.
MistakeCalling get and then put on a ConcurrentHashMap to update a value.
InsteadUse merge, compute, computeIfAbsent or putIfAbsent, which act atomically for one key.
MistakeIterating a synchronized wrapper without holding its lock.
InsteadHold the wrapper's lock for the whole loop, or use a concurrent collection whose iterators are safe.
MistakeUsing CopyOnWriteArrayList for a list that changes often.
InsteadEvery change copies the whole array; use it only for read-mostly lists such as listeners.
MistakePrinting a ConcurrentHashMap directly and expecting a fixed order.
InsteadCopy it into a TreeMap, or sort its keys, before printing.
Summary and key terms
- Ordinary collections such as ArrayList and HashMap are not thread-safe and can lose data or throw when shared.
- Synchronized wrappers make single calls safe but leave iteration and check-then-act sequences to the caller.
- ConcurrentHashMap allows concurrent reads and updates to different keys, forbids nulls, and offers atomic compound methods such as putIfAbsent, computeIfAbsent, compute and merge; the functions passed to them must be short and must not touch the same map.
- Its size and iterators are weakly consistent and never throw ConcurrentModificationException.
- CopyOnWriteArrayList copies its array on every change, which suits read-mostly lists such as listeners.
- ConcurrentLinkedQueue is a lock-free queue, and blocking queues such as ArrayBlockingQueue and LinkedBlockingQueue wait in put and take.
- A thread-safe collection makes each of its methods safe, not your sequence of calls; use one atomic method or a lock for rules that span several calls.
- Thread-safe
- Behaving correctly when used by several threads at once without extra locking by the caller.
- Synchronized wrapper
- A view from Collections.synchronizedList or similar that locks one lock for every method.
- ConcurrentHashMap
- A thread-safe hash map that lets threads read and update different keys at the same time.
- merge
- A map method that puts a value or combines it with the existing one in one step.
- computeIfAbsent
- A map method that creates and stores a value for a key only if the key is missing.
- Weakly consistent
- Reflecting the collection at some moment during the operation, without guaranteeing later changes are seen.
- ConcurrentModificationException
- The exception ordinary collections throw when changed during iteration.
- CopyOnWriteArrayList
- A list that copies its contents on every change, making reads and iteration lock-free.
- ConcurrentLinkedQueue
- A lock-free, unbounded first-in, first-out queue.
- BlockingQueue
- A queue whose put and take methods wait when it is full or empty.
Practice problems
Work each problem on paper first, then reveal the answer to check.
Why does ConcurrentHashMap not allow null values?
Show answer
So a null from get always means the key is missing, with no ambiguity under concurrency.
Which method creates a value only the first time a key is used?
Show answer
computeIfAbsent.
Does iterating a ConcurrentHashMap while others change it throw?
Show answer
No; its iterators are weakly consistent and never throw ConcurrentModificationException.
Why is CopyOnWriteArrayList a poor log for every Saturday order?
Show answer
Each add copies the whole list, which becomes slow as the list grows.
What does take do on an empty BlockingQueue?
Show answer
It waits until an element is available.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.