Java

Collections Framework Overview

Introduction

The 1.2 release of the Java platform includes a new collections framework. A collection is an object that represents a group of objects (such as the familiar Vector class). A collections framework is a unified architecture for representing and manipulating collections, allowing them to be manipulated independently of the details of their representation.

The primary advantages of a collections framework are that it:

The collections framework consists of:


Collection Interfaces

There are six collection interfaces. The most basic interface is Collection. Three interfaces extend Collection: Set, List, and SortedSet. The other two collection interfaces, Map and SortedMap, do not extend Collection, as they represent mappings rather than true collections. However, these interfaces contain collection-view operations, which allow them to be manipulated as collections.

All of the modification methods in the collection interfaces are labeled optional. Some implementations may not perform one or more of these operations, throwing a runtime exception (UnsupportedOperationException) if they are attempted. Implementations must specify in their documentation which optional operations they support. Several terms are introduced to aid in this specification:

Some implementations may restrict what elements (or in the case of Maps, keys and values) may be stored. Possible restrictions include requiring elements to:

Attempting to add an element that violates an implementation's restrictions results in a runtime exception, typically a ClassCastException, an IllegalArgumentException or a NullPointerException. Attempting to remove or test for the presence of an element that violates an implementation's restrictions may result in an exception, though some "restricted collections" may permit this usage.


Collection Implementations

Class that implement the collection interfaces typically have names of the form <Implementation-style><Interface>. The general purpose implementations are summarized in the table below:
 
  Implementations
Hash TableResizable Array Balanced TreeLinked List
Interfaces SetHashSet   TreeSet  
List   ArrayList   LinkedList
Map HashMap   TreeMap  

The general-purpose implementations support all of the optional operations in the collection interfaces, and have no restrictions on the elements they may contain. They are unsynchronized, but may be synchronized externally with synchronizing wrappers. They have fail-fast iterators, which throw a ConcurrentModificationException in response to concurrent modification of the the backing collection rather than behaving non-deterministically. The Collections class contains static factories called synchronization wrappers that may be used to add synchronization to any unsynchronized collection. All of the new implementations have fail-fast iterators, which detect illegal concurrent modification, and fail quickly and cleanly.

The AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList and AbstractMap classes provide skeletal implementations of the core collection interfaces, to minimize the effort required to implement them. The API documentation for these classes describes precisely how each method is implemented so the implementer knows which methods should be overridden, given the performance of the "basic operations" of a specific implementation.


Design Goals

The main design goal was to produce an API that was reasonably small, both in size, and, more importantly, in "conceptual weight." It was critical that the new functionality not seem alien to current Java programmers; it had to augment current facilities, rather than replacing them. At the same time, the new API had to be powerful enough to provide all the advantages described above.

To keep the number of core interfaces small, the interfaces do not attempt to capture such subtle distinctions as mutability, modifiability, resizability. Instead, certain calls in the core interfaces are optional, allowing implementations to throw an UnsupportedOperationException to indicate that they do not support a specified optional operation. Of course, collection implementers must clearly document which optional operations are supported by an implementation.

To keep the number of methods in each core interface small, an interface contains a method only if either:

  1. It is a truly fundamental operation: a basic operations in terms of which others could be reasonably defined,
  2. There is a compelling performance reason why an important implementation would want to override it.

It was critical that all reasonable representations of collections interoperate well. This included arrays, which cannot be made to implement the Collection interface directly without changing the language. Thus, the framework includes methods to allow collections to be dumped into arrays, arrays to be viewed as collections, and maps to be viewed as collections.


Copyright © 1995-98 Sun Microsystems, Inc. All Rights Reserved.



Please send comments to: collections-comments@java.sun.com
Sun
Java Software