Concurrent collections

A HashMap shared by threads loses entries and can corrupt itself, and a Hashtable or a synchronised wrapper stops that by making every thread wait. The concurrent collections are the third answer: they lock a small part of the structure instead of all of it, and their methods are atomic operations a program states directly.

ConcurrentHashMap

Four threads count four words a hundred thousand times each with merge, and the counts are exact. No lock appears in the source, and the map is shared by all four:

import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; public class Maps { public static void main(String[] args) throws InterruptedException { Map<String, Integer> counts = new ConcurrentHashMap<>(); List<Thread> workers = new ArrayList<>(); String[] words = {"a", "b", "a", "c"}; for (String word : words) { Thread worker = new Thread(() -> { for (int i = 0; i < 100_000; i++) { counts.merge(word, 1, Integer::sum); } }); workers.add(worker); worker.start(); } for (Thread worker : workers) { worker.join(); } System.out.println("a: " + counts.get("a")); System.out.println("b: " + counts.get("b")); System.out.println("size: " + counts.size()); ConcurrentHashMap<String, Integer> lengths = new ConcurrentHashMap<>(); for (String word : words) { lengths.computeIfAbsent(word, String::length); } System.out.println("lengths: " + lengths); System.out.println("putIfAbsent a: " + lengths.putIfAbsent("a", 99)); System.out.println("after: " + lengths.get("a")); System.out.println("replace b: " + lengths.replace("b", 1, 42)); System.out.println("b now: " + lengths.get("b")); System.out.println("null for missing: " + lengths.get("zz")); } }

javac -Xlint:all Maps.java
java Maps

a: 200000
b: 100000
size: 3
lengths: {a=1, b=1, c=1}
putIfAbsent a: 1
after: 1
replace b: true
b now: 42
null for missing: null

The atomic methods of the map

The first three lines are the counts: a appears twice in the input and each appearance counted a hundred thousand, so 200,000, and b and c have 100,000 each. The size is three because the map has three keys.

The rest of the program is the API of the class, and each method is one atomic step: merge reads and writes together; computeIfAbsent creates once; putIfAbsent answers the value that was already there, which is 1 and not null; replace(key, expected, value) writes only if the value is still the expected one, which is the compare-and-set of lesson 118 with a map around it. The last line is the one thing the class does not allow: a null key or a null value, so a missing key answers null and nothing else can.

BlockingQueue

A queue between threads is a queue that blocks when it is empty or full, and that is what makes a producer and a consumer easy to write: put waits for space, take waits for an element, and neither needs a lock in the source:

import java.util.concurrent.ArrayBlockingQueue; import java.util.concurrent.BlockingQueue; import java.util.concurrent.TimeUnit; public class Queue { public static void main(String[] args) throws InterruptedException { BlockingQueue<String> queue = new ArrayBlockingQueue<>(2); Thread producer = new Thread(() -> { for (String item : new String[] {"one", "two", "three"}) { try { queue.put(item); } catch (InterruptedException e) { return; } } }, "producer"); Thread consumer = new Thread(() -> { for (int i = 0; i < 3; i++) { try { String item = queue.take(); System.out.println("took " + item); } catch (InterruptedException e) { return; } } }, "consumer"); producer.start(); consumer.start(); producer.join(); consumer.join(); System.out.println("remaining: " + queue.size()); System.out.println("offer to a full queue: " + fullQueue()); } static boolean fullQueue() throws InterruptedException { BlockingQueue<String> small = new ArrayBlockingQueue<>(1); small.put("only"); boolean offered = small.offer("second", 10, TimeUnit.MILLISECONDS); return offered; } }

javac -Xlint:all Queue.java
java Queue

took one
took two
took three
remaining: 0
offer to a full queue: false

A producer and a consumer

The queue holds two items, so the producer waits on the third until the consumer has taken one, and the program finishes without either thread knowing about the other. The three items come out in the order they went in, which is the promise of a queue and the reason a buffer is a queue and not a set.

The last line is the third method of the family: offer with a timeout answers false instead of waiting for ever, offer without one answers at once, and add throws when the queue is full. A producer that must never stall uses one of the first two; a program that would rather lose a message than block is a program that has decided so.

Which collection for which thread

ConcurrentHashMap for a map shared by threads, and ConcurrentMap as the type of a field. CopyOnWriteArrayList for a list that is read often and written rarely, because every write copies it. ArrayBlockingQueue and LinkedBlockingQueue for a buffer between threads, the first with a fixed size and the second without. ConcurrentLinkedQueue for a queue that never blocks.

What none of them does is make a sequence of two calls atomic. Two put calls are two operations, and a reader may see the state between them; the rule of lesson 118 applies to collections as well. The compound operations that are safe are the ones the interface states: computeIfAbsent, merge, replace, putIfAbsent.

Exercises

  1. Run Maps with eight threads and half the loop and predict the counts before you run it.
  2. Replace merge with a get and a put in Maps and describe the counts.
  3. Give the queue a consumer that takes four items and watch it block.
  4. Use ConcurrentLinkedQueue for the same producer and consumer and explain what the consumer must do when the queue is empty.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Why is ConcurrentHashMap faster than a synchronised map?

    Answer

    It locks parts of the table instead of the whole map

    The finer lock lets two threads write different parts of the table at the same time.

  2. What does putIfAbsent answer?

    Answer

    The value that was already there, or null when it put the new one

    The answer is the old value, which is why the program prints 1 for the key a.

  3. What does take do on an empty BlockingQueue?

    Answer

    It waits until an element arrives

    The blocking is the point of the interface, and poll is the non-waiting form.

  4. What does this program print? import java.util.concurrent.ConcurrentHashMap; public class Q1 { public static void main(String[] args) { ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(); map.merge("a", 1, Integer::sum); map.merge("a", 1, Integer::sum); System.out.println(map.get("a")); System.out.println(map.computeIfAbsent("b", k -> 5)); System.out.println(map.size()); } }

    Answer

    2 / 5 / 2

    The two merges sum to two, the computeIfAbsent stores and returns five, and two keys are there.

  5. What does replace(key, expected, value) do?

    Answer

    Writes the value only if the current one is the expected one

    It is the compare-and-set of the map, and it answers whether it wrote.

  6. Which queue method waits for space and throws when interrupted?

    Answer

    put

    put blocks, offer answers with a boolean, and add throws when the queue is full.

  7. What does a CopyOnWriteArrayList do on every write?

    Answer

    Copies the whole array, which is why it suits a read-heavy list

    The copy is what makes reads lock-free, and it is the cost of every write.

  8. What does this program print? import java.util.concurrent.ArrayBlockingQueue; import java.util.concurrent.BlockingQueue; public class Q2 { public static void main(String[] args) throws InterruptedException { BlockingQueue<String> queue = new ArrayBlockingQueue<>(2); queue.put("a"); queue.put("b"); System.out.println(queue.size()); System.out.println(queue.offer("c")); System.out.println(queue.poll()); System.out.println(queue.offer("c")); } }

    Answer

    2 / false / a / true

    The two puts fill the queue, the offer fails, the poll frees a slot, and the next offer fits.

  9. Why are two separate put calls not atomic?

    Answer

    A reader may see the state between them

    Each call is atomic on its own, and the pair is not one operation.

  10. Which type should a shared map field declare?

    Answer

    ConcurrentMap, with ConcurrentHashMap as the value

    The interface says what the code promises, and the concurrent one promises the thread safety.

The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.

Article author: Arthur Isaev