concurrent collections

the picture

a plain HashMap shared between threads is a filing cabinet with no rules: two people shoving folders into the same drawer at once can lose one, or (in older javas) jam the drawer so badly the next person searching it loops forever. Collections.synchronizedMap puts one lock on the whole cabinet: safe, and only one person at a time. ConcurrentHashMap puts a tiny lock on each drawer, and only uses it when the drawer already has something in it.

first, how bad the plain one is. two threads, 100,000 distinct keys each, one shared HashMap:

import java.util.HashMap;
import java.util.Map;
 
void main() throws InterruptedException {
    Map<Integer, Integer> map = new HashMap<>();
    Thread a = new Thread(() -> { for (int i = 0; i < 100_000; i++) map.put(i, i); });
    Thread b = new Thread(() -> { for (int i = 100_000; i < 200_000; i++) map.put(i, i); });
    a.start();
    b.start();
    a.join();
    b.join();
    IO.println("size = " + map.size());
}

five runs on jdk 25 printed 133,580, 116,515, 119,990, 123,785 and 123,666. it should be 200,000. no exception, no warning: tens of thousands of entries silently gone, mostly when two resizes or two inserts into the same bucket raced.

ConcurrentHashMap

since java 8, ConcurrentHashMap is the same array-of-bins layout as HashMap, with a different write path:

• empty bin: install the new node with one CAS. no lock at all.
• non-empty bin: synchronized on the bin's first node, then walk or append. only that one bin is locked; the rest of the table is open.
• get: never locks. bins and node links are volatile, so a reader always sees fully published nodes.
• resize: threads that bump into a resize in progress help move bins over, instead of waiting for it.

with 8 bins that's 8 independent locks, and real tables have thousands of bins, so two writers rarely want the same one. the full source walk-through, including treeified bins and the CounterCells that make size() scale like a LongAdder, is in ConcurrentHashMap internals.

compound actions: use the atomic methods

ConcurrentHashMap makes every single call thread-safe. it can't make two calls atomic together, so the check-then-act race is still yours to avoid:

Integer n = counts.get(word);
counts.put(word, n == null ? 1 : n + 1);

counts.merge(word, 1, Integer::sum);

merge, compute, computeIfAbsent, computeIfPresent and putIfAbsent all run under the bin's lock, so the read and the write happen as one step:

import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
 
void main() throws InterruptedException {
    List<String> words = List.of("the", "cat", "sat", "on", "the", "mat", "the", "end");
    ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
    Runnable count = () -> {
        for (int round = 0; round < 1000; round++)
            for (String w : words) counts.merge(w, 1, Integer::sum);   // atomic read-modify-write
    };
    Thread a = new Thread(count);
    Thread b = new Thread(count);
    a.start();
    b.start();
    a.join();
    b.join();
    IO.println(counts.get("the") + " " + counts.get("cat"));
}

6000 2000

a few more differences from HashMap:

• no nulls. put(k, null) throws NullPointerException. otherwise get returning null would be ambiguous ("absent" or "mapped to null?") with no way to check both atomically.
• iterators are weakly consistent. they never throw ConcurrentModificationException, and may or may not show changes made during iteration.
• size() is a moment in a moving stream. under concurrent updates it's an estimate. mappingCount() returns a long for huge maps.

CopyOnWriteArrayList

every write (add, set, remove) copies the entire backing array, modifies the copy, and swaps it in with a volatile write. reads and iteration just use whatever array is current, with no locking at all.

·

import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
 
void main() {
    var list = new CopyOnWriteArrayList<>(List.of("a", "b", "c"));
    var it = list.iterator();         // a snapshot of the array, right now
    list.add("d");                    // copies the array, then swaps it in
    while (it.hasNext()) IO.print(it.next());
    IO.println(" " + list);
}

abc [a, b, c, d]

perfect for small lists that are read constantly and changed rarely: event listeners, plugin registries, routing rules. terrible for anything written often: adding n elements one by one copies O(n²) elements in total.

BlockingQueue: producer-consumer, built in

a BlockingQueue is the bounded buffer from the wait/notify chapter, done properly, with the conditions and the loop already inside:

each operation comes in four flavors, depending on what you want to happen at the edge:

and the implementations:

which one, when