Thread-Safe Collections

If multiple threads concurrently modify a data structure such as a hash table, then it is easily possible to damage the data structure. (We discuss hash tables in greater detail in Chapter 2.) 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 Queues and Hash Tables

The java.util.concurrent package supplies efficient implementations for a queue and a hash table, ConcurrentLinkedQueue and ConcurrentHashMap. 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.

These collections use sophisticated algorithms that never lock the entire table and that minimize contention by allowing simultaneous access to different parts of the data structure.

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

NOTE

In contrast, an iterator of a collection in the java.util package throws a ConcurrentModificationException when the collection has been modified after construction of the iterator.

The ConcurrentHashMap has useful methods for atomic insertion and removal of associations. The putIfAbsent method 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:

 cache.putIfAbsent(key, value); 

The opposite operation is remove (which perhaps should have been called removeIfPresent). The call

 cache.remove(key, value) 

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

 cache.replace(key, oldValue, newValue) 

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

 java.util.concurrent.ConcurrentLinkedQueue<E> 5.0 

• ConcurrentLinkedQueue<E>()

  constructs an unbounded, nonblocking queue that can be safely accessed by multiple threads.

 java.util.concurrent.ConcurrentHashMap<K, V> 5.0 

• ConcurrentHashMap<K, V>()

• ConcurrentHashMap<K, V>(int initialCapacity)

• ConcurrentHashMap<K, V>(int initialCapacity, float loadFactor, int concurrencyLevel)

  construct a hash map that can be safely accessed by multiple threads.

  Parameters	initialCapacity	The initial capacity for this collection. Default is 16
  	loadFactor	Controls resizing: If the average load per bucket exceeds this factor, the table is resized. Default is 0.75
  	concurrencyLevel	The estimated number of concurrent writer threads

  
  

• V putIfAbsent(K key, V value)

  if the key is not yet present in the map, associates the given value with the given key 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 JDK 1.0, the Vector and Hashtable classes provided thread-safe implementations of a dynamic array and a hash table. In JDK 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:

 List synchArrayList = Collections.synchronizedList(new ArrayList()); Map synchHashMap = Collections.synchronizedMap(new HashMap()); 

The methods of the resulting collections are protected by a lock, providing thread-safe access. However, if you want to iterate over the collection, you need to use a synchronized block:

 synchronized (synchHashMap) {    Iterator iter = synchHashMap.keySet().iterator();    while (iter.hasNext()) . . .; } 

We discuss these wrappers in greater detail in Chapter 2.