关于java:Java-集合看这一篇就够了

大家好，这里是《齐姐聊数据结构》系列之大汇合。

话不多说，间接上图：

Java 汇合，也称作容器，次要是由 两大接口 (Interface) 派生进去的：
Collection 和 Map

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

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

• Collection 寄存繁多元素；
• Map 寄存 key-value 键值对。

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

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

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

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

Collection

先来看最上层的 Collection.

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

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

Create, Read, Update, and Delete.

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

上面具体来看：

增：

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

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

看官网说的：

An ordered collection (also known as a sequence).

Unlike sets, lists typically allow duplicate elements.

这一下把 Set 的特点也说进去了，和 List 齐全相同，Set 是 无序 ， 不反复 的。

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

对于这类抉择问题：
一是思考数据结构是否能 实现须要的性能 ；
如果都能实现，二是思考哪种 更高效。

（万事都是如此啊。

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

略微解释几个：

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<E>，底层也是用数组来实现的。

然而当初曾经被弃用了，因为 … 它加了太多的 synchronized！

任何益处都是有代价的，线程平安的老本就是效率低，在某些零碎里很容易成为瓶颈，所以当初大家不再在数据结构的层面加 synchronized，而是把这个工作转移给咱们程序员 ==

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

来看 stack overflow 上的高票答复：

一是方才曾经说过的线程平安问题；
二是扩容时扩多少的区别。

这个得看看源码：

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

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

不理解这个右移操作符的小伙伴，公众号内回复「二进制」快温习一下吧～

再来看 Vector 的：

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

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

Queue & Deque

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

Queue

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

然而这里有个例外，就是 PriorityQueue，也叫 heap，并不依照进去的工夫程序进去，而是依照规定的优先级进来，并且它的操作并不是 O(1) 的，工夫复杂度的计算略微有点简单，咱们之后独自开一篇来讲。

那 Queue 的办法官网都总结好了，它有两组 API，基本功能是一样的，然而呢：

• 一组是会抛异样的；
• 另一组会返回一个非凡值。

为什么会抛异样呢？

• 比方队列空了，那 remove() 就会抛异样，然而 poll() 就返回 null；element() 就会抛异样，而 peek() 就返回 null 就好了。

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

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

那怎么抉择呢？：

• 首先，要用就用 同一组 API，前后要对立；
• 其次，依据需要。如果你须要它抛异样，那就是用抛异样的；不过做算法题时根本不必，所以选那组返回非凡值的就好了。

Deque

Deque 是两端都能够进出的，那天然是有针对 First 端的操作和对 Last 端的操作，那每端都有两组，一组抛异样，一组返回非凡值：

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

Queue 和 Deque 的这些 API 都是 O(1) 的工夫复杂度，精确来说是均摊工夫复杂度。

实现类

它们的实现类有这三个：

所以说，

• 如果想实现「一般队列 – 先进先出」的语义，就应用 LinkedList 或者 ArrayDeque 来实现；
• 如果想实现「优先队列」的语义，就应用 PriorityQueue；
• 如果想实现「栈」的语义，就应用 ArrayDeque。

咱们一个个来看。

在实现一般队列时，如何抉择用 LinkedList 还是 ArrayDeque 呢？

来看一下 StackOverflow 上的高票答复：

总结来说就是举荐应用 ArrayDeque，因为效率高，而 LinkedList 还会有其余的额定开销（overhead）。

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

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

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 这个类，然而呢，官网文档都说不让用了！

起因也很简略，因为 Vector 曾经过被弃用了，而 Stack 是继承 Vector 的。

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

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

Set

最初一个 Set，方才曾经说过了 Set 的特定是 无序 ， 不反复 的。

就和数学里学的「汇合」的概念统一。

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」获取文章哦～

总结

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

每个数据结构上面其实都有很多内容，比方 PriorityQueue 也就是堆，齐姐之前也专门写过文章解说它的相干操作，比方很有名的 heapify() 的过程为什么是 O(n) 的等面试常问题，感兴趣的小伙伴在公众号后盾回复「堆」获取文章吧～

如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！

我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！

更多干货文章见我的 Github: https://github.com/xiaoqi6666…