What is Java Collections Framework

一套官方实现的用于表示和操作集合的结构，包括三个层次：接口、实现以及算法。

接口：用来表示集合的抽象数据类型。在面向对象语言中，接口通常形成一个层次结构。

实现：是集合接口的具体实现，本质上是可重用的数据结构。

算法：对实现集合接口的对象执行计算，如搜索和排序。这些算法被认为是多态的，也就是说相同的方法可以用于相应集合接口的许多不同实现。本质上，算法是可重用的功能。

Java Collections Framework UML类图

Collection接口

继承Iterable接口；
集合层次接口中的根接口；
表示一组对象，称其为元素；
没有任何直接实现；
通常用于传递集合，并在需要最大通用性的地方对其提供操作；

Iterable接口

Implementing this interface allows an object to be the target of the “for-each loop” statement.

List接口

继承Collection接口；
相对于Collection接口，增加了一些支持下标操作的方法，如：

boolean addAll(int index, Collection<? extends E> c);
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
List<E> subList(int fromIndex, int toIndex);

相对于Collection接口，增加了ListIterator；
有序；
允许重复元素；
允许null元素；

AbstractCollection抽象类

1.实现Collection接口；

2.This class provides a skeletal implementation of the Collection interface, to minimize the effort required to implement this interface:

public boolean isEmpty() {
    return size() == 0;
}
public boolean contains(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}
public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    return it.hasNext() ? finishToArray(r, it) : r;
}
public boolean remove(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext()) {
            if (it.next()==null) {
                it.remove();
                return true;
            }
        }
    } else {
        while (it.hasNext()) {
            if (o.equals(it.next())) {
                it.remove();
                return true;
            }
        }
    }
    return false;
}
public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}
public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}
public void clear() {
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
}
public String toString() {
    Iterator<E> it = iterator();
    if (! it.hasNext())
        return "[]";
    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {
        E e = it.next();
        sb.append(e == this ? "(this Collection)" : e);
        if (! it.hasNext())
            return sb.append(']').toString();
        sb.append(',').append(' ');
    }
}

3.To implement an unmodifiable collection, the programmer needs only to extend this class and provide implementations for the iterator and size methods. (The iterator returned by the iterator method must implement hasNext and next.)

To implement a modifiable collection, the programmer must additionally override this class’s add method (which otherwise throws an UnsupportedOperationException), and the iterator returned by the iterator method must additionally implement its remove method.

AbstractList抽象类

继承AbstractCollection抽象类，实现List接口；

This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a “random access” data store (such as an array).

To implement an unmodifiable list, the programmer needs only to extend this class and provide implementations for the get(int) and size() methods.

To implement a modifiable list, the programmer must additionally override the set(int, E) method (which otherwise throws an UnsupportedOperationException). If the list is variable-size the programmer must additionally override the add(int, E) and remove(int) methods.

ArrayList类

继承AbstractList抽象类，实现List接口、RandomAccess接口、Cloneable接口以及Serializable接口；
几个重要变量和常量：

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
 //这里使用了transient关键字来避免序列化elementData是因为elementData的长度是容量，有可能大于实际数据长度，序列化会造成空间浪费，因此这里没有进行序列化，而是在writeObject方法中手动实现了序列化，且仅序列化了实际数据。
transient Object[] elementData; // non-private to simplify nested class access
/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

三个构造函数：

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

RandomAccess接口

1.Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

2.The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList). Generic list algorithms are encouraged to check whether the given list is an instanceof this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.

3.It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a List implementation should generally implement this interface. As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop

for (int i=0, n=list.size(); i < n; i++)
    list.get(i);

runs faster than this loop:

for (Iterator i=list.iterator(); i.hasNext(); )
  i.next();

Queue接口

继承Collection接口；
Besides basic Collection operations, queues provide additional insertion, removal, and inspection operations:

3.The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or “bounded”) queues.

4.The remove() and poll() methods remove and return the head of the queue. Exactly which element is removed from the queue is a function of the queue’s ordering policy, which differs from implementation to implementation. The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null.

Deque接口

继承Queue接口；
A double-ended-queue is a linear collection of elements that supports the insertion and removal of elements at both end points. The Deque interface is a richer abstract data type than both Stack and Queue because it implements both stacks and queues at the same time. The Deque interface, defines methods to access the elements at both ends of the Deque instance. Methods are provided to insert, remove, and examine the elements.

AbstractSequentialList抽象类

1.继承AbstractList抽象类；

2.This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a “sequential access” data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class.

3.To implement a list the programmer needs only to extend this class and provide implementations for the listIterator and size methods.

For an unmodifiable list, the programmer need only implement the list iterator’s hasNext, next, hasPrevious, previous and index methods.

For a modifiable list the programmer should additionally implement the list iterator’s set method. For a variable-size list the programmer should additionally implement the list iterator’s remove and add methods.

LinkedList类

继承AbstractSequentialList抽象类，实现List接口、Deque接口、Cloneable接口以及Serializable接口；
几个重要变量：

transient int size = 0;
/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

两个构造函数：

/**
 * Constructs an empty list.
 */
public LinkedList() {
}
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

Vector类

1.继承AbstractList抽象类，实现List接口、RandomAccess接口、Cloneable接口以及Serializable接口；

2.The iterators returned by this class’s iterator and listIterator methods are fail-fast；

3.The Enumerations returned by the elements method are not fail-fast；

4.Unlike the new collection implementations, Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector.

Java Collections Framework（List相关接口和类简介）