Java基础关系图



来源 | Java建设者（ID：javajianshe）

集合在我们日常开发使用的次数数不胜数， 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 接口：

提供的 API 接口含义如下：

• hasNext()：判断集合中是否存在下一个对象

• next()：返回集合中的下一个对象，并将访问指针移动一位

• remove()：删除集合中调用 next() 方法返回的对象

在早期，遍历集合的方式只有一种，通过 Iterator 迭代器操作：

再来看 Iterable 接口：

可以看到 Iterable 接口里面提供了 Iterator 接口，所以实现了 Iterable 接口 的

集合依旧可以使用迭代器遍历和操作集合中的对象；

而在 JDK 1.8中，Iterable 提供了一个新的方法 forEach()，它允许使用增强for 循环遍历对象。

翻译成代码，就和一开始的 Iterator 迭代器遍历方式基本相同了。

还有更深层次的探讨：为什么要设计两个接口 Iterable 和 Iterator，而不是保留其中一个就可以了。 简单讲解：Iterator 的保留可以让子类去实现自己的迭代器，而 Iterable 接口更加关注于 for-each 的增强语法。具体可参考：Java 中的 Iterable 与 Iterator 详解

关于 Iterator 和 Iterable 的讲解告一段落，下面来总结一下它们的重点：

1. Iterator 是提供集合操作内部对象的一个迭代器，它可以遍历、移除对象，且只能够单向移动。

2. Iterable 是对 Iterator 的封装，在 JDK 1.8 时，实现了 Iterable 接口的集合可以使用增强 for 循环遍历集合对象，我们通过反编译后发现底层还是使用 Iterator 迭代器进行遍历。

等等，这一章还没完，还有一个 ListIterator。它继承 Iterator 接口，在遍历List 集合时可以从任意索引下标开始遍历，而且支持双向遍历。

ListIterator 存在于 List 集合之中，通过调用方法可以返回起始下标为 index的迭代器：

ListIterator 中有几个重要方法，大多数方法与 Iterator 中定义的含义相同，但是比 Iterator 强大的地方是可以在任意一个下标位置返回该迭代器，且可以实现双向遍历。

Map 和 Collection 接口

Map 接口和 Collection 接口是集合框架体系的两大门派，Collection 是存储元素本身，而 Map 是存储 键值对，在 Collection 门派下有一小部分弟子去偷师，利用 Map 门派下的弟子来修炼自己。

是不是听的一头雾水哈哈哈，举个例子你就懂了：HashSet 底层利用了HashMa，TreeSet底层用了TreeMap，LinkedHashSet底层用了LinkedHashMap。

下面我会详细讲到各个具体集合类哦，所以在这里，我们先从整体上了解这两个门派的特点和区别。

Map 接口定义了存储的数据结构是 < key, value> 形式，根据 key 映射到 value，一个 key 对应一个 value ，所以 key 不可重复，而 value 可重复。

在 Map 接口下会将存储的方式细分为不同的种类：

• SortedMap 接口：该类映射可以对 按照自己的规则进行排序，具体实现有 TreeMap

• AbsractMap：它为子类提供好一些通用的 API 实现，所有的具体 Map 如 HashMap 都会继承它

而 Collection 接口提供了所有集合的通用方法（注意这里不包括 Map ）：

• 添加方法：add(E e) / addAll(Collection 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 的设计理念：定位元素的时间复杂度优化到 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 可以实现 LRU 缓存淘汰策略，因为它提供了一个方法：

该方法可以移除最靠近链表头部的一个节点，而在 get() 方法中可以看到下面这段代码，其作用是挪动结点的位置：

只要调用了 get() 且 accessOrder=true，则会将该节点更新到链表尾部，具体

的逻辑在afterNodeAccess()中，感兴趣的可翻看源码，篇幅原因这里不再展开。

现在如果要实现一个LRU缓存策略，则需要做两件事情：

• 指定 accessOrder = true 可以设定链表按照访问顺序排列，通过提供的

  构造器可以设定 accessOrder

• 重写 removeEldestEntry() 方法，内部定义逻辑，通常是判断容量是否达到上限，若是则执行淘汰。

这里就要贴出一道大厂面试必考题目：146. LRU 缓存机制，只要跟着我的步骤，就能顺利完成这道大厂题了。

关于 LinkedHashMap 主要介绍两点：

1. 它底层维护了一条双向链表，因为继承了 HashMap，所以它也不是线程安全的

2. LinkedHashMap 可实现LRU缓存淘汰策略，其原理是通过设置 accessOrder 为 true 并重写 removeEldestEntry 方法定义淘汰元素时需满足的条件

TreeMap

TreeMap 是 SortedMap 的子类，所以它具有排序功能。它是基于红黑树数据结构实现的，每一个键值对 都是一个结点，默认情况下按照key自然排序，另一种是可以通过传入定制的 Comparator 进行自定义规则排序。

TreeMap 底层使用了数组+红黑树实现，所以里面的存储结构可以理解成下面这 幅图哦。

关于自然排序与定制排序：

• 自然排序：要求 key 必须实现 Comparable 接口。

由于 Integer 类实现了 Comparable 接口，按照自然排序规则是按照 key 从小到大排序。

• 定制排序：在初始化 TreeMap 时传入新的 Comparator，不要求 key

  实现 Comparable 接口

通过传入新的 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

再者，需要注意 WeakHashMap 底层存储的元素的数据结构是数组 + 链表，没

有红黑树哦，可以换一个角度想，如果还有红黑树，那干脆直接继承 HashMap，

然后再扩展就完事了嘛，然而它并没有这样做：

/code>

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F726f8c16p00qeqwxa001dd200sr00h5g00it00b7.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

1. 它的键是一种弱键，放入 WeakHashMap 时，随时会被回收掉，所以不能确保某次访问元素一定存在

2. 它依赖普通的 Map 进行实现，是一个非线程安全的集合

3. WeakHashMap 通常作为缓存使用，适合存储那些只需访问一次、或只需保存短暂时间的键值对

Hashtable

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F571f9f29p00qeqwxa000ed200tg009tg00it0069.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

blockquote>这幅图是否有点眼熟哈哈哈哈，本质上就是 WeakHashMap 的底层存储结构了。你千万别问为什么 WeakHashMap 不继承 Hashtable 哦，Hashtable 的性能在并发环境下非常差，在非并发环境下可以用 HashMap 更优。

/blockquote>

br/>

Collection 集合体系详解

br/>

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2Fe7dd9e2dp00qeqwxb002jd200u000ewg00it009b.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

Set 接口

br/>

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F4983bf4bp00qeqwxb0009d200f600eog00f600eo.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

• 存入可变元素时，必须非常小心，因为任意时候元素状态的改变都有可能使得 Set 内部出现两个相等的元素，即 o1.equals(o2) = true，所以一般不要更改存入 Set 中的元素，否则将会破坏了 equals() 的作用！

• Set 的最大作用就是判重，在项目中最大的作用也是判重！

AbstractSet 抽象类

SortedSet 接口

HashSet

blockquote>这也是这篇文章为什么先讲解 Map 再讲解 Set 的原因！先学习 Map，有助于理解 Set

/blockquote>

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F67a21773p00qeqwxb001qd200u0008hg00it005b.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

• 底层数据结构：HashSet 也是采用数组 + 链表 + 红黑树实现

• 线程安全性：由于采用 HashMap 实现，而 HashMap 本身线程不安全，在HashSet 中没有添加额外的同步策略，所以 HashSet 也线程不安全

• 存入 HashSet 的对象的状态最好不要发生变化，因为有可能改变状态后，在集合内部出现两个元素 o1.equals(o2)，破坏了 equals() 的语义。

LinkedHashSet

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2Fbb10088cp00qeqwxb003xd200u000bwg00it007g.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

blockquote>LinkedHashSet -> LinkedHashMap -> HashMap + 双向链表

/blockquote>

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F90ec1c60p00qeqwxc0038d200u000eag00it008y.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

• 它继承了 HashSet，而 HashSet 默认是采用 HashMap 存储数据的，但是 LinkedHashSet 调用父类构造方法初始化 map 时是 LinkedHashMap 而不是 HashMap，这个要额外注意一下

• 由于 LinkedHashMap 不是线程安全的，且在 LinkedHashSet 中没有添加额外的同步策略，所以 LinkedHashSet 集合也不是线程安全的

TreeSet

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2Fcp00qeqwxc002ed200u0008zg00it005m.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

• TreeSet 的所有操作都会转换为对 TreeMap 的操作，TreeMap 采用红黑树实现，任意操作的平均时间复杂度为 O(logN)

• TreeSet 是一个线程不安全的集合

• TreeSet 常应用于对不重复的元素定制排序，例如玩家战力排行榜

blockquote>注意:TreeSet 判断元素是否重复的方法是判断 compareTo() 方法是否返回0，而不是调用 hashcode() 和 equals() 方法，如果返回 0 则认为集合内已经存在相同的元素，不会再加入到集合当中。

/blockquote>

List 接口

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2Fdp00qeqwxc000ad200ku00fgg00it00dx.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

AbstractList 和 AbstractSequentialList

Vector

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F711c65c8p00qeqwxc0017d200u0008dg00it0058.png&thumbnail=660x&quality=80&type=jpg"/>

blockquote>JDK 1.0 时代，ArrayList 还没诞生，大家都是使用 Vector 集合，但由于 Vector 的每个操作都被 synchronized 关键字修饰，即使在线程安全的情况下，仍然进行无意义的加锁与释放锁，造成额外的性能开销，做了无用功。

/blockquote>

Stack

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F8bf94f71p00qeqwxc000qd200oq00awg00it008a.png&thumbnail=660x&quality=80&type=jpg"/>

ArrayList

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F711c65c8p00qeqwxc0017d200u0008dg00it0058.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

• 具备随机访问特点，访问元素的效率较高，ArrayList 在频繁插入、删除集合元素的场景下效率较低。

• 底层数据结构：ArrayList 底层使用数组作为存储结构，具备查找快、增删慢的特点

• 线程安全性：ArrayList 是线程不安全的集合

• ArrayList 首次扩容后的长度为 10，调用 add() 时需要计算容器的最小容量。可以看到如果数组 elementData 为空数组，会将最小容量设置为 10 ，之后会将数组长度完成首次扩容到 10。

• 集合从第二次扩容开始，数组长度将扩容为原来的 1.5 倍，即：newLength = oldLength * 1.5

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F7e21f474p00qeqwxd001td200mw00a6g00it008c.png&thumbnail=660x&quality=80&type=jpg"/>

LinkedList

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F1215a089p00qeqwxd001nd200u0007vg00it004x.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2Fb7b3011dp00qeqwxd000gd200eb0051g00eb0051.png&thumbnail=660x&quality=80&type=jpg"/>

br/>

• 优势：LinkedList 底层没有扩容机制，使用双向链表存储元素，所以插入和删除元素效率较高，适用于频繁操作元素的场景

• 劣势：LinkedList 不具备随机访问的特点，查找某个元素只能从 head 或 tail 指针一个一个比较，所以查找中间的元素时效率很低

• 查找优化：LinkedList 查找某个下标 index 的元素时做了优化，若 index > (size / 2)，则从 head 往后查找，否则从 tail 开始往前查找，代码如下所示：

• 双端队列：使用双端链表实现，并且实现了 Deque 接口，使得 LinkedList 可以用作双端队列。下图可以看到 Node 是集合中的元素，提供了前驱指针和后继指针，还提供了一系列操作头结点和尾结点的方法，具有双端队列的特性。

img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2020%2F0808%2F757a8cfbp00qeqwxe001xd200e800g0g00e800g0.png&thumbnail=660x&quality=80&type=jpg"/>

blockquote>

/blockquote>

blockquote>

/blockquote>

PriorityQueue 是基于优先级堆实现的优先级队列，而堆是用数组维护的

PriorityQueue 适用于元素按优先级处理的业务场景，例如用户在请求人工客服需要排队时，根据用户的VIP等级进行 插队 处理，等级越高，越先安排客服。

Collection 接口提供了整个集合框架最通用的增删改查以及集合自身操作的抽象方法，让子类去实现

Set 接口决定了它的子类都是无序、无重复元素的集合，其主要实现有HashSet、TreeSet、LinkedHashSet。

• HashSet 底层采用 HashMap 实现，而 TreeSet 底层使用 TreeMap 实现，大部分 Set 集合的操作都会转换为 Map 的操作，TreeSet 可以将元素按照规则进行排序。

List 接口决定了它的子类都是有序、可存储重复元素的集合，常见的实现有 ArrayList，LinkedList，Vector

• ArrayList 使用数组实现，而 LinkedList 使用链表实现，所以它们两个的使用场景几乎是相反的，频繁查询的场景使用 ArrayList，而频繁插入删除的场景最好使用 LinkedList

• LinkedList 和 ArrayDeque 都可用于双端队列，而 Josh Bloch and Doug Lea 认为 ArrayDeque 具有比 LinkedList 更好的性能，ArrayDeque 使用数组实现双端队列，LinkedList 使用链表实现双端队列。

Queue 接口定义了队列的基本操作，子类集合都会拥有队列的特性：先进先出，主要实现有：LinkedList ，ArrayDeque

• PriorityQueue 底层使用二叉堆维护的优先级队列，而二叉堆是由数组实现的，它可以按照元素的优先级进行排序，优先级越高的元素，排在队列前面，优先被弹出处理。

Map 接口定义了该种集合类型是以 键值对形式保存，其主要实现有：HashMap，TreeMap，LinkedHashMap，Hashtable

• LinkedHashMap 底层多加了一条双向链表，设置 accessOrder 为 true 并重写方法则可以实现LRU缓存

• TreeMap 底层采用数组+红黑树实现，集合内的元素默认按照自然排序，也可以传入 Comparator 定制排序

看到这里非常不容易，感谢你愿意阅读我的文章，希望能对你有所帮助，你可以参考着文末总结的顺序，每当我提到一个集合时，回想它的重要知识点是什么，主要就是底层数据结构，线程安全性，该集合的一两个特有性质，只要能够回答出来个大概，我相信之后运用这些数据结构，你能够熟能生巧。

本文对整个集合体系的所有常用的集合类都分析了，这里并没有对集合内部的实现深入剖析，我想先从最宏观的角度让大家了解每个集合的的作用，应用场景，以及简单的对比，之后会抽时间对常见的集合进行源码剖析，尽情期待，感谢阅读！

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.bianchenghao6.com/h6javajc/25356.html