Concurrent Hash Table¶
A hash-addressed key–value table with an operation protocol that preserves specified mapping semantics when supported calls overlap.
Core Idea¶
A concurrent hash table stores key–value mappings at locations found by hashing keys and defines what supported operations may report when callers invoke them at overlapping times. Hashing answers where to look. A coordination or validation protocol answers what a lookup may safely observe while an update proceeds. A table keeps this identity even in a run where only one caller uses it.[ref-f59bb440494a][ref-c78adbc79467]
The exact contract matters. Java SE 17 ConcurrentHashMap allows ordinary retrievals to overlap updates and describes per-key visibility after a completed update; its aggregate operations need not give a frozen view of the entire map.[^ref-f59bb440494a] MemC3's cuckoo-hash cache index lets several readers operate alongside one serialized writer, with relocation and version checks that prevent a false miss during an insertion.[^ref-c78adbc79467] Both are concurrent hash tables, but they make different promises and use different mechanisms.
What It Is Not¶
An ordinary unsynchronized HashMap is not made safe for overlapping structural changes merely by sharing it between threads; Oracle requires external synchronization in that case.[^ref-f18b24810276] A read-only shared map also does not thereby have an overlap contract for mutation.
A concurrent hash table need not let writers change unrelated keys simultaneously. MemC3 permits only one writer at a time.[^ref-c78adbc79467] It also does not promise that every operation is linearizable or that an iterator or count is an atomic snapshot. Linearizability is a separate test on an operation history against a legal sequential specification.[^ref-4471bb11b4ff] Java's aggregate operations may report a changing state.[^ref-f59bb440494a]
Scope of Application¶
The term covers hash-addressed, in-memory associative structures that support specified overlapping calls, including a shared runtime map, a concurrent cache index, or a synchronized wrapper around a hash-backed map. Oracle's synchronized wrapper serializes access through the wrapper, and it still requires manual synchronization when traversing a collection view.[^ref-7222cb58095f] A serialized implementation can therefore qualify if its access contract handles overlapping callers. An entire cache's eviction policy does not follow from the concurrency of its index.[^ref-c78adbc79467]
Clarity¶
When choosing a table, ask four questions: What keys and values does it map? Which callers may overlap? How does it prevent an invalid lookup during an update? Which operations have which observation guarantees? “Thread-safe” without an operation scope does not answer the last question. In Java, a completed per-key update can have a documented visibility relation while size() or a bulk result remains transient under concurrent updates.[^ref-f59bb440494a]
Manages Complexity¶
The table gives callers a keyed interface while hiding the interleaving steps that maintain it. MemC3 may move entries along a cuckoo path during insertion. Its writer computes the path, moves occupants backward, and uses versions so a reader can retry if it overlaps a relocation.[^ref-c78adbc79467] This removes one class of lookup error from the caller's burden. It does not turn several application-level map calls into one transaction.
Abstract Reasoning¶
Identify the hashed mapping first, then evaluate each supported operation under overlap. A reader must not accept a mapping that the implementation's contract rules out. A writer's coordination method can be a single lock, a finer-grained protocol, or version-based validation; the method alone does not tell you whether a whole-table result is atomic. Oracle's synchronized wrapper uses one facade, while MemC3 uses one writer with optimistic reader checks.[ref-7222cb58095f][ref-c78adbc79467]
Knowledge Transfer¶
The same four questions apply to runtime maps and cache indexes, but a guarantee from one implementation does not transfer automatically to the other. A read-heavy MemC3 workload benefits from overlapping readers but its single writer becomes a bottleneck when writes grow more common.[^ref-c78adbc79467] A synchronized wrapper supplies a simpler serialized access pattern.[^ref-7222cb58095f] Choose based on the operations and observations the program actually needs.
Examples¶
Java runtime map. Several threads update task states by task ID in a ConcurrentHashMap. The task ID is the hashed key and the state is the value. Threads can invoke calls concurrently, and the map coordinates them. A get reporting a completed update has the documented per-key visibility relation, while size() is not a reliable whole-table completion snapshot during updates.[^ref-f59bb440494a]
MemC3 cache index. Object keys hash to two candidate bucket locations. Several readers can look up keys while one writer inserts an entry and displaces existing occupants. Backward relocation and version checks protect the lookup from reporting a false miss during that insertion.[^ref-c78adbc79467] These are the hash-addressed mapping, overlapping callers, validation protocol, and scoped lookup guarantee; they do not describe the cache's entire storage or eviction behavior.
Relationships to Other Abstractions¶
Current abstraction Concurrent Hash Table Domain-specific
Parents (1) — more general patterns this builds on
-
Concurrent Hash Table is a kind of Data Structure Prime
A concurrent hash table is a data structure whose hash-addressed mapping adds defined semantics for supported operations that overlap.
Hierarchy path (1) — routes to 1 parentless root
- Concurrent Hash Table → Data Structure → Trade-offs → Constraint
Neighborhood in Abstraction Space¶
Concurrent Hash Table sits in a sparse region of the domain-specific corpus (96th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2721 abstractions)
Nearest neighbors
- Hash Table — 0.80
- Skew Heap — 0.77
- Sorted Array — 0.77
- Multimap — 0.77
- Retrieval Data Structure — 0.76
Computed from structural-signature embeddings · 2026-10-17
References¶
[^ref-f59bb440494a]: Oracle, “ConcurrentHashMap (Java SE 17 & JDK 17),” official Java API documentation, class description and bulk-operations discussion, https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/concurrent/ConcurrentHashMap.html (full HTML inspected; supports per-key retrieval/update visibility and explicit aggregate limitations). [^ref-c78adbc79467]: Bin Fan, David G. Andersen, and Michael Kaminsky (2013), “MemC3 Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing,” USENIX NSDI, https://www.cs.cmu.edu/~binfan/papers/nsdi13_memc3.pdf (original full PDF inspected; §3 interface, §3.2 one-based PDF pp. 5–6 on one writer, backward displacement and optimistic lookup, §5.2/Fig. 6 on measured bottlenecks, and Appendix A on lookup correctness). [^ref-7222cb58095f]: Oracle, “Collections.synchronizedMap (Java SE 17 & JDK 17),” official Java API documentation, synchronizedMap method, https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Collections.html (full HTML inspected; serial access through the returned map and external synchronization for traversal). [^ref-f18b24810276]: Oracle, “HashMap (Java SE 17 & JDK 17),” official Java API documentation, class description synchronization paragraph, https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/HashMap.html (full HTML inspected; external synchronization required for concurrent access with structural modification). [^ref-4471bb11b4ff]: Maurice P. Herlihy and Jeannette M. Wing, “Linearizability A Correctness Condition for Concurrent Objects,” ACM Transactions on Programming Languages and Systems 12, no. 3 (1990): 463–492, https://www.cs.cmu.edu/~wing/publications/HerlihyWing90.pdf (original full PDF inspected; abstract and §2 define the history correctness condition).