Java容器类主要是为了“保存对象”，并将其划分为两个不同的概念：Collection，独立元素的集合，这些元素都服从一条或多条规则，如List必须按照插入顺序保存元素，Set不能有重复元素，Queue按照排队规则来确定对象的顺序。Map形成一组“键值对”对象，允许你使用键来查找值，故也被称为关联数组。

根据插入数据后元素的效果来看，ArrayList和LinkedList都能够按照被插入的顺序保存元素。HashSet、TreeSet、LinkedHashSet都是Set类型，其中元素的每个项都只能保存一次，但是它们的保存方式不同。HashSet是采用hash表的方式存储元素(其实所有的Set内部都有一个对应的Map，HashSet中使用的是HashMap)，故是无序的，TreeSet内部使用的是红黑树(内部是TreeMap)，它可以使结果按照升序排列，而LinkedHashSet可以按照元素添加的顺序保存对象(内部是LinkedHashMap)。HashMap是采用hash表的方式来进行快速的操作，TreeMap使用红黑树按照键的升序保存数据，LinkedHashMap则可以按照插入的顺序遍历元素(内部继承自HashMap，并且将元素插入顺序存储在自己的Entry组成的双向链表中)。

List类

ArrayList长于随机访问元素，但是在List中插入和移除元素比较慢。而LinkedList则擅长于顺序访问，同时它也支持队列操作，以及其他堆栈和双端队列操作。此外还包含两个同步的容器类，Vector和Stack。

List接口中的(部分主要)方法

add(E e)/ add(int index, E element)：添加元素/在指定位置添加元素；

get(int index)：获取列表中指定位置的元素；

indexOf(Object o)：返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1；

contains(Object o)：确定某个对象是否在列表中；

remove(Object o)：从此列表中移除第一次出现的指定元素(如果存在)；

subList(int fromIndex, int toIndex)：从较大的列表中创建一个片段(或称为视图)；

retainAll(Collection> c)：对两个集合取交集(通过equals方法判断)；

removeAll(Collection> c)：根据equals方法删除c中指定的元素；

set(int index, E element)：用指定元素替换列表中指定位置的元素(而不是集合的set)。

AbstractList是提供 List 接口的骨干实现，以最大限度地减少实现“随机访问”数据存储(如数组)支持的该接口所需的工作，其中主要包含了两个迭代器(Itr、ListItr)和hashCode方法。

ArrayList及其实现方式

ArrayList的size、isEmpty、get、set、iterator和listIterator 操作都以固定时间运行。add 操作以分摊的固定时间运行，也就是说，添加n个元素需要 O(n) 时间。其他所有操作都以线性时间运行(大体上讲)。与用于LinkedList 实现的常数因子相比，此实现的常数因子较低。每个 ArrayList 实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。

在ArrayList中拥有保存数据的elementData数组：

private transient Object[] elementData;

当添加元素时，为了防止当前元素数量不足，就会先调用ensureCapacity方法，这个方法可以判断出当前elementData数量是否足够使用，不足时会调用grow方法拓展元素数量，拓展时会拓展原来元素数量的一半newCapacity = oldCapacity + (oldCapacity >> 1)，并且调用Arrays.copyOf(elementData, newCapacity)创建新的数组，并返回这个长度为newCapacity，包含elementData中所有元素的新数组。这样ArrayList中能够存储的数据量就被增加了。

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

}

private void ensureCapacityInternal(int minCapacity) {

modCount++;

// overflow-conscious code

if (minCapacity - elementData.length > 0)

grow(minCapacity);

}

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1);

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

// minCapacity is usually close to size, so this is a win:

elementData = Arrays.copyOf(elementData, newCapacity);

}

当获取元素时ArrayList可以直接获取元素：return (E) elementData[index]。

从ArrayList中删除元素的方法有两个：remove(int index)和remove(Object o)。它们两个调用的方法不一样，实现过程大致类似：先找到指定的下标的位置或者对象，然后使用复制元素的方法，将后面的元素向前移一个位置，最后将数组中的最后一个位置设置为null。它们的不同主要在于返回值，remove(int index)会返回删除了的对象，remove(Object o)返回是否删除成功，而且remove(Object o)还是用了fastRemove方法进行删除。

public E remove(int index) {

rangeCheck(index);

modCount++;

E oldValue = elementData(index);

int numMoved = size - index - 1;

if (numMoved > 0)

System.arraycopy(elementData, index+1, elementData, index,

numMoved);

elementData[--size] = null; // Let gc do its work

return oldValue;

}

public boolean remove(Object o) {

if (o == null) {

for (int index = 0; index < size; index++)

if (elementData[index] == null) {

fastRemove(index);

return true;

}

} else {

for (int index = 0; index < size; index++)

if (o.equals(elementData[index])) {

fastRemove(index);

return true;

}

}

return false;

}

private void fastRemove(int index) {

modCount++;

int numMoved = size - index - 1;

if (numMoved > 0)

System.arraycopy(elementData, index+1, elementData, index,

numMoved);

elementData[--size] = null; // Let gc do its work

}

从这里可以看出fastRemove只是将remove(int index)中的部分步骤抽离出来，形成了一个方法。它们都是在调用System.arraycopy将元素向前移动了一个位置。

LinkedList及其实现方式

LinkedList除了实现 List 接口外，还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。此类实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表(从靠近指定索引的一端)。

LinkedList特殊的地方在于它有时候会提供多套获取方式，如getFirst和element，都是返回列表头，而且获取失败会抛出NoSuchElementException，但是peek方法虽然也是获取头元素，却不会抛出异常，只会返回null。RemoveFirst和remove失败时会抛出异常，poll会返回null。

LinkedList内部元素使用Node存储，它是一个双链表的结点：

private static class Node {

E item;

Node next;

Node prev;

Node(Node prev, E element, Node next) {

this.item = element;

this.next = next;

this.prev = prev;

}

}

LinkedList会记录这个双链表的两个端点，并且会记录链表长度：

transient int size = 0;

transient Node first;

transient Node last;

当需要向链表中添加元素时，会调用linkLast方法，将元素添加到链表尾部：

public boolean add(E e) {

linkLast(e);

return true;

}

void linkLast(E e) {

final Node l = last;

final Node newNode = new Node<>(l, e, null);

last = newNode;

if (l == null)

first = newNode;

else

l.next = newNode;

size++;

modCount++;

}

这里可以看出，无论如何，数据都会成功添加到LinkedList中。

调用pop和removeFirst，poll方法时，会间接调用unlinkFirst方法：

public E pop() {

return removeFirst();

}

public E removeFirst() {

final Node f = first;

if (f == null)

throw new NoSuchElementException();

return unlinkFirst(f);

}

public E poll() {

final Node f = first;

return (f == null) ? null : unlinkFirst(f);

}

private E unlinkFirst(Node f) {

// assert f == first && f != null;

final E element = f.item;

final Node next = f.next;

f.item = null;

f.next = null; // help GC

first = next;

if (next == null)

last = null;

else

next.prev = null;

size--;

modCount++;

return element;

}

同样的道理，push和offerFirst、addFirst都会调用linkFirst方法，只有removeLast和pollLast会调用unlinkLast方法。

使用get方法时会根据当前的index更接近队列的哪个端点来确定从哪里开始进行遍历查找到目标。

public E get(int index) {

checkElementIndex(index);

return node(index).item;

}

Node node(int index) {

if (index < (size >> 1)) {

Node x = first;

for (int i = 0; i < index; i++)

x = x.next;

return x;

} else {

Node x = last;

for (int i = size - 1; i > index; i--)

x = x.prev;

return x;

}

}

Set类

Set(Interface)

存入Set的每个元素都必须是唯一的，因为Set不保存重复元素，加入Set的元素必须定义equals方法以确保对象的唯一性。Set和Collection有完全一样的接口。Set接口不保证维护元素的次序。

HashSet*

为快速查找而设计的Set。存入HashSet的元素必须定义hashCode()

TreeSet

保持次序的Set，底层为树结构。使用它可以从Set中提取有序的序列，元素必须实现Compareable接口

LinkedHashSet

具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显式，元素也必须定义hashCode()方法。

Set不保存重复的元素，如果将相同对象的多个实例添加到Set中，那么它会阻止这种重复。由于Set常用于查询是否存在当前集合的操作，故最常用的Set是HashSet。Set总共包括三类HashSet、TreeSet、LinkedListSet，其中HashSet是最快的Set，内部使用Hash表，理想情况下查询和修改删除操作均可以在O(1)时间复杂度下完成，而TreeSet内部包含了红黑树，它是一种大致平衡的二叉搜索树，最后LinkedHashSet继承自HashSet，它的内部存储着一个插入时的元素插入顺序的链表，故可以维护插入的顺序。

Set接口中的(部分主要)方法

add(E e)：如果 set 中尚未存在指定的元素，则添加此元素(可选操作)；

contains(Object o)：如果 set 包含指定的元素，则返回 true；

remove(Object o)：如果 set 中存在指定的元素，则将其移除(可选操作)。

AbstractSet类提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作，但是事实上这个类只实现了equals(Object)、hashCode()、removeAll(Collection>)三个方法。

HashSet及其实现方式

HashSet实现 Set 接口，由哈希表(实际上是一个 HashMap 实例)支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。

在HashSet的内部存储着一个HashMap：

private transient HashMap map;

它的key是Set的元素，它的value是一个Object对象：

private static final Object PRESENT = new Object();

当需要添加(add)元素时，实际上是让Map存储了一个数据：

public boolean add(E e) {

return map.put(e, PRESENT)==null;

}

删除(remove)元素也是调用Map的删除元素的方法：

public boolean remove(Object o) {

return map.remove(o)==PRESENT;

}

返回的迭代器也是Map的key的迭代器：

public Iterator iterator() {

return map.keySet().iterator();

}

TreeSet及其实现方式

TreeSet是基于 TreeMap 的 NavigableSet 实现。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator 进行排序，具体取决于使用的构造方法。因此TreeSet能够取出有序的数据集(是比较得出的顺序，不是插入顺序)。

在TreeSet的内部存储着一个NavigableMap：

private transient NavigableMap m;

但是具体创建类时，实例化的是一个TreeMap：

public TreeSet() {

this(new TreeMap());

}

故TreeSet实际上的操作都是由TreeMap来完成的。和HashSet一样，TreeSet也是使用TreeMap的key作为关键字，Object对象作为值来进行添加(add)操作的：

public boolean add(E e) {

return m.put(e, PRESENT)==null;

}删除(remove)操作：

public boolean remove(Object o) {

return m.remove(o)==PRESENT;

}

产生迭代器：

public Iterator iterator() {

return m.navigableKeySet().iterator();

}

LinkedHashSet及其实现方式

LinkedHashSet继承自HashSet，它内部几乎没有自己的实现代码，只是多增加了几个构造器，这几个构造器在间接的调用HashSet中的构造方法。LinkedHashSet是根据哈希表和链接列表来实现。此实现与 HashSet 的不同之外在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，即按照将元素插入到 set 中的顺序(插入顺序)进行迭代。注意，插入顺序不受在 set 中重新插入的元素的影响(如果在 s.contains(e) 返回 true 后立即调用 s.add(e)，则元素

e 会被重新插入到sets中)。因此，LinkedHashSet可以维护数据插入的顺序(因为它维护了保持插入顺序的链接表)。

LinkedHashSet是根据HashSet的构造器构造LinkedHashMap对象来作为自己的存储对象：

public LinkedHashSet() {

super(16, .75f, true);

}

HashSet(int initialCapacity, float loadFactor, boolean dummy) {//HashSet的包内构造器

map = new LinkedHashMap<>(initialCapacity, loadFactor);

}

LinkedHashSet的其他方法均和HashSet完全一致，完全依赖于LinkedHashMap的操作。