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 is a hash-addressed key–value table that provides a stated contract for supported operations when callers can invoke them at overlapping times. The hash determines where a key's mapping can be found; a coordination or validation protocol ensures that a lookup does not accept an invalid intermediate mapping while an update proceeds. The contract specifies which operations and observations are covered. A table remains concurrent-capable when a particular program happens to use it from only one thread.[1][2]
This identity has more than one realization. Java SE 17 ConcurrentHashMap allows retrievals such as get generally to overlap updates such as put and remove, and documents visibility for a completed update of a given key to a retrieval reporting that value. Its bulk and status operations do not thereby become atomic snapshots of the whole table.[1] The MemC3 cache's concurrent cuckoo Index permits multiple readers alongside one serialized writer. It prevents a reader from reporting a false miss while an insertion displaces an existing key, using a backward displacement path and version checks.[2] The shared idea is a hash-addressed mapping with a concurrency contract, not one locking algorithm or a promised throughput curve.
Structural Signature¶
- Hash-addressed mapping. A key determines candidate storage locations for its value. Java's table and MemC3's two-choice cuckoo index differ in layout, but both answer keyed lookups through hashing.[1][2] Remove the keyed hash organization and a concurrent queue would be a different structure.
- Potentially overlapping callers. The implementation supports access from independent execution contexts that may overlap. Actual overlap in every run is unnecessary; the contract is what permits such use.[1][2]
- Coordination or validation. Updates cannot expose invalid supported lookup results merely because internal steps interleave. Java documents thread-safe retrieval and update behavior; MemC3's writer serialization, backward relocation and version tests serve its narrower reader–writer design. A single lock around a hash-backed map can also satisfy a concurrency contract, at the cost of serial access.[1][2][3]
- Operation scope. The guarantee must say what a lookup, insertion, deletion or aggregate observation may report during overlap. Java distinguishes per-key retrieval behavior from partial aggregate observations. MemC3's detailed interleaving argument focuses on lookup and insertion, although its interface also lists deletion.[1][2]
These roles define a concurrent table. Nonblocking reads, fine-grained locks, compare-and-swap and linear throughput growth are possible design choices or outcomes, not mandatory signature roles.
What It Is Not¶
It is not simply an ordinary hash table that two threads happen to touch. Oracle's HashMap documentation requires external synchronization if threads access one instance concurrently and at least one structurally modifies it. A safely published map read only by multiple threads is a different boundary case: it does not establish a contract for overlapping mutation.[4]
It is not necessarily a table in which unrelated keys update independently. MemC3 deliberately allows only one writer at a time to avoid deadlock along cuckoo displacement paths.[2] It is also not an all-purpose claim of linearizability. That is a condition on a concurrent object's operation history relative to its sequential specification.[5] A particular table's documentation or proof must establish its scope. Java expressly permits partial results for some aggregate operations.[1] The cited MemC3 analysis concentrates on lookup and insertion interleavings.[2]
Scope of Application¶
The pattern applies to shared, in-memory associative structures whose keys are located by hashing and whose supported calls may overlap: a runtime's shared map and a hash index within a network cache are two unlike cases. Oracle's synchronized wrapper serializes calls through a hash-backed map when all access uses the wrapper; iterating one of its collection views still requires the manual synchronization Oracle specifies.[3] That wrapper is within this entry's scope because it supplies an overlap contract, even though the calls execute serially. Oracle requires external synchronization for structural mutation of a shared HashMap.[4] An unsynchronized table under overlapping structural mutation and a concurrent queue without hashed keys fall outside this entry. MemC3's concurrent index is one component of its cache.[2] Its index contract does not, by itself, cover the cache's eviction and storage policies.
Clarity¶
The name separates two questions often collapsed into “thread-safe”: How is a key located? and What may a caller observe while another call is in progress? Hashing answers the first. The operation contract and its implementation answer the second. Reading only a get guarantee cannot justify treating size, an iterator or a bulk reduction as one frozen view of all mappings; Java documents those differences explicitly.[1]
Manages Complexity¶
The table gives callers one keyed interface while containing coordination inside the data structure. In MemC3, a cuckoo insertion may relocate several entries, a case that could transiently hide a key from a simultaneous reader. Finding a path before moving entries, filling vacancies backward, and checking versions handles that interleaving.[2] The resulting reduction in the caller's reasoning burden applies only within the documented operation scope; it does not make a multi-step application transaction atomic.
Abstract Reasoning¶
Reason about an operation's permitted observation separately from the implementation's locks. Ask whether a reader can see an invalid mapping, whether two writers can overlap, and whether a whole-table count has snapshot meaning. Oracle's synchronized wrapper serializes access through one facade; MemC3 uses one writer and optimistic reader validation.[3][2] The same contract questions can be asked of both, even though their mechanisms and performance envelopes differ.
Knowledge Transfer¶
Within computing, this pattern transfers between language-runtime maps and cache indexes: identify the hashed mapping, enumerate supported overlapping calls, and test the exact visibility promise before using the table for a decision. The transfer is not a recipe to replace one mechanism with another. MemC3's single-writer design has a measured write-heavy bottleneck, while Oracle's synchronized wrapper guarantees serial access through its facade.[2][3] Which arrangement is sufficient depends on the workload and decision being made.
Examples¶
Java SE 17 runtime map. Suppose several threads use a ConcurrentHashMap to associate task IDs with task states. A retrieval reporting an updated non-null value has the per-key visibility relation Oracle describes. If a thread uses size() to decide that all tasks have finished while updates continue, it has changed the question to a whole-table observation that Oracle says can be transient.[1] Role map: task ID → hashed key and state → mapped value; independent threads → potential overlapping callers; the documented implementation → coordination; per-key get visibility versus transient size → operation scope. The latter decision is not justified by the former per-key guarantee.
MemC3 cache index. The cache hashes an object key to two possible bucket locations. A writer's insertion may displace occupants along a cuckoo path while several readers look up keys. MemC3 serializes writers, computes a path before moving entries, moves occupants backward into the empty slot, and has readers check versions and retry when a relocation overlaps their read.[2] Role map: object key → two hashed candidate locations; readers and writer → potentially overlapping callers; backward relocation plus version checking → validation protocol; the lookup/insert interleaving argument → the cited guarantee's scope. No whole-cache eviction guarantee follows from this index behavior.
Structural Tensions¶
Reader overlap versus writer concurrency. MemC3 gains low-overhead overlapping lookups in its read-heavy target workload by accepting one writer; its measurements identify that writer lock as a limit when inserts are more common.[2] The design question is whether the expected mix rewards reader throughput enough to justify serialized updates. This measured bottleneck belongs to MemC3, not every concurrent table.
Per-key answer versus whole-table decision. Java can provide a useful completed-update relation for a key while an iterator, bulk computation or size result reflects a changing table.[1] The benefit is continued progress under updates; the cost is that a global decision may need a separate snapshot or application-level coordination. Diagnose whether the program needs one key's value or one atomic picture of all keys.
Simple serialized contract versus overlapping updates. A synchronized wrapper gives callers serial access through one map facade.[3] This simplifies the contract but gives up simultaneous progress through that facade. If the workload demands more overlapping updates, a different protocol needs its own operation-level verification; “concurrent” alone promises neither lock freedom nor linear scaling.
Structural–Framed Character¶
Java's runtime map and the MemC3 cache index use different coordination mechanisms.[1][2] This entry sits toward the structural side of the structural–framed spectrum because its roles survive that change in implementation. Evaluative weight: “concurrent” is not a judgment that one implementation is faster or fairer; its value depends on the operation contract. Human-practice dependence: programmers choose and test the contract, but the interleaving behavior is a property of the implemented table. Institutional origin: no one vendor or standard defines the identity; the Java and MemC3 cases realize it differently. Vocabulary travel: the terms hash, key, lookup and overlapping call retain their computing meanings and do not transfer literally to every use of “coordination.” Import versus recognition: recognizing the table requires evidence of both hashed mapping and an overlap contract, not importing an analogy from a social process. Its character: a reusable computing structure whose boundary is set by its operation semantics, rather than by one implementation or by a generic cooperation metaphor.
Structural Core vs. Domain Accent¶
The core is the conjunction of a hash-addressed mapping and concurrency semantics for its supported operations. The domain accent is essential: keys, buckets, lookups, updates and execution interleavings are computing objects. Stripping them to “coordination among participants” loses the table and would describe many unrelated systems. Conversely, a plain hash table without an overlap contract is the substrate, not this subtype. A more general Prime would require evidence that derived addressing plus a specified overlapping-operation contract functions without these computing roles in genuinely different substrates. What are those non-computing cases, and do their operations have comparable observable correctness conditions? Until that question has evidence, the portable ideas belong to broader existing patterns, while this named conjunction stays domain-specific.
Instantiates / Related Primes¶
This entry is a kind of Data Structure.
Hashing supplies the key-to-location ingredient and Data Structure supplies the general notion of stored data with operations. The existing Hash Table entry names the nonconcurrent storage substrate. None of those alone states the overlap contract that differentiates this entry. The similarly named Synchronization prime concerns phase alignment; that meaning does not supply a thread-operation protocol merely because the same English word is used in programming.
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.Data Structure's arrangement-for-use signature is present in both the Java map and MemC3 index: key-value information, a chosen hash layout, a lookup/update operation profile with costs, no neutral arrangement, maintained mapping invariants, and composability inside a larger program or cache. The stable differentia is an overlap-operation protocol that preserves specified mapping observations during interleaving. A sequential tree or ordinary hash table remains a data structure without that differentia. The closer live Hash Table entry requires a specific doubling-and-rehashing and expected-amortized cost profile not proved for both cited implementations, so that stricter full-signature parent is not asserted. Data Structure's own Trade-offs ancestor remains typical rather than becoming strict.
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
Not to Be Confused With¶
Hash Table names the hashed storage scheme; the concurrent subtype adds a supported overlap contract. Linearizability tests histories against a sequential specification and real-time order.[5] It is a criterion, not a synonym for the table or a blanket promise for each method. MemC3 names a cache system whose concurrent cuckoo index is one component.[2] A lock-free queue may handle overlap but does not locate keyed mappings by hashing.
References¶
[1] 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). registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k
[2] 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). registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p
[3] 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). registry ↩a ↩b ↩c ↩d ↩e
[4] 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). registry ↩a ↩b
[5] 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). registry ↩a ↩b