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."
  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
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:
        [3]: "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:
        [2]: "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:
        [2]: "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:
        [2]: "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:
        [3]: "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:
        [3]: "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:
        [3]: 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:
        [3]: 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"