Concurrent Collections
Synchronized vs Concurrent Collections
Section titled “Synchronized vs Concurrent Collections”Understanding the difference is crucial for performance!
Visual: Lock Granularity
Section titled “Visual: Lock Granularity”Java Concurrent Collections
Section titled “Java Concurrent Collections”ConcurrentHashMap
Section titled “ConcurrentHashMap”ConcurrentHashMap provides thread-safe hash map operations with high concurrency.
How It Works
Section titled “How It Works”Java 7: Segment locking (16 segments by default) Java 8+: CAS operations + synchronized blocks for individual buckets
Visual: ConcurrentHashMap Architecture
Section titled “Visual: ConcurrentHashMap Architecture”Example: Thread-Safe Cache
Section titled “Example: Thread-Safe Cache”1import java.util.concurrent.ConcurrentHashMap;2
3public class ConcurrentHashMapCache<K, V> {4 private final ConcurrentHashMap<K, V> cache = new ConcurrentHashMap<>();5
6 public V get(K key) {7 return cache.get(key); // Thread-safe read8 }9
10 public void put(K key, V value) {11 cache.put(key, value); // Thread-safe write12 }13
14 // Atomic operations15 public V putIfAbsent(K key, V value) {16 return cache.putIfAbsent(key, value); // Atomic!17 }18
19 public boolean remove(K key, V value) {20 return cache.remove(key, value); // Atomic!21 }22
23 public V computeIfAbsent(K key, java.util.function.Function<K, V> mappingFunction) {24 return cache.computeIfAbsent(key, mappingFunction); // Atomic!25 }26}CopyOnWriteArrayList
Section titled “CopyOnWriteArrayList”CopyOnWriteArrayList creates a new copy on each write, making reads lock-free.
Visual: Copy-On-Write
Section titled “Visual: Copy-On-Write”Example: CopyOnWriteArrayList
Section titled “Example: CopyOnWriteArrayList”1import java.util.List;2import java.util.concurrent.CopyOnWriteArrayList;3
4public class CopyOnWriteExample {5 public static void main(String[] args) {6 List<String> list = new CopyOnWriteArrayList<>();7
8 // Multiple readers (no locking needed!)9 for (int i = 0; i < 10; i++) {10 final int readerId = i;11 new Thread(() -> {12 for (int j = 0; j < 1000; j++) {13 list.size(); // Lock-free read14 }15 System.out.println("Reader " + readerId + " finished");16 }).start();17 }18
19 // Occasional writer20 new Thread(() -> {21 for (int i = 0; i < 10; i++) {22 list.add("Item " + i); // Creates copy23 try {24 Thread.sleep(100);25 } catch (InterruptedException e) {26 Thread.currentThread().interrupt();27 }28 }29 }).start();30 }31}BlockingQueue Implementations
Section titled “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
Section titled “Python Concurrent Collections”Thread-Safety of Built-in Types
Section titled “Thread-Safety of Built-in Types”Python’s built-in types have limited thread-safety due to the GIL.
Visual: Python Thread-Safety
Section titled “Visual: Python Thread-Safety”Example: Thread-Safe vs Unsafe Operations
Section titled “Example: Thread-Safe vs Unsafe Operations”1import threading2
3# ❌ NOT thread-safe: Compound operation4counter = 05
6def unsafe_increment():7 global counter8 counter += 1 # NOT atomic: read-modify-write9
10threads = [threading.Thread(target=unsafe_increment) for _ in range(10)]11for t in threads:12 t.start()13for t in threads:14 t.join()15
16print(f"Unsafe result: {counter}") # May not be 10!17
18# ✅ Thread-safe: Single atomic operation19d = {}20def safe_operation():21 d['key'] = 'value' # Atomic operation22
23threads = [threading.Thread(target=safe_operation) for _ in range(10)]24for t in threads:25 t.start()26for t in threads:27 t.join()28
29print(f"Safe result: {len(d)}") # Always 130
31# ✅ Thread-safe: Using locks32counter_safe = 033lock = threading.Lock()34
35def safe_increment():36 global counter_safe37 with lock:38 counter_safe += 139
40threads = [threading.Thread(target=safe_increment) for _ in range(10)]41for t in threads:42 t.start()43for t in threads:44 t.join()45
46print(f"Safe with lock: {counter_safe}") # Always 10queue Module
Section titled “queue Module”Python’s queue module provides thread-safe queue implementations.
1import queue2import threading3
4# FIFO Queue5fifo_queue = queue.Queue(maxsize=10)6
7# LIFO Queue (Stack)8lifo_queue = queue.LifoQueue(maxsize=10)9
10# Priority Queue11priority_queue = queue.PriorityQueue(maxsize=10)12
13def producer(q):14 for i in range(5):15 q.put(i)16 print(f"Produced: {i}")17
18def consumer(q):19 while True:20 try:21 item = q.get(timeout=1)22 print(f"Consumed: {item}")23 q.task_done()24 except queue.Empty:25 break26
27# Thread-safe operations28threading.Thread(target=producer, args=(fifo_queue,)).start()29threading.Thread(target=consumer, args=(fifo_queue,)).start()multiprocessing.Manager
Section titled “multiprocessing.Manager”For shared state across processes (not threads):
1import multiprocessing2
3def worker(shared_dict, shared_list):4 shared_dict['count'] = shared_dict.get('count', 0) + 15 shared_list.append(shared_dict['count'])6
7if __name__ == '__main__':8 manager = multiprocessing.Manager()9 shared_dict = manager.dict()10 shared_list = manager.list()11
12 processes = []13 for _ in range(5):14 p = multiprocessing.Process(target=worker, args=(shared_dict, shared_list))15 processes.append(p)16 p.start()17
18 for p in processes:19 p.join()20
21 print(f"Dict: {shared_dict}")22 print(f"List: {shared_list}")Comparison Table
Section titled “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
Section titled “Practice Problems”Easy: Thread-Safe Cache
Section titled “Easy: Thread-Safe Cache”Design a thread-safe cache using concurrent collections.
Solution
1import java.util.concurrent.ConcurrentHashMap;2
3public class ThreadSafeCache<K, V> {4 private final ConcurrentHashMap<K, V> cache = new ConcurrentHashMap<>();5
6 public V get(K key) {7 return cache.get(key);8 }9
10 public void put(K key, V value) {11 cache.put(key, value);12 }13
14 public V computeIfAbsent(K key, java.util.function.Function<K, V> mappingFunction) {15 return cache.computeIfAbsent(key, mappingFunction);16 }17}1import threading2
3class ThreadSafeCache:4 def __init__(self):5 self._cache = {}6 self._lock = threading.RLock()7
8 def get(self, key):9 with self._lock:10 return self._cache.get(key)11
12 def put(self, key, value):13 with self._lock:14 self._cache[key] = value15
16 def compute_if_absent(self, key, mapping_function):17 with self._lock:18 if key not in self._cache:19 self._cache[key] = mapping_function(key)20 return self._cache[key]Interview Questions
Section titled “Interview Questions”Q1: “What’s the difference between ConcurrentHashMap and synchronized HashMap?”
Section titled “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?”
Section titled “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?”
Section titled “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?”
Section titled “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
Section titled “Key Takeaways”Next Steps
Section titled “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! 📦