Almost all collections in Java are derived from the java.util.Collection interface. Collection defines the basic parts of all collections. The interface states the add() and remove() methods for adding to and removing from a collection respectively. Also required is the toArray() method, which converts the collection into a simple array of all the elements in the collection. Finally, the contains() method checks if a specified element is in the collection. The Collection interface is a subinterface of java.lang.Iterable, so any Collection may be the target of a for-each statement. (The Iterable interface provides the iterator() method used by for-each statements.) Additionally, Collection is a generic, so any collection can be written to store any class. For example, a Collection<String> can hold strings, and the elements can be used as strings without any casting required.

Collection Interfaces

To keep the number of core collection interfaces manageable, the Java platform doesn’t provide separate interfaces for each variant of each collection type. If an unsupported operation is invoked, a collection implementation throws an UnsupportedOperationException. The interfaces below are the ones you actually program against.

Collection

This is the root of the collection hierarchy. A collection represents a group of objects known as its elements. The Java platform doesn’t provide any direct implementation of this interface; instead it implements more specific subinterfaces such as List and Set.

Beyond the basic methods to query size (size, isEmpty), test membership (contains), add and remove elements (add, remove), and obtain an iterator (iterator), Collection also defines bulk operations that work on an entire collection at once – containsAll, addAll, removeAll, retainAll, clear.

List

An ordered collection, sometimes called a sequence. A List can contain duplicate elements and gives you positional (indexed) access via methods such as get(int), set(int, E), and add(int, E). It also supports searching (indexOf) and a richer ListIterator that can traverse in both directions. The common implementations are ArrayList, LinkedList, and the legacy Vector.

Set

A collection that cannot contain duplicate elements. It models the mathematical set abstraction and adds no methods of its own beyond those inherited from Collection – it merely tightens the contract so that add is a no-op when the element already exists. SortedSet is a Set that further keeps its elements in ascending order. The common implementations are HashSet, LinkedHashSet, and TreeSet.

Queue and Deque

A Queue is a collection designed for holding elements prior to processing. In addition to the basic Collection operations, it provides insertion, extraction, and inspection methods (offer, poll, peek), typically ordering elements in FIFO fashion. A Deque (double-ended queue) supports insertion and removal at both ends. Common implementations are LinkedList, ArrayDeque, and PriorityQueue.

Map

An object that maps keys to values. A Map cannot contain duplicate keys, and each key maps to at most one value. Note that Map does not extend Collection; it is a separate top-level interface, though it is considered part of the framework. SortedMap keeps its keys in ascending order. The common implementations are HashMap, LinkedHashMap, TreeMap, and the legacy Hashtable.

Common Implementations

For each interface above, the framework ships a handful of general-purpose implementations. The table at the end of this post compares them side by side; here is what each one is built on and when to reach for it.

• ArrayList: a resizable-array implementation of List. Offers fast random access but slow insertion and removal in the middle. This is the default List for most use cases.
• LinkedList: a doubly-linked-list implementation of List and Deque. Insertion and removal at the ends are cheap, but random access is slow.
• HashSet: a Set backed by a hash table. The best-performing general-purpose Set, but it makes no guarantee about iteration order.
• TreeSet: a Set backed by a red-black tree. Keeps its elements sorted, at the cost of log(n) operations.
• HashMap: a Map backed by a hash table. The best-performing general-purpose Map, with no ordering guarantee.
• TreeMap: a Map backed by a red-black tree. Keeps its keys sorted.
• Vector and Hashtable: legacy, fully synchronized counterparts of ArrayList and HashMap, retained for backward compatibility.

Collections API Algorithms

The Java Collections Framework provides algorithm implementations that are commonly used such as sorting and searching. The Collections class contains these method implementations. Most of these algorithms work on List, but some of them are applicable to all kinds of collections.

Sorting

The sort algorithm reorders a List so that its elements are in ascending order according to an ordering relationship. Two forms of the operation are provided. The simple form takes a List and sorts it according to its elements’ natural ordering. The second form of sort takes a Comparator in addition to a List and sorts the elements with the Comparator.

Shuffling

The shuffle algorithm destroys any trace of order that may have been present in a List. That is, this algorithm reorders the List based on input from a source of randomness such that all possible permutations occur with equal likelihood, assuming a fair source of randomness. This algorithm is useful in implementing games of chance.

Searching

The binarySearch algorithm searches for a specified element in a sorted List. This algorithm has two forms. The first takes a List and an element to search for (the “search key”). This form assumes that the List is sorted in ascending order according to the natural ordering of its elements. The second form takes a Comparator in addition to the List and the search key, and assumes that the List is sorted into ascending order according to the specified Comparator. The sort algorithm can be used to sort the List prior to calling binarySearch.

Composition

The frequency and disjoint algorithms test some aspect of the composition of one or more Collections.

• frequency: counts the number of times the specified element occurs in the specified collection
• disjoint: determines whether two Collections are disjoint; that is, whether they contain no elements in common

Min and Max values

The min and the max algorithms return, respectively, the minimum and maximum element contained in a specified Collection. Both of these operations come in two forms. The simple form takes only a Collection and returns the minimum (or maximum) element according to the elements’ natural ordering.
The second form takes a Comparator in addition to the Collection and returns the minimum (or maximum) element according to the specified Comparator.

Thread Safety

The general-purpose implementations are not synchronized. When several threads access a collection concurrently and at least one of them modifies it, you need external synchronization. The framework offers two approaches.

Synchronization Wrappers

The synchronization wrappers add automatic synchronization (thread-safety) to an arbitrary collection. Each of the six core collection interfaces (Collection, Set, List, Map, SortedSet, and SortedMap) has one static factory method.

public static Collection synchronizedCollection(Collection c);
public static Set synchronizedSet(Set s);
public static List synchronizedList(List list);
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m);
public static SortedSet synchronizedSortedSet(SortedSet s);
public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m);

Each of these methods returns a synchronized (thread-safe) collection backed by the specified collection. Note that you still have to synchronize manually when iterating, since iteration is not atomic.

Concurrent Collections

The Java 1.5 concurrency package (java.util.concurrent) contains thread-safe collection classes that allow a collection to be modified while it is being iterated. By design their iterators are weakly consistent rather than fail-fast, so they do not throw ConcurrentModificationException. These classes also offer far better scalability than blanket synchronization, because they lock at a finer granularity (or avoid locking altogether). Some of them are CopyOnWriteArrayList, ConcurrentHashMap, and CopyOnWriteArraySet.

Collection Classes in a Nutshell

The table below provides basic details of the commonly used collection classes discussed above.

Reference

• The Java Tutorials – Collections
• java.util.Collection API documentation
• Java collections framework – Wikipedia