api: YAML JSON TOON Database
version: 1.0.0
format: json
dataset:
  id: 60
  slug: concurrent-data-structures
  title: Concurrent Data Structures
  description: "Thread-safe data structures: concurrent hash maps, skip lists, queues, stacks, read-write locks, lock-free algorithms, and compare-and-swap patterns."
  summary: "Data structures designed for concurrent access: striped hash maps, skip lists, lock-free queues and stacks, read-write locks, compare-and-swap and safe memory reclamation with hazard pointers and epochs, each with implementations, contention and notes."
  use_when:
    - You are choosing a thread-safe container or synchronization primitive.
    - You are reading about lock-free design.
  caveats:
    - Lock-free structures are difficult to get right; prefer well-tested library implementations.
    - Performance depends on contention and hardware memory ordering.
  related:
    - concurrency-design-patterns
    - go-concurrency-patterns
    - hash-tables
    - process-management
  category: Data Structures
  category_slug: data-structures
  tags: concurrency,lock-free,compare-and-swap,concurrent-hash-map,concurrent-queue,read-write-lock,atomic
  view_count: 0
  created_at: 1778695229
  updated_at: 1778695229
  entry_count: 8
  fields:
    - section: structures
      field: name
      type: string
      example: Concurrent Hash Map (Striped/Segmented)
    - section: structures
      field: type
      type: string
      example: Lock-based
    - section: structures
      field: description
      type: string
      example: "Hash map with segmented locking: different buck…"
    - section: structures
      field: implementations
      type: array
      example: "[3 items]"
    - section: structures
      field: contention
      type: string
      example: Low (only on same segment)
    - section: structures
      field: notes
      type: string
      example: Java 8+ uses CAS + synchronized on individual b…
    - section: structures
      field: operations
      type: string
      example: O(log n) expected for search/insert/delete
data:
  structures:
    - name: Concurrent Hash Map (Striped/Segmented)
      type: Lock-based
      description: "Hash map with segmented locking: different buckets can be locked independently, allowing concurrent access to different segments"
      implementations:
        - Java ConcurrentHashMap (striped, CAS-based)
        - "C++ tbb::concurrent_unordered_map"
        - .NET ConcurrentDictionary
      contention: Low (only on same segment)
      notes: Java 8+ uses CAS + synchronized on individual bins; read operations often lock-free
    - name: Concurrent Skip List
      type: Lock-free (optimistic)
      description: Probabilistic balanced search structure; uses CAS for lock-free insertion/deletion with high probability
      implementations:
        - Java ConcurrentSkipListMap/Set
        - C++ concurrent_skiplist
      operations: O(log n) expected for search/insert/delete
      notes: Better concurrency than balanced trees (no rebalancing); used as concurrent sorted map
    - name: Lock-Free Queue (Michael-Scott)
      type: Lock-free
      description: Linked-list queue using CAS on head and tail pointers; multiple producers/consumers without locks
      implementations:
        - Java ConcurrentLinkedQueue
        - "C++ boost::lockfree::queue"
      operations: O(1) amortized enqueue/dequeue
      notes: May have memory reclamation issues (ABA problem); use hazard pointers or epoch-based reclamation in production
    - name: Concurrent Stack (Treiber Stack)
      type: Lock-free
      description: Linked-list stack using CAS on top pointer; simple but can have contention on single atomic variable
      implementations:
        - "C++ tbb::concurrent_bounded_queue (similar)"
        - Java ConcurrentLinkedDeque
      operations: O(1) push/pop
      notes: High contention under heavy concurrent use; consider combining techniques or elimination backoff
    - name: Read-Write Lock
      type: Lock-based (shared/exclusive)
      description: Allows multiple concurrent readers OR one exclusive writer; optimizes read-heavy workloads
      implementations:
        - Java ReentrantReadWriteLock
        - C++ shared_mutex (C++17)
        - POSIX pthread_rwlock_t
      operations: "Read: O(1), Write: O(1) + potential writer starvation"
      notes: Risk of writer starvation under heavy read load; use StampedLock (Java) or upgradeable read locks
    - name: Compare-And-Swap (CAS)
      type: Atomic primitive
      description: "Atomically: if (location == expected) location = new_value; return success/failure. Foundation of all lock-free algorithms"
      implementations:
        - Java Unsafe.compareAndSwap*()
        - "C++ std::atomic<T>::compare_exchange_weak/strong"
        - x86 CMPXCHG instruction
      operations: O(1) atomic
      notes: "CAS loop pattern: while (!CAS(loc, expected, new)) expected = *loc; ABA problem requires versioned pointers or hazard pointers"
    - name: Hazard Pointers
      type: Memory reclamation
      description: "Lock-free memory reclamation technique: threads announce which nodes they're accessing; nodes not in any hazard list can be safely freed"
      implementations:
        - Boost.Lockfree
        - Folly (Facebook)
        - DPDK
      operations: O(1) publish/unpublish
      notes: Solves ABA and use-after-free in lock-free structures; bounded memory overhead (O(threads × hazard_slots))
    - name: Epoch-Based Reclamation
      type: Memory reclamation
      description: Threads announce their epoch; retired nodes are freed when all threads have moved past the epoch when node was retired
      implementations:
        - Seastar
        - Folly
        - RCU (Read-Copy-Update) in Linux kernel
      operations: O(1) enter/exit epoch
      notes: Lower overhead than hazard pointers for read-heavy workloads; used extensively in kernel RCU