The Java programming language's Java Collections Framework version 1.5 and later defines and implements the original regular single-threaded maps, and also new thread-safe maps implementing the java.util.concurrent.ConcurrentMap interface among other concurrent interfaces. In Java 1.6, the java.util.NavigableMap interface was added, extending java.util.SortedMap, and the java.util.concurrent.ConcurrentNavigableMap interface was added as a subinterface combination.
Java Map Interfaces The version 1.8 java.util.Map<K, V> interface diagram has the shape below. Sets can be considered sub-cases of corresponding maps in which the values are always a particular constant which can be ignored, although the java.util.Set<E> API uses corresponding but differently named methods. At the bottom is the java.util.concurrent.ConcurrentNavigableMap<K, V>, which is a multiple-inheritance.
java.util.Collection java.util.Map java.util.SortedMap java.util.NavigableMap java.util.concurrent.ConcurrentNavigableMap java.util.concurrent.ConcurrentMap java.util.concurrent.ConcurrentNavigableMap
Implementations
ConcurrentHashMap For unordered access as defined in the java.util.Map<K, V> interface, the java.util.concurrent.ConcurrentHashMap<K, V> implements java.util.concurrent.ConcurrentMap<K, V>. The mechanism is a hash access to a hash table with lists of entries, each entry holding a key, a value, the hash, and a next reference. Previous to Java 8, there were multiple locks each serializing access to a 'segment' of the table. In Java 8, native synchronization is used on the heads of the lists themselves, and the lists can mutate into small trees when they threaten to grow too large due to unfortunate hash collisions. Also, Java 8 uses the compare-and-set primitive optimistically to place the initial heads in the table, which is very fast. Performance is O ( n ) {\displaystyle O(n)} , but there are delays occasionally when rehashing is necessary. After the hash table expands, it never shrinks, possibly leading to a memory 'leak' after entries are removed.
ConcurrentSkipListMap For ordered access as defined by the java.util.NavigableMap<K, V> interface, java.util.concurrent.ConcurrentSkipListMap<K, V> was added in Java 1.6, and implements java.util.concurrent.ConcurrentMap<K, V> and also java.util.concurrent.ConcurrentNavigableMap<K, V>. It is a skip list which uses lock-free techniques to make a tree. Performance is O ( l o g ( n ) ) {\displaystyle O(log(n))} .
Concurrent modification problem One problem solved by the Java 1.5 java.util.concurrent<K, V> package is that of concurrent modification. The collection classes it provides may be reliably used by multiple java.lang.Threads. All thread-shared non-concurrent maps and other collections need to use some form of explicit locking such as native synchronization in order to prevent concurrent modification, or else there must be a way to prove from the program logic that concurrent modification cannot occur. Concurrent modification of a java.lang.Map<K, V> by multiple threads will sometimes destroy the internal consistency of the data structures inside the java.lang.Map<K, V>, leading to bugs which manifest rarely or unpredictably, and which are difficult to detect and fix. Also, concurrent modification by one thread with read access by another thread or threads will sometimes give unpredictable results to the reader, although the map's internal consistency will not be destroyed. Using external program logic to prevent concurrent modification increases code complexity and creates an unpredictable risk of errors in existing and future code, although it enables non-concurrent Collections to be used. However, either locks or program logic cannot coordinate external threads which may come in contact with the java.util.Collection<E>.
Modification counters In order to help with the concurrent modification problem, the non-concurrent java.lang.Map<K, V> implementations and other java.util.Collection<E>s use internal modification counters which are consulted before and after a read to watch for changes: the writers increment the modification counters. A concurrent modification is supposed to be detected by this mechanism, throwing a java.util.ConcurrentModificationException, but it is not guaranteed to occur in all cases and should not be relied on. The counter maintenance is also a performance reducer. For performance reasons, the counters are not volatile, so it is not guaranteed that changes to them will be propagated between Threads.
Collections.synchronizedMap() One solution to the concurrent modification problem is using a particular wrapper class provided by a factory in java.util.Collections : public static <K, V> Map<K, V> synchronizedMap(Map<K, V> m) which wraps an existing non-thread-safe Map with methods that synchronize on an internal mutex. There are also wrappers for the other kinds of java.util.Collection<E>s. This is a partial solution, because it is still possible that the underlying java.util.Map<K, V> can be inadvertently accessed by java.lang.Threads which keep or obtain unwrapped references. Also, all java.util.Collection<E>s implement the java.lang.Iterable but the synchronized-wrapped java.util.Map<K, V>s and other wrapped java.util.Collection<E>s do not provide synchronized iterators, so the synchronization is left to the client code, which is slow and error prone and not possible to expect to be duplicated by other consumers of the synchronized java.util.Map<K, V>. The entire duration of the iteration must be protected as well. Furthermore, a java.util.Map<K, V> which is wrapped twice in different places will have different internal mutex objects on which the synchronizations operate, allowing overlap. The delegation is a performance reducer, but modern just-in-time compilers often inline heavily, limiting the performance reduction. Here is how the wrapping works inside the wrapper - the mutex is just a final java.util.Object and m is the final wrapped java.util.Map<K, V>:
The synchronization of the iteration is recommended as follows; however, this synchronizes on the wrapper rather than on the internal mutex, allowing overlap:
… excerpt ends here. Continue reading the full article.
