Skip to content

Concurrent data structures

Category: Lock-free · Status: stub · Lessons: chapter 02, Shared state

One line: Queues, maps, stacks and lists built to be used by many threads at once — with locks inside, lock-free algorithms, or both — so that their callers need no synchronization of their own.

Also called: concurrent collections, thread-safe containers, ConcurrentHashMap.

How it connects

flowchart LR
  n_compare_and_swap["Compare-and-swap"]
  n_concurrent_data_structures["Concurrent data structures"]
  n_concurrent_data_structures -->|uses| n_compare_and_swap
  classDef center stroke-width:3px
  class n_concurrent_data_structures center
  classDef outside stroke-dasharray: 4 3
  class n_compare_and_swap outside

In each language
Rust none in the standard library besides channels; crossbeam::queue ↗ has lock-free queues
Go sync.Map ↗, meant for keys that are written once and read many times; a plain map needs its own mutex
Java ConcurrentHashMap ↗ and the other collections in java.util.concurrent
Python queue.Queue ↗, whose classes implement all the required locking
C# System.Collections.Concurrent ↗: ConcurrentDictionary, ConcurrentQueue, BlockingCollection

Where to read more