Concurrent Collections, Queues & Lock-Free Structures — Interview Questions

How to use this lesson

Choosing the right concurrent structure is a design decision. Explain it with:

• the read/write ratio;
• ordering needs;
• blocking vs non-blocking hand-off;
• memory cost.

And know that ConcurrentHashMap changed fundamentally in Java 8. "Segments" is an outdated answer.

Q1. How does ConcurrentHashMap avoid ConcurrentModificationException?

Short answer: Its iterators and views are weakly consistent. They traverse the table's bins directly, using volatile reads, without a modCount check. Concurrent inserts and removals may or may not be seen, but the iterator never throws, never returns an element twice, and never breaks. During a resize, bins that have been moved are marked with forwarding nodes, which point iterators and readers to the new table. So traversal stays valid while other threads write.

Learn it in depth → ConcurrentHashMap & CopyOnWriteArrayList

Q2. How does ConcurrentHashMap differ from HashMap internally, in Java 7 versus Java 8? What are its advantages over Hashtable?

Short answer:

• Java 7: the map was split into segments, each a small hash table with its own ReentrantLock (the default concurrencyLevel of 16 meant 16 segments). Writes locked one segment, and reads were mostly lock-free. Concurrency was limited to the number of segments.
• Java 8 and later: a single table of bins, like HashMap:
  • Reads are lock-free (volatile reads of the node values and links).
  • Inserting into an empty bin uses CAS, with no lock.
  • Updating a non-empty bin synchronizeds on the first node of that bin only.
  • Resizing is cooperative: several threads help transfer bins, and forwarding nodes redirect readers.
  • Long bins treeify (TreeBin).
  • Counting uses striped counter cells (like LongAdder).
• Compared with HashMap: it's thread-safe, with no null keys or values, and adds atomic compound operations: putIfAbsent, computeIfAbsent, compute, merge, replace(k, old, new), and bulk parallel operations (forEach, reduce, search with a parallelism threshold).
• Compared with Hashtable: Hashtable locks the whole table for every read and write. ConcurrentHashMap has non-blocking reads and bin-level write locking, so it scales with cores. It also has atomic compound operations (with Hashtable, "check-then-put" still needs external locking), and weakly consistent iterators instead of fail-fast ones.

Common trap: the source describes Java 7's segments as the current design. Say "segments were Java 7. Since Java 8, it uses CAS plus per-bin locking."

ConcurrentMap<String, LongAdder> hits = new ConcurrentHashMap<>();
hits.computeIfAbsent(endpoint, k -> new LongAdder()).increment();       // atomic, and contention-friendly

Q3. What happens when several threads write to a HashMap without synchronisation?

Short answer: Undefined, and dangerous:

• Lost updates: two threads inserting into the same bin overwrite each other's links.
• Corruption during resize: entries vanish or duplicate. In Java 7 and earlier, a circular list could form, making get loop forever (100% CPU).
• Wrong size(), and ConcurrentModificationException in readers.
• Visibility problems: other threads may see partially initialised nodes, or stale tables.

It only takes one unsynchronised writer to break the map for all readers. Use ConcurrentHashMap, or confine the map to one thread, or publish an immutable map.

Q4. How would you make a thread-safe HashMap without using ConcurrentHashMap?

Short answer: Options, with their trade-offs:

1. Collections.synchronizedMap(new HashMap<>()): every method synchronises on one mutex. You must hold the lock manually while iterating, and for compound actions. Simple, but coarse.
2. Wrap it with a ReentrantReadWriteLock: many concurrent readers, and exclusive writers. Good for read-heavy maps. Watch out for writer starvation, and lock-upgrade deadlocks.
3. Copy-on-write with an immutable map in a volatile/AtomicReference: readers get a lock-free, consistent snapshot. Writers copy and CAS (or lock). Ideal for rarely changing configuration or routing tables.
4. Lock striping: N locks, with a key's hash choosing its stripe (the way Java 7's CHM worked). Higher write concurrency, more complexity.
5. Thread confinement or actor-style ownership: one thread owns the map, and others send it messages.

public final class ReadMostlyRegistry<K, V> {
    private final AtomicReference<Map<K, V>> ref = new AtomicReference<>(Map.of());
    public V get(K key) { return ref.get().get(key); }                    // lock-free reads
    public void put(K key, V value) {
        ref.updateAndGet(old -> {                                         // CAS loop; the copy is O(n)
            Map<K, V> copy = new HashMap<>(old); copy.put(key, value);
            return Map.copyOf(copy);
        });
    }
}

Q5. What is CopyOnWriteArrayList used for in multithreaded applications?

Short answer: Read-mostly lists that are iterated often and modified rarely: event listener and observer lists, a set of active configuration handlers, subscriber registries, and small whitelists. Reads and iterations are lock-free, and see a consistent snapshot, even while listeners are added or removed during notification. Avoid it for large or frequently modified lists: every write copies the whole array.

Q6. Is Collections.synchronizedList() the same as CopyOnWriteArrayList?

Short answer: No.

Q7. What's the time complexity of put() and get() in ConcurrentHashMap?

Short answer: Like HashMap: O(1) on average. The worst case is O(log n) when a bin is treeified (many collisions). get is lock-free. put into an empty bin is one CAS, otherwise a short synchronized on that bin. Resizes cost O(n) in total, but threads share the work, and reads continue during them. Contention on a single hot key's bin serialises writers for that bin only.

Q8. When should you use a BlockingQueue, and when a ConcurrentLinkedQueue?

Short answer:

• BlockingQueue (ArrayBlockingQueue, LinkedBlockingQueue, and others): when consumers should wait for work, and producers should wait (or be rejected) when it's full. That means producer-consumer hand-off with back-pressure, as in thread pools and pipelines. It uses locks and conditions internally.
• ConcurrentLinkedQueue: a non-blocking, lock-free (CAS-based), unbounded queue. poll() returns null immediately when it's empty. Use it when threads never want to block (they have other work to do, or poll in an event loop), and throughput under contention matters. Because it's unbounded, you need your own back-pressure.

Key points to cover:

• LinkedTransferQueue combines both: non-blocking, with an optional blocking hand-off (transfer).

Q9. How is thread safety achieved in ConcurrentSkipListMap? What is a concurrent skip list?

Short answer: A skip list is a sorted linked list with several levels of "express lanes". Each node is promoted to higher index levels with probability ½ (random), which gives O(log n) expected search, insert and delete, without rebalancing. That's what makes it easy to make lock-free.

ConcurrentSkipListMap/Set (Java 6) implement it with CAS-based, lock-free algorithms:

• nodes are inserted and deleted by atomically swinging next pointers;
• deletion first marks a node (using a marker node), then unlinks it, so concurrent operations never see an inconsistent state;
• index levels are updated lazily.

The result is a concurrent, sorted, navigable map (floorKey, headMap, and so on) with weakly consistent iterators. It's the concurrent analogue of TreeMap. It's used for leaderboards, time-ordered event buffers, and priority-ordered schedulers read by many threads.

Q10. Which concurrent collection preserves order and supports blocking operations?

Short answer:

• FIFO order, blocking:
  • LinkedBlockingQueue (optionally bounded) and ArrayBlockingQueue (bounded, with optional fairness);
  • LinkedBlockingDeque (a blocking deque at both ends).
• Priority order, blocking: PriorityBlockingQueue (unbounded; take blocks when it's empty).
• Delay order: DelayQueue: elements become available after their delay (scheduling, retry-after, cache expiry).
• A direct hand-off: SynchronousQueue (no storage), and LinkedTransferQueue.

Q11. How would you design a concurrent LRU cache?

Short answer: In production, use Caffeine: it's concurrent, uses W-TinyLFU eviction (better hit rates than LRU), and supports size or weight bounds, expiry and statistics. If you're asked to build one, show you know the trade-offs:

• Simple: LinkedHashMap (access order) plus removeEldestEntry, guarded by one lock. It's correct, but every get is a write (it reorders the list), so reads serialise.

• Scalable: a ConcurrentHashMap for lookup, plus a separate eviction policy:

  • buffer the access events in a lock-free ring buffer (reads don't lock);
  • drain the buffer periodically, under a single lock, to update an LRU list or a sampled policy;
  • evict when the size exceeds the maximum.

  This is Caffeine's design. Accepting approximate LRU is what buys the scalability.

• Sharding: N independent LRU segments, chosen by key hash. It reduces contention, but the LRU becomes per-segment.

final class SynchronizedLru<K, V> {
    private final Map<K, V> map;
    SynchronizedLru(int max) {
        this.map = new LinkedHashMap<>(16, 0.75f, true) {
            @Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > max; }
        };
    }
    synchronized V get(K k) { return map.get(k); }                  // get mutates the access order, so it must lock
    synchronized void put(K k, V v) { map.put(k, v); }
}

Learn it in depth → Thread-Safe LRU Cache

Q12. What is a ring-buffer architecture?

Short answer: A ring (circular) buffer is a fixed-size, pre-allocated array, used as a queue, with producer and consumer sequence counters that wrap around (index = sequence & (size - 1), where the size is a power of two). Its benefits:

• no allocation per message, so no GC churn;
• cache-friendly, contiguous memory;
• bounded by design, which gives natural back-pressure: producers wait when they'd overwrite unconsumed slots;
• with a single producer, coordination needs just memory barriers, no locks.

It's used in high-throughput, low-latency systems (trading, logging: Log4j2 async loggers are built on the Disruptor), network stacks (NIC rings, io_uring), and audio and telemetry pipelines.

Q13. How does the LMAX Disruptor pattern work?

Short answer: It's a ring buffer, plus sequence-based coordination instead of queues and locks:

1. Pre-allocated event objects fill the ring. Producers claim a sequence number (a CAS, or just an increment for a single producer), write into the existing event object (no allocation), then publish the sequence.
2. Consumers (event handlers) track their own sequences, and wait on a WaitStrategy: busy-spin (lowest latency), yielding, sleeping, or blocking.
3. Dependencies between consumers form a graph: consumer B only processes up to consumer A's sequence (for example, journaling → replication → business logic). No queues are needed between stages.
4. Batching: a consumer that's behind processes everything available in one go, so it catches up efficiently.
5. Mechanical sympathy: padded sequences, avoiding false sharing, and a single writer per sequence.

The result was millions of events per second, on one thread for the business logic, with microsecond latency. It's ideal for in-process pipelines (Log4j2 async logging, exchange matching engines). It's not a distributed message queue.

Follow-up questions this topic invites — and their answers

Q: Why doesn't ConcurrentHashMap.computeIfAbsent let you call the map recursively in the mapping function? A: The mapping function runs while the bin is locked. Modifying the same map from inside it (especially keys hashing to the same bin) can deadlock, or throw IllegalStateException("Recursive update") (Java 9+). Keep mapping functions short, and free of side effects on the map.

Q: ConcurrentHashMap.newKeySet() vs Collections.synchronizedSet? A: newKeySet() returns a concurrent Set backed by a ConcurrentHashMap: lock-free reads, and weakly consistent iteration. synchronizedSet serialises all access, and needs manual locking while iterating.

Q: What does the parallelismThreshold in ConcurrentHashMap.forEach(threshold, ...) mean? A: The bulk operation runs in parallel on the common ForkJoinPool only if the map's estimated size exceeds the threshold. Use Long.MAX_VALUE for sequential, and 1 for maximum parallelism.

Q: Why are ArrayBlockingQueue's put and take slower under contention than LinkedBlockingQueue's? A: ArrayBlockingQueue uses one lock for both ends. LinkedBlockingQueue uses separate put and take locks, so producers and consumers don't contend with each other (at the cost of allocating a node per element).