Java

Collections Framework Overview

Introduction

The Java 2 platform includes a collections framework. A collection is an object that represents a group of objects (such as the classic 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 fourteen collection interfaces. The most basic interface is Collection. These interfaces extend Collection: Set, List, SortedSet, NavigableSet, Queue, Deque, BlockingQueue and BlockingDeque. The other collection interfaces, Map, SortedMap, NavigableMap, ConcurrentMap and ConcurrentNavigableMap 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.

Many 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

Classes 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 Hash Table + Linked List
Interfaces SetHashSet   TreeSet   LinkedHashSet
List  ArrayList   LinkedList  
Deque  ArrayDeque   LinkedList  
Map HashMap   TreeMap   LinkedHashMap

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 the Collections class contains static factories called synchronization wrappers that may be used to add synchronization to many unsynchronized collections. All of the new implementations have fail-fast iterators, which detect illegal concurrent modification, and fail quickly and cleanly (rather than behaving erratically).

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, and 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-2004 Sun Microsystems, Inc. All Rights Reserved.



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