8.1 Overview of Collection Classes - Java Threads, Third Edition

8.1 Overview of Collection Classes

In the beginning, Java provided only a few collection classes. In fact, in the first version of Java, these classes weren't even referred to as collection classes; they were simply utility classes that Java provided. For the most part, these classes were all threadsafe; the early collection classes were designed to prevent developers from inadvertently corrupting the data structures by using them in different threads without appropriate data synchronization.

JDK 1.2 introduced the formal idea of collection classes. The few existing data collection classes from JDK 1.0 and 1.1 were integrated into this framework, which was expanded to include new classes and new interfaces. Defining the collection classes in terms of interfaces made it possible to write programs that could use different collection implementations at runtime.

The controversial change introduced in JDK 1.2 is that most of the collection classes are now, by default, not threadsafe. Threadsafe versions of the classes exist, but the decision was made to allow the developer to manage the thread-safety of the classes. Two factors inform this decision: the performance of synchronization and the requirements of algorithms that use the collection. We'll have more to say on those issues in the next section. JDK 1.3 and 1.4 added some minor extensions to these collection classes.

J2SE 5.0 introduces a number of new collection classes. Some of these classes are simple extensions to the existing collections framework, but many of them have two distinguishing features. First, their internal implementation makes heavy use of the new J2SE 5.0 synchronization tools (in particular, atomic variables). Second, most of these classes are designed to be used by multiple threads and support the idea of thread notification when data in the collection becomes available.

8.1.1 Collection Interfaces

As we mentioned, the collection classes are based around a set of interfaces introduced in JDK 1.2:

java.util.List

A list is an ordered set of data (e.g., an array). Unlike actual arrays, lists are not fixed in size; they can grow as more data is added. Lists provide methods to get and set data elements by index and also to insert or remove data at arbitrary points (expanding or shrinking the list as necessary). Therefore, they can also be thought of as linked lists.

java.util.Map

A map associates values with keys. Duplicate keys are not allowed; each key maps to at most one value. The java.util.SortedMap interface extends this to provide maps that are sorted based on a collection-specific definition. The java.util.Dictionary interface provides essentially the same interface as a map but is "obsolete" (unofficially deprecated).

java.util.Set

A set is a collection of elements that are stored in no particular order. Duplicate elements are not allowed. The java.util.SortedSet interface extends this to provide a sorted set of objects.

java.util.Queue

A queue is an ordered set of data that is operated on in either last-in-first-out (LIFO) or first-in-first-out (FIFO) order (although no implementations presently support a LIFO ordering). Previously, queues could be simulated by lists, but the new queue implementations are more efficient. This interface was introduced in J2SE 5.0.

8.1.2 Threadsafe Collection Classes

Only a few collection classes are threadsafe. As we'll see later, being threadsafe does not necessarily mean that you can safely use them in every multithreaded program; programs must still be designed in a fashion that allows the collection to be used by multiple threads. Here are some of the more common threadsafe collection classes:

java.util.Vector (a List)

A simple array, allowing index-based operations and random insertion and deletion.

java.util.Stack (a List)

The Stack class extends the Vector class to provide the ability to treat the vector as a stack. Objects can be pushed onto the stack or popped from the stack, providing a LIFO ordering (however, this class does not implement the Queue interface).

java.util.Hashtable (a Map)

A simple, unordered map of keys to values.

java.util.concurrent.ConcurrentHashMap (a Map)

A class that implements an unordered map. It uses less synchronization than the Hashtable class.

java.util.concurrent.CopyOnWriteArrayList (a List)

A simple array list that provides safe semantics for unsynchronized iterator access.

java.util.concurrent.CopyOnWriteArraySet (a Set)

A simple set that provides safe semantics for unsynchronized iterator access.

java.util.concurrent.ConcurrentLinkedQueue (a Queue)

An unbounded FIFO queue. It is optimized for multiple threads inserting and removing items from the collection.

8.1.3 Thread-Unsafe Collection Classes

The majority of collection classes are not threadsafe. When used in multithreaded programs, access to them must always be controlled by some synchronization. This synchronization can be accomplished either by using a "wrapper" class that synchronizes every access operation (using the Collections class, which we'll show later) or by using explicit synchronization:

java.util.BitSet

A bit set stores an array of boolean (1-bit) values. The size of the array can grow at will. A BitSet saves space compared to an array of booleans since the bit set can store multiple values in one long variable. Despite its name, it does not implement the Set interface.

java.util.HashSet (a Set)

A class that implements an unordered set collection.

java.util.TreeSet (a SortedSet)

A class that implements a sorted (and ordered) set collection.

java.util.HashMap (a Map)

A class that implements an unordered map collection.

java.util.WeakHashMap (a Map)

This class is similar to the HashMap class. The difference is that the key is a weak reference梚t is not counted as a reference by the garbage collector. The class therefore deletes key-value pair entries from the map when the key has been garbage collected.

java.util.TreeMap (a SortedMap)

A class that implements a sorted (and ordered) map collection. This map is based on binary trees (so operations require log(n) time to perform).

java.util.ArrayList (a List)

A class that implements a list collection. Internally, it is implemented using arrays.

java.util.LinkedList (a List and a Queue)

A class that implements a list and a queue collection, providing a doubly linked list.

java.util.LinkedHashSet (a Set)

A set collection that sorts its items based on the order in which they are added to the set.

java.util.LinkedHashMap (a Map)

A map collection that sorts its items based on the order in which they are added to the map.

java.util.IdentityHashMap (a Map)

A map collection. Unlike all other maps, this class uses == for key comparison instead of the equals() method.

java.util.EnumSet (a Set)

A specialized set collection that holds only Enum values.

java.util.EnumMap (a Map)

A specialized map collection that uses only Enum values as keys.

java.util.PriorityQueue (a Queue)

An unbounded queue in which retrieval is not based on order (LIFO or FIFO); instead, objects are removed according to which is the smallest (as determined by the Comparable or Comparator interface).

8.1.4 Thread-Notification Collection Classes

A number of classes in the java.util.concurrent package are designed to provide thread notification when their contents change. They are inherently threadsafe since they are expected to be used by multiple threads simultaneously. They simplify usage of collections by providing semantics to handle out-of-space and out-of-data conditions within the collection. We'll see examples of this later in the chapter.

java.util.concurrent.ArrayBlockingQueue (a Queue)

A bounded FIFO queue. This collection supports the blocking interface, an interface that allows threads to wait either for space to be available (while storing data) or data to be available (while retrieving data).

java.util.concurrent.LinkedBlockingQueue (a Queue)

A FIFO queue that can be either bounded or unbounded. This collection supports the blocking interface.

java.util.concurrent.SynchronousQueue (a Queue)

A bounded FIFO queue. The bound on this queue is one (no elements are actually held in the collection), and multiple threads operate on it synchronously.

java.util.concurrent.PriorityBlockingQueue (a Queue)

A threadsafe implementation of the PriorityQueue class. This class also supports the blocking interface.

java.util.concurrent.DelayQueue (a Queue)

A class that implements an unbounded queue with a time-based order. Retrieval from the queue is based on the object whose getDelay() method has expired earliest: elements whose time expiration has not occurred can't be retrieved from the queue.