java集合图解【Java中的集合】 收藏 0

还不懂Java集合框架？看这一篇就够了

话不多说，直接上图：

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

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

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

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

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

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

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

先来看最上层的 Collection.

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

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

Create, Read, Update, and Delete.

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

下面具体来看：

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

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

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

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

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

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

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

• 判断集合是否为空：

• 集合的大小：

• 把集合转成数组：

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

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

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

那我们一个个来看。

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 更小，或者说内存使用更有效率。

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

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

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

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

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

来看 stack overflow 上的高票回答：

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

这个得看看源码：

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

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

再来看 Vector 的：

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

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

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

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

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

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

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

功能抛异常返回值增add(e)offer(e)删remove()poll()瞧element()peek()

为什么会抛异常呢？

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

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

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

那怎么选择呢？：

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

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

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

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

它们的实现类有这三个：

所以说，

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

我们一个个来看。

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

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

总结来说就是推荐使用 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 在语义上是 后进先出（LIFO） 的线性数据结构。

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

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

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

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

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

最后一个 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。

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

干货：Java集合框架综述

近被陆陆续续问了几遍HashMap的实现，回答的不好，打算复习复习JDK中的集合框架，并尝试分析其源码，这么做一方面是这些类非常实用，掌握其实现能更好的优化我们的程序；另一方面是学习借鉴JDK是如何实现了这么一套优雅高效的类库，提升编程能力。

在介绍具体适合类之前，本篇文章对Java中的集合框架做一个大致描述，从一个高的角度俯视这个框架，了解了这个框架的一些理念与约定，会大大帮助后面分析某个具体类，让我们开始吧。

集合框架（collections framework）

首先要明确，集合代表了一组对象（和数组一样，但数组长度不能变，而集合能）。Java中的集合框架定义了一套规范，用来表示、操作集合，使具体操作与实现细节解耦。

其实说白了，可以把一个集合看成一个微型数据库，操作不外乎“增删改查”四种操作，我们在学习使用一个具体的集合类时，需要把这四个操作的时空复杂度弄清楚了，基本上就可以说掌握这个类了。

设计理念

主要理念用一句话概括就是：提供一套“小而美”的API。API需要对程序员友好，增加新功能时能让程序员们快速上手。

为了保证核心接口足够小，最顶层的接口（也就是Collection与Map接口）并不会区分该集合是否可变（mutability）,是否可更改 （modifiability）,是否可改变大小（resizability）这些细微的差别。相反，一些操作是可选的，在实现时抛出UnsupportedOperationException即可表示集合不支持该操作。集合的实现者必须在文档中声明那些操作是不支持的。

为了保证最顶层的核心接口足够小，它们只能包含下面情况下的方法：

1. 基本操作，像之前说的“增删改查”

2. There is a compelling performance reason why an important implementation would want to override it.

此外，所有的集合类都必须能提供友好的交互操作，这包括没有继承Collection类的数组对象。因此，框架提供一套方法，让集合类与数组可以相互转化，并且可以把Map看作成集合。

两大基类Collection与Map

在集合框架的类继承体系中，最顶层有两个接口：

• Collection表示一组纯数据

• Map表示一组key-value对

一般继承自Collection或Map的集合类，会提供两个“标准”的构造函数：

• 没有参数的构造函数，创建一个空的集合类

• 有一个类型与基类（Collection或Map）相同的构造函数，创建一个与给定参数具有相同元素的新集合类

因为接口中不能包含构造函数，所以上面这两个构造函数的约定并不是强制性的，但是在目前的集合框架中，所有继承自Collection或Map的子类都遵循这一约定。

Collection

java-collection-hierarchy

如上图所示，Collection类主要有三个接口：

• Set表示不允许有重复元素的集合（A collection that contains no duplicate elements）

• List表示允许有重复元素的集合（An ordered collection (also known as a sequence)）

• Queue JDK1.5新增，与上面两个集合类主要是的区分在于Queue主要用于存储数据，而不是处理数据。（A collection designed for holding elements prior to processing.）

Map

MapClassHierarchy

Map并不是一个真正意义上的集合（are not true collections），但是这个接口提供了三种“集合视角”（collection views ），使得可以像操作集合一样操作它们，具体如下：

• 把map的内容看作key的集合（map’s contents to be viewed as a set of keys）

• 把map的内容看作value的集合（map’s contents to be viewed as a collection of values）

• 把map的内容看作key-value映射的集合（map’s contents to be viewed as a set of key-value mappings）

总结

今天先开个头，后面会陆陆续续来一系列干货，Stay Tuned。

需要说明一点，今后所有源码分析都将基于Oracle JDK 1.7.0_71，请知悉。

$ java -version

java version \”1.7.0_71\”

Java(TM) SE Runtime Environment (build 1.7.0_71-b14)

Java HotSpot(TM) 64-Bit Server VM (build 24.71-b01, mixed mode)

聚焦最新最前沿最有料的IT技术资讯

IT行业精华内容、产品交流心得

微信ID：weixin51cto

51CTO官方微信

长按二维码关注微互动

其他推荐：51CTO博客

如果你觉得文章还不错，帮我点个赞哦~

或者分享给更多的人^_^谢谢啦~

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com