Thread-Safe Collections in Java

← Back to the section

Java's standard collections — HashMap, ArrayList, LinkedList — aren't designed to be used from several threads at once. As soon as multiple threads start reading from and writing to a single collection, the program starts behaving unpredictably. Java ships with ready-made alternatives — and each one has its own internal algorithm for thread safety, with its own strengths and limits.

What goes wrong with regular collections

Imagine two threads adding elements to an ArrayList at the same time. Internally, ArrayList keeps an array and a size counter. If both threads read the counter simultaneously (say, it equals 5), both will write a new element at position 5 — and one element gets lost. The counter still becomes 6, even though two elements were actually added.

With HashMap the situation is even more dangerous. When adding an element, the map sometimes rebuilds its internal structure (rehash). If two threads hit a rehash at the same time, you can end up with an infinite loop during traversal or lose data — and in Java 7 and earlier this would hang applications.

Typical symptoms:

• lost entries (you added an element, but it never shows up);
• ArrayIndexOutOfBoundsException or ConcurrentModificationException in unexpected places;
• the program hangs for no visible reason.

Every thread-safe collection solves this in one of three ways: with a lock (a gate around the data), with copying (write into a copy, read without a lock), or with non-blocking atomic operations (CAS — compare-and-swap). The difference between them is exactly the difference in speed and in limits.

ConcurrentHashMap — a thread-safe map

ConcurrentHashMap is the primary replacement for HashMap in multithreaded code. Several threads can work with different parts of the map at the same time without getting in each other's way.

live example

import java.util.concurrent.ConcurrentHashMap;

public class CounterDemo {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> counter = new ConcurrentHashMap<>();
        counter.put("events", 1);

        // compute: reading the old value and writing the new one is one indivisible step
        counter.compute("events", (key, value) -> value == null ? 1 : value + 1);

        // merge — the same thing, shorter for counters
        counter.merge("events", 1, Integer::sum);

        System.out.println(counter);
    }
}

The key advantage is that the methods compute, merge, and computeIfAbsent run atomically: no other thread can slip in between reading the old value and writing the new one. This eliminates the classic "read before you locked" mistake — here it is in plain sight, counted two ways in two threads:

live example

import java.util.concurrent.ConcurrentHashMap;

public class LostUpdateDemo {
    public static void main(String[] args) throws InterruptedException {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        map.put("getPut", 0);
        map.put("merge", 0);

        Runnable job = () -> {
            for (int i = 0; i < 50_000; i++) {
                // wrong: another thread slips in between get and put
                map.put("getPut", map.get("getPut") + 1);
                // right: one indivisible operation
                map.merge("merge", 1, Integer::sum);
            }
        };

        Thread a = new Thread(job);
        Thread b = new Thread(job);
        a.start();
        b.start();
        a.join();
        b.join();

        System.out.println("get + put: " + map.get("getPut") + " of 100000");
        System.out.println("merge:     " + map.get("merge") + " of 100000");
    }
}

The first line differs on every run and falls short of one hundred thousand — those are lost updates. The second is always exactly one hundred thousand.

ConcurrentHashMap does not allow null as a key or a value — unlike HashMap. That is not a whim but protection from an ambiguity you cannot resolve: in a plain HashMap the question "get returned null — is the key missing, or is the value null?" is answered by containsKey. In a concurrent map the pair get + containsKey is not atomic — between the two calls another thread could insert or remove the entry, so there is no consistent answer. Banning null makes get(key) == null unambiguous: the key is missing. If you need an "empty value", use a marker object.

Inside: lock striping and CAS

Internally a HashMap is an array of buckets: a key lands in one of the array slots according to its hash. The problem with concurrency is that a single lock over the whole map would kill parallelism: threads working with different keys would still wait for each other.

ConcurrentHashMap splits the lock up. In Java 7 the map was divided into 16 segments (Segment), each with its own ReentrantLock — this is called lock striping: a key lands in a segment according to the high bits of its hash, and two keys from different segments lock independently.

In Java 8+ the lock became finer still — at the level of an individual bucket:

• if the bucket is empty, the first node is placed with no lock at all, by an atomic CAS (compare-and-swap: "write this, but only if the slot is still empty");
• if the bucket already holds elements (a collision), the thread takes synchronized on the head of that bucket only;
• when a bucket's chain grows long (8+ elements with a table of 64 or more), it turns into a balanced tree, so lookups there stay fast.

Limits worth remembering:

• Iterators are weakly consistent: traversal never throws ConcurrentModificationException, but it also gives no guarantee that you will see changes made by other threads while you iterate. It is a view "somewhere between" the start and the end of the traversal, not a strict snapshot of one moment.
• size() is approximate: to avoid locking the whole map for a counter, the size is spread across several counter cells (CounterCell) that size() adds up — under active writes the value can lag slightly.
• Atomicity covers a single key only. compute/merge are indivisible for one key, but you cannot atomically change two keys at once or "lock the whole map" — that calls for an external lock or a different structure.

CopyOnWriteArrayList — a list for rare writes

CopyOnWriteArrayList solves the problem differently: on every modification (adding, removing) it creates a full copy of the internal array. You can see it in a single thread — start a traversal and append an element in the middle of it:

live example

import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;

public class SnapshotDemo {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> listeners = new CopyOnWriteArrayList<>();
        listeners.add("listener-1");
        listeners.add("listener-2");

        Iterator<String> walk = listeners.iterator();
        listeners.add("listener-3");   // a write after the traversal started — a new copy

        while (walk.hasNext()) {
            System.out.println("traversal sees: " + walk.next());
        }
        System.out.println("the list already holds: " + listeners.size());
    }
}

The traversal prints two elements while the list already holds three: the iterator keeps the array that existed when it was created.

Inside: copy on write

Inside there is a volatile reference to an array. A read (get, traversal) simply takes the current array through that reference — with no lock at all, which is why readers never wait. A write, on the other hand:

1. takes the single lock shared by all writers (they queue up one after another);
2. copies the whole array into a new, slightly larger one;
3. applies the change to the copy;
4. flips the reference to the new array with a volatile write.

A reader that started its traversal before step 4 keeps working with the old array — the very snapshot that was current when it started. That is why iteration is safe and never throws ConcurrentModificationException: the array under the reader does not change at all, it is simply replaced wholesale.

Limits:

• Every write is O(n) plus a fresh allocation: the whole array is copied. On large lists or frequent changes that costs both time and memory (pressure on the garbage collector).
• The iterator sees a stale snapshot: if someone adds an element while you traverse, you will not see it in that traversal. And iterator().remove() is not supported — it throws UnsupportedOperationException.

When it fits: the list is read very often and written rarely (event handlers, rarely changing configuration). When it does not — frequent additions and removals.

Collections.synchronizedX — wrappers and their limits

The methods Collections.synchronizedList, Collections.synchronizedMap, and their siblings wrap a regular collection and add synchronized to every method — on one shared mutex (the wrapper object).

Internally this is one coarse lock over the whole collection: at any moment exactly one thread works with it while the rest wait. There is no real concurrency — unlike ConcurrentHashMap, where threads run in parallel across different buckets. On top of that, iteration is not protected: if one thread traverses the list while another removes an element, you get a ConcurrentModificationException. You have to lock the whole traversal by hand:

live example

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SyncWrapperDemo {
    public static void main(String[] args) {
        List<String> syncList = Collections.synchronizedList(new ArrayList<>());
        syncList.add("a");   // every call is protected
        syncList.add("b");

        synchronized (syncList) {   // the traversal you have to close yourself
            for (String s : syncList) {
                System.out.println(s);
            }
        }
    }
}

This is inconvenient and easy to forget. That's why ConcurrentHashMap and CopyOnWriteArrayList are preferable in new code — they were designed for concurrency rather than adapted to it.

BlockingQueue — a bridge between producer and consumer

BlockingQueue is a special kind of queue that blocks a thread when an operation can't be performed right now:

• put blocks the producer if the queue is full;
• take blocks the consumer if the queue is empty.

This is a ready-made primitive for the classic producer-consumer scheme. The capacity below is deliberately tiny — two elements: the producer runs ahead, hits a full queue and waits for the consumer, and none of that needs manual synchronization.

live example

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class ProducerConsumerDemo {
    private static final String STOP = "stop";

    public static void main(String[] args) throws InterruptedException {
        BlockingQueue<String> queue = new ArrayBlockingQueue<>(2);   // capacity 2

        Thread producer = new Thread(() -> {
            try {
                for (int i = 1; i <= 5; i++) {
                    queue.put("task-" + i);   // waits if the queue is full
                }
                queue.put(STOP);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });

        Thread consumer = new Thread(() -> {
            try {
                String task;
                while (!(task = queue.take()).equals(STOP)) {   // waits if the queue is empty
                    System.out.println("processing: " + task);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });

        producer.start();
        consumer.start();
        producer.join();
        consumer.join();
    }
}

The last element is an end marker (STOP): otherwise the consumer would fall asleep on an empty queue forever and the program would never finish.

Inside: one lock versus two

The "wait until you can" behaviour is built on ReentrantLock + Condition — a waiting room where a thread sleeps and gets woken when the condition changes. How many locks there are, though, differs fundamentally between the two main implementations:

• ArrayBlockingQueue (a ring buffer of fixed capacity) — one lock and two conditions (notEmpty, notFull). Producer and consumer share that lock: while one works with the queue, the other waits.
• LinkedBlockingQueue (linked nodes) — two separate locks: putLock at the tail and takeLock at the head. The producer appends at the tail while the consumer takes from the head at the same time, without getting in each other's way. An atomic counter (AtomicInteger) keeps track of the element count.

There are other implementations too: PriorityBlockingQueue (ordered by priority) and SynchronousQueue (hands an element over directly with no buffer — the producer waits for a consumer). BlockingQueue is the foundation of ExecutorService — it is exactly how tasks are handed off to the pool's threads.

Limits: in ArrayBlockingQueue the single lock caps throughput when both sides are busy, and the capacity is fixed forever. LinkedBlockingQueue defaults to a capacity of Integer.MAX_VALUE — effectively unbounded: if the producer is steadily faster than the consumer, the queue grows until OutOfMemoryError. Setting the capacity explicitly is almost always the right call.

ConcurrentLinkedQueue — a queue without locks

Sometimes locks aren't needed at all. ConcurrentLinkedQueue is an unbounded queue that gets by without a single lock, on atomic CAS alone. It is built on the Michael-Scott queue algorithm — a classic of non-blocking data structures.

live example

import java.util.concurrent.ConcurrentLinkedQueue;

public class LockFreeQueueDemo {
    public static void main(String[] args) {
        ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();
        queue.offer("a");   // appending without a lock
        queue.offer("b");

        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());   // empty queue — null, not waiting
    }
}

Inside: appending by CAS with a retry

The queue is a linked list of nodes with pointers to the head and the tail. Appending an element goes like this:

1. create a new node;
2. try to attach it to the next field of the last node with an atomic CAS: "set this reference, but only if it is still null";
3. if the CAS succeeded — move the tail to the new node (another CAS);
4. if the CAS failed (another thread got there first) — retry from step 2.

Nobody blocks anybody: instead of waiting on a lock, a thread does one extra lap of the loop in the worst case. Threads even help each other out — any thread that notices a lagging tail can move it.

Limits:

• There is no blocking — both a plus and a minus. For the producer-consumer scheme ConcurrentLinkedQueue is a poor fit: it has no take to put the consumer to sleep on an empty queue — the third poll() above simply returned null. You would have to spin on poll() in a loop (busy-wait) and burn the processor. For that scenario use LinkedBlockingQueue.
• size() is O(n) and imprecise: counting means walking every node, and concurrent changes make the result approximate. isEmpty() is cheap; size() on a hot path is not.
• The queue is unbounded: just like LinkedBlockingQueue by default, a mismatch in speeds leaks memory.

How to choose the right collection

In short

• Thread safety is built in three ways: locking, copy on write, and non-blocking CAS — speed and limits follow from that choice.
• ConcurrentHashMap locks a single bucket rather than the whole map (an empty one it writes by CAS), so threads run in parallel; the price is weakly consistent iterators, an approximate size(), and atomicity only inside a single call: a get + put pair loses updates here too.
• CopyOnWriteArrayList copies the array on every write and flips the reference — perfect for "read often, write rarely", expensive under frequent changes; the iterator sees an old snapshot.
• Collections.synchronizedX is one coarse lock: no real concurrency, and iteration has to be synchronized by hand.
• BlockingQueue blocks a thread instead of failing: ArrayBlockingQueue has one lock and a fixed capacity, LinkedBlockingQueue has two locks (head/tail) but is unbounded by default and can eat all the memory.
• ConcurrentLinkedQueue works without locks, on CAS (the Michael-Scott algorithm); in exchange it has no blocking take, and size() is O(n).

What to read next

• Atomic variables and CAS — how CAS works, the thing ConcurrentHashMap and ConcurrentLinkedQueue stand on.
• Explicit locks: Lock and ReentrantLock — the very lock that blocking queues wait on.
• ExecutorService and thread pools — how BlockingQueue is used inside thread pools.
• Race conditions — where concurrency bugs come from and how to find them.