# 新手引导 集合在我们日常开发使用的次数数不胜数，`ArrayList`/`LinkedList`/`HashMap`/`HashSet`······信手拈来，抬手就拿来用，在 IDE 上龙飞凤舞，但是作为一名合格的优雅的程序猿，仅仅了解怎么使用`API`是远远不够的，如果在调用`API`时，知道它内部发生了什么事情，就像开了`透视`外挂一样，洞穿一切，这种感觉才真的爽，而且这样就**不是集合提供什么功能给我们使用，而是我们选择使用它的什么功能了**。  ## 集合框架总览 下图堪称集合框架的**上帝视角**，讲到集合框架不得不看的就是这幅图，当然，你会觉得眼花缭乱，不知如何看起，这篇文章带你一步一步地秒杀上面的每一个接口、抽象类和具体类。我们将会从最顶层的接口开始讲起，一步一步往下深入，帮助你把对集合的认知构建起一个知识网络。  工欲善其事必先利其器，让我们先来过一遍整个集合框架的组成部分： 1. 集合框架提供了两个遍历接口：`Iterator`和`ListIterator`，其中后者是前者的`优化版`，支持在任意一个位置进行**前后双向遍历**。注意图中的`Collection`应当继承的是`Iterable`而不是`Iterator`，后面会解释`Iterable`和`Iterator`的区别 2. 整个集合框架分为两个门派（类型）：`Collection`和`Map`，前者是一个容器，存储一系列的**对象**；后者是键值对``，存储一系列的**键值对** 3. 在集合框架体系下，衍生出四种具体的集合类型：`Map`、`Set`、`List`、`Queue` 4. `Map`存储``键值对，查找元素时通过`key`查找`value` 5. `Set`内部存储一系列**不可重复**的对象，且是一个**无序**集合，对象排列顺序不一 6. `List`内部存储一系列**可重复**的对象，是一个**有序**集合，对象按插入顺序排列 7. `Queue`是一个**队列**容器，其特性与`List`相同，但只能从`队头`和`队尾`操作元素 8. JDK 为集合的各种操作提供了两个工具类`Collections`和`Arrays`，之后会讲解工具类的常用方法 9. 四种抽象集合类型内部也会衍生出许多具有不同特性的集合类，**不同场景下择优使用，没有最佳的集合** 上面了解了整个集合框架体系的组成部分，接下来的章节会严格按照上面罗列的顺序进行讲解，每一步都会有`承上启下`的作用 > 学习`Set`前，最好最好要先学习`Map`，因为`Set`的操作本质上是对`Map`的操作，往下看准没错 ### Iterator Iterable ListIterator 在第一次看这两个接口，真以为是一模一样的，没发现里面有啥不同，**存在即合理**，它们两个还是有本质上的区别的。 首先来看`Iterator`接口： ```java public interface Iterator { boolean hasNext(); E next(); void remove(); } ``` 提供的API接口含义如下： - `hasNext()`：判断集合中是否存在下一个对象 - `next()`：返回集合中的下一个对象，并将访问指针移动一位 - `remove()`：删除集合中调用`next()`方法返回的对象 在早期，遍历集合的方式只有一种，通过`Iterator`迭代器操作 ```java List list = new ArrayList<>(); list.add(1); list.add(2); list.add(3); Iterator iter = list.iterator(); while (iter.hasNext()) { Integer next = iter.next(); System.out.println(next); if (next == 2) { iter.remove(); } } ``` 再来看`Iterable`接口： ```java public interface Iterable { Iterator iterator(); // JDK 1.8 default void forEach(Consumer super T> action) { Objects.requireNonNull(action); for (T t : this) { action.accept(t); } } } ``` 可以看到`Iterable`接口里面提供了`Iterator`接口，所以实现了`Iterable`接口的集合依旧可以使用`迭代器`遍历和操作集合中的对象； 而在 `JDK 1.8`中，`Iterable`提供了一个新的方法`forEach()`，它允许使用增强 for 循环遍历对象。 ```java List list = new ArrayList<>(); for (Integer num : list) { System.out.println(num); } ``` 我们通过命令：`javap -c`反编译上面的这段代码后，发现它只是 Java 中的一个`语法糖`，本质上还是调用`Iterator`去遍历。  翻译成代码，就和一开始的`Iterator`迭代器遍历方式基本相同了。 ```java Iterator iter = list.iterator(); while (iter.hasNext()) { Integer num = iter.next(); System.out.println(num); } ``` > 还有更深层次的探讨：为什么要设计两个接口`Iterable`和`Iterator`，而不是保留其中一个就可以了。 > > 简单讲解：`Iterator`的保留可以让子类去**实现自己的迭代器**，而`Iterable`接口更加关注于`for-each`的增强语法。具体可参考：[Java中的Iterable与Iterator详解](https://www.cnblogs.com/litexy/p/9744241.html) 关于`Iterator`和`Iterable`的讲解告一段落，下面来总结一下它们的重点： 1. `Iterator`是提供集合操作内部对象的一个迭代器，它可以**遍历、移除**对象，且只能够**单向移动** 2. `Iterable`是对`Iterator`的封装，在`JDK 1.8`时，实现了`Iterable`接口的集合可以使用**增强 for 循环**遍历集合对象，我们通过**反编译**后发现底层还是使用`Iterator`迭代器进行遍历 等等，这一章还没完，还有一个`ListIterator`。它继承 Iterator 接口，在遍历`List`集合时可以从**任意索引下标**开始遍历，而且支持**双向遍历**。 ListIterator 存在于 List 集合之中，通过调用方法可以返回**起始下标**为 `index`的迭代器 ```java List list = new ArrayList<>(); // 返回下标为0的迭代器 ListIterator listIter1 = list.listIterator(); // 返回下标为5的迭代器 ListIterator listIter2 = list.listIterator(5); ``` ListIterator 中有几个重要方法，大多数方法与 Iterator 中定义的含义相同，但是比 Iterator 强大的地方是可以在**任意一个下标位置**返回该迭代器，且可以实现**双向遍历**。 ```java public interface ListIterator extends Iterator { boolean hasNext(); E next(); boolean hasPrevious(); E previous(); int nextIndex(); int previousIndex(); void remove(); // 替换当前下标的元素,即访问过的最后一个元素 void set(E e); void add(E e); } ``` ### Map 和 Collection 接口 Map 接口和 Collection 接口是集合框架体系的两大门派，Collection 是存储元素本身，而 Map 是存储``键值对，在 Collection 门派下有一小部分弟子去`偷师`，利用 Map 门派下的弟子来修炼自己。 是不是听的一头雾水哈哈哈，举个例子你就懂了：`HashSet`底层利用了`HashMap`，`TreeSet`底层用了`TreeMap`，`LinkedHashSet`底层用了`LinkedHashMap`。 下面我会详细讲到各个具体集合类哦，所以在这里，我们先从整体上了解这两个`门派`的特点和区别。  `Map`接口定义了存储的数据结构是``形式，根据 key 映射到 value，一个 key 对应一个 value ，所以`key`不可重复，而`value`可重复。 在`Map`接口下会将存储的方式细分为不同的种类： - `SortedMap`接口：该类映射可以对``按照自己的规则进行**排序**，具体实现有 TreeMap - `AbsractMap`：它为子类提供好一些**通用的API实现**，所有的具体Map如`HashMap`都会继承它 而`Collection`接口提供了所有集合的**通用方法**（注意这里不包括`Map`）： - 添加方法：`add(E e)` / `addAll(Collection extends E> var1)` - 删除方法：`remove(Object var1)` / `removeAll(Collection> var1)` - 查找方法：`contains(Object var1)` / `containsAll(Collection> var1);` - 查询集合自身信息：`size()` / `isEmpty()` - ··· 在`Collection`接口下，同样会将集合细分为不同的种类： - `Set`接口：一个**不允许存储重复元素**的**无序**集合，具体实现有`HashSet` / `TreeSet`··· - `List`接口：一个**可存储重复元素**的**有序**集合，具体实现有`ArrayList` / `LinkedList`··· - `Queue`接口：一个**可存储重复元素**的**队列**，具体实现有`PriorityQueue` / `ArrayDeque`··· ## Map 集合体系详解 `Map`接口是由``组成的集合，由`key`映射到**唯一**的`value`，所以`Map`不能包含重复的`key`，每个键**至多**映射一个值。下图是整个 Map 集合体系的主要组成部分，我将会按照日常使用频率从高到低一一讲解。 不得不提的是 Map 的设计理念：**定位元素**的时间复杂度优化到 `O(1)` Map 体系下主要分为 AbstractMap 和 SortedMap两类集合 `AbstractMap`是对 Map 接口的扩展，它定义了普通的 Map 集合具有的**通用行为**，可以避免子类重复编写大量相同的代码，子类继承 AbstractMap 后可以重写它的方法，**实现额外的逻辑**，对外提供更多的功能。 `SortedMap` 定义了该类 Map 具有 `排序`行为，同时它在内部定义好有关排序的抽象方法，当子类实现它时，必须重写所有方法，对外提供排序功能。 ### HashMap HashMap 是一个**最通用的**利用哈希表存储元素的集合，将元素放入 HashMap 时，将`key`的哈希值转换为数组的`索引`下标**确定存放位置**，查找时，根据`key`的哈希地址转换成数组的`索引`下标**确定查找位置**。 HashMap 底层是用数组 + 链表 + 红黑树这三种数据结构实现，它是**非线程安全**的集合。  发送哈希冲突时，HashMap 的解决方法是将相同映射地址的元素连成一条`链表`，如果链表的长度大于`8`时，且数组的长度大于`64`则会转换成`红黑树`数据结构。 关于 HashMap 的简要总结： 1. 它是集合中最常用的`Map`集合类型，底层由`数组 + 链表 + 红黑树`组成 2. HashMap不是线程安全的 3. 插入元素时，通过计算元素的`哈希值`，通过**哈希映射函数**转换为`数组下标`；查找元素时，同样通过哈希映射函数得到数组下标`定位元素的位置` ### LinkedHashMap LinkedHashMap 可以看作是 `HashMap` 和 `LinkedList` 的结合：它在 HashMap 的基础上添加了一条双向链表，`默认`存储各个元素的插入顺序，但由于这条双向链表，使得 LinkedHashMap 可以实现 `LRU`缓存淘汰策略，因为我们可以设置这条双向链表按照`元素的访问次序`进行排序  LinkedHashMap 是 HashMap 的子类，所以它具备 HashMap 的所有特点，其次，它在 HashMap 的基础上维护了一条`双向链表`，该链表存储了**所有元素**，`默认`元素的顺序与插入顺序**一致**。若`accessOrder`属性为`true`，则遍历顺序按元素的访问次序进行排序。 ```java // 头节点 transient LinkedHashMap.Entry head; // 尾结点 transient LinkedHashMap.Entry tail; ``` 利用 LinkedHashMap 可以实现 `LRU` 缓存淘汰策略，因为它提供了一个方法： ```java protected boolean removeEldestEntry(java.util.Map.Entry eldest) { return false; } ``` 该方法可以移除`最靠近链表头部`的一个节点，而在`get()`方法中可以看到下面这段代码，其作用是挪动结点的位置： ```java if (this.accessOrder) { this.afterNodeAccess(e); } ``` 只要调用了`get()`且`accessOrder = true`，则会将该节点更新到链表`尾部`，具体的逻辑在`afterNodeAccess()`中，感兴趣的可翻看源码，篇幅原因这里不再展开。 现在如果要实现一个`LRU`缓存策略，则需要做两件事情： - 指定`accessOrder = true`可以设定链表按照访问顺序排列，通过提供的构造器可以设定`accessOrder` ```java public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } ``` - 重写`removeEldestEntry()`方法，内部定义逻辑，通常是判断`容量`是否达到上限，若是则执行淘汰。 这里就要贴出一道大厂面试必考题目：[146. LRU缓存机制](https://leetcode-cn.com/problems/lru-cache/)，只要跟着我的步骤，就能顺利完成这道大厂题了。 关于 LinkedHashMap 主要介绍两点： 1. 它底层维护了一条`双向链表`，因为继承了 HashMap，所以它也不是线程安全的 2. LinkedHashMap 可实现`LRU`缓存淘汰策略，其原理是通过设置`accessOrder`为`true`并重写`removeEldestEntry`方法定义淘汰元素时需满足的条件 ### TreeMap TreeMap 是 `SortedMap` 的子类，所以它具有**排序**功能。它是基于`红黑树`数据结构实现的，每一个键值对``都是一个结点，默认情况下按照`key`自然排序，另一种是可以通过传入定制的`Comparator`进行自定义规则排序。 ```java // 按照 key 自然排序，Integer 的自然排序是升序 TreeMap naturalSort = new TreeMap<>(); // 定制排序，按照 key 降序排序 TreeMap customSort = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1)); ``` TreeMap 底层使用了数组+红黑树实现，所以里面的存储结构可以理解成下面这幅图哦。  图中红黑树的每一个节点都是一个`Entry`，在这里为了图片的简洁性，就不标明 key 和 value 了，注意这些元素都是已经按照`key`排好序了，整个数据结构都是保持着`有序` 的状态！ 关于`自然`排序与`定制`排序： - 自然排序：要求`key`必须实现`Comparable`接口。 由于`Integer`类实现了 Comparable 接口，按照自然排序规则是按照`key`从小到大排序。 ```java TreeMap treeMap = new TreeMap<>(); treeMap.put(2, "TWO"); treeMap.put(1, "ONE"); System.out.print(treeMap); // {1=ONE, 2=TWO} ``` - 定制排序：在初始化 TreeMap 时传入新的`Comparator`，**不**要求`key`实现 Comparable 接口 ```java TreeMap treeMap = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1)); treeMap.put(1, "ONE"); treeMap.put(2, "TWO"); treeMap.put(4, "FOUR"); treeMap.put(3, "THREE"); System.out.println(treeMap); // {4=FOUR, 3=THREE, 2=TWO, 1=ONE} ``` 通过传入新的`Comparator`比较器，可以覆盖默认的排序规则，上面的代码按照`key`降序排序，在实际应用中还可以按照其它规则自定义排序。 `compare()`方法的返回值有三种，分别是：`0`，`-1`，`+1` （1）如果返回`0`，代表两个元素相等，不需要调换顺序 （2）如果返回`+1`，代表前面的元素需要与后面的元素调换位置 （3）如果返回`-1`，代表前面的元素不需要与后面的元素调换位置 而何时返回`+1`和`-1`，则由我们自己去定义，JDK默认是按照**自然排序**，而我们可以根据`key`的不同去定义降序还是升序排序。 关于 TreeMap 主要介绍了两点： 1. 它底层是由`红黑树`这种数据结构实现的，所以操作的时间复杂度恒为`O(logN)` 2. TreeMap 可以对`key`进行自然排序或者自定义排序，自定义排序时需要传入`Comparator`，而自然排序要求`key`实现了`Comparable`接口 3. TreeMap 不是线程安全的。 ### WeakHashMap WeakHashMap 日常开发中比较少见，它是基于普通的`Map`实现的，而里面`Entry`中的键在每一次的`垃圾回收`都会被清除掉，所以非常适合用于**短暂访问、仅访问一次**的元素，缓存在`WeakHashMap`中，并尽早地把它回收掉。 当`Entry`被`GC`时，WeakHashMap 是如何感知到某个元素被回收的呢？ 在 WeakHashMap 内部维护了一个引用队列`queue` ```java private final ReferenceQueue