Concurrent Data Structures
Thread-safe data structures: concurrent hash maps, skip lists, queues, stacks, read-write locks, lock-free algorithms, and compare-and-swap patterns.
The data
Structures
| Name | Type | Description | Implementations | Contention | Notes | Operations |
|---|---|---|---|---|---|---|
| Concurrent Hash Map (Striped/Segmented) | Lock-based | Hash map with segmented locking: different buckets can be locked independently, allowing concurrent access to different segments |
| Low (only on same segment) | Java 8+ uses CAS + synchronized on individual bins; read operations often lock-free | null |
| Concurrent Skip List | Lock-free (optimistic) | Probabilistic balanced search structure; uses CAS for lock-free insertion/deletion with high probability |
| null | Better concurrency than balanced trees (no rebalancing); used as concurrent sorted map | O(log n) expected for search/insert/delete |
| Lock-Free Queue (Michael-Scott) | Lock-free | Linked-list queue using CAS on head and tail pointers; multiple producers/consumers without locks |
| null | May have memory reclamation issues (ABA problem); use hazard pointers or epoch-based reclamation in production | O(1) amortized enqueue/dequeue |
| Concurrent Stack (Treiber Stack) | Lock-free | Linked-list stack using CAS on top pointer; simple but can have contention on single atomic variable |
| null | High contention under heavy concurrent use; consider combining techniques or elimination backoff | O(1) push/pop |
| Read-Write Lock | Lock-based (shared/exclusive) | Allows multiple concurrent readers OR one exclusive writer; optimizes read-heavy workloads |
| null | Risk of writer starvation under heavy read load; use StampedLock (Java) or upgradeable read locks | Read: O(1), Write: O(1) + potential writer starvation |
| Compare-And-Swap (CAS) | Atomic primitive | Atomically: if (location == expected) location = new_value; return success/failure. Foundation of all lock-free algorithms |
| null | CAS loop pattern: while (!CAS(loc, expected, new)) expected = *loc; ABA problem requires versioned pointers or hazard pointers | O(1) atomic |
| Hazard Pointers | Memory reclamation | Lock-free memory reclamation technique: threads announce which nodes they're accessing; nodes not in any hazard list can be safely freed |
| null | Solves ABA and use-after-free in lock-free structures; bounded memory overhead (O(threads × hazard_slots)) | O(1) publish/unpublish |
| Epoch-Based Reclamation | Memory reclamation | Threads announce their epoch; retired nodes are freed when all threads have moved past the epoch when node was retired |
| null | Lower overhead than hazard pointers for read-heavy workloads; used extensively in kernel RCU | O(1) enter/exit epoch |
Fetch the same bytes
The static files are identical to what the API returns, but with no rate limit and no server round trip. Use the API when you want a query and a content type; use the files when you want to cache one document.
curl "https://yjtoon.com/api/dataset/concurrent-data-structures?format=toon"
const res = await fetch( "https://yjtoon.com/static-data/dataset/concurrent-data-structures.toon" ); const toon = await res.text();
Rate limit: 120 requests per minute per IP, no key and no signup. API reference →