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.

Data Structures
8 entries
CC0 — public domain

JSON8,236 B
YAML5,941 B · −28%
TOON5,396 B · −34%

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 it when

You are choosing a thread-safe container or synchronization primitive.
You are reading about lock-free design.

Watch out for

Lock-free structures are difficult to get right; prefer well-tested library implementations.
Performance depends on contention and hardware memory ordering.

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	Java ConcurrentHashMap (striped, CAS-based) C++ tbb::concurrent_unordered_map .NET ConcurrentDictionary	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	Java ConcurrentSkipListMap/Set C++ concurrent_skiplist	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	Java ConcurrentLinkedQueue C++ boost::lockfree::queue	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	C++ tbb::concurrent_bounded_queue (similar) Java ConcurrentLinkedDeque	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	Java ReentrantReadWriteLock C++ shared_mutex (C++17) POSIX pthread_rwlock_t	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	Java Unsafe.compareAndSwap*() C++ std::atomic<T>::compare_exchange_weak/strong x86 CMPXCHG instruction	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	Boost.Lockfree Folly (Facebook) DPDK	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	Seastar Folly RCU (Read-Copy-Update) in Linux kernel	null	Lower overhead than hazard pointers for read-heavy workloads; used extensively in kernel RCU	O(1) enter/exit epoch

Fields

The shape of this dataset, read from the data itself: every column, its type and a real value. Agents can use this to plan a query without fetching the whole document.

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

Fetch the same bytes

The static files contain the same reference rows as the API, with no API rate limit. Live metadata, such as view counts, may differ. Use the API for content negotiation; use the static files for a cacheable snapshot.

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 →