Java ConcurrentMap
| Company type | Software framework |
|---|---|
| Industry | Software development |
| Founded | 2004 |
| Products | ConcurrentMap, ConcurrentHashMap, ConcurrentSkipListMap, Ctrie |
| Website | docs |
The Java Collections Framework introduced in Java version 1.5 brought both traditional single-threaded Maps and thread-safe Maps implementing the Template:Javadoc:SE interface, alongside other concurrency-related interfaces. With the release of Java 1.6, the Template:Javadoc:SE interface was introduced as an extension of Template:Javadoc:SE, while Template:Javadoc:SE appeared as a subinterface merging these functionalities.
Java Map Interfaces
In Java 1.8, the Map interface hierarchy expanded to include Sets as specialized forms of Maps where values remain constant and are frequently disregarded, although the Set API employs distinct method names. At the most specific level lies java.util.concurrent.ConcurrentNavigableMap, which exemplifies multiple inheritance.
ConcurrentHashMap
For unordered key-value mappings as defined by java.util.Map, the java.util.concurrent.ConcurrentHashMap class implements ConcurrentMap. It utilizes a hash table structure where entries contain keys, values, hash codes, and references to subsequent nodes. Prior to Java 8, the map employed multiple segment locks to manage concurrent access; however, Java 8 replaced this with built-in synchronization on list heads and transforms lengthy linked lists into balanced trees to mitigate hash collisions. Additionally, it uses optimistic compare-and-set operations to expedite initial insertion at the head. Typically, its performance is high with occasional pauses during resizing operations. The table can expand but does not reduce in size, which may lead to retained memory even after entries are removed.
ConcurrentSkipListMap
Introduced in Java 1.6 for ordered mappings compliant with java.util.NavigableMap, ConcurrentSkipListMap implements both ConcurrentMap and ConcurrentNavigableMap. It is based on a Skip list data structure employing lock-free algorithms to maintain a tree-like organization with expected logarithmic time complexity.
Ctrie
Concurrent modification problem
The java.util.concurrent package introduced in Java 1.5 addresses issues related to concurrent modifications by offering collection classes designed for safe use across multiple threads.
Traditional non-concurrent Maps and collections require explicit synchronization or programmatic safeguards to prevent concurrent modification errors that can compromise internal data integrity or yield inconsistent read results. Depending on external locking mechanisms increases code complexity and introduces potential risks, particularly when several threads interact with the collection simultaneously.
Modification counters
Implementations of Map that are not designed for concurrent use often rely on internal modification counters. These counters, incremented by writing operations, help identify concurrent modifications by triggering a ConcurrentModificationException. Nevertheless, this approach is not infallible and can negatively affect performance because the counters are not declared volatile, which means updates might not be visible across different threads.
Collections.synchronizedMap()
A widely used approach to safeguard non-thread-safe Maps is the Collections.synchronizedMap() wrapper. This wrapper synchronizes method invocations on an internal mutex, thereby reducing concurrency-related issues. However, if references to the original Map remain accessible without the wrapper, concurrent access risks persist. Moreover, synchronized wrappers do not inherently provide thread-safe iterators; therefore, users must explicitly synchronize during iteration—a process prone to errors and potential performance degradation.
Applying multiple synchronized wrappers results in separate mutexes, which may cause overlapping synchronization scopes. Although this layering introduces additional delegation overhead, modern Just-in-Time compilers frequently inline these calls, minimizing the impact on performance. An example of synchronization within the wrapper is shown below:
<syntaxhighlight lang="java">
public V put(K key, V value) {
synchronized (mutex) {
return m.put(key, value);
}
}
</syntaxhighlight>
When iterating over the wrapped Map safely, client code needs to lock the wrapper object throughout the iteration:
<syntaxhighlight lang="java">
Map<String, String> wrappedMap = Collections.synchronizedMap(map);
...
synchronized (wrappedMap) {
for (final String s : wrappedMap.keySet()) {
// potentially lengthy operation that may block other accesses
}
}
</syntaxhighlight>
Native synchronization
Any Map instance can be securely accessed in a multi-threaded environment by synchronizing all interactions using Java’s built-in synchronization mechanism:
<syntaxhighlight lang="java">
final Map<String, String> map = new HashMap<>();
...
// Thread A
synchronized(map) {
map.put("key","value");
}
...
// Thread B
synchronized (map) {
String result = map.get("key");
...
}
...
// Thread C
synchronized (map) {
for (final Entry<String, String> s : map.entrySet()) {
/*
* Potentially slow operation that may delay other quick operations.
* Synchronization cannot be applied individually to iterations.
*/
...
}
}
</syntaxhighlight>
ReentrantReadWriteLock
The Template:Javadoc:SE provides enhanced concurrency by permitting multiple simultaneous read operations. It is important to use these locks within try/finally blocks to guarantee unlocking even if exceptions occur or control flow changes unexpectedly. This locking strategy improves upon native synchronization by differentiating between read and write locks; however, implementing write preference over reads demands careful consideration. Alternatively, a Template:Javadoc:SE can be employed when no distinction between read and write locks is necessary. Additional capabilities such as tryLock() and timed tryLock() methods offer greater control.
<syntaxhighlight lang="java">
final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
final ReadLock readLock = lock.readLock();
final WriteLock writeLock = lock.writeLock();
..
// Thread A
try {
writeLock.lock();
map.put("key","value");
...
} finally {
writeLock.unlock();
}
...
// Thread B
try {
readLock.lock();
final String s = map.get("key");
..
} finally {
readLock.unlock();
}
// Thread C
try {
readLock.lock();
for (final Entry<String, String> s : map.entrySet()) {
/*
* Potentially slow operation that may delay other quick operations.
* Synchronization on individual iterations is not feasible.
*/
...
}
} finally {
readLock.unlock();
}
</syntaxhighlight>
Convoys
Mutual exclusion mechanisms can lead to a lock convoy scenario, where multiple threads line up waiting for a lock. This situation compels the JVM to handle expensive wait queues and to 'park' threads. The operations of parking and unparking threads incur significant context switch costs—ranging from microseconds up to milliseconds—while typical Map operations complete in nanoseconds. When contention is intense, system performance may deteriorate sharply, with throughput falling to a small fraction of what a single thread could achieve. Conversely, when contention is minimal, modern JVM implementations often inline most locking code, thereby maintaining low overhead. Nonetheless, reentrant locks such as native synchronization or java.util.concurrent.ReentrantReadWriteLock introduce additional overhead by tracking reentrancy depth, which affects performance even when contention is absent. Although contemporary JVMs have mitigated convoy problems to some extent, slow context switches can still cause considerable latency spikes; with hundreds of threads involved, 10ms context switches may result in total latency measured in seconds.
Multiple cores
Techniques based on mutual exclusion tend to underutilize multi-core processors because only one Thread can execute Map-related code at any given moment. Certain concurrent Map implementations within the Java Collections Framework exploit multiple cores through lock free programming strategies. These utilize atomic operations like compareAndSet(), an intrinsic method available in classes such as Template:Javadoc:SE, to update internal Map structures atomically. The JCF classes enhance compareAndSet() with native-level code that allows atomic modifications of internal object components via 'unsafe' access. These sophisticated methods depend on inter-thread communication principles including volatile variables, happens-before relationships, and lock-free retry loops that ensure forward progress. The compareAndSet() operation relies on processor-specific instructions and can facilitate Lock-free or even Wait-free concurrency models, guaranteeing bounded latency. Lock-free approaches are generally more straightforward to implement for simpler data structures like stacks.
The accompanying diagram contrasts synchronization achieved by wrapping a HashMap (represented in purple) against ConcurrentHashMap (shown in red). Ordered ConcurrentNavigableMaps such as AirConcurrentMap (blue) and ConcurrentSkipListMap (green) demonstrate superior scalability. Note that flat regions in the graph correspond to table expansions during rehashing; ConcurrentHashMap consumes more memory as a trade-off. The system used for testing is an 8-core i7 processor running at 2.5 GHz with -Xms5000m configured to reduce garbage collection interference. JVM and GC activities influence performance curves, and some lock-free implementations generate garbage under contention conditions.
Predictable latency
Approaches relying on mutual exclusion often produce unpredictable latency because they assume operations are fully atomic. Iterators and bulk operations like putAll() may take time proportional to the size of the Map, causing delays for other Threads requiring low-latency access. For example, a multi-threaded web server cannot afford delays caused by lengthy iterations that block other requests searching for values. Moreover, Threads holding locks might never release them if they enter infinite loops, potentially leading to permanent blocking situations. Occasionally, slow owner Threads can be interrupted to mitigate this issue. Hash-based Maps also suffer from sudden pauses during rehashing phases.
Weak consistency
The java.util.concurrent framework tackles challenges such as concurrent modifications, convoy effects, consistent latency, and multi-core processing through a design principle known as weak consistency. This approach allows read operations to proceed without being blocked by ongoing updates, enabling simultaneous reads and writes as well as overlapping updates. For instance, when iterating over a ConcurrentMap within a single Thread, the map's content might be altered during the iteration. Since iterators are intended for use by one thread at a time, maps containing interrelated entries may exhibit inconsistencies during concurrent changes. Changing a key atomically (e.g., switching from k1,v to k2,v) involves a remove(k1) followed by put(k2,v), which can lead to missing or duplicated entries during iteration. Retrieval operations always reflect the most recently completed update on a key, thereby enforcing a 'happens-before' relationship.
Unlike standard Map implementations, ConcurrentMaps do not lock the entire data structure and do not throw ConcurrentModificationException. The size() method may be slower because it often requires scanning all entries instead of relying on a maintained size counter, as seen in non-concurrent collections. During concurrent updates, results from methods like size(), , and represent some snapshot of the map’s state but are not guaranteed to be fully consistent; therefore, these methods are primarily intended for monitoring purposes rather than precise computations.
ConcurrentMap 1.5 methods
The ConcurrentMap interface introduces atomic modification operations that extend beyond those offered by the standard Map. The method replace(K, v1, v2) atomically swaps the value v1 with v2 only if v1 is currently mapped to key K. The replace(k,v) operation executes put(k,v) only if the key k already exists in the map. The putIfAbsent(k,v) method inserts the pair only if k is not present, while remove(k, v) deletes the entry exclusively if its value matches v. These atomic operations facilitate safe multi-threaded manipulation but operate independently of weak consistency semantics.
The following operations on ConcurrentMaps guarantee atomicity:
m.putIfAbsent(k, v) atomically inserts if absent: <syntaxhighlight lang="java">
if (k == null || v == null)
throw new NullPointerException();
if (!m.containsKey(k)) {
return m.put(k, v);
} else {
return m.get(k);
}
</syntaxhighlight>
m.replace(k, v) atomically replaces value if key exists: <syntaxhighlight lang="java">
if (k == null || v == null)
throw new NullPointerException();
if (m.containsKey(k)) {
return m.put(k, v);
} else {
return null;
}
</syntaxhighlight>
m.replace(k, v1, v2) atomically swaps v1 with v2 if present: <syntaxhighlight lang="java">
if (k == null || v1 == null || v2 == null)
throw new NullPointerException();
if (m.containsKey(k) && Objects.equals(m.get(k), v1)) {
m.put(k, v2);
return true;
} else
return false;
} </syntaxhighlight>
m.remove(k, v) atomically removes entry matching value: <syntaxhighlight lang="java">
if (k == null || v == null)
throw new NullPointerException();
if (m.containsKey(k) && Objects.equals(m.get(k), v)) {
m.remove(k);
return true;
} else
return false;
} </syntaxhighlight>
ConcurrentMap 1.8 Methods
Because both Map and ConcurrentMap are interfaces, introducing new methods carries the risk of breaking existing implementations. Java 8 addressed this by adding default methods to the Map interface, including getOrDefault(Object, V), forEach(BiConsumer), replaceAll(BiFunction), computeIfAbsent(K, Function), computeIfPresent(K, BiFunction), compute(K, BiFunction), and merge(K, V, BiFunction). Although these default implementations in Map do not guarantee atomicity, the ConcurrentMap interface provides overrides that employ Lock free mechanisms to maintain atomic operations. Implementing classes may choose to override these defaults to optimize performance and clarify their concurrency characteristics.
Lock-Free Atomic Operations
ConcurrentMaps leverage lock-free strategies enabled by methods with an infinite consensus number, allowing coordination among any number of Threads. For instance, atomically multiplying a value stored in the map by a constant C can be achieved using Java 8’s merge() method or through a general lock-free approach demonstrated below:
<syntaxhighlight lang="java">
static final long C = 10;
void atomicMultiply(ConcurrentMap<Long, Long> map, Long key) {
while (true) {
Long oldValue = map.get(key);
Long newValue = oldValue * C;
if (map.replace(key, oldValue, newValue))
break;
}
}
</syntaxhighlight>
The putIfAbsent(k, v) method is particularly useful when entries might not exist. Although this behavior can also be implemented with compute(), the example illustrates a more general lock-free pattern. Since replace(k,v1,v2) does not accept null arguments, a combined approach is employed: if v1 is null, putIfAbsent(k, v2) is executed; otherwise replace(k,v1,v2) is used.
<syntaxhighlight lang="java">
void atomicMultiplyNullable(ConcurrentMap<Long, Long> map, Long key) {
while (true) {
Long oldValue = map.get(key);
Long newValue = oldValue == null ? INITIAL_VALUE : oldValue * C;
if (replaceNullable(map, key, oldValue, newValue))
break;
}
}
...
static boolean replaceNullable(ConcurrentMap<Long, Long> map, Long key, Long v1, Long v2) {
return v1 == null ? map.putIfAbsent(key, v2) == null : map.replace(key, v1, v2);
}
</syntaxhighlight>
Historical Background
The foundation of the Java collections framework was mainly designed and developed by Joshua Bloch, debuting with JDK 1.2. The initial concurrency-related classes were contributed from Doug Lea’s collection library.
See also
References
External links
- Collections Lessons
- Java 6 Collection Tutorial — Jakob Jenkov and Kadafi Kamphulusa
- Taming Tiger: The Collections Framework
- 'The Collections Framework' (Oracle Java SE 8 documentation)
- 'The Java Tutorials - Collections' by Josh Bloch
- What Java Collection should I use? — A decision flowchart for selecting collections
- 'Which Java Collection to use?' — Janeve George