Close

Java - Concurrent Maps

[Last Updated: Jul 2, 2017]

This is a quick walk-through tutorial of Java concurrent Maps.

Interfaces



Operations




Implementations


All implementations of map in java.util.concurrent package are thread safe. These implementations use fine grained locking/synchronization for thread safety.

Impl
ADT
Data Structure
Performance 
(Big O notation)
ConcurrentHashMap ConcurrentMap Hash table.
Null Not permitted for keys or values.
Locking (fine grained) is applied but not on retrieval operations. Unlike Hashtable, high expected concurrency for updates.
Capacity and Load Factor are the tuning factors (just like HashMap)
concurrencyLevel: is another optional tuning factor which is the estimated number of concurrently updating threads. This value is a capacity hint:
if (initialCapacity < concurrencyLevel)
initialCapacity = concurrencyLevel;   

parallelismThreshold is the argument used by additional bulk methods (Java 8 stream related): forEach, forEachKey, forEachValue, forEachEntry, reduce, reduceKeys, reduceKeysToDouble(Int/Long), reduceValues, reduceValuesToDouble(Int/Long), reduceToDouble(Int/Long), search, searchKeys, searchValues, searchEntries. Using a value of 1 results in maximal parallelism. Like other read-only methods these methods do not entail locking.
Ignoring locking overhead:
get, put: O(1) It can be O(n) if we use bad hashCode causing more elements added to one bucket.
Iteration over collection views requires time proportional to the capacity of the map plus its size.

Iterators, Spliterators and Enumerations reflect the state of the map at the time they were created. They do not throw ConcurrentModificationException. Iterators are designed to be used by only one thread at a time.
Similarly, the results of aggregate status methods including size, isEmpty, and containsValue are typically useful only when a map is not undergoing concurrent updates in other threads. Otherwise the results of these methods reflect transient states that are not suitable for program control.
ConcurrentSkipListMap ConcurrentNavigableMap Skip List.

Does not permit null keys or values.

Insertion, removal, update, and access operations safely execute concurrently by multiple threads.

Bulk operations putAll, equals, toArray, containsValue, and clear are not guaranteed to be performed atomically. For example, an iterator operating concurrently with a putAll operation might view only some of the added elements.
containsKey, get, put and remove operations and their variants: O(log n)
size: is not a constant-time operation. Because of the asynchronous nature of these maps, determining the current number of elements requires a traversal of the elements, and so may report inaccurate results if this collection is modified during traversal.

Iterators and spliterators are weakly consistent.

Ascending key ordered views and their iterators are faster than descending ones.




Choosing a Thread-safe Map

Generally we should use java.util.concurrent maps if different thread must not coordinates reads and write, that's because they give higher throughput as compare to Collections.synchronizedXyz(....) methods.

See Also