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:
        - "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"