|
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 TablesThe 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
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
java.util.concurrent.ConcurrentHashMap<K, V> 5.0
Copy on Write ArraysThe 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 CollectionsEver 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. |
|