Collections Framework Enhancements

This page summarizes enhancements to the collections framework in version 5 of the JDK.

Three new language features significantly enhance the collections framework:

Generics - adds compile-time type safety to the collections framework and eliminates the need to cast when reading elements from collections.
Enhanced for loop - eliminates the need for explicit iterators when interating over collections.
Autoboxing/unboxing - automatically converts primitives (such as int) to wrapper classes (such as Integer) when inserting them into collections, and converts wrapper class instances to primitives when reading from collections.

Three new collection interfaces are provided:

Queue - represents a collection designed for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations.
BlockingQueue - extends Queue with operations that wait for the queue to become non-empty when retrieving an element, and that wait for space to become available in the queue when storing an element. (This interface is part of the new package java.util.concurrent.)
ConcurrentMap - extends Map with atomic putIfAbsent, remove, and replace methods. (This interface is part of java.util.concurrent.)

Two new concrete Queue implementations are provided, one existing List implementation has been retrofitted to implement Queue, and one abstract Queue implementation is provided:

PriorityQueue - an unbounded priority queue backed by a heap.
ConcurrentLinkedQueue - an unbounded thread-safe FIFO (first-in first-out) queue backed by linked nodes. (This class is part of java.util.concurrent.)
LinkedList - retrofitted to implement the Queue interface. When accessed via the Queue interface, LinkedList behaves as a FIFO queue.
AbstractQueue - a skeletal Queue implementation.

Five new BlockingQueue implementations are provided, all of which are part of java.util.concurrent:

LinkedBlockingQueue - an optionally bounded FIFO blocking queue backed by linked nodes.
ArrayBlockingQueue - a bounded FIFO blocking queue backed by an array.
PriorityBlockingQueue - an unbounded blocking priority queue backed by a heap.
DelayQueue - a time-based scheduling queue backed by a heap.
SynchronousQueue - a simple rendezvous mechanism utilizing the BlockingQueue interface.

One ConcurrentMap implementation is provided:

ConcurrentHashMap - a highly concurrent, high-performance ConcurrentMap implementation backed by a hash table. This implementation never blocks when performing retrievals and allows the client to select the concurrency level for updates. It is intended as a drop-in replacement for Hashtable: in addition to implementing ConcurrentMap, it supports all of the "legacy" methods peculiar to Hashtable.

Special-purpose List and Set implementations are provided for use in situations where read operations vastly outnumber write operations and iteration cannot or should not be synchronized:

CopyOnWriteArrayList - a List implementation backed by an array. All mutative operations (such as add, set, and remove) are implemented by making a new copy of the array. No synchronization is necessary, even during iteration, and iterators are guaranteed never to throw ConcurrentModificationException. This implementation is well-suited to maintaining event-handler lists (where change is infrequent, and traversal is frequent and potentially time-consuming).
CopyOnWriteArraySet - a Set implementation backed by a copy-on-write array. This implementation is similar in nature to CopyOnWriteArrayList. Unlike most Set implementations, the add, remove, and contains methods require time proportional to the size of the set. This implementation is well-suited to maintaining event-handler lists that must prevent duplicates.

Special-purpose Set and Map implementations are provided for use with enums:

EnumSet - a high-performance Set implementation backed by a bit-vector. All elements of each EnumSet instance must be elements of a single enum type.
EnumMap - a high-performance Map implementation backed by an array. All keys in each EnumMap instance must be elements of a single enum type.

A new family of wrapper implementations is provided, primarily for use with generic collections:

Collections.checkedInterface - returns a dynamically typesafe view of the specified collection, which throws a ClassCastException if a client attempts to add an element of the wrong type. The generics mechanism in the language provides compile-time (static) type checking, but it is possible to defeat this mechanism. Dynamically typesafe views eliminate this possibility entirely.

Three new generic algorithms and one comparator converter were added to the Collections utility class:

frequency(Collection<?> c, Object o) - counts the number of times the specified element occurs in the specified collection.
disjoint(Collection<?> c1, Collection<?> c2) - determines whether two collecitons are disjoint, in other words, whether they contain no elements in common.
addAll(Collection<? super T> c, T... a) - convenience method to add all of the elements in the specified array to the specified collection.
Comparator<T> reverseOrder(Comparator<T> cmp) - returns a comparator that represents the reverse ordering of the specified comparator.

The Arrays utility class has been outfitted with content-based hashCode and toString methods for arrays of all types. These methods complement the existing equals methods. Versions of all three methods are provided to operate on nested (or "multidimensional") arrays: deepEquals, deepHashCode, and deepToString. It is now trivial to print the contents of any array. The idiom for printing a "flat" array is:

    System.out.println(Arrays.toString(a));

The idiom for printing a nested (multidimensional) array is:

    System.out.println(Arrays.deepToString(a));

Finally, Boolean was retrofitted to implement Comparable.