Concurrent Collections

Synchronized vs Concurrent Collections

Understanding the difference is crucial for performance!

Visual: Lock Granularity

---

Java Concurrent Collections

ConcurrentHashMap

ConcurrentHashMap provides thread-safe hash map operations with high concurrency.

How It Works

Java 7: Segment locking (16 segments by default) Java 8+: CAS operations + synchronized blocks for individual buckets

Visual: ConcurrentHashMap Architecture

Example: Thread-Safe Cache

Java

ConcurrentHashMapCache.java

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapCache<K, V> {
    private final ConcurrentHashMap<K, V> cache = new ConcurrentHashMap<>();

    public V get(K key) {
        return cache.get(key);  // Thread-safe read
    }

    public void put(K key, V value) {
        cache.put(key, value);  // Thread-safe write
    }

    // Atomic operations
    public V putIfAbsent(K key, V value) {
        return cache.putIfAbsent(key, value);  // Atomic!
    }

    public boolean remove(K key, V value) {
        return cache.remove(key, value);  // Atomic!
    }

    public V computeIfAbsent(K key, java.util.function.Function<K, V> mappingFunction) {
        return cache.computeIfAbsent(key, mappingFunction);  // Atomic!
    }
}

CopyOnWriteArrayList

CopyOnWriteArrayList creates a new copy on each write, making reads lock-free.

Visual: Copy-On-Write

Example: CopyOnWriteArrayList

Java

CopyOnWriteExample.java

import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteExample {
    public static void main(String[] args) {
        List<String> list = new CopyOnWriteArrayList<>();

        // Multiple readers (no locking needed!)
        for (int i = 0; i < 10; i++) {
            final int readerId = i;
            new Thread(() -> {
                for (int j = 0; j < 1000; j++) {
                    list.size();  // Lock-free read
                }
                System.out.println("Reader " + readerId + " finished");
            }).start();
        }

        // Occasional writer
        new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                list.add("Item " + i);  // Creates copy
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            }
        }).start();
    }
}

When to Use CopyOnWriteArrayList

• Use when: Reads vastly outnumber writes (e.g., 100:1 ratio)
• Don’t use when: Frequent writes (too expensive)
• Perfect for: Event listeners, configuration that rarely changes

BlockingQueue Implementations

We covered these in Producer-Consumer, but here’s a quick reference:

Queue Type	Characteristics	Use Case
ArrayBlockingQueue	Array-backed, bounded	Fixed-size queues
LinkedBlockingQueue	Node-based, optionally bounded	Better throughput
PriorityBlockingQueue	Priority ordering	Priority-based processing
DelayQueue	Time-based scheduling	Scheduled tasks
SynchronousQueue	Zero capacity	Direct handoff

---

Python Concurrent Collections

Thread-Safety of Built-in Types

Python’s built-in types have limited thread-safety due to the GIL.

Visual: Python Thread-Safety

Example: Thread-Safe vs Unsafe Operations

Python

thread_safety_example.py

import threading

# ❌ NOT thread-safe: Compound operation
counter = 0

def unsafe_increment():
    global counter
    counter += 1  # NOT atomic: read-modify-write

threads = [threading.Thread(target=unsafe_increment) for _ in range(10)]
for t in threads:
    t.start()
for t in threads:
    t.join()

print(f"Unsafe result: {counter}")  # May not be 10!

# ✅ Thread-safe: Single atomic operation
d = {}
def safe_operation():
    d['key'] = 'value'  # Atomic operation

threads = [threading.Thread(target=safe_operation) for _ in range(10)]
for t in threads:
    t.start()
for t in threads:
    t.join()

print(f"Safe result: {len(d)}")  # Always 1

# ✅ Thread-safe: Using locks
counter_safe = 0
lock = threading.Lock()

def safe_increment():
    global counter_safe
    with lock:
        counter_safe += 1

threads = [threading.Thread(target=safe_increment) for _ in range(10)]
for t in threads:
    t.start()
for t in threads:
    t.join()

print(f"Safe with lock: {counter_safe}")  # Always 10

queue Module

Python’s queue module provides thread-safe queue implementations.

Python

queue_module.py

import queue
import threading

# FIFO Queue
fifo_queue = queue.Queue(maxsize=10)

# LIFO Queue (Stack)
lifo_queue = queue.LifoQueue(maxsize=10)

# Priority Queue
priority_queue = queue.PriorityQueue(maxsize=10)

def producer(q):
    for i in range(5):
        q.put(i)
        print(f"Produced: {i}")

def consumer(q):
    while True:
        try:
            item = q.get(timeout=1)
            print(f"Consumed: {item}")
            q.task_done()
        except queue.Empty:
            break

# Thread-safe operations
threading.Thread(target=producer, args=(fifo_queue,)).start()
threading.Thread(target=consumer, args=(fifo_queue,)).start()

multiprocessing.Manager

For shared state across processes (not threads):

Python

multiprocessing_manager.py

import multiprocessing

def worker(shared_dict, shared_list):
    shared_dict['count'] = shared_dict.get('count', 0) + 1
    shared_list.append(shared_dict['count'])

if __name__ == '__main__':
    manager = multiprocessing.Manager()
    shared_dict = manager.dict()
    shared_list = manager.list()

    processes = []
    for _ in range(5):
        p = multiprocessing.Process(target=worker, args=(shared_dict, shared_list))
        processes.append(p)
        p.start()

    for p in processes:
        p.join()

    print(f"Dict: {shared_dict}")
    print(f"List: {shared_list}")

---

Comparison Table

Collection Type	Java	Python	Thread-Safety
HashMap/Dict	ConcurrentHashMap	dict + locks	Java: Full, Python: Limited
List	CopyOnWriteArrayList	list + locks	Java: Full, Python: Limited
Queue	BlockingQueue variants	queue.Queue	Both: Full
Set	ConcurrentSkipListSet	set + locks	Java: Full, Python: Limited

---

Practice Problems

Easy: Thread-Safe Cache

Design a thread-safe cache using concurrent collections.

Solution

Java

import java.util.concurrent.ConcurrentHashMap;

public class ThreadSafeCache<K, V> {
    private final ConcurrentHashMap<K, V> cache = new ConcurrentHashMap<>();

    public V get(K key) {
        return cache.get(key);
    }

    public void put(K key, V value) {
        cache.put(key, value);
    }

    public V computeIfAbsent(K key, java.util.function.Function<K, V> mappingFunction) {
        return cache.computeIfAbsent(key, mappingFunction);
    }
}

Python

import threading

class ThreadSafeCache:
    def __init__(self):
        self._cache = {}
        self._lock = threading.RLock()

    def get(self, key):
        with self._lock:
            return self._cache.get(key)

    def put(self, key, value):
        with self._lock:
            self._cache[key] = value

    def compute_if_absent(self, key, mapping_function):
        with self._lock:
            if key not in self._cache:
                self._cache[key] = mapping_function(key)
            return self._cache[key]

---

Interview Questions

Q1: “What’s the difference between ConcurrentHashMap and synchronized HashMap?”

Answer:

• synchronized HashMap: Locks entire map for any operation (low concurrency)
• ConcurrentHashMap: Fine-grained locking or CAS (high concurrency)
• Performance: ConcurrentHashMap is much faster for concurrent access
• Use ConcurrentHashMap: When you need thread-safe map with high concurrency

Q2: “When would you use CopyOnWriteArrayList?”

Answer:

• Use when: Reads vastly outnumber writes (e.g., 100:1 ratio)
• Perfect for: Event listeners, configuration, read-heavy scenarios
• Don’t use when: Frequent writes (too expensive - creates copy each time)
• Trade-off: Expensive writes for lock-free reads

Q3: “Are Python’s built-in dict and list thread-safe?”

Answer:

• Single operations: Yes, atomic (e.g., dict[key] = value, list.append(item))
• Compound operations: No, NOT thread-safe (e.g., if key in dict: dict[key] = value)
• Solution: Use locks for compound operations or thread-safe collections
• GIL: Provides some protection but doesn’t guarantee thread-safety for compound ops

Q4: “What’s the difference between ArrayBlockingQueue and LinkedBlockingQueue?”

Answer:

• ArrayBlockingQueue: Array-backed, always bounded, fixed memory, slightly lower throughput
• LinkedBlockingQueue: Node-based, optionally bounded, dynamic memory, typically higher throughput
• Choose: ArrayBlockingQueue for fixed-size needs, LinkedBlockingQueue for better performance

---

Key Takeaways

Remember

• Concurrent collections use fine-grained locking or lock-free algorithms
• ConcurrentHashMap: High-performance thread-safe map
• CopyOnWriteArrayList: Lock-free reads, expensive writes
• Python built-ins: Limited thread-safety (single ops atomic, compound ops not)
• queue module: Thread-safe queues in Python
• Choose wisely: Match collection to your access pattern (read-heavy vs write-heavy)

---

Next Steps

Continue learning concurrency:

• Asynchronous Patterns - Futures and async/await
• Lock-Free Programming - CAS and atomic operations

Mastering concurrent collections is essential for building thread-safe systems! 📦