复习一下 Java 集合框架

叁歲伎倆 2021-08-30 12:25 399阅读 0赞

话不多说，直接上图：

![format_png][]

Java 集合，也称作容器，主要是由`两大接口 (Interface)` 派生出来的：  
`Collection 和 Map`

顾名思义，容器就是用来存放数据的。

那么这两大接口的不同之处在于：

*  Collection 存放单一元素；
 *  Map 存放 key-value 键值对。

就是单身狗放 Collection 里面，couple 就放 Map 里。（所以你属于哪里？

学习这些集合框架，我认为有 4 个目标：

1.  明确每个接口和类的对应关系；
2.  对每个接口和类，熟悉常用的 API；
3.  对不同的场景，能够选择合适的数据结构并分析优缺点；
4.  学习源码的设计，面试要会答啊。

关于 Map，之前那篇 HashMap 的文章已经讲的非常透彻详尽了，所以本文不再赘述。如果还没看过那篇文章的小伙伴，快去公众号内回复「**HashMap**」看文章吧～

## Collection ##

先来看最上层的 Collection.

![format_png 1][]

Collection 里还定义了很多方法，这些方法也都会继承到各个子接口和实现类里，而这些 API 的使用也是日常工作和面试常见常考的，所以我们先来看下这些方法。

操作集合，无非就是「增删改查」四大类，也叫 `CRUD`:

> Create, Read, Update, and Delete.

那我也把这些 API 分为这四大类：

<table> 
 <thead> 
  <tr> 
   <th>功能</th> 
   <th>方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增</td> 
   <td>add()/addAll()</td> 
  </tr> 
  <tr> 
   <td>删</td> 
   <td>remove()/ removeAll()</td> 
  </tr> 
  <tr> 
   <td>改</td> 
   <td>Collection Interface 里没有</td> 
  </tr> 
  <tr> 
   <td>查</td> 
   <td>contains()/ containsAll()</td> 
  </tr> 
  <tr> 
   <td>其他</td> 
   <td>isEmpty()/size()/toArray()</td> 
  </tr> 
 </tbody> 
</table>

下面具体来看：

#### 增： ####

boolean add(E e);

`add()` 方法传入的数据类型必须是 Object，所以当写入基本数据类型的时候，会做自动装箱 auto-boxing 和自动拆箱 unboxing。

还有另外一个方法 `addAll()`，可以把另一个集合里的元素加到此集合中。

boolean addAll(Collection<? extends E> c);

#### 删： ####

boolean remove(Object o);

`remove()`是删除的指定元素。

那和 `addAll()` 对应的，  
自然就有`removeAll()`，就是把集合 B 中的所有元素都删掉。

boolean removeAll(Collection<?> c);

#### 改： ####

Collection Interface 里并没有直接改元素的操作，反正删和增就可以完成改了嘛！

#### 查： ####

*  查下集合中有没有某个特定的元素：

boolean contains(Object o);

*  查集合 A 是否包含了集合 B：

boolean containsAll(Collection<?> c);

#### 还有一些对集合整体的操作： ####

*  判断集合是否为空：

boolean isEmpty();

*  集合的大小：

int size();

*  把集合转成数组：

Object[] toArray();

以上就是 Collection 中常用的 API 了。

在接口里都定义好了，子类不要也得要。

当然子类也会做一些自己的实现，这样就有了不同的数据结构。

那我们一个个来看。

## List ##

![format_png 2][]

List 最大的特点就是：`有序`，`可重复`。

看官网说的：

> An ordered collection (also known as a sequence).

> Unlike sets, lists typically allow duplicate elements.

这一下把 Set 的特点也说出来了，和 List 完全相反，Set 是 `无序`，`不重复`的。

List 的实现方式有 LinkedList 和 ArrayList 两种，那面试时最常问的就是这两个数据结构如何选择。

对于这类选择问题：  
一是考虑数据结构是否能**完成需要的功能**；  
如果都能完成，二是考虑哪种**更高效**。

（万事都是如此啊。

那具体来看这两个 classes 的 API 和它们的时间复杂度：

<table> 
 <thead> 
  <tr> 
   <th>功能</th> 
   <th>方法</th> 
   <th>ArrayList</th> 
   <th>LinkedList</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增</td> 
   <td>add(E e)</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>增</td> 
   <td>add(int index, E e)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>删</td> 
   <td>remove(int index)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>删</td> 
   <td>remove(E e)</td> 
   <td>O(n)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>改</td> 
   <td>set(int index, E e)</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>查</td> 
   <td>get(int index)</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
 </tbody> 
</table>

稍微解释几个：

`add(E e)` 是在尾巴上加元素，虽然 ArrayList 可能会有扩容的情况出现，但是均摊复杂度（amortized time complexity）还是 O(1) 的。

`add(int index, E e)`是在特定的位置上加元素，LinkedList 需要先找到这个位置，再加上这个元素，虽然单纯的「加」这个动作是 O(1) 的，但是要找到这个位置还是 O(n) 的。（这个有的人就认为是 O(1)，和面试官解释清楚就行了，拒绝扛精。

`remove(int index)`是 remove 这个 index 上的元素，所以

*  ArrayList 找到这个元素的过程是 O(1)，但是 remove 之后，后续元素都要往前移动一位，所以均摊复杂度是 O(n)；
 *  LinkedList 也是要先找到这个 index，这个过程是 O(n) 的，所以整体也是 O(n)。

`remove(E e)`是 remove 见到的第一个这个元素，那么

*  ArrayList 要先找到这个元素，这个过程是 O(n)，然后移除后还要往前移一位，这个更是 O(n)，总的还是 O(n)；
 *  LinkedList 也是要先找，这个过程是 O(n)，然后移走，这个过程是 O(1)，总的是 O(n).

那造成时间复杂度的区别的原因是什么呢？

**答**：

*  因为 ArrayList 是用数组来实现的。
 *  而数组和链表的最大区别就是**数组是可以随机访问的（random access）**。

这个特点造成了在数组里可以通过下标用 O(1) 的时间拿到任何位置的数，而链表则做不到，只能从头开始逐个遍历。

也就是说在「改查」这两个功能上，因为数组能够随机访问，所以 ArrayList 的效率高。

那「增删」呢？

如果不考虑找到这个元素的时间，

数组因为物理上的连续性，当要增删元素时，在尾部还好，但是其他地方就会导致后续元素都要移动，所以效率较低；而链表则可以轻松的断开和下一个元素的连接，直接插入新元素或者移除旧元素。

但是呢，实际上你不能不考虑找到元素的时间啊。。。而且如果是在尾部操作，数据量大时 ArrayList 会更快的。

**所以说：**

1.  **改查选择 ArrayList；**
2.  **增删在尾部的选择 ArrayList；**
3.  **其他情况下，如果时间复杂度一样，推荐选择 ArrayList，因为 overhead 更小，或者说内存使用更有效率。**

### Vector ###

那作为 List 的最后一个知识点，我们来聊一下 Vector。这也是一个年龄暴露帖，用过的都是大佬。

那 Vector 和 ArrayList 一样，也是继承自 java.util.AbstractList，底层也是用数组来实现的。

但是现在已经被弃用了，因为...它加了太多的 synchronized！

任何好处都是有代价的，线程安全的成本就是效率低，在某些系统里很容易成为瓶颈，所以现在大家不再在数据结构的层面加 synchronized，而是把这个任务转移给我们程序员==

**那么面试常问题：Vector 和 ArrayList 的区别是什么，只答出来这个还还不太全面。**

来看 stack overflow 上的高票回答：

![format_png 3][]

> 一是刚才已经说过的线程安全问题；  
> 二是扩容时扩多少的区别。

这个得看看源码：

![format_png 4][]

这是 ArrayList 的扩容实现，这个**算术右移**操作是把这个数的二进制往右移动一位，最左边**补符号位**，但是因为容量没有负数，所以还是补 0.

那右移一位的效果就是除以 2，那么定义的新容量就是原容量的 **1.5 倍**。

再来看 Vector 的：

![format_png 5][]

因为通常 capacityIncrement 我们并不定义，所以默认情况下它是**扩容两倍**。

答出来这两点，就肯定没问题了。

## Queue & Deque ##

Queue 是一端进另一端出的线性数据结构；而 Deque 是两端都可以进出的。

![format_png 6][]

### Queue ###

Java 中的 这个 Queue 接口稍微有点坑，一般来说队列的语义都是**先进先出**（FIFO）的。

但是这里有个例外，就是 PriorityQueue，也叫 heap，并不按照进去的时间顺序出来，而是按照规定的优先级出去，并且它的操作并不是 O(1) 的，时间复杂度的计算稍微有点复杂，我们之后单独开一篇来讲。

那 Queue 的方法官网\[1\]都总结好了，它有两组 API，基本功能是一样的，但是呢：

*  一组是会抛异常的；
 *  另一组会返回一个特殊值。

<table> 
 <thead> 
  <tr> 
   <th>功能</th> 
   <th>抛异常</th> 
   <th>返回值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增</td> 
   <td>add(e)</td> 
   <td>offer(e)</td> 
  </tr> 
  <tr> 
   <td>删</td> 
   <td>remove()</td> 
   <td>poll()</td> 
  </tr> 
  <tr> 
   <td>瞧</td> 
   <td>element()</td> 
   <td>peek()</td> 
  </tr> 
 </tbody> 
</table>

**为什么会抛异常呢？**

*  比如队列空了，那 remove() 就会抛异常，但是 poll() 就返回 null；element() 就会抛异常，而 peek() 就返回 null 就好了。

**那 add(e) 怎么会抛异常呢？**

有些 Queue 它会有容量的限制，比如 **BlockingQueue**，那如果已经达到了它最大的容量且不会扩容的，就会抛异常；但如果 offer(e)，就会 return false.

**那怎么选择呢？：**

*  首先，要用就用**同一组 API**，前后要统一；
 *  其次，根据需求。如果你需要它抛异常，那就是用抛异常的；不过做算法题时基本不用，所以选那组返回特殊值的就好了。

### Deque ###

Deque 是两端都可以进出的，那自然是有针对 First 端的操作和对 Last 端的操作，那每端都有两组，一组抛异常，一组返回特殊值：

<table> 
 <thead> 
  <tr> 
   <th>功能</th> 
   <th>抛异常</th> 
   <th>返回值</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增</td> 
   <td>addFirst(e)/ addLast(e)</td> 
   <td>offerFirst(e)/ offerLast(e)</td> 
  </tr> 
  <tr> 
   <td>删</td> 
   <td>removeFirst()/ removeLast()</td> 
   <td>pollFirst()/ pollLast()</td> 
  </tr> 
  <tr> 
   <td>瞧</td> 
   <td>getFirst()/ getLast()</td> 
   <td>peekFirst()/ peekLast()</td> 
  </tr> 
 </tbody> 
</table>

使用时同理，要用就用同一组。

Queue 和 Deque 的这些 API 都是 O(1) 的时间复杂度，准确来说是均摊时间复杂度。

### 实现类 ###

它们的实现类有这三个：

![format_png 7][]

所以说，

*  如果想实现「普通队列 - 先进先出」的语义，就使用 LinkedList 或者 ArrayDeque 来实现；
 *  如果想实现「优先队列」的语义，就使用 PriorityQueue；
 *  如果想实现「栈」的语义，就使用 ArrayDeque。

我们一个个来看。

在实现普通队列时，**如何选择用 LinkedList 还是 ArrayDeque 呢？**

来看一下 StackOverflow\[2\] 上的高票回答：

![format_png 8][]

总结来说就是推荐使用 ArrayDeque，因为效率高，而 LinkedList 还会有其他的额外开销（overhead）。

**那 ArrayDeque 和 LinkedList 的区别有哪些呢？**

![format_png 9][]

还是在刚才的同一个问题下，这是我认为总结的最好的：

1.  ArrayDeque 是一个可扩容的数组，LinkedList 是链表结构；
2.  ArrayDeque 里不可以存 null 值，但是 LinkedList 可以；
3.  ArrayDeque 在操作头尾端的增删操作时更高效，但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的；
4.  ArrayDeque 在内存使用方面更高效。

所以，只要不是必须要存 null 值，就选择 ArrayDeque 吧！

**那如果是一个很资深的面试官问你，什么情况下你要选择用 LinkedList 呢？**

*  答：Java 6 以前。。。因为 ArrayDeque 在 Java 6 之后才有的。。

为了版本兼容的问题，实际工作中我们不得不做一些妥协。。

那最后一个问题，就是关于 Stack 了。

### Stack ###

Stack 在语义上是 **后进先出（LIFO）** 的线性数据结构。

有很多高频面试题都是要用到栈的，比如接水问题，虽然最优解是用双指针，但是用栈是最直观的解法也是需要了解的，之后有机会再专门写吧。

那在 Java 中是怎么实现栈的呢？

虽然 Java 中有 Stack 这个类，但是呢，官方文档都说不让用了！

![format_png 10][]

原因也很简单，因为 Vector 已经过被弃用了，而 Stack 是继承 Vector 的。

那么想实现 Stack 的语义，就用 ArrayDeque 吧：

Deque<Integer> stack = new ArrayDeque<>();

## Set ##

最后一个 Set，刚才已经说过了 Set 的特定是`无序`，`不重复`的。

就和数学里学的「集合」的概念一致。

![format_png 11][]

Set 的常用实现类有三个：

**HashSet**: 采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。

**LinkedHashSet**: 这个是一个 HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。

**TreeSet**: 采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。

那每个 Set 的**底层实现**其实就是对应的 Map：

**数值放在 map 中的 key 上，value 上放了个 PRESENT，是一个静态的 Object，相当于 place holder，每个 key 都指向这个 object。**

那么具体的**实现原理**、**增删改查**四种操作，以及**哈希冲突**、**hashCode()/equals()** 等问题都在 HashMap 那篇文章里讲过了，这里就不赘述了，没有看过的小伙伴可以在公众号后台回复「HashMap」获取文章哦～

## 总结 ##

![format_png][]

再回到开篇的这张图，有没有清楚了一些呢？

每个数据结构下面其实都有很多内容，比如 PriorityQueue 本文没有细说，因为这家伙一说又要半天。。

如果你觉得文章不错，文末的赞 ???? 又回来啦，**记得给我「点赞」和「在看」哦～**

最后呢，很多读者一直有问我交流群的问题，因为考虑到我有时差不方便管理，所以一直没做。

但现在我找了一个专业的管理员和我一起管理，所以「齐姐的秘密基地」正在筹备中，并且我会邀请国内外的一些大佬入场，给大家带来不一样的视角。

那么第一期交流群计划于 7 月中上旬开放，到时候我会在朋友圈发邀请，大家敬请期待！

### 参考资料 ###

\[1\]

Queue: *https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html*

\[2\]

ArrayDeque vs LinkedList: *https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist*

--------------------

\-END-

如果看到这里，说明你喜欢这篇文章，请 转发、点赞。同时 标星（置顶）本公众号可以第一时间接受到博文推送。

**推****荐****阅****读**

***1. ***[我用一根网线攻击了舍友！][Link 1]

***2. ***[为什么用了索引，查询还是慢？][Link 2]

***3.*** [从零开始写一个迷你版的Tomcat][Tomcat]

***4. ***[Spring Boot+Redis实现接口自动幂等][Spring Boot_Redis]

![format_png 12][]

最近整理一份面试资料**《Java技术栈学习手册》**，覆盖了Java技术、面试题精选、Spring全家桶、Nginx、SSM、微服务、数据库、数据结构、架构等等。

获取方式：点“ **在看**，关注公众号 **Java后端** 并回复 **777** 领取，更多内容陆续奉上。

喜欢文章，点个在看 ![format_png 13][]

[format_png]: /images/20210730/2a78da7119dd4ff88a88ee2145b2e7b4.png
[format_png 1]: /images/20210730/6728d0551ef545b199353cd5544ec04d.png
[format_png 2]: /images/20210730/c2945f0ec8b84b328644b420dc8b7c92.png
[format_png 3]: /images/20210730/661af374049b477d9dc8ddfd6242f26d.png
[format_png 4]: /images/20210730/dcd4d240d00342f68904f245a0e47885.png
[format_png 5]: /images/20210730/fa2b839928bd49b0856c38c6405eeeea.png
[format_png 6]: /images/20210730/a5ef7400c70447898249b3b5bff379cd.png
[format_png 7]: /images/20210730/96f6af7b03404ad298a8223f6f5ff082.png
[format_png 8]: /images/20210730/944718a6c19b4312a7126b56cee806b5.png
[format_png 9]: /images/20210730/14a227f9f25b4f5680c56e8c05dad02b.png
[format_png 10]: /images/20210730/12990dbe480b493f93a589bd2551b01b.png
[format_png 11]: /images/20210730/b16617769a6640a186be9f956fa02787.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=Mzg2MjEwMjI1Mg%3D%3D&chksm=ce0e50a4f979d9b2b675b7e53dcadca5d610b2617113d5316d74adf47164c8d153ed9260f69e&idx=1&mid=2247493415&scene=21&sn=7fec8a80f988e85755a5eee8a2ae5802#wechat_redirect
[Link 2]: https://blog.csdn.net/qq_37217713/article/details/105942268
[Tomcat]: https://blog.csdn.net/qq_37217713/article/details/105942269
[Spring Boot_Redis]: https://blog.csdn.net/qq_37217713/article/details/105926425
[format_png 12]: /images/20210730/e6dae5a985de434b996476e84efd7839.png
[format_png 13]: /images/20210730/8e50957977154d64940fab2c86ca9f18.png