23.7 Concurrent Collections and Maps
Most of the collections in the java.util package are not thread-safe—executing concurrent operations on them is courting disaster. Exceptions to this are the legacy Vector and Hashtable classes, but these use a single lock, allowing only one thread at a time to execute an operation on the collection while other threads are blocked. The synchronized collections created by methods in the java.util.Collections class are not much better, as they are just thread-safe wrappers around a backing collection, again providing only mutually exclusive operations on the backing collection. However, the concurrent collections provided by the java.util.concurrent package use special-purpose locking mechanisms to enable multiple threads to operate concurrently, without explicit locking on the collection and with minimal contention. The concurrent collections offer greater flexibility and higher scalability compared to the collections in the java.util package, when concurrent access is crucial for multiple threads sharing objects stored in a collection.
We assume familiarity with the Collections Framework, especially the core interfaces in the java.util package (Chapter 15, p. 781), as these are implemented by the concurrent collections to provide thread-safety and atomicity of operations defined by these interfaces:
| Collection | (§15.3, p. 863) | Queue | (§15.6, p. 877) |
| List | (§15.3, p. 863) | Deque | (§15.7, p. 884) |
| Set | (§15.4, p. 867) | Map | (§15.8, p. 894) |
| NavigableSet | (§15.5, p. 874) | NavigableMap | (§15.10, p. 909) |
It is also important to note that concurrent collections avoid memory consistency errors by defining a happens-before relationship that essentially states that an action by a thread to place an object into a concurrent collection happens-before a subsequent action to access or remove that object from the collection by another thread.
The concurrent collections and maps in the java.util.concurrent package can be categorized as follows:
- Concurrent collections (p. 1485)
- Concurrent maps (p. 1490)
- Blocking queues (p. 1495)
- Copy-on-write collections (p. 1501)
The following aspects about collections and maps should be noted, as they can be crucial in selecting an appropriate collection for maintaining the elements:
- Non-blocking or blocking
Operations on a non-blocking collection do not use any locking mechanism (are lock-free) to access elements of the collection, allowing multiple threads to execute concurrently, in contrast to a blocking collection in which operations can block to acquire a lock before they can proceed, because only one thread at a time is allowed.
Collections with Concurrent as a prefix to their name are all non-blocking—for example, a ConcurrentHashMap. All queues implementing the BlockingQueue<E> interface, not surprisingly, are blocking collections. The names of many queues reveal their blocking nature—for example, a LinkedBlockingQueue.
- Unbounded and bounded
A bounded collection has a fixed capacity that defines the maximum number of elements allowed in the collection and is usually specified when the collection is created. When the collection is full, some operations, such as adding an element, will block until there is space in the collection. Unbounded collections are not bounded by any capacity restriction. Optionally bounded collections can be instantiated to behave either as bounded or as unbounded.
An ArrayBlockingQueue is a bounded queue, whereas a ConcurrentLinkedQueue is unbounded, but a LinkedBlockingDeque can be optionally bounded.
