api: YAML JSON TOON Database
version: 1.0.0
format: toon
dataset:
  id: 2756
  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[2]: You are choosing a thread-safe container or synchronization primitive.,You are reading about lock-free design.
  caveats[2]: Lock-free structures are difficult to get right; prefer well-tested library implementations.,Performance depends on contention and hardware memory ordering.
  related[4]: concurrency-design-patterns,go-concurrency-patterns,hash-tables,process-management
  entry_count: 8
  fields[7]{section,field,type,example}:
    structures,name,string,Concurrent Hash Map (Striped/Segmented)
    structures,type,string,Lock-based
    structures,description,string,"Hash map with segmented locking: different buck…"
    structures,implementations,array,"[3 items]"
    structures,contention,string,Low (only on same segment)
    structures,notes,string,Java 8+ uses CAS + synchronized on individual b…
    structures,operations,string,O(log n) expected for search/insert/delete
  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: 44
  created_at: 1778695229
  updated_at: 1778695229
data:
  structures[8]:
    - 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