Annotated Outline of Java Collections Framework

• The Collection Hierarchy (Core Collection Interfaces)
  • Collection - A group of Objects that may or may not be ordered, duplicate free, mutable, etc.
  • Set - The familiar set abstraction. No duplicate elements permitted. Order (if any) is generally established at Set creation time. Extends Collection.
  • List - Ordered Collection (also known as a sequence). Duplicates are generally permitted. The caller generally has precise control over the position of each element in the list. Extends Collection.
  • Map - A mapping from keys to values. Each key can map to at most one value.
  • SortedSet - A Set whose elements are automatically sorted, either in their natural ordering (see Comparable), or by a Comparator provided at SortedSet creation time.
  • SortedMap - A Map whose mappings are automatically sorted by key, either in the keys' natural ordering or by a Comparator provided at SortedMap creation time.
• Concrete Implementations - All of the new collection implementations are unsynchronized, but may be synchronized externally with synchronizing wrappers. All have fail-fast iterators, which throw a runtime exception in response to concurrent modification of the the backing collection, rather than behaving non-deterministically. New implementations are summarized in tabular form.
  • HashSet - a Set backed by a hash table. This class serves as a good general-purpose Set implementation.
  • TreeSet A balanced binary tree implementation of the SortedSet interface. Unlike HashSet, imposes an ordering on its elements.
  • ArrayList - a resizable-array implementation of the List interface. (Essentially an unsynchronized Vector.) The class was provided in addition to Vector for consistency in naming and behavior. It serves as a good general-purpose List implementation.
  • LinkedList - a doubly-linked List. May provide better performance than ArrayList if elements are frequently inserted or deleted within the List. Useful for queues and double-ended queues (deques).
  • HashMap - a hash table implementation of the Map interface. (Essentially an unsynchronized Hashtable that supports null keys and values) The class was provided in addition to Hashtable for consistency in naming and behavior. It serves as a good general-purpose Map implementation.
  • TreeMap A balanced binary tree implementation of the SortedMap interface. Unlike HashMap, imposes an ordering on its elements.
  • Vector - a synchronized resizable-array implementation of a List with additional "legacy methods."
  • Hashtable - A synchronized hash table implementation of the Map interface, with additional "legacy" methods.
  • WeakHashMap - a special-purpose implementation of the Map interface that stores only weak references to its keys, which allows key-value pairs to be garbage-collected when the key is no longer referenced outside of the WeakHashMap. This class provides the easiest way to harness the power of weak references. It is useful for implementing "registry-like" data structures, where the utility of an entry vanishes when its key is no longer reachable by any thread.
• Anonymous Implementations - These implementations are accessed solely through public static factory methods (their class definitions are not exported). All of these except Arrays.asList are contained in a single class, Collections.
  • Arrays.asList - Allows an array to be viewed as a List.
  • unmodifiableCollection, unmodifiableSet, unmodifiableList, unmodifiableMap, unmodifiableSortedSet, unmodifiableSortedMap - Return an unmodifiable view of a specified collection that throws an UnsupportedOperationException if the user attempts to modify it.
  • synchronizedCollection, synchronizedSet, synchronizedList, synchronizedMap, synchronizedSortedSet, synchronizedSortedMap - Return a synchronized collection is backed by the specified (typically unsynchronized) collection. As long as all accesses to the backing collection are via the returned collection, thread-safety is guaranteed.
  • EMPTY_SET and EMPTY_LIST - constants representing the empty Set and List (immutable).
  • singleton - returns an immutable "singleton" Set containing only the specified object.
  • nCopies - Returns an immutable List consisting of n copies of a specified object.
• Abstract Implementations - The API documentation for these classes describes precisely how each method is implemented so the implementer will know which methods should be overridden, given the performance of the "basic operations" of a specific implementation.
  • AbstractCollection - Skeletal implementation of a Collection that is neither a Set nor a List (e.g., a "bag" or multiset).
  • AbstractSet - Skeletal implementation of a Set.
  • AbstractList - Skeletal implementation of a List backed by a random-access data store (such as an array).
  • AbstractSequentialList - Skeletal implementation of a List backed by a sequential-access data store (such as a linked list).
  • AbstractMap - Skeletal implementation of a Map.
• Infrastructure
  • Iterators - Similar to Enumeration, but more powerful, and with improved method names.
    • Iterator - In addition to all of the functionality of Enumeration, has improved method names and allows the user to remove elements from the backing collection with well defined, useful semantics. (Designed to eventually supplant the use of Enumeration.)
    • ListIterator - Allows the user to manipulate the List as the enumeration progresses. Extends Iterator with various list-specific operations. Allows bi-directional iteration, element replacement, element insertion and index retrieval.
  • Ordering
    • Comparable - Classes that implement this interface provide a natural ordering, which may be used to order a Collection or sort an array containing elements of this class. Many classes in the JDK implement this interface.
    • Comparator - Represents an order relation, which may be used to order a Collection or sort an array. A Comparator may be used in preference to a Comparable type's natural ordering, or it may be used to order elements of a type that does not implement Comparable.
  • Runtime Exceptions
    • UnsupportedOperationException - Thrown by Collections if an unsupported optional operation is called.
    • ConcurrentModificationException - Thrown by Iterators and ListIterators if the backing collection is concurrently modified while the iteration is in progress.
• Algorithms
  • sort(List) - Sorts a List using a merge sort algorithm, which provides average-case performance comparable to a high-quality quicksort, guaranteed O(n*log n) performance (unlike quicksort), and stability (unlike quicksort). (A stable sort is one that does not reorder equal elements.)
  • binarySearch(List, Object) - Searches for an element in an ordered List using the binary search algorithm.
  • reverse(List) - Reverses the order of the elements in the a List.
  • shuffle(List) - Randomly permutes the elements in a List.
  • fill(List, Object) - Overwrites every element in a List with the specified value.
  • copy(List dest, List src) - Copies the source List into the destination List.
  • min(Collection) - Returns the minimum element in a Collection.
  • max(Collection) - Returns the maximum element in a Collection.
• Array Utilities
  • Arrays - Contains static methods to sort, search, compare and fill arrays of primitives and Objects.

The following table summarizes the new implementations of the the core collection interfaces. The names are all of the form <Implementation><Interface>. All of these implementations are unsynchronized. All have fail-fast iterators.

		Implementations
		Hash Table	Resizable Array	Balanced Tree	Linked List
Interfaces	Set	HashSet	2	TreeSet	2
	List	1	ArrayList	1	LinkedList
	Map	HashMap	2	TreeMap	2

Footnotes

Copyright © 1995-98 Sun Microsystems, Inc. All Rights Reserved. Please send comments to: collections-comments@java.sun.com

Java Software