Collections Framework Overview

Introduction

The Java platform includes acollections framework. Acollection is an object that represents a group of objects(such as the classicVector class). Acollections framework is a unified architecture for representingand manipulating collections, enabling collections to bemanipulated independently of implementation details.

The primary advantages of a collections framework are thatit:

Reduces programming effort by providing datastructures and algorithms so you don't have to write themyourself.
Increases performance by providinghigh-performance implementations of data structures and algorithms.Because the various implementations of each interface areinterchangeable, programs can be tuned by switchingimplementations.
Provides interoperability between unrelatedAPIs by establishing a common language to pass collectionsback and forth.
Reduces the effort required to learn APIs byrequiring you to learn multiple ad hoc collection APIs.
Reduces the effort required to design and implementAPIs by not requiring you to produce ad hoc collectionsAPIs.
Fosters software reuse by providing a standardinterface for collections and algorithms with which to manipulatethem.

The collections framework consists of:

Collection interfaces. Represent differenttypes of collections, such as sets, lists, and maps. Theseinterfaces form the basis of the framework.
General-purpose implementations. Primaryimplementations of the collection interfaces.
Legacy implementations. The collection classesfrom earlier releases,Vector andHashtable, wereretrofitted to implement the collection interfaces.
Special-purpose implementations.Implementations designed for use in special situations. Theseimplementations display nonstandard performance characteristics,usage restrictions, or behavior.
Concurrent implementations. Implementationsdesigned for highly concurrent use.
Wrapper implementations. Add functionality,such as synchronization, to other implementations.
Convenience implementations. High-performance"mini-implementations" of the collection interfaces.
Abstract implementations. Partialimplementations of the collection interfaces to facilitate customimplementations.
Algorithms. Static methods that perform usefulfunctions on collections, such as sorting a list.
Infrastructure. Interfaces that provideessential support for the collection interfaces.
Array Utilities. Utility functions for arraysof primitive types and reference objects. Not, strictly speaking, apart of the collections framework, this feature was added to theJava platform at the same time as the collections framework andrelies on some of the same infrastructure.

Collection Interfaces

Thecollection interfaces are divided into two groups.The most basic interface,java.util.Collection,has the following descendants:

The other collection interfaces are based onjava.util.Map and arenot true collections. However, these interfaces containcollection-view operations, which enable them to bemanipulated as collections.Map has the followingoffspring:

Many of the modification methods in the collection interfacesare labeledoptional. Implementations are permitted to notperform one or more of these operations, throwing a runtimeexception (UnsupportedOperationException) if they areattempted. The documentation for each implementation must specifywhich optional operations are supported. Several terms areintroduced to aid in this specification:

Collections that do not support modification operations (suchasadd,remove andclear) are referredto asunmodifiable. Collections that are not unmodifiablearemodifiable.
Collections that additionally guarantee that no change in theCollection object will be visible are referred to asimmutable. Collections that are not immutable aremutable.
Lists that guarantee that their size remains constant eventhough the elements can change are referred to asfixed-size. Lists that are not fixed-size are referred to asvariable-size.
Lists that support fast (generally constant time) indexedelement access are known asrandom access lists. Lists thatdo not support fast indexed element access are known assequential access lists. TheRandomAccessmarker interface enables lists to advertise the fact that theysupport random access. This enables generic algorithms to changetheir behavior to provide good performance when applied to eitherrandom or sequential access lists.

Some implementations restrict what elements (or in the case ofMaps, keys and values) can be stored. Possiblerestrictions include requiring elements to:

Be of a particular type.
Be not null.
Obey some arbitrary predicate.

Attempting to add an element that violates an implementation'srestrictions results in a runtime exception, typically aClassCastException, anIllegalArgumentException,or aNullPointerException. Attempting to remove or testfor the presence of an element that violates an implementation'srestrictions can result in an exception. Some restrictedcollections permit this usage.

Collection Implementations

Classes that implement the collection interfaces typically havenames in the form of<Implementation-style><Interface>.The general purpose implementations are summarized in the followingtable:

Interface	Hash Table	Resizable Array	Balanced Tree	Linked List	Hash Table + Linked List
`Set`	`HashSet`		`TreeSet`		`LinkedHashSet`
`List`		`ArrayList`		`LinkedList`
`Deque`		`ArrayDeque`		`LinkedList`
`Map`	`HashMap`		`TreeMap`		`LinkedHashMap`

The general-purpose implementations support all of theoptional operations in the collection interfaces and have norestrictions on the elements they may contain. They areunsynchronized, but theCollections class contains staticfactories calledsynchronization wrappers that can be used to addsynchronization to many unsynchronized collections. All of the newimplementations havefail-fast iterators, which detectinvalid concurrent modification, and fail quickly and cleanly(rather than behaving erratically).

TheAbstractCollection,AbstractSet,AbstractList,AbstractSequentialList andAbstractMap classes provide basic implementations of thecore collection interfaces, to minimize the effort required toimplement them. The API documentation for these classes describesprecisely how each method is implemented so the implementer knowswhich methods must be overridden, given the performance of thebasic operations of a specific implementation.

Concurrent Collections

Applications that use collections from more than one thread mustbe carefully programmed. In general, this is known asconcurrentprogramming. The Java platform includes extensive support forconcurrent programming. SeeJava ConcurrencyUtilities for details.

Collections are so frequently used that various concurrentfriendly interfaces and implementations of collections are includedin the APIs. These types go beyond the synchronization wrappersdiscussed previously to provide features that are frequently neededin concurrent programming.

These concurrent-aware interfaces are available:

The following concurrent-aware implementation classes areavailable. See the API documentation for the correct usage of theseimplementations.

Design Goals

The main design goal was to produce an API that was small insize and, more importantly, in "conceptual weight." Itwas critical that the new functionality not seem too different tocurrent Java programmers; it had to augment current facilities,rather than replace them. At the same time, the new API had to bepowerful enough to provide all the advantages describedpreviously.

To keep the number of core interfaces small, the interfaces donot attempt to capture such subtle distinctions as mutability,modifiability, and resizability. Instead, certain calls in the coreinterfaces areoptional, enabling implementations to throwanUnsupportedOperationException to indicate that they donot support a specified optional operation. Collection implementersmust clearly document which optional operations are supported by animplementation.

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

It is a trulyfundamental operation: a basic operationsin terms of which others could be reasonably defined,
There is a compelling performance reason why an importantimplementation would want to override it.