概述
Java的集合框架十分强大，它将常用的数据结构和算法进行封装，使得Java开发者无需精通底层数据结构和算法就可以轻松使用集合框架的API。例如最常见的数组、链表以及队列，栈再到二叉树，红黑树，JDK都将其进行不同程度的封装，极大提升了开发人员的开发效率。不过虽然我们在项目中无需直接接触此类底层逻辑，但我们还是需要熟练掌握其内容。因为在极端的业务场景下，我们可能需要对其底层数据结构进行调试甚至优化，所以熟练掌握底层结构也是必备技能。
以下是一张Collection接口图。
从图中我们可以看到，Collection接口拥有三个主要的子接口，分别是：
Set、List、Queue。
详解-List
我们首先来讲解List接口。
List的特点
- 存储的元素是有序（存储和取出的顺序）的。
- 同一元素可重复存储（可重复）。
- 可通过索引值操作元素。
List接口下包含有ArrayList、Vector、LinkedList三个类分别实现了List接口。
接下来我们来详细讨论其的区别。
我们根据底层数据结构的不同来将其分为两大类：
- 底层是数组。数组查询快，增删慢。
- 底层是链表。链表查询慢，增删快。
ArrayList和Vector属于底层是数组的分类。
ArrayList和Vector的区别？
ArrayList线程不安全，但效率高，适用于频繁的查找工作。Vector线程安全，但效率低。其也是Java早期提供线程安全的动态数组，不推荐在实际生产环境中使用。
源码分析
ArrayList.java
transient Object[] elementData; // non-private to simplify nested class access
private int size;
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);
}
}
从源码可以看出，ArrayList中使用的是Object[]数组，并且查阅ArrayList源码，发现类中没有使用到synchronized和其他任何锁的关键字，故ArrayList是线程不安全。
public synchronized void copyInto(Object[] anArray) {
System.arraycopy(elementData, 0, anArray, 0, elementCount);
}
public synchronized void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (elementCount < oldCapacity) {
elementData = Arrays.copyOf(elementData, elementCount);
}
}
public synchronized void ensureCapacity(int minCapacity) {
if (minCapacity > 0) {
modCount++;
ensureCapacityHelper(minCapacity);
}
}
在Vector类中，同样使用了数组的结构，方法中都带有synchronized关键字，这就使得Vector天生线程安全。但大量使用同步锁造成在高并发场景下，将会有大量阻塞的线程等待，效率地下。
LinkedList
我们再来看看LinkedList。LinkedList底层是链表结构，线程不安全，效率高。
接下来我们来探讨ArrayList和LinkedList的区别。
ArrayList和LinkedList的区别
ArrayList底层采用的是Object数组，而LinkedList底层采用的是双向链表的结构。
注：JDK1.6(包含)和之前采用的是双向循环链表，JDK1.7开始取消了循环。
引用 - 双向链表：包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。
引用 - 双向循环链表：最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。
ArrayList插入和删除的时间复杂度受元素位置的影响。原因如下：ArrayList会将元素追加到末尾，此时，时间复杂度为O(1)。这时我们通过索引在指定的位置i插入或删除元素，那么时间复杂度则为O(n-i) (n为数组的长度)。这是因为数组中第i个和第i个之后的(n-i)个元素都要跟着向后或向前移动一位。LinkedList插入和删除的时间复杂度不受元素位置影响。因为其数据结构为双向链表，所以在add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、removeLast()操作中，其时间复杂度为O(1)，而通过索引下标i进行插入或删除操作时间复杂度为O(n)。这是因为链表指针需要移动到指定位置后插入。ArrayList支持RandomAccess（即高效的随机访问），而LinkedList则不支持。
源码分析
/**
* 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;上图为LinkedList的部分源码。LinkedList类定义了first和last两个Node结点，分别指向头元素和尾元素，是典型的链表结构。
LinkedList类没有用到锁，故其也是线程不安全的。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{...}ArrayList实现了RandomAccess，这个接口与Cloneable一样，只是作为一个标识。说明ArrayList支持高效的随机访问，实现Cloneable说明该类支持克隆。同时，实现了Serializable接口说明该类可被序列化。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{...}可以看到LinkedList并没有支持高效的随机访问。其实现了一个双端队列Deque，其余部分与ArrayList同理。
ArrayList的扩容机制
ArrayList是动态数组，与传统数组相比，它的容量能够动态增长。在源码中，扩容的核心方法是grow()，此处我们详细分析grow()方法，若要了解详细的扩容机制，可自行查阅源码或搜索相关资料。
源码分析
// minCapacity: 最小需要容量
private void grow(int minCapacity) {
// oldCapacity: 旧容量，newCapacity: 新容量
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 此处MAX_ARRAY_SIZE常量值为：Integer.MAX_VALUE - 8
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);
}解释：int newCapacity = oldCapacity + (oldCapacity >> 1);此语句的意思是将oldCapacity做右移一位的运算，其效果相当于oldCapacity / 2。此处使用为位运算而不直接使用除法运算目的在于：位运算速度比除法运算快得多，有助于提升效率，节省资源。
grow方法的逻辑：先将oldCapacity右移一位，然后判断新容量是否小于最小需要容量，若条件满足（即newCapacity < minCapacity），则将新容量设为传入的最小需要容量。
若新容量大于MAX_ARRAY_SIZE，则调用hugeCapacity()方法来比较minCapacity和MAX_ARRAY_SIZE。
hugeCapacity代码如下：
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}即：如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。
最后，使用Arrays.copyOf();方法生成一个新的扩容好的数组，并将其赋值给原始数组即elementData。这就实现了数组的扩容操作。
此外，ArrayList还提供了可供外部调用的扩容方法ensureCapacity。
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}通过源码可以看出，ensureCapacity方法使用的是public修饰符，可供开发者进行调用。在添加大量元素前，开发者可以通过ensureCapacity动态地为数组扩展容量，这样可以避免频繁地扩容带来的性能损失。此处不是此篇的重点，具体感兴趣可自行查看源码。
详解-Set
Set也是Collection的重要子接口之一。从文章开头的框架图可以看出，Set下包含HashSet、LinkedHashSet、TreeSet等子接口。
Set的特点
- 无序性：即存储的元素是无序（存储和取出的顺序）的。
- 唯一性：所有的元素都是唯一的。
Set适合应用在需要去重的场景中。
将Set进行分类，我们同样能够将其分为两大类：
- 底层是哈希表，即HashMap，在下文源码中可以看出。具体HashMap的实现，我将于下一篇进行介绍。
- 底层是二叉树。
HashSet和LinkedHashSet属于第一种分类，即底层是哈希表（LinkedHashSet底层是哈希表+链表）。TreeSet则属于底层是二叉树的分类。
HashSet使用hashCode()和equals()来保证元素的唯一性。
源码分析
我们来看HashSet的两个源码片段。
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}public boolean add(E e) {
return map.put(e, PRESENT)==null;
}从源码可以看出HashSet在初始化时创建了一个HashMap对象。在添加元素的时候，我们可以看到，元素其实是以键的形式存储在HashMap中，对应的值为一个PRESENT的常量。PRESENT的值实际上是一个final的Object对象。这就解释了HashSet如何保证元素的唯一性。
HashSet常用于保证元素唯一性的场景，而TreeSet常用于对排序有要求的场景。在不需要排序的场景下使用HashSet可以获得更好的性能。
谈起排序，我们来具体讨论一下Comparable和Comparator接口。
Comparable接口在java.lang包，它有一个compareTo(Object obj)方法用于排序。Comparator接口在java.util包，它有一个compare(Object obj1, Object obj2)方法用于排序。
Comparable和Comparator接口的区别
Comparable接口是一个自然排序接口，它用于实现自然排序，compareTo也称为自然比较方法。当开发者调用Collections中的sort方法时，对象可按照自身实现的Comparable进行自然排序。这个对象必须实现Comparable接口。Comparator接口可以理解为定制化排序接口，开发者可对没有实现Comparable接口的类进行定制化排序，而无需修改类的源码。
TreeSet源码分析
TreeSet类就同时提供了Comparable和Comparator两种排序的方式。具体我们追溯到源码。
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}通过源码可以看出，TreeSet底层是通过TreeMap实现的，所以我们需要进一步进入到TreeMap中查看具体排序的逻辑。TreeSet的构造函数提供了一个无参构造函数和一个有参构造函数。无参构造函数在TreeMap中将会使用Comparable的自然排序，而有参构造函数传入了一个Comparator对象。
现在我们进入到TreeMap中进行查看。
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}通过源码可以看出，在comparator不为空的时候，getEntry方法会调用getEntryUsingComparator，进而就调用了我们自定义的排序方法。默认则是通过Comparable接口进行自然排序。
HashSet、LinkedHashSet、TreeSet比较
HashSet、LinkedHashSet、TreeSet都是Set接口的实现类，都能保证元素唯一，都不是线程安全的。HashSet底层数据结构为哈希表，基于HashMap进行实现。LinkedHashSet的底层数据结构是链表+哈希表。元素的插入和取出顺序是先进先出。TreeSet的底层数据结构是红黑树（自平衡二叉查找树）。HashSet适用于不需要保证元素插入和取出顺序和不关心排序的场景，LinkedHashSet适用于保证元素的插入和取出顺序满足先进先出的场景，TreeSet适用于需要自定义排序规则的场景。
补充-Queue
Queue是单端队列，即元素只能从一段插入，另一端删除，一般遵循FIFO即先进先出原则。它扩展了Collection接口。
Deque是双端队列，即队列两队均可插入或删除元素。它扩展了Queue接口，并且提供push和pop等特殊方法，可用于模拟栈结构。
Deque接口下用得较多的就是LinkedList类，具体可查看前文内容。
总结
在本文的末尾，我总结了一个表格对比了上文讲述的对象的特点。
| 对象 | 底层数据结构 | 是否线程安全 |
|---|---|---|
| ArrayList | 数组 | 否 |
| Vector | 数组 | 是 |
| LinkedList | 链表 | 否 |
| HashSet | 哈希表 | 否 |
| LinkedHashSet | 哈希表+链表 | 否 |
| TreeSet | 红黑树 | 否 |
Java容器中的Collection是一个面试常考/必考的知识点，并且在开发中也十分常用。熟练掌握Collection体系内容是极其必要的。