前言
在 Java 中数组的长度是不可修改的。然而在实际应用的很多情况下，无法确定数据数量。这些数据不适合使用数组来保存，这时候就需要使用集合。Java 的集合就像一个容器，用来存储 Java 类的对象，这个容器里只能放对象，对于基本类型(int, long, float, double等)，需要将其包装成对象类型后(Integer, Long, Float, Double等)才能放到容器里。很多时候拆包装和解包装能够自动完成。
在集合中经常会用到泛型来使集合更加安全。
Java 集合框架如下所示：
分类
Java 集合主要是由两大接口 (Interface) 派生出来的：Collection 和 Map。
这两大接口的不同之处在于：Collection 存放单一元素；Map 存放 key-value 键值对。
Collection 接口
Collection 接口是 List、Set 和 Queue 接口的父接口，通常情况下不被直接使用。
Collection 接口定义了很多方法，这些方法也都会继承到各个子接口和实现类里。
Collection 接口中常用的方法，如下表所示：
| 序号 | 方法名称 | 说明 |
|---|---|---|
| 1 | boolean add(E e); | 传入的数据类型必须是 Object，当写入基本数据类型的时候，会做自动装箱和自动拆箱。 |
| 2 | boolean addAll(Collection<? extends E> c); | 可以把另一个集合 c 里的所有元素加到集合中。 |
| 3 | boolean remove(Object o); | 从集合中删除一个指定元素，当集合中包含了一个或多个元素 o 时，该方法只删除第一个符合条件的元素，该方法将返回 true。 |
| 4 | boolean removeAll(Collection<?> c); | 从集合中删除所有在集合 c 中出现的元素。 |
| 5 | boolean contains(Object o); | 判断集合中是否存在指定的元素。 |
| 6 | boolean containsAll(Collection c); | 判断集合中是否包含集合 c 中的所有元素。 |
| 7 | boolean isEmpty(); | 判断集合是否为空。 |
| 8 | int size(); | 返回集合中元素的个数。 |
| 9 | Object[] toArray(); | 把集合转换为一个数组，所有的集合元素变成对应的数组元素。 |
| 10 | Iterator | 返回一个 Iterator 对象，用于遍历集合中的元素。 |
List 接口
List 是一个有序、可重复的集合，集合中每个元素都有其对应的顺序索引，第一个元素的索引值是 0。List 的实现类有 ArrayList、LinkedList、Vector、Stack。
List 实现了 Collection 接口，常用的实现类有：ArrayList 类和 LinkedList 类。
ArrayList：基于动态数组实现，支持随机访问。Vector：和 ArrayList 类似，但它是线程安全的。LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素，还可以用作栈、队列和双向队列。
| 功能 | 方法 | ArrayList | LinkedList |
|---|---|---|---|
| 增 | add(E e) | O(1) | O(1) |
| 增 | add(int index, E e) | O(n) | O(n) |
| 删 | remove(int index) | O(n) | O(n) |
| 删 | remove(E e) | O(n) | O(n) |
| 改 | set(int index, E e) | O(1) | O(n) |
| 查 | get(int index) | O(1) | O(n) |
小结：
- 改查选择 ArrayList；
- 增删在尾部的选择 ArrayList；
- 其他情况下，如果时间复杂度一样，推荐选择 ArrayList，因为 overhead 更小，或者说内存使用更有效率。
Vector 是 JDK1.0 中给出的类，和 ArrayList 一样，也是继承自 java.util.AbstractList，底层也是用数组来实现的。但是现在已经不推荐使用了，因为线程安全造成效率低，现在大家也不在数据结构的层面加 synchronized；其次是扩容时的区别：Vector 空间满了之后，扩容是一倍，而 ArrayList 仅仅是一半，也就是说扩容后的 Vector 是原来的 2 倍，ArrayList 是原来的 1.5 倍。Vector 分配内存的时候需要连续的存储空间，如果数据太多，容易分配内存失败。
Queue 接口
Queue 接口继承自 Collection 接口，除了最基本的 Collection 的方法之外，它还支持额外的插入、获取和检查操作。
有两组格式，共 6 个方法，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回 null)。
其中有一种特殊的队列叫做 PriorityQueue，即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器。
| 抛异常 | 返回值 | 说明 |
|---|---|---|
| add(e) | offer(e) | 都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。 |
| remove() | poll() | 都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。 |
| element() | peek() | 都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null。 |
小结：
- 首先，要用就用同一组 API，前后要统一；
- 其次，根据需求。如果你需要它抛异常，那就是用抛异常的；不过做算法题时基本不用，所以选那组返回特殊值的就好了。
Deque 接口
Deque 接口继承自 Queue接口，除了支持 Queue 的方法之外，还有自己的方法。由于 Deque 是双向的，所以可以对队列的头和尾都进行操作，它同时也支持两组格式，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。
| 功能 | 抛异常 | 返回值 |
|---|---|---|
| 插入 | addFirst(e) / addLast(e) | offerFirst(e) / offerLast(e) |
| 移除 | removeFirst() / removeLast() | pollFirst() / pollLast() |
| 检查 | getFirst() / getLast() | peekFirst() / peekLast() |
小结：
- 前后要统一，要么全部使用前一组，要么全部使用后一组；
- Queue 和 Deque 的这些 API 都是 O(1) 的时间复杂度，准确来说是均摊时间复杂度。
- 如果想实现「先进先出」的普通队列，就使用 LinkedList 或者 ArrayDeque 来实现，但更推荐使用 ArrayDeque，因为效率高，而 LinkedList 还会有其他的额外开销（overhead）；
- 如果想实现「优先队列」，就使用 PriorityQueue；
- 如果想实现「栈」，就使用 ArrayDeque。
Stack
虽然 Java 中有 Stack 这个类，但是根据官方文档，已经不推荐使用了，因为 Vector 都已经过时被弃用了，而 Stack 是继承 Vector 的。
所以，想实现「栈」，就使用 ArrayDeque。例如：Deque<Integer> stack = new ArrayDeque<Integer>();
Set 接口
与 List 恰好相反，Set 是无序、不重复的集合，它最多只允许包含一个 null 元素。
它主要有三个常用的实现类：散列集 HashSet、链式散列集 LinkedHashSet 和树形集 TreeSet。
HashSet: 采用 HashMap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。LinkedHashSet: 继承自 HashSet，其底层是基于 LinkedHashMap 来实现的，有序，非同步。特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序，也就是说，当遍历该集合时候，LinkedHashSet 将会以元素的添加顺序访问集合的元素。TreeSet: 采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序，其中自然排序为默认的排序方式；缺点就是查询速度没有 HashSet 快。
那每个 Set 的底层实现其实就是对应的 Map：
数值放在 map 中的 key 上，value 上放了个 PRESENT，是一个静态的 Object，相当于 place holder，每个 key 都指向这个 object。
Map 接口
Map 是一个映射接口，即 key-value 键值对。
HashMap
HashSet 和 HashMap 二者在 Java 里有着相同的实现，前者仅仅是对后者做了一层包装，也就是说 HashSet 里面有一个HashMap(适配器模式)。
HashMap实现了 Map 接口，即允许放入 key 为 null 的元素，也允许插入 value 为 null 的元素；除该类未实现同步外，其余跟 Hashtable 大致相同；跟 TreeMap 不同，该容器不保证元素顺序。
根据对冲突的处理方式不同，哈希表有两种实现方式，一种开放地址方式，另一种是冲突链表方式。
在 Java8 中，当链表中的元素达到了 8 个时，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。
LinkedHashMap
LinkedHashSet 和 LinkedHashMap 在 Java 里也有着相同的实现，前者仅仅是对后者做了一层包装，也就是说 LinkedHashSet里面有一个 LinkedHashMap (适配器模式)。
从名字上可以看出该容器是 linkedList 和 HashMap 的混合体，也就是说它同时满足 HashMap 和 linkedList 的某些特性。可将 LinkedHashMap 看作采用 linkedList 增强的 HashMap。事实上 LinkedHashMap 是 HashMap 的直接子类，二者唯一的区别是 LinkedHashMap 在 HashMap 的基础上，采用双向链表(doubly-linked list)的形式将所有 entry 连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。
将对象放入到 LinkedHashMap 或 LinkedHashSet 中时，有两个方法需要特别关心: hashCode()和 equals()。hashCode()方法决定了对象会被放到哪个 bucket 里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到 LinkedHashMap 或 LinkedHashSet中，需要 @Override hashCode()和 equals()方法。
TreeMap
TreeMap 是一个有序的 key-value 集合，非同步，基于红黑树（Red-Black tree）实现，每一个 key-value 节点作为红黑树的一个节点。
TreeMap 实现了 SortedMap 接口，也就是说会按照 key的大小顺序对Map中的元素进行排序，其中排序方式也是分为两种，一种是自然排序，一种是定制排序，具体取决于使用的构造方法。
Iterator 接口
Iterator（迭代器）是一个接口，它是集合的迭代器。Collection 和 Map 系列集合主要用于盛装其他对象，而 Iterator 则主要用于遍历（即迭代访问）Collection 集合中的元素。
| 方法名 | 说明 |
|---|---|
| boolean hasNext() | 判断集合里是否存在下一个元素。如果有，hasNext() 方法返回 true。 |
| E next() | 返回集合里下一个元素，如果没有就抛出NoSuchElementException异常。 |
| default void remove() | 删除集合里上一次 next 方法返回的元素。 |
| default void forEachRemaining(Consumer<? super E> action) | Java 8 为 Iterator 新增的默认方法，该方法可使用 Lambda 表达式来遍历集合元素。 |
ListIterator 接口
ListIterator 是一个功能更加强大的迭代器, 它继承于 Iterator 接口，只能用于对各种 List 类型的访问。
参考
CSDN
官方文档
Java 全栈知识体系
Java专栏
