{"title":"Concurrent Collections","description":null,"content":"# Concurrent Collections\n\nA HashMap shared between threads. One thread reads while another writes. Suddenly, your application hangs in an infinite loop or throws a `ConcurrentModificationException`.\n\nStandard collections are not designed for concurrent access. Using them in multithreaded code leads to data corruption, infinite loops, and crashes.\n\n**Concurrent collections** solve this problem. They are designed from the ground up for safe, efficient access by multiple threads.\n\nIn this article, we'll explore:\n\n- Why standard collections fail in concurrent code\n- Different approaches to thread-safe collections\n- How concurrent collections work internally\n- When to use each type\n- Common patterns and pitfalls\n\n---\n\nIf you're enjoying this newsletter and want to get even more value, consider becoming a **[paid subscriber](https://blog.algomaster.io/subscribe)**.\n\nAs a paid subscriber, you'll unlock all **premium articles** and gain full access to all **[premium courses](https://algomaster.io/newsletter/paid/resources)** on **[algomaster.io](https://algomaster.io)**.\n\n[Unlock Full Access](undefined)\n\n---\n\n## 1. The Problem with Standard Collections\n\nStandard collections like ArrayList, HashMap, and LinkedList are designed for single-threaded use. They have no synchronization, and their internal state can become corrupted when accessed by multiple threads.\n\n### What Goes Wrong\n\n\n```java\nMap map = new HashMap<>();\n\n// Thread 1: Adding entries\nfor (int i = 0; i < 10000; i++) {\n map.put(\"key\" + i, i);\n}\n\n// Thread 2: Iterating\nfor (String key : map.keySet()) {\n System.out.println(map.get(key));\n}\n```\n\n\nRunning these concurrently can cause:\n\n- **ConcurrentModificationException** during iteration\n- **Infinite loops** (HashMap's internal linked list becomes circular)\n- **Lost updates** (entries disappear)\n- **Corrupted data** (wrong values returned)\n\n\n```mermaid\nflowchart TB\n subgraph Problem[\"Problems with Unsynchronized Collections\"]\n P1[\"ConcurrentModificationException\"]\n P2[\"Infinite Loops\"]\n P3[\"Lost Updates\"]\n P4[\"Data Corruption\"]\n end\n\n Cause[\"Multiple threads
accessing same collection\"]\n\n Cause --> P1\n Cause --> P2\n Cause --> P3\n Cause --> P4\n\n style Problem fill:#ff8787,stroke:#000,color:#000\n style Cause fill:#ffa94d,stroke:#000,color:#000\n style P1 fill:#00ceff,stroke:#000,color:#000\n style P2 fill:#00ceff,stroke:#000,color:#000\n style P3 fill:#00ceff,stroke:#000,color:#000\n style P4 fill:#00ceff,stroke:#000,color:#000\n```\n\n\n### HashMap Infinite Loop\n\nIn older implementations, concurrent modification of HashMap could cause the internal bucket chain to form a cycle, making `get()` loop forever.\n\n\n```mermaid\nflowchart LR\n subgraph Normal[\"Normal Bucket Chain\"]\n A1[\"Entry A\"] --> B1[\"Entry B\"] --> C1[\"Entry C\"] --> Null1[\"null\"]\n end\n\n subgraph Corrupted[\"Corrupted Chain (Cycle)\"]\n A2[\"Entry A\"] --> B2[\"Entry B\"] --> C2[\"Entry C\"]\n C2 --> B2\n end\n\n style Normal fill:#69db7c,stroke:#000,color:#000\n style Corrupted fill:#ff8787,stroke:#000,color:#000\n```\n\n\n---\n\n## 2. Approaches to Thread-Safe Collections\n\nThere are three main approaches to making collections thread-safe:\n\n\n```mermaid\nflowchart TD\n Root[\"Thread-Safe Collections\"]\n\n Sync[\"Synchronized Wrappers\"]\n Concurrent[\"Concurrent Collections\"]\n CopyOnWrite[\"Copy-on-Write Collections\"]\n\n Root --> Sync\n Root --> Concurrent\n Root --> CopyOnWrite\n\n SyncDesc[\"Wrap entire collection
with single lock\"]\n ConcDesc[\"Fine-grained locking
or lock-free algorithms\"]\n CowDesc[\"Copy entire structure
on modification\"]\n\n Sync --> SyncDesc\n Concurrent --> ConcDesc\n CopyOnWrite --> CowDesc\n\n style Root fill:#00ceff,stroke:#000,color:#000\n style Sync fill:#ffa94d,stroke:#000,color:#000\n style Concurrent fill:#69db7c,stroke:#000,color:#000\n style CopyOnWrite fill:#9775fa,stroke:#000,color:#000\n```\n\n\n### Comparison\n\n\n| ##### Approach | ##### Mechanism | ##### Read Performance | ##### Write Performance | ##### Best For |\n| --- | --- | --- | --- | --- |\n| Synchronized Wrappers | Single lock | Blocking | Blocking | Simple cases, low contention |\n| Concurrent Collections | Segmented/lock-free | Non-blocking | Varies | High concurrency |\n| Copy-on-Write | Copy on write | Non-blocking | Expensive | Read-heavy workloads |\n\n\n---\n\n## 3. Synchronized Wrappers\n\nThe simplest approach is wrapping a standard collection with synchronization:\n\n\n```java\nList syncList = Collections.synchronizedList(new ArrayList<>());\nMap syncMap = Collections.synchronizedMap(new HashMap<>());\nSet syncSet = Collections.synchronizedSet(new HashSet<>());\n```\n\n\nEvery method acquires a lock on the wrapper object before delegating to the underlying collection.\n\n\n```mermaid\nflowchart LR\n subgraph Wrapper[\"Synchronized Wrapper\"]\n Lock[\"Lock\"]\n Method[\"Method Call\"]\n Delegate[\"Delegate to
underlying collection\"]\n end\n\n T1[\"Thread 1\"] -->|\"blocked\"| Lock\n T2[\"Thread 2\"] -->|\"waiting\"| Lock\n Lock --> Method --> Delegate\n\n style Wrapper fill:#ffa94d,stroke:#000,color:#000\n style Lock fill:#ff8787,stroke:#000,color:#000\n style T1 fill:#00ceff,stroke:#000,color:#000\n style T2 fill:#9775fa,stroke:#000,color:#000\n```\n\n\n### Problems with Synchronized Wrappers\n\n**1. Compound operations are not atomic:**\n\n\n```java\nMap map = Collections.synchronizedMap(new HashMap<>());\n\n// NOT thread-safe! Check-then-act race condition\nif (!map.containsKey(\"key\")) {\n map.put(\"key\", 1); // Another thread might put between check and put\n}\n```\n\n\n**2. Iteration requires manual synchronization:**\n\n\n```java\nMap map = Collections.synchronizedMap(new HashMap<>());\n\n// Must synchronize during iteration\nsynchronized (map) {\n for (String key : map.keySet()) {\n System.out.println(map.get(key));\n }\n}\n```\n\n\n**3. Poor scalability:**\n\nAll operations use the same lock. Even read operations block each other.\n\n---\n\n## 4. ConcurrentHashMap\n\n`ConcurrentHashMap` is the most commonly used concurrent collection. It provides thread-safe operations without locking the entire map.\n\n### How It Works\n\nInstead of one lock for the entire map, ConcurrentHashMap uses fine-grained locking at the bucket level. Different threads can access different buckets concurrently.\n\n\n```mermaid\nflowchart TB\n subgraph SyncMap[\"Synchronized HashMap\"]\n SLock[\"Single Lock\"]\n SB1[\"Bucket 0\"]\n SB2[\"Bucket 1\"]\n SB3[\"Bucket 2\"]\n SB4[\"Bucket 3\"]\n SLock --> SB1\n SLock --> SB2\n SLock --> SB3\n SLock --> SB4\n end\n\n subgraph ConcMap[\"ConcurrentHashMap\"]\n CB1[\"Bucket 0\"]\n CB2[\"Bucket 1\"]\n CB3[\"Bucket 2\"]\n CB4[\"Bucket 3\"]\n L1[\"Lock\"]\n L2[\"Lock\"]\n L3[\"Lock\"]\n L4[\"Lock\"]\n L1 --> CB1\n L2 --> CB2\n L3 --> CB3\n L4 --> CB4\n end\n\n style SyncMap fill:#ff8787,stroke:#000,color:#000\n style ConcMap fill:#69db7c,stroke:#000,color:#000\n style SLock fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nModern implementations use CAS operations and synchronized blocks only when necessary (during resizing or when buckets have many entries).\n\n### Key Features\n\n\n```java\nConcurrentHashMap map = new ConcurrentHashMap<>();\n\n// Basic operations (thread-safe)\nmap.put(\"key\", 1);\nInteger value = map.get(\"key\");\n\n// Atomic compound operations\nmap.putIfAbsent(\"key\", 1); // Put only if absent\nmap.remove(\"key\", 1); // Remove only if value matches\nmap.replace(\"key\", 1, 2); // Replace only if value matches\nmap.computeIfAbsent(\"key\", k -> 1); // Compute if absent\n\n// Atomic update\nmap.merge(\"key\", 1, Integer::sum); // Add to existing or put if absent\n```\n\n\n### Atomic Compound Operations\n\nThese operations solve the check-then-act problem:\n\n\n```java\n// Without ConcurrentHashMap (race condition)\nif (!map.containsKey(\"key\")) {\n map.put(\"key\", 1);\n}\n\n// With ConcurrentHashMap (atomic)\nmap.putIfAbsent(\"key\", 1);\n```\n\n\n\n```mermaid\nflowchart LR\n subgraph NonAtomic[\"Non-Atomic (Race Condition)\"]\n Check[\"containsKey()\"]\n Gap[\"Gap
(other thread can act)\"]\n Put[\"put()\"]\n Check --> Gap --> Put\n end\n\n subgraph Atomic[\"Atomic (Safe)\"]\n Single[\"putIfAbsent()
(single operation)\"]\n end\n\n style NonAtomic fill:#ff8787,stroke:#000,color:#000\n style Atomic fill:#69db7c,stroke:#000,color:#000\n style Gap fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n### Iteration\n\nConcurrentHashMap provides **weakly consistent** iterators. They:\n\n- Never throw ConcurrentModificationException\n- May or may not reflect modifications made after iterator creation\n- Are guaranteed to traverse elements as they existed at some point\n\n\n```java\nConcurrentHashMap map = new ConcurrentHashMap<>();\n\n// Safe to iterate without external synchronization\nfor (Map.Entry entry : map.entrySet()) {\n System.out.println(entry.getKey() + \": \" + entry.getValue());\n}\n```\n\n\n---\n\n## 5. CopyOnWriteArrayList\n\n`CopyOnWriteArrayList` takes a different approach: every modification creates a new copy of the underlying array.\n\n\n```mermaid\nflowchart TB\n subgraph Before[\"Before Write\"]\n Ref1[\"Reference\"] --> Array1[\"[A, B, C]\"]\n Reader1[\"Reader 1\"] --> Array1\n Reader2[\"Reader 2\"] --> Array1\n end\n\n subgraph After[\"After Write (add D)\"]\n Ref2[\"Reference\"] --> Array2[\"[A, B, C, D]\"]\n Reader3[\"Reader 1\"] --> Array1b[\"[A, B, C]
(old copy)\"]\n Reader4[\"Reader 2\"] --> Array1b\n NewReader[\"New Reader\"] --> Array2\n end\n\n style Before fill:#00ceff,stroke:#000,color:#000\n style After fill:#69db7c,stroke:#000,color:#000\n style Array1 fill:#ffa94d,stroke:#000,color:#000\n style Array2 fill:#ffa94d,stroke:#000,color:#000\n style Array1b fill:#9775fa,stroke:#000,color:#000\n```\n\n\n### How It Works\n\n1. Reads see a snapshot of the array at the time they started\n2. Writes copy the entire array, modify the copy, then atomically swap the reference\n3. Ongoing reads continue using the old array\n\n\n```java\nCopyOnWriteArrayList list = new CopyOnWriteArrayList<>();\n\n// Reads are lock-free\nString first = list.get(0);\n\n// Writes copy the entire array\nlist.add(\"new element\"); // Expensive for large lists\n```\n\n\n### When to Use\n\n\n| ##### Use CopyOnWriteArrayList | ##### Avoid CopyOnWriteArrayList |\n| --- | --- |\n| Read-heavy workloads (99% reads) | Write-heavy workloads |\n| Small lists | Large lists |\n| Event listeners | Frequently modified data |\n| Configuration that rarely changes | Queues or buffers |\n\n\n### CopyOnWriteArraySet\n\nA Set implementation backed by CopyOnWriteArrayList:\n\n\n```java\nCopyOnWriteArraySet set = new CopyOnWriteArraySet<>();\nset.add(\"element\"); // Copies entire backing array\n```\n\n\n---\n\n## 6. Blocking Queues\n\nBlocking queues are designed for producer-consumer scenarios. They provide blocking operations that wait for the queue to become non-empty (for consumers) or non-full (for producers).\n\n\n```mermaid\nflowchart LR\n subgraph Producers[\"Producers\"]\n P1[\"Producer 1\"]\n P2[\"Producer 2\"]\n end\n\n subgraph Queue[\"BlockingQueue\"]\n Q[\"[item1, item2, item3]\"]\n end\n\n subgraph Consumers[\"Consumers\"]\n C1[\"Consumer 1\"]\n C2[\"Consumer 2\"]\n end\n\n P1 -->|\"put()\"| Q\n P2 -->|\"put()\"| Q\n Q -->|\"take()\"| C1\n Q -->|\"take()\"| C2\n\n style Queue fill:#00ceff,stroke:#000,color:#000\n style Producers fill:#69db7c,stroke:#000,color:#000\n style Consumers fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n### BlockingQueue Operations\n\n\n| ##### Operation | ##### If Not Possible | ##### Description |\n| --- | --- | --- |\n| `put(e)` | Blocks | Insert, wait if full |\n| `take()` | Blocks | Remove, wait if empty |\n| `offer(e)` | Returns false | Insert if possible |\n| `poll()` | Returns null | Remove if possible |\n| `offer(e, timeout)` | Returns false after timeout | Insert with timeout |\n| `poll(timeout)` | Returns null after timeout | Remove with timeout |\n\n\n### Types of Blocking Queues\n\n\n```mermaid\nflowchart TD\n Root[\"BlockingQueue\"]\n\n ABQ[\"ArrayBlockingQueue\"]\n LBQ[\"LinkedBlockingQueue\"]\n PBQ[\"PriorityBlockingQueue\"]\n SQ[\"SynchronousQueue\"]\n DQ[\"DelayQueue\"]\n\n Root --> ABQ\n Root --> LBQ\n Root --> PBQ\n Root --> SQ\n Root --> DQ\n\n ABQ_Desc[\"Fixed size, array-backed\"]\n LBQ_Desc[\"Optional bound, linked nodes\"]\n PBQ_Desc[\"Unbounded, priority ordering\"]\n SQ_Desc[\"Zero capacity, direct handoff\"]\n DQ_Desc[\"Elements available after delay\"]\n\n ABQ --> ABQ_Desc\n LBQ --> LBQ_Desc\n PBQ --> PBQ_Desc\n SQ --> SQ_Desc\n DQ --> DQ_Desc\n\n style Root fill:#00ceff,stroke:#000,color:#000\n style ABQ fill:#ffa94d,stroke:#000,color:#000\n style LBQ fill:#ffa94d,stroke:#000,color:#000\n style PBQ fill:#ffa94d,stroke:#000,color:#000\n style SQ fill:#ffa94d,stroke:#000,color:#000\n style DQ fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n### ArrayBlockingQueue\n\nFixed-size queue backed by an array:\n\n\n```java\nBlockingQueue queue = new ArrayBlockingQueue<>(100);\n\n// Producer\nqueue.put(new Task()); // Blocks if queue is full\n\n// Consumer\nTask task = queue.take(); // Blocks if queue is empty\n```\n\n\n### LinkedBlockingQueue\n\nOptionally bounded queue using linked nodes. Better throughput than ArrayBlockingQueue under high contention because it uses separate locks for put and take.\n\n\n```java\n// Bounded\nBlockingQueue bounded = new LinkedBlockingQueue<>(100);\n\n// Unbounded (be careful - can cause OutOfMemoryError)\nBlockingQueue unbounded = new LinkedBlockingQueue<>();\n```\n\n\n### SynchronousQueue\n\nA queue with zero capacity. Each put must wait for a take, and vice versa. It's a direct handoff mechanism.\n\n\n```java\nSynchronousQueue queue = new SynchronousQueue<>();\n\n// Producer blocks until consumer takes\nqueue.put(new Task());\n\n// Consumer blocks until producer puts\nTask task = queue.take();\n```\n\n\n\n```mermaid\nsequenceDiagram\n participant P as Producer\n participant Q as SynchronousQueue\n participant C as Consumer\n\n P->>Q: put(task)\n Note over P: Blocked (waiting for taker)\n C->>Q: take()\n Q-->>C: task\n Note over P: Unblocked\n```\n\n\n---\n\n## 7. ConcurrentLinkedQueue and ConcurrentLinkedDeque\n\nNon-blocking, lock-free queues using CAS operations. They never block but may return null if empty.\n\n\n```java\nConcurrentLinkedQueue queue = new ConcurrentLinkedQueue<>();\n\n// Non-blocking operations\nqueue.offer(new Task()); // Always succeeds (unbounded)\nTask task = queue.poll(); // Returns null if empty\n\n// Size is O(n) - avoid in performance-critical code\nint size = queue.size(); // Traverses entire queue\n```\n\n\n### When to Use\n\n\n| ##### Use ConcurrentLinkedQueue | ##### Use BlockingQueue |\n| --- | --- |\n| Non-blocking required | Need to wait for elements |\n| Unbounded is acceptable | Need bounded capacity |\n| Size not needed frequently | Back-pressure required |\n\n\n---\n\n## 8. ConcurrentSkipListMap and ConcurrentSkipListSet\n\nThread-safe sorted collections based on skip lists. They provide O(log n) operations and maintain elements in sorted order.\n\n\n```mermaid\nflowchart TB\n subgraph SkipList[\"Skip List Structure\"]\n L3[\"Level 3\"] --- N3_1[\"1\"] --- N3_4[\"4\"] --- N3_9[\"9\"]\n L2[\"Level 2\"] --- N2_1[\"1\"] --- N2_3[\"3\"] --- N2_4[\"4\"] --- N2_7[\"7\"] --- N2_9[\"9\"]\n L1[\"Level 1\"] --- N1_1[\"1\"] --- N1_2[\"2\"] --- N1_3[\"3\"] --- N1_4[\"4\"] --- N1_5[\"5\"] --- N1_7[\"7\"] --- N1_9[\"9\"]\n end\n\n style L3 fill:#ff8787,stroke:#000,color:#000\n style L2 fill:#ffa94d,stroke:#000,color:#000\n style L1 fill:#69db7c,stroke:#000,color:#000\n```\n\n\n\n```java\nConcurrentSkipListMap map = new ConcurrentSkipListMap<>();\n\n// Sorted map operations\nmap.put(\"banana\", 2);\nmap.put(\"apple\", 1);\nmap.put(\"cherry\", 3);\n\nString first = map.firstKey(); // \"apple\"\nString last = map.lastKey(); // \"cherry\"\n\n// Range views\nSortedMap sub = map.subMap(\"apple\", \"cherry\");\n```\n\n\n### Comparison with ConcurrentHashMap\n\n\n| ##### Aspect | ##### ConcurrentHashMap | ##### ConcurrentSkipListMap |\n| --- | --- | --- |\n| Ordering | No | Sorted |\n| Get/Put | O(1) average | O(log n) |\n| Iteration order | Unpredictable | Sorted |\n| Memory | Less | More (skip list pointers) |\n| Range operations | No | Yes |\n\n\n---\n\n## 9. Choosing the Right Collection\n\n\n```mermaid\nflowchart TD\n Start[\"Need thread-safe collection?\"]\n\n Q1{\"Map or
List/Set/Queue?\"}\n Q2{\"Need sorted
order?\"}\n Q3{\"Read-heavy or
write-heavy?\"}\n Q4{\"Need blocking?\"}\n Q5{\"Need sorted?\"}\n\n CHM[\"ConcurrentHashMap\"]\n CSLM[\"ConcurrentSkipListMap\"]\n COWAL[\"CopyOnWriteArrayList\"]\n CLQ[\"ConcurrentLinkedQueue\"]\n BQ[\"BlockingQueue\"]\n CSLS[\"ConcurrentSkipListSet\"]\n\n Start --> Q1\n Q1 -->|\"Map\"| Q2\n Q2 -->|\"No\"| CHM\n Q2 -->|\"Yes\"| CSLM\n\n Q1 -->|\"List\"| Q3\n Q3 -->|\"Read-heavy\"| COWAL\n Q3 -->|\"Write-heavy\"| CLQ\n\n Q1 -->|\"Queue\"| Q4\n Q4 -->|\"Yes\"| BQ\n Q4 -->|\"No\"| CLQ\n\n Q1 -->|\"Set\"| Q5\n Q5 -->|\"Yes\"| CSLS\n Q5 -->|\"No\"| CHM\n\n style Start fill:#00ceff,stroke:#000,color:#000\n style CHM fill:#69db7c,stroke:#000,color:#000\n style CSLM fill:#69db7c,stroke:#000,color:#000\n style COWAL fill:#69db7c,stroke:#000,color:#000\n style CLQ fill:#69db7c,stroke:#000,color:#000\n style BQ fill:#69db7c,stroke:#000,color:#000\n style CSLS fill:#69db7c,stroke:#000,color:#000\n```\n\n\n### Quick Reference\n\n\n| ##### Need | ##### Use |\n| --- | --- |\n| Thread-safe HashMap | ConcurrentHashMap |\n| Thread-safe sorted Map | ConcurrentSkipListMap |\n| Thread-safe List (read-heavy) | CopyOnWriteArrayList |\n| Producer-consumer queue | BlockingQueue (ArrayBlockingQueue, LinkedBlockingQueue) |\n| Non-blocking queue | ConcurrentLinkedQueue |\n| Thread-safe sorted Set | ConcurrentSkipListSet |\n| Thread-safe Set (unsorted) | ConcurrentHashMap.newKeySet() |\n| Direct handoff between threads | SynchronousQueue |\n| Delayed task queue | DelayQueue |\n\n\n---\n\n## 10. Common Patterns\n\n### Pattern 1: Caching with ConcurrentHashMap\n\n\n```java\nConcurrentHashMap cache = new ConcurrentHashMap<>();\n\npublic Data getData(String key) {\n return cache.computeIfAbsent(key, k -> loadFromDatabase(k));\n}\n```\n\n\n### Pattern 2: Producer-Consumer with BlockingQueue\n\n\n```java\nBlockingQueue queue = new ArrayBlockingQueue<>(100);\n\n// Producer thread\npublic void produce(Task task) throws InterruptedException {\n queue.put(task); // Blocks if full\n}\n\n// Consumer thread\npublic void consume() throws InterruptedException {\n while (true) {\n Task task = queue.take(); // Blocks if empty\n process(task);\n }\n}\n```\n\n\n### Pattern 3: Event Listeners with CopyOnWriteArrayList\n\n\n```java\nCopyOnWriteArrayList listeners = new CopyOnWriteArrayList<>();\n\npublic void addListener(EventListener listener) {\n listeners.add(listener);\n}\n\npublic void fireEvent(Event event) {\n for (EventListener listener : listeners) { // Safe, no ConcurrentModificationException\n listener.onEvent(event);\n }\n}\n```\n\n\n### Pattern 4: Counting with ConcurrentHashMap\n\n\n```java\nConcurrentHashMap counters = new ConcurrentHashMap<>();\n\npublic void increment(String key) {\n counters.computeIfAbsent(key, k -> new LongAdder()).increment();\n}\n\npublic long getCount(String key) {\n LongAdder adder = counters.get(key);\n return adder != null ? adder.sum() : 0;\n}\n```\n\n\n---\n\n## 11. Common Pitfalls\n\n### Pitfall 1: Non-Atomic Check-Then-Act\n\n\n```java\nConcurrentHashMap> map = new ConcurrentHashMap<>();\n\n// Bad: Race condition between get and put\nList list = map.get(key);\nif (list == null) {\n list = new ArrayList<>();\n map.put(key, list); // Another thread might have put already\n}\nlist.add(value); // Might add to wrong list\n\n// Good: Use computeIfAbsent\nmap.computeIfAbsent(key, k -> new ArrayList<>()).add(value);\n```\n\n\n### Pitfall 2: Iterating Over Size\n\n\n```java\nConcurrentLinkedQueue queue = new ConcurrentLinkedQueue<>();\n\n// Bad: size() is O(n) and result is immediately stale\nfor (int i = 0; i < queue.size(); i++) { // Don't do this\n process(queue.poll());\n}\n\n// Good: Use isEmpty() or iterate directly\nTask task;\nwhile ((task = queue.poll()) != null) {\n process(task);\n}\n```\n\n\n### Pitfall 3: External Synchronization Defeating Purpose\n\n\n```java\nConcurrentHashMap map = new ConcurrentHashMap<>();\n\n// Bad: Defeats the purpose of ConcurrentHashMap\nsynchronized (map) {\n if (!map.containsKey(key)) {\n map.put(key, 1);\n }\n}\n\n// Good: Use built-in atomic operation\nmap.putIfAbsent(key, 1);\n```\n\n\n### Pitfall 4: Modifying Values Without Atomicity\n\n\n```java\nConcurrentHashMap map = new ConcurrentHashMap<>();\n\n// Bad: Read-modify-write is not atomic\nInteger value = map.get(key);\nmap.put(key, value + 1); // Lost update possible\n\n// Good: Use atomic update\nmap.merge(key, 1, Integer::sum);\n// Or\nmap.compute(key, (k, v) -> v == null ? 1 : v + 1);\n```\n\n\n### Pitfall 5: Unbounded Queues Causing OOM\n\n\n```java\n// Bad: Unbounded queue can grow forever\nBlockingQueue queue = new LinkedBlockingQueue<>(); // No limit!\n\n// Good: Set a reasonable bound\nBlockingQueue queue = new LinkedBlockingQueue<>(10000);\n// Or use ArrayBlockingQueue which requires a bound\nBlockingQueue queue = new ArrayBlockingQueue<>(10000);\n```\n\n\n---\n\n## 12. Performance Considerations\n\n### ConcurrentHashMap Tuning\n\n\n```java\n// Initial capacity and concurrency level\nConcurrentHashMap map = new ConcurrentHashMap<>(\n initialCapacity, // Expected number of entries\n loadFactor, // Default 0.75 is usually fine\n concurrencyLevel // Expected number of concurrent writers\n);\n```\n\n\n### Read vs Write Performance\n\n\n| ##### Collection | ##### Read | ##### Write | ##### Iteration |\n| --- | --- | --- | --- |\n| ConcurrentHashMap | Fast | Fast | Weakly consistent |\n| CopyOnWriteArrayList | Very fast | Very slow | Snapshot |\n| ConcurrentSkipListMap | O(log n) | O(log n) | Sorted |\n| BlockingQueue | Blocking | Blocking | Not recommended |\n\n\n### Memory Overhead\n\n\n```mermaid\nflowchart LR\n subgraph Memory[\"Memory Usage (Relative)\"]\n HashMap[\"HashMap
(baseline)\"]\n CHM[\"ConcurrentHashMap
(~1.5x)\"]\n CSLM[\"ConcurrentSkipListMap
(~2-3x)\"]\n COWAL[\"CopyOnWriteArrayList
(2x during write)\"]\n end\n\n style HashMap fill:#69db7c,stroke:#000,color:#000\n style CHM fill:#ffa94d,stroke:#000,color:#000\n style CSLM fill:#ff8787,stroke:#000,color:#000\n style COWAL fill:#9775fa,stroke:#000,color:#000\n```\n\n\n---\n\n## 13. Summary\n\n**Concurrent collections** provide thread-safe access to shared data without the drawbacks of synchronized wrappers.\n\n\n```mermaid\nflowchart TD\n subgraph Types[\"Concurrent Collection Types\"]\n Maps[\"Maps\"]\n Lists[\"Lists\"]\n Queues[\"Queues\"]\n Sets[\"Sets\"]\n end\n\n CHM[\"ConcurrentHashMap\"]\n CSLM[\"ConcurrentSkipListMap\"]\n COWAL[\"CopyOnWriteArrayList\"]\n ABQ[\"ArrayBlockingQueue\"]\n LBQ[\"LinkedBlockingQueue\"]\n CLQ[\"ConcurrentLinkedQueue\"]\n CSLS[\"ConcurrentSkipListSet\"]\n COWAS[\"CopyOnWriteArraySet\"]\n\n Maps --> CHM\n Maps --> CSLM\n Lists --> COWAL\n Queues --> ABQ\n Queues --> LBQ\n Queues --> CLQ\n Sets --> CSLS\n Sets --> COWAS\n\n style Types fill:#00ceff,stroke:#000,color:#000\n style Maps fill:#ffa94d,stroke:#000,color:#000\n style Lists fill:#ffa94d,stroke:#000,color:#000\n style Queues fill:#ffa94d,stroke:#000,color:#000\n style Sets fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n### Key Takeaways\n\n\n| ##### Collection | ##### Use When |\n| --- | --- |\n| ConcurrentHashMap | General-purpose thread-safe map |\n| CopyOnWriteArrayList | Read-heavy list with rare writes |\n| BlockingQueue | Producer-consumer patterns |\n| ConcurrentLinkedQueue | Non-blocking unbounded queue |\n| ConcurrentSkipListMap/Set | Need sorted concurrent collection |\n\n\n### Best Practices\n\n1. **Prefer concurrent collections** over synchronized wrappers\n2. **Use atomic compound operations** (putIfAbsent, computeIfAbsent, merge)\n3. **Choose based on read/write ratio** (CopyOnWrite for reads, ConcurrentHashMap for mixed)\n4. **Bound your queues** to prevent memory issues\n5. **Avoid size() on unbounded queues** (O(n) traversal)\n6. **Don't wrap concurrent collections** with external synchronization\n7. **Use the right BlockingQueue** for your use case\n\nConcurrent collections are essential tools for building scalable multithreaded applications. Understanding their trade-offs helps you choose the right one for each situation.\n\n---\n\nThank you for reading!\n\nIf you found it valuable, hit a like and consider subscribing for more such content every week.\n\nIf you have any questions or suggestions, leave a comment.\n\nThis post is public so feel free to share it.\n\n[Share](undefined)\n\n---\n\n**P.S.** If you're enjoying this newsletter and want to get even more value, consider becoming a **[paid subscriber](https://blog.algomaster.io/subscribe)**.\n\nAs a paid subscriber, you'll unlock all **premium articles** and gain full access to all **[premium courses](https://algomaster.io/newsletter/paid/resources)** on **[algomaster.io](https://algomaster.io)**.\n\n[Unlock Full Access](undefined)\n\n**There are [group discounts](https://blog.algomaster.io/subscribe?group=true), [gift options](https://blog.algomaster.io/subscribe?gift=true), and [referral bonuses](https://blog.algomaster.io/leaderboard) available.**\n\n---\n\nCheckout my **[Youtube channel](https://www.youtube.com/@ashishps_1/videos)** for more in-depth content.\n\nFollow me on **[LinkedIn](https://www.linkedin.com/in/ashishps1/)** and **[X](https://twitter.com/ashishps_1)** to stay updated.\n\nCheckout my **[GitHub repositories](https://github.com/ashishps1)** for free interview preparation resources.\n\nI hope you have a lovely day!\n\nSee you soon, Ashish\n\n---\n\n## References\n\n- [Java Concurrency in Practice (Brian Goetz)](undefined) - Chapter 5: Building Blocks\n- [Java ConcurrentHashMap Documentation](undefined)\n- [Java BlockingQueue Documentation](undefined)\n- [Doug Lea's Concurrent Programming in Java](undefined)\n\n---\n\n## Images Needed\n\n[IMAGE 1: Standard Collection Problems] \n\n[IMAGE 2: Synchronized vs Concurrent Collections] \n\n[IMAGE 3: ConcurrentHashMap Segments] \n\n[IMAGE 4: Copy-on-Write Mechanism] \n\n[IMAGE 5: Producer-Consumer with BlockingQueue] \n\n[IMAGE 6: Collection Selection Flowchart] ","pageType":"lld-interviews"}

Concurrent Collections

Ashish Pratap Singh

Get Premium