【Java编程思想读后整理（干货版）】第十二章集合1-阿里云开发者社区

前言

这个系列记录我读完Java编程思想后整理的干货笔记。

为什么要整理呢？因为原著作者讲过于详细了，而且写得有点“随性”，往往是想到哪讲到哪。这对于新手的阅读就不太友好，因为你往往抓不住重点，文字会因为作者的笔风（加上英文翻译造成的语言习惯问题）而感到晦涩难懂。所以我把它讲的东西根据我的理解给整理出来，方便更多人的阅读和反复查阅。

PS：原文排版不行，行文组织上偏散，不利于新手阅读，所以我在原文基础上做了提炼，对其顺序进行了调整，对于一些晦涩难懂的地方根据自己的理解做了相应的修改和补充。相信阅读此文对于阅读原版Tinking in Java应该是有很大帮助的。

一、问题引入

通常，程序总是根据运行时才知道的某些条件去创建新的对象。在此之前，无法知道所需对象的数量甚至确切类型。为了解决这个普遍的编程问题，需要在任意时刻和任意位置创建任意数量的对象。因此，不能依靠创建命名的引用来持有每一个对象。

二、基本概念

Java集合类库采用“持有对象”（holding objects）的思想，并将其分为两个不同的概念，表示为类库的基本接口：

集合（Collection）：一个独立元素的序列，这些元素都服从一条或多条规则。List 必须以插入的顺序保存元素， Set 不能包含重复元素， Queue 按照排队规则来确定对象产生的顺序（通常与它们被插入的顺序相同）。

映射（Map）：一组成对的“键值对”对象，允许使用键来查找值。 ArrayList 使用数字来查找对象，因此在某种意义上讲，它是将数字和对象关联在一起。 map 允许我们使用一个对象来查找另一个对象，它也被称作关联数组（associative array），因为它将对象和其它对象关联在一起；或者称作字典（dictionary），因为可以使用一个键对象来查找值对象，就像在字典中使用单词查找定义一样。 Map 是强大的编程工具。

这显示了Java集合库中的两个主要类型。它们的区别在于集合中的每个“槽”（slot）保存的元素个数。 Collection 类型在每个槽中只能保存一个元素。此类集合包括： List ，它以特定的顺序保存一组元素； Set ，其中元素不允许重复； Queue ，只能在集合一端插入对象，并从另一端移除对象（就本例而言，这只是查看序列的另一种方式，因此并没有显示它）。 Map 在每个槽中存放了两个元素，即键和与之关联的值。

三、思路导图概览

为方便大家更好理解本文，我加了两张关于集合的uml继承关系图，而本文的组织也是根据这两张uml图来的。

去q1.png

可以看到，实际上只有四个基本的集合组件： Map ， List ， Set 和 Queue ，它们各有两到三个实现版本。

PS：上述继承结构看起来有些奇怪，实际上这是满足经常彼此之间互为牵制的各方面需求以及满足Java向后兼容的结果。

四、集合抽象类

我们可看到在重要的接口（比如Collection、List、Queue、Set、Map）下都有个相应的抽象类继承（如AbstractCollection、AbstractList…）。

这些类的意义就在于抽象，一方面是对于类库的抽象，方便类库的组织和编写，一方面是方便我们自己去实现相应的集合类，比如我想自己写个List类，而我又不想从头开始写那些共有的代码，那么我只需继承这个抽象类并实现相应的抽象方法即可。

五、集合（Collection）

1.列表List

List承诺将元素保存在特定的序列中。 List 接口在 Collection 的基础上添加了许多方法，允许在 List 的中间插入和删除元素。

有两种类型的 List ：

基本的 ArrayList ，擅长随机访问元素，但在 List 中间插入和删除元素时速度较慢。

LinkedList ，它通过代价较低的在 List 中间进行的插入和删除操作，提供了优化的顺序访问。 LinkedList 对于随机访问来说相对较慢，但它具有比 ArrayList 更大的特征集。

PS：原文并没有在这两种数据结构中进行进一步说明，也许是在后面章节讲，但我觉得在这里有必要简要说明一下这两者的原理实现，以下是我的补充。

ArrayList

基本原理

顾名思义，其实现原理就是内部维护了一个elementData数组，该类就是在其上进行一个封装。

扩容机制

我们知道数组一旦创建，其大小就已经固定，那么我们是如何实现扩容机制的呢？

设计者采用一种复制数组的方法来实现扩容的效果，通过阅读源码发现，扩容的操作在grow（）方法中

一般情况下，数组的大小是以3/2倍增长的。

常用方法封装

add(E x)

get(E x)

get(int index)

set(E x)

remove(E x)

size()

返回当前list中元素的个数，如果想要返回当前list的数组大小得通过反射获取elementData数组来实现。

…

LinkedList

基本原理

顾名思义，LinkedList是通过链表方式来实现的，它有个嵌套类Node，其实扮演链表中结点的角色

通过源码我们可以看到LinkedList在其内部维护了几个变量，分别是size、first、last

这样就可以实现链表的效果。

常用方法封装

这些通用方法两者都有，但是其内部实现截然不同

add(E x)

get(E x)

get(int index)

set(E x)

remove(E x)

size()

…

两者比较

查找效率

以get（int index）方法为例，

对于ArrayList而言，其内部实际是维护了个数组，如果我们知道其下标，那么我们可以直接从数组的对应位置拿到相应元素，而这个位置只需查找一次。

而对于LinkedList而言，内部是由一串链接在一起的Node组成，就像一串铁链，我们只知道头尾的结点，因此拿到下标我们只能通过不断next去达到相应的结点。

这样一比较，就可以明白ArrayList在查找效率上有着天然的优势。

插入删除效率

对于ArrayList而言，在内部数组足够大的情况下，插入一个元素到数组末尾并不是什么难事。但是一旦涉及到数组扩容，那么这个效率就有些不够看了，尤其是在数组已经特别大的时候。因为这涉及到数组复制，大量数据从一个数组复制到另一个数组。

PS：所以我们在平常使用过程中，在创建对象的时候，便给ArrayList一个初始化的大小，具体操作详见使用技巧部分。

同时，在数组中间插入一个元素我们还需先为这个元素“腾”出位置，然后再赋值达到插入的效果，而这个腾出位置的过程是通过数据后移（即后面的元素不断赋值到下一个位置）实现的，涉及数据的大量复制，效率可想而知。

尽管最后是调用本地内置的方法，但是效率也是大打折扣。

对于LinkedList而言，插入删除便简单了，对于末尾插入，它只需创建一个Node结点，再将这个Node结点挂到最后一个结点上就行了。所以这种情况下效率极高。

对于中间插入，比如add（int index，E element），

对于插入的过程确实快，但是在这个过程之前还有个查找的过程，而我们知道LinkedList的查找效率并不理想。

所以我们会看到一种奇怪的现象：不断向ArrayList和LinkedList中间插入数组，LinkedList耗时高于ArrayList。

测试结果如下：

我想原因就在于ArrayList中数据复制的过程调用本地方法，所以耗时上并没有我们想象的那么大，而LinkedList查找上耗时巨大，两相拉扯，就造成了这种结果。

结论

两者对于List的方法都有所实现，但是两者在数据存储和方法实现上截然不同。我们必须根据自己的需求去选择合适的实现。如果查找频繁，则选择ArrayList；如果插入删除频繁，则选择LinkedList；如果两者都频繁，那么根据自身情况作出选择，或者尽量从设计上避免这种情况的发生。

当然，在使用习惯上，如果没有特殊情况，我一般都会选择ArrayList。

2.集合Set

基本概念

Set 不保存重复的元素。如果试图将相同对象的多个实例添加到 Set 中，那么它会阻止这种重复行为。Set 最常见的用途是测试归属性，可以很轻松地询问某个对象是否在一个 Set 中。因此，查找通常是 Set 最重要的操作，因此通常会选择 HashSet 实现，该实现针对快速查找进行了优化。

实现类HashSet、TreeSet、EnumSet

通过继承关系图，我们可以看到其实现类有三个，分别是HashSet、TreeSet和EnumSet。

HashSet

HashSet 使用了散列，该实现针对快速查找进行了优化

事实上，该Set实现内部借助了HashMap，它只是针对Set做了进一步的封装。

正因为HashSet使用了散列，所以没有存储顺序，如果有存储顺序上的要求，则可以使用其他Set实现或者使用它的子类LinkedHashSet。

从源码中可以看到，如果使用LinkedHashSet，则原来的map会是LinkedHashMap对象，即LinkedHashSet维护一个遍历其所有条目的双向链接列表。此链表定义了迭代顺序，即将元素插入集合中的顺序。

TreeSet

TreeSet 将元素存储在红-黑树数据结构中，虽然查询速度没有HashSet那么快，但是它可以有存储顺序。

EnumSet

EnumSet 是一个专为枚举设计的集合类，EnumSet中的所有元素都必须是指定枚举类型的枚举值，该枚举类型在创建EnumSet时显式或隐式地指定。一般不常见，所以不过多介绍。

3.堆栈Stack

基本概念

堆栈是“后进先出”（LIFO）集合。它有时被称为叠加栈（pushdown stack），因为最后“压入”（push）栈的元素，第一个被“弹出”（pop）栈。经常用来类比栈的事物是带有弹簧支架的自助餐厅托盘。最后装入的托盘总是最先拿出来使用的。

Stack那些事

Java 1.0 中附带了一个 Stack 类，结果设计得很糟糕（为了向后兼容）。

Java 6 添加了 ArrayDeque ，它继承于Deque，其中包含直接实现堆栈功能的方法。

尽管已经有了 java.util.Stack ，但是 ArrayDeque 可以产生更好的 Stack ，因此更可取。

PS：事实上，LinkedList也能实现相应操作，只需将其向上转型为Queue接口类型实现“窄化”即可。

4.队列Queue

基本概念

队列是一个典型的“先进先出”（FIFO）集合。即从集合的一端放入事物，再从另一端去获取它们，事物放入集合的顺序和被取出的顺序是相同的。队列通常被当做一种可靠的将对象从程序的某个区域传输到另一个区域的途径。队列在并发编程中尤为重要，因为它们可以安全地将对象从一个任务传输到另一个任务。

如何创建Queue

LinkedList 实现了 Queue 接口，并且提供了一些方法以支持队列行为，因此 LinkedList 可以用作 Queue 的一种实现。通过将 LinkedList 向上转换为 Queue 。

事实上，队列Queue 接口只是窄化了对 LinkedList 方法的访问权限，因此只有适当的方法才能使用，能够访问到的 LinkedList 的方法会变少。

优先级队列PriorityQueue

先进先出（FIFO）描述了最典型的队列规则（queuing discipline）。队列规则是指在给定队列中的一组元素的情况下，确定下一个弹出队列的元素的规则。先进先出声明的是下一个弹出的元素应该是等待时间最长的元素。

优先级队列声明下一个弹出的元素是最需要的元素（具有最高的优先级）。

例如，在机场，当飞机临近起飞时，这架飞机的乘客可以在办理登机手续时排到队头。如果构建了一个消息传递系统，某些消息比其他消息更重要，应该尽快处理，而不管它们何时到达。

在Java 5 中添加了 PriorityQueue ，以便自动实现这种行为。

六、映射Map

PS：怎么说呢，这部分原文讲的很乱，没有讲到要点上，很难概括总结（也许是我功力不深），所以此部分我将结合网上优秀的博文结合上自己的理解对其做个总结。

基本概念

Map 提供了一个更通用的元素存储方法。Map 集合类用于存储元素对（称作“键”和“值”），其中每个键映射到一个值。

实现类HashMap

Map的实现类有五种（如果算上HashMap的子类LinkedHashMap的话，那么有六种）

由于其他Map实现类并不常见，这里就只简单介绍HashMap实现类。

基本原理

HashMap，顾名思义，该实现类使用hash散列算法实现。

HashMap的本质可以认为是一个数组，数组的每个索引被称为桶，每个桶里放着一个单链表，一个节点连着一个节点。很明显通过下标来检索数组元素时间复杂度为O(1)，而且遍历链表的时间复杂度是O(n)，所以在链表长度尽可能短的前提下，HashMap的查询复杂度接近O(1)。

使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket（桶）位置来储存Entry对象。HashMap是在bucket中储存键对象和值对象，作为Map.Entry。并不是仅仅只在bucket中存储值。

PS：详情请看HashMap原理深入理解，这篇讲的不错，有兴趣的朋友可以看看

使用方法

1.使用put(key, value)存储对象到HashMap中

2.使用get(key)从HashMap中获取对象

3.遍历方法

方法一使用For-Each迭代entries(推荐)

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue())
 }

方法二使用For-Each迭代keys和values（只需要用到map的keys或values时）

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
  Map.Entry<Integer, Integer> entry = entries.next();
  System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

方法三使用Iterator迭代

使用泛型

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
  Map.Entry<Integer, Integer> entry = entries.next();
  System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

不使用泛型

Map map = new HashMap();
Iterator entries = map.entrySet().iterator();
while (entries.hasNext()) {
  Map.Entry entry = (Map.Entry) entries.next();
  Integer key = (Integer)entry.getKey();
  Integer value = (Integer)entry.getValue();
  System.out.println("Key = " + key + ", Value = " + value);
 }

【Java编程思想读后整理（干货版）】第十二章集合1

一、问题引入

二、基本概念

三、思路导图概览

四、集合抽象类

五、集合（Collection）

1.列表List

2.集合Set

3.堆栈Stack

4.队列Queue

六、映射Map

热门文章

最新文章

相关课程

相关电子书

相关实验场景

【Java编程思想读后整理（干货版）】第十二章 集合1

一、问题引入

二、基本概念

三、思路导图概览

四、集合抽象类

五、集合（Collection）

1.列表List

2.集合Set

3.堆栈Stack

4.队列Queue

六、映射Map

热门文章

最新文章

相关课程

相关电子书

相关实验场景

【Java编程思想读后整理（干货版）】第十二章集合1