Thread-Safe Collections Core Java

If multiple threads concurrently modify a data structure such as a hash table, then it is easily possible to damage the data structure. For example, one thread may begin to insert a new element. Suppose it is preempted while it is in the middle of rerouting the links between the hash table’s buckets.

If another thread starts traversing the same list, it may follow invalid links and create havoc, perhaps throwing exceptions or being trapped in an infinite loop. You can protect a shared data structure by supplying a lock, but it is usually easier to choose a thread-safe implementation instead. The blocking queues that we discussed in the preceding section are, of course, thread-safe collections. In the following sections, we discuss the other thread-safe collections that the Java library provides.

Efficient Maps, Sets, and Queues

The java.util.concurrent package supplies efficient implementations for maps, sorted sets, and queues: Concurrent Hash Map, Concurrent Skip List Map, Concurrent Skip List Set, and Concurrent Linked Queue.

These collections use sophisticated algorithms that minimize contention by allowing concurrent access to different parts of the data structure. Unlike in most collections, the size method does not necessarily operate in constant time. Determining the current size of one of these collections usually requires traversal.

The collections return weakly consistent iterators. That means that the iterators may ormay not reflect all modifications that are made after they were constructed, but they will not return a value twice and they will not throw a Concurrent Modification Exception.

NOTE: In contrast, an iterator of a collection in the java.util package throws a Concurrent Modification Exception

when the collection has been modified after construction of the iterator. The concurrent hash map can efficiently support a large number of readers and a fixed number of writers. By default, it is assumed that there are up to 16 simultaneous writer threads. There can be many more writer threads, but if more than 16 write at the same time, the others are temporarily blocked. You can specify a higher number in the constructor, but it is unlikely that you will need to.

The ConcurrentHashMap and ConcurrentSkipListMap classes have useful methods for atomic insertion and removal of associations. The putIfAbsent method atomically adds a new association provided there wasn’t one before. This is useful for a cache that is accessed by multiple threads, to ensure that only one thread adds an item into the cache:

The opposite operation is remove .

atomically removes the key and value if they are present in the map. Finally,

atomically replaces the old value with the new one, provided the old value was associated with the given key.

java.util.concurrent.ConcurrentLinkedQueue<E>

  • ConcurrentLinkedQueue<E>()
    constructs an unbounded, nonblocking queue that can be safely accessed by multiple threads.

java.util.concurrent.ConcurrentSkipListSet<E>

  • ConcurrentSkipListSet<E>()
  • ConcurrentSkipListSet<E>(Comparator<? super E> comp)
    constructs a sorted set that can be safely accessed by multiple threads. The first constructor requires that the elements implement the Comparable interface.

java.util.concurrent.ConcurrentSkipListMap<K, V>

  • ConcurrentHashMap<K, V>()
  • ConcurrentHashMap<K, V>(int initialCapacity)
  • ConcurrentHashMap<K, V>(int initialCapacity, float loadFactor, int concurrencyLevel)
    constructs a hash map that can be safely accessed by multiple threads.
  • ConcurrentSkipListMap<K, V>()
  • ConcurrentSkipListSet<K, V>(Comparator<? super K> comp)
    constructs a sorted map that can be safely accessed by multiple threads. The first constructor requires that the keys implement the Comparable interface.
  • V putIfAbsent(K key, V value)
    if the key is not yet present in the map, associates the given value with the givenkey and returns null. Otherwise returns the existing value associated with the key.
  • boolean remove(K key, V value)
    if the given key is currently associated with this value, removes the given key and value and returns true. Otherwise returns false.
  • boolean replace(K key, V oldValue, V newValue)
    if the given key is currently associated with oldValue, associates it with newValue. Otherwise, returns false.

Copy on Write Arrays

The CopyOnWriteArrayList and CopyOnWriteArraySet are thread-safe collections in which all mutators make a copy of the underlying array. This arrangement is useful if the number of threads that iterate over the collection greatly outnumbers the threads that mutate it.

When you construct an iterator, it contains a reference to the current array. If the array is later mutated, the iterator still has the old array, but the collection’s array is replaced. As a consequence, the older iterator has a consistent (but potentially outdated) view that it can access without any synchronization expense.

Older Thread-Safe Collections

Ever since the initial release of Java, the Vector and Hashtable classes provided thread-safe implementations of a dynamic array and a hash table. In Java SE 1.2, these classes were declared obsolete and replaced by the ArrayList and HashMap classes. Those classes are not thread-safe. Instead, a different mechanism is supplied in the collections library. Any collection class can be made thread-safe by means of a synchronization wrapper:

The methods of the resulting collections are protected by a lock, providing thread-safeaccess.You should make sure that no thread accesses the data structure through the original unsynchronized methods. The easiest way to ensure this is not to save any reference to the original object. Simply construct a collection and immediately pass it to the wrapper, as we did in our examples.

You still need to use “client-side” locking if you want to iterate over the collection while another thread has the opportunity to mutate it:

You must use the same code if you use a “for each” loop because the loop uses an iterator. Note that the iterator actually fails with a ConcurrentModificationException if another thread mutates the collection while the iteration is in progress. The synchronization is still required so that the concurrent modification can be reliably detected.

You are usually better off using the collections defined in the java.util.concurrent package instead of the synchronization wrappers. In particular, the ConcurrentHashMap map has been carefully implemented so that multiple threads can access it without blocking each other, provided they access different buckets. One exception is an array list that is frequently mutated. In that case, a synchronized ArrayList can outperform a CopyOnWriteArrayList.

  • static <E> Collection<E> synchronizedCollection(Collection<E> c)
  • static <E> List synchronizedList(List<E> c)
  • static <E> Set synchronizedSet(Set<E> c)
  • static <E> SortedSet synchronizedSortedSet(SortedSet<E> c)
  • static <K, V> Map<K, V> synchronizedMap(Map<K, V> c)
  • static <K, V> SortedMap<K, V> synchronizedSortedMap(SortedMap<K, V> c) constructs views of the collection whose methods are synchronized.

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Core Java Topics