The Java collections framework (JCF) is a set ofclasses
and
interfaces that implement commonly reusable collection
data structures.^[1]

Although referred to as a
framework, it works in a manner of a library. The JCF provides both interfaces that define various collections and classes that implement them.

History

Collection implementations in pre-JDK 1.2 versions of the Java platform included few data structure classes, but did not contain a collections
framework.^[2] The standard methods for grouping Java objects
were via the array, the Vector, and theHashtable
classes, which unfortunately were not easy to extend, and did not implement a standard member interface.^[3]

To address the need for reusable collection
data structures, several independent frameworks were developed,^[2]
the most used being
Doug Lea's Collections package,^[4] andObjectSpaceGeneric
Collection Library (JGL),^[5] whose main goal was consistency with
the
C++
Standard Template Library (STL).^[6]

The collections framework was designed and developed primarily by
Joshua Bloch, and was introduced in
JDK 1.2. It reused many ideas and classes from Doug Lea's Collections package, which was deprecated as a result.^[4]
Sun chose not to use the ideas of JGL, because they wanted a compact framework, and consistency with C++ was not one of their goals.^[7]

Doug Lea later developed a
concurrency
package, comprising new Collection-related classes.^[8]
An updated version of these concurrency utilities was included in
JDK 5.0 as of
JSR 166.

Architecture

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 ofjava.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.) All collections have an iterator that goes through all of the elements in the collection. Additionally, Collection
is a generic. Any collection can be written to store any class. For example, Collection<String> can hold strings, and the elements from the collection can be used as strings without any casting required.^[9]

The general-purpose implementations are summarized in the
following table.

General-purpose Implementations

Interfaces	Hash table Implementations	Resizable array Implementations	Tree Implementations	Linked list Implementations	Hash table + Linked list Implementations
Set	HashSet		TreeSet		LinkedHashSet
List		ArrayList		LinkedList
Queue
Deque		ArrayDeque		LinkedList
Map	HashMap		TreeMap		LinkedHashMap

Java1.5 collection framework

Java1.4 collection framework

上图中不包含Queue内容，部分Map的实现类未给出。

    常见使用的有List、Set、Map及他们的实现类。

    List、Set、Map接口及各实现类的特性

接口	特性	实现类	实现类特性	成员要求
List	线性、有序的存储容器，可通过索引访问元素	ArrayList	数组实现。非同步。
		Vector	类似ArrayList，同步。
		LinkedList	双向链表。非同步。
Map	保存键值对成员	HashMap	基于哈希表的 Map 接口的实现，满足通用需求	任意Object对象，如果修改了equals方法，需同时修改hashCode方法
		TreeMap	默认根据自然顺序进行排序，或者根据创建映射时提供的 Comparator进行排序	键成员要求实现caparable接口，或者使用Comparator构造TreeMap。键成员一般为同一类型。
		LinkedHashMap	类似于HashMap，但迭代遍历时取得“键值对”的顺序是其插入顺序或者最近最少使用的次序	与HashMap相同
		IdentityHashMap	使用==取代equals()对“键值”进行比较的散列映射	成员通过==判断是否相等
		WeakHashMap	弱键映射，允许释放映射所指向的对象
		ConcurrentHashMap	线性安全的Map
Set	成员不能重复	HashSet	为快速查找设计的Set	元素必须定义hashCode()
		TreeSet	保持次序的Set，底层为树结构	元素必须实现Comparable接口
		LinkedHashSet	内部使用链表维护元素的顺序（插入的次序）	元素必须定义hashCode()

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

    在满足要求的情况下，Map应尽量使用HashMap，Set应尽量使用HashSet。

The collections framework consists of:

• Collection Interfaces - The primary means bywhich collections are manipulated.
  • Collection- A group of objects. No assumptions are made about the order ofthe collection (if any), or whether it may contain
    duplicateelements.
  • Set - Thefamiliar set abstraction. No duplicate elements permitted. May ormay not be ordered. Extends theCollection interface.
  • List -Ordered collection, also known as asequence. Duplicates aregenerally permitted. Allows positional access. Extends
    theCollection interface.
  • Queue - Acollection designed for holding elements prior to processing.Besides basicCollection operations, queues provideadditional
    insertion, extraction, and inspection operations.
  • Deque - Adouble ended queue, supporting element insertion andremoval at both ends. Extends theQueue interface.
  • Map - Amapping from keys to values. Each key can map to at most onevalue.
  • SortedSet- A set whose elements are automatically sorted, either in theirnatural ordering (see theComparableinterface),
    or by a
    Comparatorobject provided when a SortedSet instance is created.Extends theSet interface.
  • SortedMap- A map whose mappings are automatically sorted by key, either inthe keys'natural ordering or by a comparator
    provided whena SortedMap instance is created. Extends theMapinterface.
  • NavigableSet- ASortedSet extended with navigation methods reportingclosest matches for given search targets. ANavigableSetmay
    be accessed and traversed in either ascending or descendingorder.
  • NavigableMap- ASortedMap extended with navigation methods returningthe closest matches for given search targets.
    ANavigableMap may be accessed and traversed in eitherascending or descending key order.
  • BlockingQueue- AQueue with operations that wait for the queue tobecome non-empty when retrieving an
    element, and that wait forspace to become available in the queue when storing an element.(This interface is part ofjava.util.concurrent.)
  • BlockingDeque- ADeque with operations that wait for the deque tobecome non-empty when retrieving an
    element, and wait for space tobecome available in the deque when storing an element. Extends boththeDeque andBlockingQueue interfaces. (Thisinterface is part ofjava.util.concurrent.)
  • ConcurrentMap- AMap with atomicputIfAbsent,remove,and
    replace methods. (This interface is part ofjava.util.concurrent.)
  • ConcurrentNavigableMap - AConcurrentMap thatis also aNavigableMap.
• General-Purpose Implementations - The primaryimplementations of the collection interfaces.
  • HashSet - Hashtable implementation of theSet interface. The bestall-around implementation of theSet interface.
  • TreeSet- Red-black tree implementation of theNavigableSetinterface.
  • LinkedHashSet- Hash table and linked list implementation of theSetinterface. An insertion-orderedSet implementation
    thatruns nearly as fast asHashSet.
  • ArrayList -Resizable-array implementation of theList interface.(Essentially an unsynchronizedVector.) The
    bestall-around implementation of theList interface.
  • ArrayDeque -Efficient resizable-array implementation of theDequeinterface.
  • LinkedList- Doubly-linked list implementation of theList interface.May provide better performance than theArrayListimplementation
    if elements are frequently inserted or deletedwithin the list. Also implements theDeque interface. Whenaccessed via theQueue interface,LinkedListbehaves as a FIFO queue.
  • PriorityQueue- Heap implementation of an unbounded priority queue.
  • HashMap - Hashtable implementation of theMap interface. (Essentially anunsynchronizedHashtable that supportsnull
    keysand values.) The best all-around implementation of theMapinterface.
  • TreeMapRed-black tree implementation of theNavigableMapinterface.
  • LinkedHashMap- Hash table and linked list implementation of theMapinterface. An insertion-orderedMap implementation
    thatruns nearly as fast asHashMap. Also useful for buildingcaches (seeremoveEldestEntry(Map.Entry)
    ).
• Wrapper Implementations -Functionality-enhancing implementations for use with otherimplementations. Accessed solely through static factory methods.
  • Collections.unmodifiableInterface -Return an unmodifiable view of
    a specified collection that throwsan UnsupportedOperationException if the user attempts tomodify it.
  • Collections.synchronizedInterface-
    Return a synchronized collection that is backed by the specified(typically unsynchronized) collection. As long as all accesses tothe backing collection are through the returned collection,thread-safety is guaranteed.
  • Collections.checkedInterface - Return adynamically
    typesafe view of the specified collection, which throwsa ClassCastException if a client attempts to add anelement of the wrong type. The generics mechanism in the languageprovides compile-time (static) type checking, but it is possible todefeat this
    mechanism. Dynamically typesafe views eliminate thispossibility entirely.
• Convenience Implementations - High-performance"mini-implementations" of the collection interfaces.
  • Arrays.asList- Allows an array to be viewed as a list.
  • EMPTY_SET,EMPTY_LISTandEMPTY_MAP-
    Constants representing the empty set and list (immutable).
  • singleton,singletonList,
    and
    singletonMap- Returns an immutable "singleton" set, list, or map, containingonly the specified object (or key-value mapping).
  • nCopies - Returns an immutable list consisting of ncopies of a specified object.
• Legacy Implementations - Older collectionclasses have been retrofitted to implement the collectioninterfaces.
  • Vector -Synchronized resizable-array implementation of theListinterface with additional "legacy methods."
  • Hashtable- Synchronized hash table implementation of theMapinterface that does not allownull keys or values,
    withadditional "legacy methods."
• Special Purpose Implementations
  • WeakHashMap- An implementation of theMap interface that stores onlyweakreferences
    to its keys. Storing only weak references allowskey-value pairs to be garbage-collected when the key is no longerreferenced outside of theWeakHashMap. This class providesthe easiest way to harness the power of weak references. It isuseful for implementing
    "registry-like" data structures, where theutility of an entry vanishes when its key is no longer reachable byany thread.
  • IdentityHashMap- Identity-based Map implementation based on a hash table. Thisclass is useful for topology-preserving
    object graphtransformations (such as serialization or deep-copying). To performsuch transformations, you need to maintain an identity-based "nodetable" that keeps track of which objects have already been seen.Identity-based maps are also used to maintainobject-to-meta-information
    mappings in dynamic debuggers andsimilar systems. Finally, identity-based maps are useful inthwarting "spoof attacks" resulting from intentionally perverseequals methods. (IdentityHashMap never invokes the equalsmethod on its keys.) An added benefit
    of this implementation isthat it is fast.
  • CopyOnWriteArrayList- aList implementation backed by an copy-on-write array.All mutative operations
    (such asadd, set, andremove) are implemented by making a new copy of the array.No synchronization is necessary, even during iteration, anditerators are guaranteed never to throwConcurrentModificationException. This implementation
    iswell-suited to maintaining event-handler lists (where change isinfrequent, and traversal is frequent and potentiallytime-consuming).
  • CopyOnWriteArraySet- ASet implementation backed by a copy-on-write array.This implementation is
    similar in nature toCopyOnWriteArrayList. Unlike mostSetimplementations, theadd,remove, andcontains methods require time proportional to the size ofthe set. This implementation is well-suited to maintainingevent-handler
    lists that must prevent duplicates.
  • EnumSet - ahigh-performanceSet implementation backed by abit-vector. All elements of eachEnumSet instance must
    beelements of a single enum type.
  • EnumMap - ahigh-performanceMap implementation backed by an array.All keys in eachEnumMap instance must be elements
    of asingle enum type.
• Concurrent Implementations - Theseimplementations are part ofjava.util.concurrent.
  • ConcurrentLinkedQueue- An unbounded FIFO (first-in first-out) queue based on linkednodes.
  • LinkedBlockingQueue - An optionally bounded FIFOblocking queue backed by linked nodes.
  • ArrayBlockingQueue - A bounded FIFO blocking queuebacked by an array.
  • PriorityBlockingQueue - An unbounded blocking priorityqueue backed by a priority heap.
  • DelayQueue- A time-based scheduling queue backed by a priority heap.
  • SynchronousQueue- A simple rendezvous mechanism utilizing theBlockingQueue interface.
  • LinkedBlockingDeque - An optionally bounded FIFOblocking deque backed by linked nodes.
  • ConcurrentHashMap- A highly concurrent, high-performanceConcurrentMapimplementation based on a hash
    table. This implementation neverblocks when performing retrievals and allows the client to selectthe concurrency level for updates. It is intended as a drop-inreplacement forHashtable:
    inaddition to implementingConcurrentMap, it supports all ofthe "legacy" methods peculiar toHashtable.
  • ConcurrentSkipListSet - Skip list implementation oftheNavigableSet interface.
  • ConcurrentSkipListMap - Skip list implementation oftheConcurrentNavigableMap interface.
• Abstract Implementations - Skeletalimplementations of the collection interfaces to facilitate customimplementations.
  • AbstractCollection- SkeletalCollection implementation that is neither a setnor a list (such as a "bag" or
    multiset).
  • AbstractSet- SkeletalSet implementation.
  • AbstractList- SkeletalList implementation backed by a random-accessdata store (such as an array).
  • AbstractSequentialList- SkeletalList implementation backed by asequential-access data store (such as a
    linked list).
  • AbstractQueue- SkeletalQueue implementation.
  • AbstractMap- SkeletalMap implementation.
• Algorithms - The
  Collectionsclass contains these useful static methods:
  • sort(List)- Sorts a list using a merge sort algorithm, which providesaverage-case performance comparable
    to a high-quality quicksort,guaranteed O(n*log n) performance (unlike quicksort), andstability (unlike quicksort). (A stable sort is one thatdoes not reorder equal elements.)
  • binarySearch(List, Object) - Searches for an elementin 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 alist with the specified value.
  • copy(List dest, List src) - Copies the source listinto the destination list.
  • min(Collection) - Returns the minimum element in acollection.
  • max(Collection) - Returns the maximum element in acollection.
  • rotate(List list, int distance) - Rotates all of theelements in the list by the specified
    distance.
  • replaceAll(List list, Object oldVal, Object newVal) -Replaces all occurrences of
    one specified value with another.
  • indexOfSubList(List source, List target) - Returns theindex of the first
    sublist of source that is equal to target.
  • lastIndexOfSubList(List source, List target) - Returnsthe index of
    the last sublist of source that is equal totarget.
  • swap(List, int, int) - Swaps the elements at thespecified positions in the specified
    list.
  • frequency(Collection, Object) - Counts the number oftimes the specified
    element occurs in the specifiedcollection.
  • disjoint(Collection, Collection) - Determines whethertwo collections
    are disjoint, in other words, whether they containno elements in common.
  • addAll(Collection<? super T>, T...) - Adds allof the elements in the specified array
    to the specifiedcollection.
  • newSetFromMap(Map) - Creates a general purposeSet implementation from a general
    purposeMapimplementation.
  • asLifoQueue(Deque) - Returns a view of aDeque as a Last-in-first-out (Lifo)Queue.
• Infrastructure
  • Iterators - Similar to the familiar
    Enumerationinterface, but more powerful, and with improved method names.
    • Iterator- In addition to the functionality of theEnumerationinterface, allows the user to remove elements from the backingcollection
      with well defined, useful semantics.
    • ListIterator- Iterator for use with lists. In addition to the functionality oftheIterator interface, supports bi-directional
      iteration,element replacement, element insertion and index retrieval.
  • Ordering
    • Comparable- Imparts anatural ordering to classes that implement it.The natural ordering may be used to sort a list
      or maintain orderin a sorted set or map. Many classes have been retrofitted toimplement this interface.
    • Comparator- Represents an order relation, which may be used to sort a list ormaintain order in a sorted set or map. Can override
      a type'snatural ordering, or order objects of a type that does notimplement the
      Comparable interface.
  • Runtime Exceptions
    • UnsupportedOperationException - Thrown by collectionsif an unsupported optional operation is called.
    • ConcurrentModificationException - Thrown by iteratorsand list iterators if the backing collection is modifiedunexpectedly
      while the iteration is in progress. Also thrown bysublist views of lists if the backing list is modifiedunexpectedly.
  • Performance
    • RandomAccess- Marker interface that allowsList implementations toindicate that they support fast (generally constant
      time) randomaccess. This allows generic algorithms to alter their behavior toprovide good performance when applied to either random orsequential access lists.
• Array Utilities
  • Arrays -Contains static methods to sort, search, compare, hash, copy,resize, convert toString, and fill arrays of primitivesand
    Objects.

List interface

Lists are implemented in the JCF via the java.util.List interface. It defines
a list as essentially a more flexible version of an array. Elements have a specific order, and duplicate elements are allowed. Elements can be placed in a specific position. They can also be searched for within the list. Two concrete classes implement List.
The first isjava.util.ArrayList, which implements the list as an array. Whenever
functions specific to a list are required, the class moves the elements around within the array in order to do it. The other implementation isjava.util.LinkedList.
This class stores the elements in nodes that each have a pointer to the previous and next nodes in the list. The list can be traversed by following the pointers, and elements can be added or removed simply by changing the pointers around to place the node
in its proper place.^[10]

Stack interfaces

Stacks are implemented using java.util.Stack. The stack offers to put new object
on the stack (method push()) and to get objects from the stack (method pop()). A stack returns the object according to last-in-first-out (LIFO), e.g. the object which was placed latest on the stack is returned first. Java provides a standard implementation
of a stack in java.util.Stack. The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method
to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top. When a stack is first created, it contains no items.

Queue interfaces

The java.util.Queue interface defines the queue data structure, which stores
elements in the order in which they are inserted. New additions go to the end of the line, and elements are removed from the front. It creates a first-in first-out system. This interface is implemented byjava.util.LinkedList,java.util.ArrayDeque,
andjava.util.PriorityQueue. LinkedList, of course, also implements the
List interface and can also be used as one. But it also has the Queue methods. ArrayDeque implements the queue as an array. Both LinkedList and ArrayDeque also implement thejava.util.Deque
interface, giving it more flexibility.^[11]

java.util.Queue can be used more flexibly with its subinterface,java.util.concurrent.BlockingQueue.
The BlockingQueue interface works like a regular queue, but additions to and removals from the queue are blocking. If remove is called on an empty queue, it can be set to wait either a specified time or indefinitely for an item to appear in the queue. Similarly,
adding an item is subject to an optional capacity restriction on the queue, and the method can wait for space to become available in the queue before returning.^[12]

java.util.PriorityQueue implementsjava.util.Queue,
but also alters it. Instead of elements being ordered by the order in which they are inserted, they are ordered by priority. The method used to determine priority is either the compareTo() method in the elements or a method given in the constructor. The class
creates this by using a heap to keep the items sorted.^[13]

Double-ended queue (deque) interfaces

The java.util.Queue interface is expanded by thejava.util.Deque
subinterface. Deque creates a double-ended queue. While a regular queue only allows insertions at the rear and removals at the front, the deque allows insertions or removals to take place both at the front and the back. A deque is like a queue that can be
used forwards or backwards, or both at once. Additionally, both a forwards and a backwards iterator can be generated. The Deque interface is implemented byjava.util.ArrayDeque
andjava.util.LinkedList.^[14]

The java.util.concurrent.BlockingDeque interface works similarly
tojava.util.concurrent.BlockingQueue. The same methods for
insertion and removal with time limits for waiting for the insertion or removal to become possible are provided. However, the interface also provides the flexibility of a deque. Insertions and removals can take place at both ends. The blocking function is
combined with the deque function.^[15]

Set interfaces

Java's java.util.Set interface defines the set. A set can't have any duplicate
elements in it. Additionally, the set has no set order. As such, elements can't be found by index. Set is implemented byjava.util.HashSet,java.util.LinkedHashSet,
andjava.util.TreeSet. HashSet uses a hash table. More specifically, it uses
ajava.util.HashMap to store the hashes and elements and to prevent duplicates.java.util.LinkedHashSet
extends this by creating a doubly linked list that links all of the elements by their insertion order. This ensures that the iteration order over the set is predictable.java.util.TreeSet
uses ared-black tree implemented by ajava.util.TreeMap.
The red-black tree makes sure that there are no duplicates. Additionally, it allows TreeSet to implementjava.util.SortedSet.^[16]

The java.util.Set interface is extended by thejava.util.SortedSet
interface. Unlike a regular set, the elements in a sorted set are sorted, either by the element's compareTo() method, or a method provided to the constructor of the sorted set. The first and last elements of the sorted set can be retrieved, and subsets can
be created via minimum and maximum values, as well as beginning or ending at the beginning or ending of the sorted set. The SortedSet interface is implemented byjava.util.TreeSet^[17]

java.util.SortedSet is extended further via thejava.util.NavigableSet
interface. It's similar to SortedSet, but there are a few additional methods. The floor(), ceiling(), lower(), and higher() methods find an element in the set that's close to the parameter. Additionally, a descending iterator over the items in the set is provided.
As with SortedSet,java.util.TreeSet implements NavigableSet.^[18]

Map interfaces

Maps are defined by the java.util.Map interface in Java. Maps are simple data
structures that associate a key with a value. The element is the value. This lets the map be very flexible. If the key is the hash code of the element, the map is essentially a set. If it's just an increasing number, it becomes a list. Maps are implemented
byjava.util.HashMap,java.util.LinkedHashMap,
andjava.util.TreeMap. HashMap uses a hash table. The hashes of the keys are
used to find the values in various buckets. LinkedHashMap extends this by creating a doubly linked list between the elements. This allows the elements to be accessed in the order in which they were inserted into the map. TreeMap, in contrast to HashMap and
LinkedHashMap, uses a red-black tree. The keys are used as the values for the nodes in the tree, and the nodes point to the values in the map.^[19]

The java.util.Map interface is extended by its subinterface,java.util.SortedMap.
This interface defines a map that's sorted by the keys provided. Using, once again, the compareTo() method or a method provided in the constructor to the sorted map, the key-value pairs are sorted by the keys. The first and last keys in the map can be called.
Additionally, submaps can be created from minimum and maximum keys. SortedMap is implemented byjava.util.TreeMap.^[20]

The java.util.NavigableMap interface extendsjava.util.SortedMap
in various ways. Methods can be called that find the key or map entry that's closest to the given key in either direction. The map can also be reversed, and an iterator in reverse order can be generated from it. It's implemented byjava.util.TreeMap.^[21]

Extensions to the Java collections framework

The Java collections framework is extended by the
Apache Commons Collections library, which adds collection types such as a bag and bidirectional map, as well as utilities for creating unions and intersections.^[22]

TheJava Collections Frameworkwas
a major addition in JDK 1.2.It added many powerful data structures that accelerate development of most significant Java applications.Since that time it has become the recognised standard for collection handling in Java.

Commons-Collections seek to build upon the JDK classes by providing new interfaces, implementations and utilities.There are many features, including:

• Bag interface for collections that have a number of copies of each object
• BidiMap interface for maps that can be looked up from value to key as well and key to value
• MapIterator interface to provide simple and quick iteration over maps
• Transforming decorators that alter each object as it is added to the collection
• Composite collections that make multiple collections look like one
• Ordered maps and sets that retain the order elements are added in, including an LRU based map
• Reference map that allows keys and/or values to be garbage collected under close control
• Many comparator implementations
• Many iterator implementations
• Adapter classes from array and enumerations to collections
• Utilities to test or create typical set-theory properties of collections such as union, intersection, and closure

fastutil扩展了Java Collections Framework，提供特定类型的映射(maps)，集合(sets)，列表(lists)和队列，为Java提供一个小的内存占用和快速访问与插入。它还提供了大的（64位）阵列（arrays），组（sets ）和列表（lists）。用于处理二进制文件和文本文件的快速、实用I / O的类。

http://fastutil.dsi.unimi.it/

guava-libraries(google collections):http://code.google.com/p/google-collections/

See also

• Container (data structure)
• Standard Template Library
• Java concurrency

References

External links

The Wikibook Java Programming has a page on the topic of:Collections

• Collections Lessons
• CollectionSpy — A profiler for Java's Collections Framework.
• Generic Types
• Java 6 Collection Tutorial — By Jakob Jenkov, Kadafi Kamphulusa
• Java Generics and Collections
• Taming Tiger: The Collections Framework
• 'The Collections Framework' (Oracle Java SE 7 documentation)
• 'The Java Tutorials - Collections' by Josh Bloch
• 'Which Java Collection to use?' — by Janeve George
• Java集合类源码分析汇总: http://www.cnblogs.com/hzmark/archive/2013/01/05/JavaCollectionSum.html