Skip to content
Tutorials Center
My learning

Topics

Lesson 135 of 201 ยท Concurrency

Concurrent Collections

Learn Java concurrent collections - ConcurrentHashMap with atomic merge and compute, CopyOnWriteArrayList, BlockingQueue producer-consumer, and ConcurrentLinkedQueue.

ArrayList, HashMap and ArrayDeque are fast because they assume one thread at a time. Share them between threads without protection and you get lost entries, ConcurrentModificationException, or a corrupted structure that misbehaves later. Wrapping every access in synchronized works but turns the collection into a single-lane bridge.

The java.util.concurrent package has collections designed for sharing. They use fine-grained locking, lock-free algorithms built on atomic operations, or copy-on-write snapshots, and they offer atomic compound operations so you don't need your own locks at all. In this lesson you'll use the four that cover most real code: ConcurrentHashMap, CopyOnWriteArrayList, the BlockingQueue family and ConcurrentLinkedQueue, and you'll learn which one fits which job.

Why "synchronized" wrappers aren't enough

Collections.synchronizedList(list) and Collections.synchronizedMap(map) wrap a collection so that each method call holds a lock. Each single call is safe, but two problems remain:

  • Compound actions still race. if (!map.containsKey(k)) map.put(k, v); is two calls; another thread can slip in between.
  • Iteration isn't covered. You must hold the wrapper's lock for the whole loop yourself (synchronized (list) { for (...) ... }), or risk ConcurrentModificationException.

And because one lock guards everything, threads queue up even when they touch unrelated keys. The concurrent collections solve all three issues.

ConcurrentHashMap

ConcurrentHashMap<K, V> is the thread-safe HashMap you'll use most. Reads don't lock at all, and writes lock only the small part of the table they touch, so many threads can read and write at the same time. It has the full HashMap API, and its compound methods are atomic:

Method Atomic behavior
putIfAbsent(k, v) adds only if the key is missing
computeIfAbsent(k, fn) creates a value once per key, even if many threads ask at the same time
compute(k, fn) / computeIfPresent(k, fn) replaces the value based on the old one
merge(k, v, fn) inserts v or combines it with the old value
remove(k, v) / replace(k, old, new) conditional updates, like compareAndSet for entries

The next example counts words with eight threads, first with the tempting get-then-put pattern, then with merge.

Java get-then-put race vs merge

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Both maps are ConcurrentHashMap, so neither gets corrupted, yet the get-then-put version usually loses counts: two threads read the same old value and both write old + 1. A thread-safe collection makes each call safe; it can't make your sequence of calls atomic. Use merge and compute, which run the whole read-modify-write while holding the entry's lock.

(Why 26,672 for green? Each thread loops 20,000 times over a six-word array, so green, at index 1, comes up 3,334 times per thread, and 8 ร— 3,334 = 26,672.)

Rules and extras

  • No null keys or values. get returning null must unambiguously mean "absent", so put(k, null) throws NullPointerException.
  • Keep compute functions short. While compute, computeIfAbsent or merge runs your function, other updates to that part of the map wait. Never do I/O there, and never modify the same map from inside the function.
  • Iterators are weakly consistent. They never throw ConcurrentModificationException, and they may or may not show changes made during the loop.
  • size() is an estimate while other threads are writing. mappingCount() returns a long for very large maps.
  • Concurrent sets: ConcurrentHashMap.newKeySet() gives you a thread-safe Set backed by the map.
  • Bulk operations such as forEach(parallelismThreshold, ...), reduceValues(...) and search(...) can process big maps in parallel. A threshold of Long.MAX_VALUE runs them sequentially; 1 gives maximum parallelism.
Java computeIfAbsent, newKeySet and bulk operations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

computeIfAbsent created exactly three sets, one per city, even though several threads asked for the same city at the same time. The duplicate "ana in Lisbon" signup was dropped by the concurrent key set. The cities may print in a different order on another JVM, because hash map order is never guaranteed.

CopyOnWriteArrayList

CopyOnWriteArrayList takes the opposite approach: every write (add, set, remove) copies the whole internal array, and every iterator walks the snapshot that existed when it was created. Readers never lock and never see a half-done change, and you can modify the list while iterating without exceptions. The price: writes cost O(n) and allocate a new array every time.

That trade-off is perfect for lists that are read constantly and changed rarely, like event listeners, plugins, or configuration entries, and terrible for lists that change often.

Java Snapshot iteration with CopyOnWriteArrayList

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

During the first event, the one-shot listener removed itself and added a new one, but the loop kept walking its snapshot, so the late joiner only hears the second event. The same trick on an ArrayList throws ConcurrentModificationException (Iterators). CopyOnWriteArraySet is the set version, backed by the same mechanism.

BlockingQueue: producer-consumer done right

A BlockingQueue adds waiting to the queue operations from Queues, Deques and PriorityQueue. A consumer that calls take() sleeps until an item arrives; a producer that calls put() on a full bounded queue sleeps until there's room. This is the cleanest way to hand work between threads, and it replaces hand-written wait/notify code (Inter-Thread Communication).

Throws Returns special value Blocks Waits with timeout
Insert add(e) offer(e) โ†’ false put(e) offer(e, time, unit)
Remove remove() poll() โ†’ null take() poll(time, unit)
Examine element() peek() โ†’ null

A bounded queue also gives you backpressure: when consumers fall behind, producers slow down automatically instead of filling memory.

Java Producers, consumers and a poison pill

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

All 12 jobs are processed and the queue ends empty, while the two consumers share the work in an order that changes between runs. The poison pill is a common shutdown technique: after the producers finish, put one special marker per consumer so each one knows to stop. An alternative is to interrupt the consumers, or to use an executor, which is a thread pool with a blocking queue built in.

The BlockingQueue implementations:

  • ArrayBlockingQueue: bounded, array-based, one lock; predictable memory. A good default.
  • LinkedBlockingQueue: optionally bounded (unbounded by default!), separate locks for head and tail, so producers and consumers contend less.
  • PriorityBlockingQueue: unbounded, hands out the smallest element first (natural order or a comparator).
  • DelayQueue: elements become available only after their delay expires; good for retry schedules and caches.
  • SynchronousQueue: no capacity at all; each put waits for a matching take. Executors.newCachedThreadPool uses it.
  • LinkedTransferQueue: unbounded; transfer(e) waits until a consumer actually receives the element.
  • LinkedBlockingDeque: a blocking double-ended queue, used for work-stealing designs.

Bulk operations, timeouts and FutureTask

The blocking methods in the table above have timed versions that give up instead of waiting forever. offer(e, time, unit) returns false if there was no room in time, and poll(time, unit) returns null if nothing arrived. Timed calls are what make a consumer loop stoppable and a producer able to report "the system is overloaded" instead of hanging.

drainTo(collection) moves every currently available element into a collection in one call and returns how many it moved; drainTo(collection, max) caps the count. A batching consumer calls take() once to wait for work, then drainTo to grab whatever else piled up, which means one lock acquisition per batch instead of one per item. Unlike iterating the queue, drainTo removes the elements atomically with respect to other threads.

Two details separate the main implementations. Bounds: ArrayBlockingQueue always needs a capacity, while LinkedBlockingQueue is bounded only if you pass one, and the default is Integer.MAX_VALUE, which means a slow consumer lets the queue eat all your memory. Fairness: new ArrayBlockingQueue<>(n, true) hands waiting threads access in first-come order, preventing starvation at the cost of throughput; the unfair default is faster. LinkedBlockingQueue has no fairness option but uses separate head and tail locks.

Java Timed offer/poll, drainTo and capacity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

FutureTask: a Runnable that is also a Future

FutureTask<V> implements both Runnable and Future<V>. Give it a Callable (or a Runnable plus a fixed result); you can then run it on a plain Thread, submit it to an executor, or call run() yourself, and any thread can get() the outcome later. It runs the work at most once, supports cancel(true) (which interrupts the running thread), and wraps an exception from the task in ExecutionException. When you call executor.submit(callable), the executor creates exactly such a task behind the scenes. Use FutureTask directly when you need a one-shot result computed lazily and shared, or when you must hand a result-producing job to an API that only accepts Runnable. For chains of dependent steps, CompletableFuture is the better tool.

Java FutureTask as Runnable and Future

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

ConcurrentLinkedQueue and ConcurrentLinkedDeque

When you need a thread-safe queue but nobody should ever wait on it, use ConcurrentLinkedQueue (or ConcurrentLinkedDeque for both ends). They are unbounded and lock-free, built on compare-and-set, so offer and poll never block; poll simply returns null when the queue is empty. They're ideal for collecting results from many threads, or as a work list that threads poll in a loop.

Java
var results = new ConcurrentLinkedQueue<String>();
// any number of threads:
results.offer("result from " + Thread.currentThread().getName());
// later, any thread:
String next = results.poll();            // null if empty, never blocks

One gotcha: size() on these classes walks the whole queue (O(n)) and may be stale. Use isEmpty() when that's what you mean.

Sorted concurrent maps and sets

ConcurrentSkipListMap and ConcurrentSkipListSet are the concurrent counterparts of TreeMap and TreeSet: keys stay sorted, and you get firstKey, ceilingKey, headMap and the other navigation methods, with O(log n) lock-free operations. Use them for leaderboards, time-ordered event indexes, or any shared data you need in order.

Choosing a concurrent collection

Need Use
shared key-value map ConcurrentHashMap (use merge/compute for updates)
shared set ConcurrentHashMap.newKeySet()
sorted shared map or set ConcurrentSkipListMap / ConcurrentSkipListSet
list read often, changed rarely (listeners) CopyOnWriteArrayList
hand work from producers to consumers, with waiting ArrayBlockingQueue or LinkedBlockingQueue (bounded)
non-blocking shared queue or result bag ConcurrentLinkedQueue / ConcurrentLinkedDeque
delayed or prioritized work DelayQueue / PriorityBlockingQueue
list or map with heavy writes and consistent multi-step changes a regular collection guarded by a lock

Don't forget the simplest option: if threads don't need to see each other's data while working, give each thread its own ArrayList or HashMap and merge them at the end. No sharing beats any concurrent collection. Fork/Join, up next, is built on exactly that idea.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Several threads run Integer c = map.get(k); map.put(k, c == null ? 1 : c + 1); on a ConcurrentHashMap. What can happen?

    Each call is thread-safe, but the read-then-write sequence isn't atomic. Use map.merge(k, 1, Integer::sum) instead.
  2. 2. What happens when you call put("key", null) on a ConcurrentHashMap?

    ConcurrentHashMap rejects null keys and values so that a null from get() always means the key is absent.
  3. 3. A thread iterates over a CopyOnWriteArrayList while another thread adds an element. What does the iterating thread see?

    Iterators of copy-on-write collections walk an immutable snapshot, so they never throw and never see later changes.
  4. 4. Which BlockingQueue method waits until space is available in a full bounded queue?

    put blocks while the queue is full. offer returns false immediately, and add throws IllegalStateException.
  5. 5. Which collection fits a list of event listeners that is read on every event but changed only at startup?

    CopyOnWriteArrayList gives lock-free, exception-free iteration and makes rare writes pay the copying cost.

Summary

  • Synchronized wrappers make single calls safe but not compound actions or iteration; concurrent collections fix both and scale better.
  • ConcurrentHashMap: lock-free reads, atomic merge, compute, computeIfAbsent and putIfAbsent; no nulls; weakly consistent iterators; newKeySet() for sets.
  • A thread-safe collection doesn't make your sequence of calls atomic; use the atomic compound methods.
  • CopyOnWriteArrayList: snapshot iteration, costly writes; ideal for listeners and rarely changing lists.
  • BlockingQueue (put/take, timed offer/poll) is the standard producer-consumer tool; bounded queues give backpressure; poison pills stop consumers.
  • ConcurrentLinkedQueue/Deque are non-blocking and lock-free; ConcurrentSkipListMap/Set stay sorted.

Next: The Fork/Join Framework, where you'll split big problems into small tasks that run in parallel.