{
    "api": "YAML JSON TOON Database",
    "version": "1.0.0",
    "format": "json",
    "dataset": {
        "id": 379,
        "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": 1,
        "created_at": 1781275786,
        "updated_at": 1781275786
    },
    "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 \u00d7 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"
            }
        ]
    }
}