面试问答

• 1: 数据结构
• 1.1: CH01-数组/链表
• 1.2: CH02-哈希表
• 1.3: CH03-树/二叉树
• 1.4: CH04-排序二叉树
• 1.5: CH05-平衡二叉树
• 1.6: CH06-红黑树
• 1.7: CH07-哈夫曼树
• 1.8: CH08-前缀树
• 1.9: CH09-图概念
• 1.10: CH10-图遍历
• 1.11: CH11-最小生成树
• 1.12: CH12-图最短路径
• 1.13: CH13-图拓扑排序
• 1.14: CH14-图-AOE-关键路径
• 1.15: CH15-Iterable
• 1.16: CH16-Collection
• 1.17: CH17-List
• 1.18: CH18-ArrayList
• 1.19: CH19-Queue
• 1.20: CH20-Deque
• 1.21: CH21-ArrayQueue
• 1.22: CH22-PriorityQueue
• 1.23: CH23-LinkedList
• 1.24: CH24-Vector
• 1.25: CH25-Stack
• 1.26: CH26-Map
• 1.27: CH27-SortedMap
• 1.28: CH28-NavigableMap
• 1.29: CH29-TreeMap
• 1.30: CH30-HashMap
• 1.31: CH31-LinkedHashMap
• 1.32: CH32-EnumMap
• 1.33: CH33-HashTable
• 1.34: CH34-Set
• 1.35: CH35-EnumSet
• 1.36: CH36-HashSet
• 1.37: CH37-LinkedHashSet
• 1.38: CH38-TreeSet
• 1.39: CH39-FailFast
• 2: 排序算法
• 2.1: CH01-冒泡排序
• 2.2: CH02-选择排序
• 2.3: CH03-插入排序
• 2.4: CH04-希尔排序
• 2.5: CH05-归并排序
• 2.6: CH06-快速排序
• 2.7: CH07-堆排序
• 2.8: CH08-计数排序
• 2.9: CH09-桶排序
• 2.10: CH10-基数排序
• 3: 剑指 Offer
• 4: 面试宝典
• 5: 面试金典
• 6: 面试指南
• 7: Leet Code

1 - 数据结构

1.1 - CH01-数组/链表

数组和链表是数据结构中最基本的部分，也是其余众多数据结构的基础。即使在 Java 中，这两种结构使用的也很普遍。这里我们会先对它们进行简要分析。

数组

在java中，数组定义为一种基本类型，其可以通过下标获取到对应位置的数据。其在内存中的存放结构如下：

正如上图所示，数组在内存中是一段连续的存储单元，每个数据依次放在每个单元中。分析这种结构，我们可以得出以下几个结论：

• 创建一个数组，必须声明其长度，以在内存中寻找合适的一段连续存储单元。这也意味着数组的大小是固定的，我们无法动态调整其大小。
• 想要获取数组中第i个元素，其时间复杂度是 O(1)，因为可以根据其地址直接找到它。同理修改也是。
• 数组对查询表现一般，要想查找一个元素，需要遍历，时间复杂度为O(n)。
• 因为地址连续，想要在数组中插入一个元素是复杂的，因为从插入位置起，后边的所有元素都需要向后移动一位。同理删除也是，只是移动方向为向前。并且，当数组存满时，就无法继续插入了。
• 因为数组要占据一整块内存，有可能产生许多的碎片，也可能因为找不到合适的内存块，而导致存储失败。

链表

链表是一种离散存储结构，其在内存中存储不是连续的，每个数据元素都通过一个指针指向其下一个元素的地址。根据指针域的不同，链表又分为单链表、双向链表、循环链表等，这里我们只分析单链表。示意图如下所示：

分析这种结构，我们可以得出以下几个结论：

• 声明一个链表时，不需要知道其长度，也不需要连续的内存块，所以其大小可以动态调整。
• 链表的每个元素都分为数据域和指针域，前者是实际存储的数据，后者则指向下一个元素的地址。和数组相比，每个元素需要占用的内存更大了。
• 要获取链表的第 i 个元素变得复杂，因为其地址存放在它上一个元素的指针域里，所以只能从第一个元素起，进行 i 次操作。同理修改也是。
• 链表对查询表现也一般，需要遍历，时间复杂度为O(n)。
• 增加与删除一个元素更方便了，因为没有对内存地址的限制，我们只需要在对应节点合理处理下指针域的值，就可以把一个元素插入链表或者从链表删除。
• 链表对内存的要求很小，只要能够存储下一个数据元素的内存块都可以使用，因此不会造成碎片化。

总结起来就是：大小可以动态调整，增删迅速，查找较慢，数据元素所占内存略多，不需要整块内存块，不会造成碎片化。

如何选择

通过以上分析，数组和链表对我们影响最大的几点区别在于：

• 数组按位置查找迅速，链表增删方便。
• 数组是固定大小，链表可以随时扩充与缩减。
• 链表每个元素占据内存略多于数组。
• 数组和链表在查询方面表现都比较一般，耗时较长。

在数据量很小，内容基本固定时，我们选择何种数据结构的影响并不大。但当数据量较大时，如果我们需要对数据进行频繁的插入删除，我们应该选择链表，如果我们需要频繁的获取某个位置的元素，我们应该选择数组。数组与链表并没有明确的优劣之分，根据不同的使用场景进行不同的选择，才是这两种结构使用的最佳方式。

1.2 - CH02-哈希表

无论是数组还是链表，其对数据的查询表现都比较无力，要想知道一个元素是否在数组或链表中，只能从前向后挨个对比。出现这个问题的根源在于，我们没有办法直接根据一个元素找到它存储的位置，那有没有办法消除这个对比的过程呢？

哈希表就是解决查询问题的一种方案。在后续将会分析的二叉排序树中，还会将数据排序以进行二分查找，将时间复杂度从 O(n) 降低到 O(lg n)。

哈希表与 hash 函数

通俗来讲，哈希表就是通过关键字来获取数据的一种数据结构，它通过把关键字映射为表中的位置来获取元素，这种映射主要是使用 Hash 函数。

Hash 函数，实际上是建立起 key 值与 int 值映射关系的函数。这就好比我们每个人都有一个身份证号一样，无论是男是女，出生在何处，都可以通过身份证号来分辨，这就是把人的信息映射成一串数字的典型做法。Hash 函数和此类似，不过是把任意的 Java 对象，映射成一个 int 数值，供哈希表使用。

而哈希表，就是一个数组，只是其元素不是按照数组的规则排列的。任何一个元素要放进哈希表中，都必须先通过 Hash 函数获取到一个 int 数值，这个数值经过处理后将作为它的存放位置，然后这个元素才能放进哈希表中。

可以发现，数组与哈希表的操作不同之处主要在于，前者是直接插入，后者需要通过 Hash 函数计算后再插入。可以通过下图对比来理解：

哈希表完全继承了数组的优点，又显著的提高了查询的速度，通过 Hash 函数使得查询速度达到了 O(1)。既然有了哈希表，它这么优秀，为何还需要数组的存在呢？那是因为 Hash 表是有缺陷的，这个缺陷就是哈希碰撞。

哈希碰撞

Hash 函数所做的事，就是无论什么对象，都根据一个规则映射为一个 int 值。被转换的对象有无数种可能，但是 int 的值是有限的，它只有 2^32 个，这样一来，必然会有不同的对象，映射得到相同的 int 值，这就是所谓的哈希碰撞。发生碰撞之后，就要把不同的元素插入到相同的位置，这时候单纯的使用一维数组已经无法满足需求了。

解决哈希碰撞

要解决哈希碰撞，我们可以想到多种解决方案。例如使用二维数组，将碰撞的元素按顺序存储起来，类似下图：

这样的方式有一个很大的诟病，因为数组大小是固定的，所以第二维的数组长度都是一样的，但是哈希碰撞一定是比较少发生的情况，也就是我们声明了一个很大的数组，但是其中大部分都是闲置的，这就浪费了大量的内存。

还有一些方案是考虑了哈希表的散列化，将元素插入到空闲的位置去。因为哈希表基本不会像数组一样每个位置都有元素，这样就可以将碰撞的元素插入到这些空闲的位置中区，这种方案称为定址法。但是这个方法在扩展性上表现不佳，我们这里就不再浪费篇幅来解释它了。

目前比较通用的方法，就是使用数组+链表组合的方式。当出现哈希碰撞时，在该位置的数据就通过链表的方式链接起来，如下图所示：

这是当前比较理想的方法，既继承了数组的优点，又在碰撞时继承了链表的优点，这也是哈希表强大的地方之一。

在 JDK1.7 及之前的版本中，HashMap 的存储结构和上图是一致的，在 JDK1.8 之后还加入了红黑树以进一步优化，在后续文章中我们会对其进行详尽的分析。

哈希表的优缺点

哈希表是一种优化存储的思想，具体存储元素的依然是其他的数据结构。设计良好的哈希表，能同时兼备数组和链表的优点，它能在插入和查找时都具备良好的性能。然而设计不好的哈希表，有可能会出现较多的哈希碰撞，导致链表过长，从而哈希表会更像一个链表。还有当数据量很大时，为防止链表过长，就需要对数组进行扩容，这时就涉及到了数组的拷贝，其对性能的影响也很严重，所以需要提前对可能的情况有良好的预测，才能真正发挥哈希表的优势。

1.3 - CH03-树/二叉树

数组和链表都是用来解决一对一问题的，而一对多问题则需要树来解决。这里，我们重点关注二叉排序树，所以只会介绍一些必需了解的概念，关于树的更多知识，大家可以查看相关书籍进行系统的学习。

树的定义

树(Tree)是 n(n≥0) 个结点的有限集。n=0 时称为空树。在任意一棵非空树中:

1. 有且仅有一个特定的称为根(Root)的结点；
2. 当 n>1 时，其余结点可分为 m(m>0) 个互不相交的有限集 T1 、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

如下图：

与现实中的树不同，数据结构里的树的根在最上方，并且只有一个根，就像一棵倒置的树。树的每个结点往下都是一棵子树，且这些子树不能相交，如下所示就不是一棵正确的树：

相关概念

节点分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree) 。度为 0 的结点称为叶结点(Leaf) 或终端结点；度不为 0 的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

如下图所示，A 结点为根节点，G、H、I、J、F 为叶节点，其余节点则为内部节点，此树的度为 3。

节点间的关系

结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

深度

结点的层次(LeveI)从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第 L 层，则其子树的根就在第 L+1 层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度。

有序树，无序树

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

二叉树

二叉树(Binary Tree)是n(n ≥ 0) 个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

下图就是一个二叉树，二叉树就是每个结点的度≤2的树。

二叉树遍历

二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次旦仅被访问一次。

前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树， 再前序遍历右子树。

如下图所示，遍历结果为：ABDGHCEIF。

中序遍历

规则是若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点) ，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

如下图所示，遍历结果为：GDHBAEICF。

后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

如下图所示，遍历结果为：GHDBIEFCA。

1.4 - CH04-排序二叉树

解决查询速度慢的方案除了哈希表外，还可以使用二叉排序树。我们知道，查询慢主要是因为不知道元素的位置，使用 hash 函数映射虽然解决了问题，但其并不稳定，当出现大量的哈希碰撞后其表现更像一个链表，查询速度大大降低。

二叉排序树的方案则是使元素有序，这样便可以使用二分法进行查找了，虽然效率相比 hash 函数低一些，但可以通过 AVL 树、红黑树等增加稳定性。

HashMap 在 JDK1.8 的实现中，就结合了哈希表的高效和红黑树的稳定，我们之后会详细分析其实现。

定义

二叉排序树(Binary Sort Tree)，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
• 它的左、右子树也分别为二叉排序树。

如下就是一棵简单的二叉排序树：

当对这棵树进行中序遍历时，其结果将按照从小到大排序。

查询操作

二叉排序树的查找时间复杂度为 O(lg n)，查找使用二分法。要在上图中找到元素 37，只需要四次操作即可。

首先，找到根元素22，37比22大，所以淘汰左子树，再找到35，淘汰左子树，再找到41，进入左子树，得到37。可以看到其速度比挨个对比高了很多。

插入操作

二叉排序树的插入操作和查询类似，也需要通过二分法进行查找，找到合适的位置再插入元素，所以其插入速度相比链表较慢。

删除操作

从二叉排序树中删除一个元素主要分为三种情况。

例如要从下面这个二叉排序树中删除一个元素：

1. 删除的元素是叶结点，这时可以直接删除它。比如要删除值为 1 的元素，删除它对树没有任何影响。
2. 删除的元素仅有左孩子或者仅有右孩子时，直接让其孩子顶替它即可。比如要删除元素 35，只需要用 41 顶替它即可。
3. 删除的元素既有左孩子又有右孩子，这时删除它相对复杂。一种好的方式是找到它的前驱或者后继来代替它。比如要删除元素 9，就用 6 或者 13 代替它即可。

问题

一棵普通的二叉排序树也会出现不平衡问题，如果插入的数据都在树的一侧，就会使得树的深度迅速增大，每次二分查找可以排除的数据很少，从而查询速度严重下降，比如下方这棵树：

要查找值为 2 的元素，使用二分法和使用链表速度差不多。为了解决这种问题，就需要在元素插入时即进行修正，后续介绍的AVL树和红黑树就是两种不同的解决方案。

1.5 - CH05-平衡二叉树

二叉排序树很好的平衡了插入与查找的效率，但不平衡的二叉排序树效率大打折扣。今天介绍的 AVL 树就是一种解决此问题的方案。

定义

平衡二叉树(Self-Balancing Binary Search Tree 或Height-Balanced Binary Search Tree)，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于 1 。它是一种高度平衡的二叉排序树。意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1 。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子 BF(Balance Factor)，那么平衡二叉树上所有结点的平衡因子只可能是 -1 、0 和 1。

如下图就不是一棵AVL树，因为结点18的左子树高度为2，右子树高度为0，高度差大于1。

但通过一定的步骤调整之后，可以将其转为一棵平衡二叉树，如下图：

实现原理

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。最小不平衡子树是指距离插入结点最近的，且平衡因子的绝对值大于 1 的结点为根的子树。

下面通过一个实例，了解平衡二叉树的构建过程。

假如我们要将数组 int[] a = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8} 构建成一棵二叉排序树，如果直接按照二叉排序树的定义，会得到下面的结果：

这样的结果对查找是十分不利的，树的高度达到了 8，而且大多数只有一个孩子。所以我们需要一些操作，将它变成一棵 AVL 树。

首先，插入元素3和2时，没有什么影响，此时3的平衡因子为1，2的平衡因子为0，结果如下：

现在，要把1插入树中，这时结果如下所示：

此时3的平衡因子为2了，不再符合平衡二叉树的规则。此时，整棵树就是最小不平衡子树，我们将其右旋：

再插入4，也不会影响平衡，结果如下：

此时，插入元素5，以3为根结点的子树成为了最小不平衡子树，如下所示：

现在要对其进行左旋：

现在继续插入元素6，此时以2为根结点的右子树为最小不平衡子树，结果如下：

这时再次需要对其进行左旋，这次旋转后要将4的左孩子变为2的右孩子，以满足二叉排序树的定义，如下所示：

再插入7时，情况和之前有些类似了，结果如下：

左旋后结果如下：

现在，继续插入10，此时无需调整，结果如下：

下一步，插入元素9，此时结果如下：

按照之前的经验，这时我们应该进行左旋了，但是左旋之后9将变为10的右孩子，这会不符合二叉排序树的定义。和之前不同的是，7和10的平衡因子符号相反，这是造成这一结果的原因。这种情况下，要先以10为根节点右旋，再进行左旋，结果如下所示：

最后插入元素8，如下所示：

此时情况和上述类似，6是最小不平衡子树的根结点，9和6的平衡因子符号相反，所以先以9为根结点右旋：

然后再以6左旋：

可以看到，此树的高度仅为4，与之前的8相差很多，性能自然也好很多。

平衡二叉树的删除操作与插入类似，这里将不再介绍。大家可以自己思考如何最高效地删除元素，可以分叶结点、仅有一个子结点和有两个子结点三种情况考虑，这里还用到了递归的思想。

接下来我们将介绍另一种实现方式，红黑树。

1.6 - CH06-红黑树

红黑树和AVL树的思想是类似的，都是在插入过程中对二叉排序树进行调整，从而提升性能，它的增删改查均可以在 O(lg n) 内完成。

定义

红黑树是一棵二叉排序树。且满足以下特点：

• 每个节点或者是黑色，或者是红色。
• 根节点是黑色。
• 每个叶子节点（NIL）是黑色。(注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！)
• 如果一个节点是红色的，则它的两个儿子都是黑色的。
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

示例中每个结点最后都是一个 NIL 结点，它是黑色的，不过我们画图时通常会省略它。所以下文以及后续文章中绘制时都会省略NIL结点，大家记得还有它就可以。

实现原理

红黑树的插入与删除和AVL树类似，也是每插入一个结点，都检查是否破坏了树的结构，然后进行调整。红黑树每个结点插入时默认都为红色，这样做可以降低黑高，也可以减少调整的次数。

插入元素

红黑树的概念理解起来较为复杂，我们以一个简单的示例，看看如何构造一棵红黑树。

现有数组 int[] a = {1, 10, 9, 2, 3, 8, 7, 4, 5, 6}; 我们要将其变为一棵红黑树。

首先插入1，此时树是空的，1就是根结点，根结点是黑色的：

然后插入元素10，此时依然符合规则，结果如下：

当插入元素9时，这时是需要调整的第一种情况，结果如下：

红黑树规则4中强调不能有两个相邻的红色结点，所以此时我们需要对其进行调整。调整的原则有多个相关因素，这里的情况是，父结点10是其祖父结点1（父结点的父结点）的右孩子，当前结点9是其父结点10的左孩子，且没有叔叔结点（父结点的兄弟结点），此时需要进行两次旋转，第一次，以父结点10右旋：

然后将父结点（此时是9）染为黑色，祖父结点1染为红色，如下所示：

然后以祖父结点1左旋：

下一步，插入元素2，结果如下：

此时情况与上一步类似，区别在于父结点1是祖父结点9的左孩子，当前结点2是父结点的右孩子，且叔叔结点10是红色的。这时需要先将叔叔结点10染为黑色，再进行下一步操作，具体做法是将父结点1和叔叔结点10染为黑色，祖父结点9染为红色，如下所示：

由于结点9是根节点，必须为黑色，将它染为黑色即可：

下一步，插入元素3，如下所示：

这和我们之前插入元素10的情况一模一样，需要将父结点2染为黑色，祖父结点1染为红色，如下所示：

然后左旋：

下一步，插入元素8，结果如下：

此时和插入元素2有些类似，区别在于父结点3是右孩子，当前结点8也是右孩子，这时也需要先将叔叔结点1染为黑色，具体操作是先将1和3染为黑色，再将祖父结点2染为红色，如下所示：

此时树已经平衡了，不需要再进行其他操作了，现在插入元素7，如下所示：

这时和之前插入元素9时一模一样了，先将7和8右旋，如下所示：

然后将7染为黑色，3染为红色，再进行左旋，结果如下：

下一步要插入的元素是4，结果如下：

这里和插入元素2是类似的，先将3和8染为黑色，7染为红色，如下所示：

但此时2和7相邻且颜色均为红色，我们需要对它们继续进行调整。这时情况变为了父结点2为红色，叔叔结点10为黑色，且2为左孩子，7为右孩子，这时需要以2左旋。这时左旋与之前不同的地方在于结点7旋转完成后将有三个孩子，结果类似于下图：

这种情况处理起来也很简单，只需要把7原来的左孩子3，变成2的右孩子即可，结果如下：

然后再把2的父结点7染为黑色，祖父结点9染为红色。结果如下所示：

此时又需要右旋了，我们要以9右旋，右旋完成后7又有三个孩子，这种情况和上述是对称的，我们把7原有的右孩子8，变成9的左孩子即可，如下所示：

下一个要插入的元素是5，插入后如下所示：

有了上述一些操作，处理5变得十分简单，将3染为红色，4染为黑色，然后左旋，结果如下所示：

最后插入元素6，如下所示：

又是叔叔结点3为红色的情况，这种情况我们处理过多次了，首先将3和5染为黑色，4染为红色，结果如下：

此时问题向上传递到了元素4，我们看2、4、7、9的颜色和位置关系，这种情况我们也处理过，先将2和9染为黑色，7染为红色，结果如下：

最后7是根结点，染为黑色即可，最终结果如下所示：

插入总结

可以看到，在插入元素时，叔叔结点是主要影响因素，待插入结点与父结点的关系决定了是否需要多次旋转。可以总结为以下几种情况：

• 如果父结点是黑色，插入即可，无需调整。
• 如果叔叔结点是红色，就把父结点和叔叔结点都转为黑色，祖父结点转为红色，将不平衡向上传递。
• 如果叔叔结点是黑色或者没有叔叔结点，就看父结点和待插入结点的关系。如果待插入结点和父结点的关系，与父结点与祖父结点的关系一致，比如待插入结点是父结点的左孩子，父结点也是祖父结点的左孩子，就无需多次旋转。否则就先通过相应的旋转将其关系变为一致。

删除元素

要从一棵红黑树中删除一个元素，主要分为三种情况。

情况-1：待删除元素没有孩子

没有孩子指的是没有值不为NIL的孩子。这种情况下，如果删除的元素是红色的，可以直接删除，如果删除的元素是黑色的，就需要进行调整了。

例如我们从下图中删除元素1：

删除元素1后，2的左孩子为NIL，这条支路上的黑色结点数就比其他支路少了，所以需要进行调整。

这时，我们的关注点从叔叔结点转到兄弟结点，也就是结点4，此时4是红色的，就把它染为黑色，把父结点2染为红色，如下所示：

然后以2左旋，结果如下：

此时兄弟结点为3，且它没有红色的孩子，这时只需要把它染为红色，父结点2染为黑色即可。结果如下所示：

情况-2：待删除元素有一个孩子

这应该是删除操作中最简单的一种情况了，根据红黑树的定义，我们可以推测，如果一个元素仅有一个孩子，那么这个元素一定是黑色的，而且其孩子是红色的。

假设我们有一个红色节点，它是树中的某一个节点，且仅有一个孩子，那么根据红色节点不能相邻的条件，它的孩子一定是黑色的，如下所示：

但这个子树的黑高却不再平衡了（注意每个节点的叶节点都是一个NIL节点），因此红色节点不可能只有一个孩子。

而若是一个黑色节点仅有一个孩子，如果其孩子是黑色的，同样会打破黑高的平衡，所以其孩子只能是红色的，如下所示：

只有这一种情况符合红黑树的定义，这时要删除这个元素，只需要使用其孩子代替它，仅代替值而不代替颜色即可，上图的情况删除完后变为：

可以看到，树的黑高并没有发生变化，因此也不需要进行调整。

情况-3：待删除元素有两个孩子

我们在讨论二叉排序树时说过，如果删除一个有两个孩子的元素，可以使用它的前驱或者后继结点代替它。因为它的前驱或者后继结点最多只会有一个孩子，所以这种情况可以转为情况1或情况2处理。

删除总结

删除元素最复杂的是情况1，这主要由其兄弟结点以及兄弟结点的孩子颜色共同决定。这里简要做下总结。

我们以N代表当前待删除节点，以P代表父结点，以S代表兄弟结点，以SL代表兄弟结点的左孩子，SR代表兄弟结点的右孩子，如下所示：

根据红黑树定义，这种情况下S要么有红色的子结点，要么只有NIL结点，以下对S有黑色结点的情况均表示NIL。

主要有以下几种：

1. S是红色，P一定是黑色，S也不会有红色的孩子，如下：

此时把P和S颜色变换，再左旋，如下：

这样变换后，N支路上的黑色结点并没有增加，所以依然少一个，

2. P，S以及S的全部孩子都是黑色。

无论S有几个孩子，或者没有孩子，只要不是红色都是这种情况，此时情况如下：

我们把S染为红色，这样一来，N和S两个支路都少了一个黑色结点，所以可以把问题向父结点转移，通过递归解决。染色后如下：

3. P为红（S一定为黑），S的孩子都为黑。

这种情况最为简单，只需要把P和S颜色交换即可。这样N支路多了一个黑色元素，而S支路没有减少，所以达到了平衡。

4. P任意色，S为黑，N是P的左孩子，S的右孩子SR为红，S的左孩子任意。

如下所示：

此时将S改为P的颜色，SR和P改为黑色，然后左旋，结果如下：

可以发现，此时N支路多了一个黑色结点，而其余支路均没有收到影响，所以调整完毕。

5. P任意色，S为黑，N是P的左孩子，S的左孩子SL为红，S的右孩子SR为黑，如下所示：

此时变换S和SL的颜色，然后右旋，结果如下：

这时，所有分支的黑色结点数均没有改变，但情况5转为了情况4，再进行一次操作即可。

还有一些情况与上述是对称的，我们进行相应的转换即可。

总结

红黑树的操作比较复杂，插入元素可能需要多次变色与旋转，删除也是。这些操作的目的都是为了保证红黑树的结构不被破坏。这些复杂的插入与删除操作希望大家可以亲手尝试一下，以加深理解。

红黑树是 JDK 中 TreeMap、TreeSet 的底层数据结构，在 JDK1.8 中HashMap也用到了红黑树，所以掌握它对我们后续的分析十分重要。

• 关于红黑树与AVL树的区别？
• 为何选用红黑树？

1.7 - CH07-哈夫曼树

相关名词

先看一棵哈夫曼树: (哈夫曼树推理是通过叶子节点，所以理解的时候需要忽略非叶子节点，很多文章在这点上有误导)：

• 路径与路径长度：从树中一个节点到另一个节点之间的分支构成了两个节点之间的路径，路径上的分支数目称作路径长度。若规定根节点位于第一层，则根节点到第H层的节点的路径长度为H-1。如到40 的路径长度为1；30的路径长度为2；20的路径长度为3。
• 节点的权：将树中的节点赋予一个某种含义的数值作为该节点的权值，该值称为节点的权；
• 带权路径长度：从根节点到某个节点之间的路径长度与该节点的权的乘积。例如上图节点10的路径长度为3,它的带权路径长度为 10 * 3 = 30。
• 树的带权路径长度：树的带权路径长度为所有叶子节点的带权路径长度之和，称为WPL。上图的WPL = 1x40+2x30+3x10+3x20 = 190，而哈夫曼树就是树的带权路径最小的二叉树。

哈夫曼树的构建

假设 n 个权值，则构造出的哈夫曼树有 n 个叶子节点。n 个权值分别设为 w1、w2、…、wn，哈夫曼树的构造规则为：

• 将w1、w2、…，wn看成是有 n 棵树的森林(每棵树仅有一个结点)；
• 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
• 从森林中删除选取的两棵树，并将新树加入森林；
• 重复上面两步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

上图中，它的叶子节点为 10、20、30、40，以这四个权值来构建哈夫曼树的过程为：

哈夫曼编码

为{10，20，30，40}这四个权值构建了哈夫曼编码后，我们可以由如下规则获得它们的哈夫曼编码:

从根节点到每一个叶子节点的路径上，左分支记为0，右分支记为1，将这些0与1连起来即为叶子节点的哈夫曼编码。如下图:

由此可见，出现频率越高的字母(也即权值越大)，其编码越短。这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

具体流程如下:

哈夫曼树的实现

哈夫曼树的重点是如何构造哈夫曼树。本文构造哈夫曼时，用到了"(二叉堆)最小堆"。下面对哈夫曼树进行讲解。

节点

public class HuffmanNode implements Comparable, Cloneable {
    protected int key;              // 权值
    protected HuffmanNode left;     // 左孩子
    protected HuffmanNode right;    // 右孩子
    protected HuffmanNode parent;   // 父结点

    protected HuffmanNode(int key, HuffmanNode left, HuffmanNode right, HuffmanNode parent) {
        this.key = key;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }

    @Override
    public Object clone() {
        Object obj=null;

        try {
            obj = (HuffmanNode)super.clone();//Object 中的clone()识别出你要复制的是哪一个对象。    
        } catch(CloneNotSupportedException e) {
            System.out.println(e.toString());
        }

        return obj;    
    }

    @Override
    public int compareTo(Object obj) {
        return this.key - ((HuffmanNode)obj).key;
    }
}

树

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class Huffman {

	private HuffmanNode mRoot;	// 根结点

	/* 
	 * 创建Huffman树
	 *
	 * @param 权值数组
	 */
	public Huffman(int a[]) {
        HuffmanNode parent = null;
		MinHeap heap;

		// 建立数组a对应的最小堆
		heap = new MinHeap(a);
	 
		for(int i=0; i<a.length-1; i++) {   
        	HuffmanNode left = heap.dumpFromMinimum();  // 最小节点是左孩子
        	HuffmanNode right = heap.dumpFromMinimum(); // 其次才是右孩子
	 
			// 新建parent节点，左右孩子分别是left/right；
			// parent的大小是左右孩子之和
			parent = new HuffmanNode(left.key+right.key, left, right, null);
			left.parent = parent;
			right.parent = parent;

			// 将parent节点数据拷贝到"最小堆"中
			heap.insert(parent);
		}

		mRoot = parent;

		// 销毁最小堆
		heap.destroy();
	}

	/*
	 * 前序遍历"Huffman树"
	 */
	private void preOrder(HuffmanNode tree) {
		if(tree != null) {
			System.out.print(tree.key+" ");
			preOrder(tree.left);
			preOrder(tree.right);
		}
	}

	public void preOrder() {
		preOrder(mRoot);
	}

	/*
	 * 中序遍历"Huffman树"
	 */
	private void inOrder(HuffmanNode tree) {
		if(tree != null) {
			inOrder(tree.left);
			System.out.print(tree.key+" ");
			inOrder(tree.right);
		}
	}

	public void inOrder() {
		inOrder(mRoot);
	}


	/*
	 * 后序遍历"Huffman树"
	 */
	private void postOrder(HuffmanNode tree) {
		if(tree != null)
		{
			postOrder(tree.left);
			postOrder(tree.right);
			System.out.print(tree.key+" ");
		}
	}

	public void postOrder() {
		postOrder(mRoot);
	}

	/*
	 * 销毁Huffman树
	 */
	private void destroy(HuffmanNode tree) {
		if (tree==null)
			return ;

		if (tree.left != null)
			destroy(tree.left);
		if (tree.right != null)
			destroy(tree.right);

		tree=null;
	}

	public void destroy() {
		destroy(mRoot);
		mRoot = null;
	}

	/*
	 * 打印"Huffman树"
	 *
	 * key        -- 节点的键值 
	 * direction  --  0，表示该节点是根节点;
	 *               -1，表示该节点是它的父结点的左孩子;
	 *                1，表示该节点是它的父结点的右孩子。
	 */
	private void print(HuffmanNode tree, int key, int direction) {

		if(tree != null) {

			if(direction==0)	// tree是根节点
				System.out.printf("%2d is root\n", tree.key);
			else				// tree是分支节点
				System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");

			print(tree.left, tree.key, -1);
			print(tree.right,tree.key,  1);
		}
	}

	public void print() {
		if (mRoot != null)
			print(mRoot, mRoot.key, 0);
	}
}

最小堆

import java.util.ArrayList;
import java.util.List;

public class MinHeap {

	private List<HuffmanNode> mHeap;		// 存放堆的数组

	/* 
	 * 创建最小堆
	 *
	 * 参数说明：
	 *     a -- 数据所在的数组
	 */
	protected MinHeap(int a[]) {
		mHeap = new ArrayList<HuffmanNode>();
		// 初始化数组
		for(int i=0; i<a.length; i++) {
		    HuffmanNode node = new HuffmanNode(a[i], null, null, null);
			mHeap.add(node);
		}

		// 从(size/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个最小堆。
		for (int i = a.length / 2 - 1; i >= 0; i--)
			filterdown(i, a.length-1);
	}

	/* 
	 * 最小堆的向下调整算法
	 *
	 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
	 *
	 * 参数说明：
	 *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
	 *     end   -- 截至范围(一般为数组中最后一个元素的索引)
	 */
	protected void filterdown(int start, int end) {
		int c = start; 	 	// 当前(current)节点的位置
		int l = 2*c + 1; 	// 左(left)孩子的位置
		HuffmanNode tmp = mHeap.get(c);	// 当前(current)节点

		while(l <= end) {
			// "l"是左孩子，"l+1"是右孩子
			if(l < end && (mHeap.get(l).compareTo(mHeap.get(l+1))>0))
				l++;		// 左右两孩子中选择较小者，即mHeap[l+1]

			int cmp = tmp.compareTo(mHeap.get(l));
			if(cmp <= 0)
				break;		//调整结束
			else {
				mHeap.set(c, mHeap.get(l));
				c = l;
				l = 2*l + 1;   
			}       
		}   
		mHeap.set(c, tmp);
	}
	
	/*
	 * 最小堆的向上调整算法(从start开始向上直到0，调整堆)
	 *
	 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
	 *
	 * 参数说明：
	 *     start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
	 */
	protected void filterup(int start) {
		int c = start;			// 当前节点(current)的位置
		int p = (c-1)/2;		// 父(parent)结点的位置 
		HuffmanNode tmp = mHeap.get(c);	// 当前(current)节点

		while(c > 0) {
			int cmp = mHeap.get(p).compareTo(tmp);
			if(cmp <= 0)
				break;
			else {
				mHeap.set(c, mHeap.get(p));
				c = p;
				p = (p-1)/2;   
			}       
		}
		mHeap.set(c, tmp);
	} 
 
	/* 
	 * 将node插入到二叉堆中
	 */
	protected void insert(HuffmanNode node) {
		int size = mHeap.size();

		mHeap.add(node);	// 将"数组"插在表尾
		filterup(size);		// 向上调整堆
	}

	/*
	 * 交换两个HuffmanNode节点的全部数据
	 */
	private void swapNode(int i, int j) {
		HuffmanNode tmp = mHeap.get(i);
		mHeap.set(i, mHeap.get(j));
		mHeap.set(j, tmp);
	}

	/* 
	 * 新建一个节点，并将最小堆中最小节点的数据复制给该节点。
	 * 然后除最小节点之外的数据重新构造成最小堆。
	 *
	 * 返回值：
	 *     失败返回null。
	 */
	protected HuffmanNode dumpFromMinimum() {
		int size = mHeap.size();

		// 如果"堆"已空，则返回
		if(size == 0)
			return null;

		// 将"最小节点"克隆一份，将克隆得到的对象赋值给node
		HuffmanNode node = (HuffmanNode)mHeap.get(0).clone();

		// 交换"最小节点"和"最后一个节点"
		mHeap.set(0, mHeap.get(size-1));
		// 删除最后的元素
		mHeap.remove(size-1);

		if (mHeap.size() > 1)
			filterdown(0, mHeap.size()-1);

		return node;
	}

	// 销毁最小堆
	protected void destroy() {
		mHeap.clear();
		mHeap = null;
	}
}

测试

public class HuffmanTest {

	private static final int a[]= {5,6,8,7,15};

	public static void main(String[] args) {
		int i;
		Huffman tree;

		System.out.print("== 添加数组: ");
		for(i=0; i<a.length; i++) 
			System.out.print(a[i]+" ");
	
		// 创建数组a对应的Huffman树
		tree = new Huffman(a);

		System.out.print("\n== 前序遍历: ");
		tree.preOrder();

		System.out.print("\n== 中序遍历: ");
		tree.inOrder();

		System.out.print("\n== 后序遍历: ");
		tree.postOrder();
		System.out.println();

		System.out.println("== 树的详细信息: ");
		tree.print();

		// 销毁二叉树
		tree.destroy();
	}
}

1.8 - CH08-前缀树

Trie，又称字典树、单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于文本词频统计。

它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

什么是前缀树

在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie 这个术语来自于 retrieval。根据词源学，trie 的发明者 Edward Fredkin 把它读作/ˈtriː/ “tree”。但是，其他作者把它读作/ˈtraɪ/ “try”。trie 中的键通常是字符串，但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie 中的键是一串位元，可以用于表示整数或者内存地址。trie 树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质：

• 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
• 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符互不相同。
• 从第一字符开始有连续重复的字符只占用一个节点，比如上面的to，和ten，中重复的单词t只占用了一个节点。

前缀树的实现

节点

public class Trie {
  //根节点
  private Node root;
  //Trie单词个数
  private int size;

  public Trie(){
      root = new Node();
      size = 0;
  }

  // 获得Trie中存储的单词数量
  public int getSize(){
      return size;
  }
  
  private class Node{

      public boolean isWord; // 是否是某个单词的结束
      
      public TreeMap<Character, Node> next; //到下一个节点的映射

      public Node(boolean isWord){
          this.isWord = isWord;
          //初始化字典树
          next = new TreeMap<>();
      }

      public Node(){
          this(false);
      }
  }
}

插入方法：非递归

向Trie中添加一个新的单词word: 将单词拆分成一个个字符c，然后从根节点开始往下添加：

public void add(String word){

    Node cur = root;
    //循环判断新的cur节点是否包含下一个字符到下一个节点的映射
    for(int i = 0 ; i < word.length() ; i ++){
        //将c当成一个节点插入Trie中
        char c = word.charAt(i);
        //判断cur.next是不是已经指向我们要找的c字符相应的节点
        if(cur.next.get(c) == null){
            //新建节点
            cur.next.put(c, new Node());
        }
        //否则，就直接走到该节点位置即可
        cur = cur.next.get(c);
    }
    //判断该单词并不表示任何一个单词的结尾
    if(!cur.isWord){
        //确定cur是新的单词
        cur.isWord = true;
        size ++;
    }
}

插入方法：递归

/**
  * 向Trie中添加一个新的单词word(递归写法接口)
  *
  * @param word
  */
public void recursionAdd(String word) {
    Node cur = root;
    add(root, word, 0);
}

/**
  * 递归写法调用方法实现递归添加
  *
  * @param node 传入要进行添加的节点
  * @param word 传入要进行添加的单词
  */
public void add(Node node, String word, int index) {
    // 确定终止条件,这个终止条件在没加index这个参数时,很难确定
    // 此时一个单词已经遍历完成了,如果这个结束节点没有标记为单词,就标记为单词
    if (!node.isWord && index == word.length()) {
        node.isWord = true;
        size++;
    }

    if (word.length() > index) {
        char addLetter = word.charAt(index);
        // 判断trie的下个节点组中是否有查询的字符,如果没有,就添加
        if (node.next.get(addLetter) == null) {
            node.next.put(addLetter, new Node());
        }
        // 基于已经存在的字符进行下个字符的递归查询
        add(node.next.get(addLetter), word, index + 1);
    }
}

查找单词：非递归

/**
  * 查询单词word是否在Trie中(非递归写法)
  *
  * @param word
  * @return
  */
public boolean contains(String word) {
    Node cur = root;
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        if (cur.next.get(c) == null) {
            return false;
        } else {
            cur = cur.next.get(c);
        }
    }
    return cur.isWord;
}

查找单词：递归

/**
  * 查询单词word中是否在Trie中接口(递归写法)
  *
  * @param word
  * @return
  */
public boolean recursionContains(String word) {
    Node cur = root;
    return contains(root, word, 0);
}

/**
  * 查询word中是否在Trie中递归写法
  *
  * @param node
  * @param word
  * @param index
  * @return
  */
private boolean contains(Node node, String word, int index) {
    if (index == word.length()) {
        return node.isWord;
    }
    char c = word.charAt(index);
    if (node.next.get(c) == null) {
        return false;
    } else {
        return contains(node.next.get(c), word, index + 1);
    }
}

查询前缀：非递归

/**
  * 查询是否在Trie中有单词一prefix为前缀
  *
  * @param prefix
  * @return
  */
public boolean isPrefix(String prefix) {
    Node cur = root;
    for (int i = 0; i < prefix.length(); i++) {
        char c = prefix.charAt(i);
        if (cur.next.get(c) == null) {
            return false;
        }
        cur = cur.next.get(c);
    }
    return true;
}

查询前缀：递归

/**
  * 查询是否在Trie中有单词一prefix为前缀(递归调用)
  *
  * @param prefix
  * @return
  */
public boolean recursionIsPrefix(String prefix) {
    Node node = root;
    return recursionIsPrefix(root, prefix, 0);
}

/**
  * 查询是否在Trie中有单词一prefix为前缀(递归实现)
  *
  * @return
  */
public boolean recursionIsPrefix(Node root, String prefix, int index) {
    if (prefix.length() == index) {
        return true;
    }
    char c = prefix.charAt(index);
    if (root.next.get(c) == null) {
        return false;
    } else {
        return recursionIsPrefix(root.next.get(c), prefix, ++index);
    }
}

拓展理解

前缀树的复杂度

设平均查询的query词长n， 白名单m条记录，平均长度k,

简单单词查询：一个query，需要遍历每一个白名单，调用query是否contains方法，contains方法遍历前词，找到头元素一致，再遍历判断尾序列，contains的复杂度是O(n)，整体复杂度是O(mn)

前缀树查询: 一个query，将这个query从头到尾遍历，每个元素在前缀树中判断，操作都是取下一个节点和判断是否是end，时间复杂度是O(1)，整体时间复杂度是O(n)

前缀树应用场景

• 前缀匹配、URL 匹配
• 字符串检索， 比如 敏感词过滤，黑白名单等
• 词频统计
• 字符串排序

前缀树压缩：基数树

在计算机科学中，基数树，或称压缩前缀树，是一种更节省空间的 Trie（前缀树）。对于基数树的每个节点，如果该节点是确定的子树的话，就和父节点合并。基数树可用来构建关联数组。 用于 IP 路由。 信息检索中用于文本文档的倒排索引。

基数树可看做是以二进制位串为关键字的 trie 树，是一种多叉树形结构，同时又类似多层索引表，每个中间节点包含指向多个子节点的指针数组，叶子节点包含指向实际的对象的指针(由于对象不具备树节点结构，因此将其父节点看做叶节点)。基数树也被设计成多道树，以提高磁盘交互性能。同时，基数树也是按照字典序来组织叶节点的，这种特点使之适合持久化改造，加上它的多道特点，灵活性较强，适合作为区块链的基础数据结构，构建持久性区块时较好地映射各类数据集合上。基数树支持插入、删除、查找操作。查找包括完全匹配、前缀匹配、前驱查找、后继查找。所有这些操作都是 O(k)复杂度，其中 k 是所有字符串中最大的长度。

双数组 Trie 树：DoubleArrayTrie

双数组Trie树(DoubleArrayTrie)是一种空间复杂度低的Trie树，应用于字符区间大的语言（如中文、日文等）分词领域。

双数组Trie (Double-Array Trie)结构由日本人JUN-ICHI AOE于1989年提出的，是Trie结构的压缩形式，仅用两个线性数组来表示Trie树，该结构有效结合了数字搜索树(Digital Search Tree)检索时间高效的特点和链式表示的Trie空间结构紧凑的特点。双数组Trie的本质是一个确定有限状态自动机（DFA），每个节点代表自动机的一个状态，根据变量不同，进行状态转移，当到达结束状态或无法转移时，完成一次查询操作。在双数组所有键中包含的字符之间的联系都是通过简单的数学加法运算表示，不仅提高了检索速度，而且省去了链式结构中使用的大量指针，节省了存储空间。——《基于双数组Ｔｒｉｅ树算法的字典改进和实现》

1.9 - CH09-图概念

图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中，图是最灵活的数据结构之一，很多问题都可以使用图模型进行建模求解。例如: 生态环境中不同物种的相互竞争、人与人之间的社交与关系网络、化学上用图区分结构不同但分子式相同的同分异构体、分析计算机网络的拓扑结构确定两台计算机是否可以通信、找到两个城市之间的最短路径等等。

基本概念

定义

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

和线性表，树的差异:

• 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点(Vertex)。
• 线性表可以没有元素，称为空表；树中可以没有节点，称为空树；但是，在图中不允许没有顶点(有穷非空性)。
• 线性表中的各元素是线性关系，树中的各元素是层次关系，而图中各顶点的关系是用边来表示(边集可以为空)。

术语

• 顶点的度
  • 顶点Vi的度(Degree)是指在图中与Vi相关联的边的条数。对于有向图来说，有入度(In-degree)和出度(Out-degree)之分，有向图顶点的度等于该顶点的入度和出度之和。
• 邻接
  • 若无向图中的两个顶点V1和V2存在一条边(V1,V2)，则称顶点V1和V2邻接(Adjacent)；
  • 若有向图中存在一条边<V3,V2>，则称顶点V3与顶点V2邻接，且是V3邻接到V2或V2邻接直V3；
• 路径
  • 在无向图中，若从顶点Vi出发有一组边可到达顶点Vj，则称顶点Vi到顶点Vj的顶点序列为从顶点Vi到顶点Vj的路径(Path)。
• 连通
  • 若从Vi到Vj有路径可通，则称顶点Vi和顶点Vj是连通(Connected)的。
• 权(Weight)
  • 有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权(Weight)。

类型

无向图

• 如果图中任意两个顶点之间的边都是无向边(简而言之就是没有方向的边)，则称该图为无向图(Undirected graphs)。

• 无向图中的边使用小括号“()”表示; 比如 (V1,V2);

有向图

• 如果图中任意两个顶点之间的边都是有向边(简而言之就是有方向的边)，则称该图为有向图(Directed graphs)。

• 有向图中的边使用尖括号“<>”表示; 比如 /<V1,V2>

完全图

• 无向完全图: 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。(含有n个顶点的无向完全图有(n×(n-1))/2条边)
• 有向完全图: 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。(含有n个顶点的有向完全图有n×(n-1)条边)

存储结构

邻接矩阵表示法

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

无向图

有向图

我们再来看一个有向图样例，如下图所示的左边。顶点数组为 vertex [4]={v0,v1,v2,v3}，弧数组 arc[4][4] 为下图右边这样的一个矩阵。主对角线上数值依然为0。但因为是有向图，所以此矩阵并不对称，比如由v1到v0有弧，得到arc[1][0]=1，而v到v没有弧，因此 arc[0][1]=0。

不足: 由于存在n个顶点的图需要n*n个数组元素进行存储，当图为稀疏图时，使用邻接矩阵存储方法将会出现大量0元素，这会造成极大的空间浪费。这时，可以考虑使用邻接表表示法来存储图中的数据

邻接表示法

首先，回忆我们在线性表时谈到，顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题，于是引出了链式存储的结构。同样的，我们也可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。

邻接表由表头节点和表节点两部分组成，图中每个顶点均对应一个存储在数组中的表头节点。如果这个表头节点所对应的顶点存在邻接节点，则把邻接节点依次存放于表头节点所指向的单向链表中。

无向图

从上图中我们知道，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。例如: v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2。

对于无向图来说，使用邻接表进行存储也会出现数据冗余的现象。例如上图中，顶点V0所指向的链表中存在一个指向顶点V3的同事，顶点V3所指向的链表中也会存在一个指向V0的顶点。

有向图

若是有向图，邻接表结构是类似的，但要注意的是有向图由于有方向的。因此，有向图的邻接表分为出边表和入边表(又称逆邻接表)，出边表的表节点存放的是从表头节点出发的有向边所指的尾节点；入边表的表节点存放的则是指向表头节点的某个顶点，如下图所示。

带权图

对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可，如下图所示。

1.10 - CH10-图遍历

深度优先搜索

假设初始状态是图中所有顶点均未被访问，则从某个顶点 V 出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索来遍历整个图，直至图中所有和 V 有路径相通的顶点都被访问到。这里的关键是访问到邻接点时，接着去访问该邻接点的所有邻接点，然后再去访问第一层邻接点中的下一个邻接点的所有邻接点。

若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

显然，深度优先搜索是一个递归的过程。

深度优先搜索：无向图

对上面的图G1进行深度优先遍历，从顶点A开始。

1. 访问 A。
2. 访问(A的邻接点)C。 在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。
3. 访问(C的邻接点)B。 在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。
4. 访问(C的邻接点)D。 在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。
5. 访问(A的邻接点)F。 前面已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。
6. 访问(F的邻接点)G。
7. 访问(G的邻接点)E。

因此访问顺序是: A -> C -> B -> D -> F -> G -> E

深度优先搜索：有向图

下面以"有向图"为例，来对深度优先搜索进行演示。

对上面的图G2进行深度优先遍历，从顶点A开始。

1. 访问A。
2. 访问B。 在访问了A之后，接下来应该访问的是A的出边的另一个顶点，即顶点B。
3. 访问C。 在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。
4. 访问E。 接下来访问C的出边的另一个顶点，即顶点E。
5. 访问D。 接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。
6. 访问F。 接下应该回溯"访问A的出边的另一个顶点F"。
7. 访问G。

因此访问顺序是: A -> B -> C -> E -> D -> F -> G

广度优先搜索

广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。

它的思想是: 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2…的顶点。

广度优先搜索：无向图

下面以"无向图"为例，来对广度优先搜索进行演示。还是以上面的图G1为例进行说明。

1. 访问 A。
2. 依次访问C,D,F。 在访问了A之后，接下来访问A的邻接点。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，C在"D和F"的前面，因此，先访问C。再访问完C之后，再依次访问D,F。
3. 依次访问B,G。 在第2步访问完C,D,F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。
4. 访问E。 在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。

因此访问顺序是: A -> C -> D -> F -> B -> G -> E

广度优先搜索：有向图

下面以"有向图"为例，来对广度优先搜索进行演示。还是以上面的图G2为例进行说明。

1. 访问A。
2. 访问B。
3. 依次访问C,E,F。 在访问了B之后，接下来访问B的出边的另一个顶点，即C,E,F。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，因此会先访问C，再依次访问E,F。
4. 依次访问D,G。 在访问完C,E,F之后，再依次访问它们的出边的另一个顶点。还是按照C,E,F的顺序访问，C的已经全部访问过了，那么就只剩下E,F；先访问E的邻接点D，再访问F的邻接点G。

因此访问顺序是: A -> B -> C -> E -> F -> D -> G

1.11 - CH11-最小生成树

概念

• 连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。
• 强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。
• 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
• 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
• 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

最小生成树算法

Kruskal 算法

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

Prim 算法

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

• 图的所有顶点集合为VV；初始令集合u={s},v=V−uu={s},v=V−u;
• 在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
• 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

由于不断向集合u中加点，所以最小代价边必须同步更新；需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息:

总结

• 因为Kruskal涉及大量对边的操作，所以它适用于稀疏图；

• 普通的prim算法适用于稠密图，但堆优化的prim算法更适用于稀疏图，因为其时间复杂度是由边的数量决定的。

1.12 - CH12-图最短路径

介绍

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。最短路径不一定是经过边最少的路径，但在这些最短路径中，长度最短的那一条路径上只有一条边，且它的权值在从源点出发的所有边的权值最小。

从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小，例: 公交查询系统。

路径长度最短的最短路径的特点:

• 在这条路径上，必定只含一条弧，并且这条弧的权值最小。
• 下一条路径长度次短的最短路径的特点:
• 它只可能有两种情况: 或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。

问题解法:

• 求从某个源点到其余各点的最短路径 — Dijkstra算法
• 每一对顶点之间的最短路径 — Floyd算法

最短路径算法

Dijkstra 算法

定义概述

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。

问题描述: 在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。(单源最短路径)

算法描述

算法思想: 设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了)，第二组为其余未确定最短路径的顶点集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

算法步骤

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中(该选定的距离就是v到k的最短路径长度)。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

Floyd 算法

1.13 - CH13-图拓扑排序

概念

对于任何有向图而言，其拓扑排序为其所有结点的一个线性排序(对于同一个有向图而言可能存在多个这样的结点排序)。该排序满足这样的条件——对于图中的任意两个结点u和v，若存在一条有向边从u指向v，则在拓扑排序中u一定出现在v前面。

例如一个有向无环图如下:

• 结点1必须在结点2、3之前
• 结点2必须在结点3、4之前
• 结点3必须在结点4、5之前
• 结点4必须在结点5之前

则一个满足条件的拓扑排序为 [1, 2, 3, 4, 5]。

前提

当且仅当一个有向图为有向无环图(directed acyclic graph，或称DAG)时，才能得到对应于该图的拓扑排序。这里有两点要注意:

• 对于有环图，必然会造成循环依赖(circular dependency)，不符合拓扑排序定义；
• 对于每一个有向无环图都至少存在一种拓扑排序；

不唯一的情况:

上图中若我们删 4、5结点之前的有向边，上图变为如下所示:

则我们可得到两个不同的拓扑排序结果: [1, 2, 3, 4, 5]和[1, 2, 3, 5, 4]。

算法

为了说明如何得到一个有向无环图的拓扑排序，我们首先需要了解有向图结点的入度(indegree)和出度(outdegree)的概念。

假设有向图中不存在起点和终点为同一结点的有向边。

入度: 设有向图中有一结点v，其入度即为当前所有从其他结点出发，终点为v的的边的数目。也就是所有指向v的有向边的数目。

出度: 设有向图中有一结点v，其出度即为当前所有起点为v，指向其他结点的边的数目。也就是所有由v发出的边的数目。

在了解了入度和出度的概念之后，再根据拓扑排序的定义，我们自然就能够得出结论: 要想完成拓扑排序，我们每次都应当从入度为0的结点开始遍历。因为只有入度为0的结点才能够成为拓扑排序的起点。否则根据拓扑排序的定义，只要一个结点v的入度不为0，则至少有一条边起始于其他结点而指向v，那么这条边的起点在拓扑排序的顺序中应当位于v之前，则v不能成为当前遍历的起点。

由此我们可以进一步得出一个改进的深度优先遍历或广度优先遍历算法来完成拓扑排序。以广度优先遍历为例，这一改进后的算法与普通的广度优先遍历唯一的区别在于我们应当保存每一个结点对应的入度，并在遍历的每一层选取入度为0的结点开始遍历(而普通的广度优先遍历则无此限制，可以从该吃呢个任意一个结点开始遍历)。这个算法描述如下:

• 初始化一个int[] inDegree保存每一个结点的入度。
• 对于图中的每一个结点的子结点，将其子结点的入度加1。
• 选取入度为0的结点开始遍历，并将该节点加入输出。
• 对于遍历过的每个结点，更新其子结点的入度: 将子结点的入度减1。
• 重复步骤3，直到遍历完所有的结点。
• 如果无法遍历完所有的结点，则意味着当前的图不是有向无环图。不存在拓扑排序。

实现

广度优先遍历拓扑排序的Java代码如下:

public class TopologicalSort {
    /**
     * Get topological ordering of the input directed graph 
     * @param n number of nodes in the graph
     * @param adjacencyList adjacency list representation of the input directed graph
     * @return topological ordering of the graph stored in an List<Integer>. 
     */
    public List<Integer> topologicalSort(int n, int[][] adjacencyList) {
        List<Integer> topoRes = new ArrayList<>();
        int[] inDegree = new int[n];
        for (int[] parent : adjacencyList) {
            for (int child : parent) {
                inDegree[child]++;
            }
        }
        
        Deque<Integer> deque = new ArrayDeque<>();
        
        // start from nodes whose indegree are 0
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) deque.offer(i);
        }
        
        while (!deque.isEmpty()) {
            int curr = deque.poll();
            topoRes.add(curr);
            for (int child : adjacencyList[curr]) {
                inDegree[child]--;
                if (inDegree[child] == 0) {
                    deque.offer(child);
                }
            }
        }
    
        return topoRes.size() == n ? topoRes : new ArrayList<>();
    }
}

复杂度

• 时间复杂度: O(n + e)，其中n为图中的结点数目，e为图中的边的数目

• 空间复杂度: O(n)

1.14 - CH14-图-AOE-关键路径

概念

相关术语:

• AOV网络(Activity On Vertex Network): 有向图，用顶点表示活动，用弧表示活动的先后顺序
• AOE网络(Activity On Edge): 有向图，用顶点表示事件，用弧表示活动，用权值表示活动消耗时间(带权的有向无环图)
• 活动: 业务逻辑中的行为，用边表示
• 事件: 活动的结果或者触发条件
• 关键路径: 具有最大路径长度(权重)的路径，可能不止一条
• 活动的两个属性: e(i)最早开始时间，l(i)最晚开始时间
• 事件的两个属性: ve(j)最早开始时间，vl(j)最晚开始时间

AOV和AOE的对比: 虽然都是用来对工程建模，但是还是有很大不同。主要体现在:

• AOV网是顶点表示活动的网，他只描述活动之间的制约更新，
• AOE网是用边表示活动的网，边上的权值表示活动持续的时间

实现

4个关键概念

事件最早发生时间

事件最早发生时间etv(earliest time of vertex)，即顶点Vk的最早发生时间。

事件最晚发生时间

事件最晚发生时间ltv(lastest time of vertex)，即顶点Vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的事件，超出此事件将会延误整个工期。

活动的最早开工时间

活动的最早开工时间ete(earliest time of edge)，即弧ak的最早发生时间。

活动的最晚开工时间

活动的最晚开工时间lte(lastest time if edge)，即弧的最晚发生时间，也就是不推迟工期的最晚开工时间。

4个时间的关系

我们可以由事件的最早发生时间和事件的最晚发生时间求出活动的最早和最晚开工时间。 由1,2可以求得3,4，然后在根据ete[k]是否与lte[k]相等来判断ak是否是关键活动。

算法实现

• 推演图

• etv 从左到右推导

• ltv 从右向左推导

• ete：活动最早开工时间需要和 etv 事件最早发生时间结合

• lte：活动最晚开工时间需要和 ltv 事件最晚发生时间结合(都是倒序获得)：

1.15 - CH15-Iterable

当我们想要遍历集合时，Java 为我们提供了多种选择，通常有以下三种写法：

• for 循环

  for (int i = 0, len = strings.size(); i < len; i++) {
    System.out.println(strings.get(i));
  }
  

• foreach 循环

  for (String var : strings) {
    System.out.println(var);
  }
  

• while iterator

  Iterator iterator = strings.iterator();
  while (iterator.hasNext()) {
    System.out.println(iterator.next());
  }
  

• for 循环我们很熟悉了，就是根据下标来获取元素，这个特性与数组十分吻合，不熟悉的朋友可以阅读前面讲解数组的文章。

• foreach 则主要对类似链表的结构提供遍历支持，链表没有下标，所以使用 for 循环遍历会大大降低性能。

• Iterator 就是我们今天要讲述的主角，它实际上就是 foreach。

Iterable

Iterable 是迭代器的意思，作用是为集合类提供 for-each 循环的支持。由于使用 for 循环需要通过位置获取元素，而这种获取方式仅有数组支持，其他许多数据结构，比如链表，只能通过查询获取数据，这会大大的降低效率。Iterable 就可以让不同的集合类自己提供遍历的最佳方式。

Iterable 的文档声明仅有一句：

Implementing this interface allows an object to be the target of the “for-each loop” statement.

它的作用就是为 Java 对象提供 foreach 循环，其主要方法是返回一个 Iterator 对象：

Iterator<T> iterator();

也就是说，如果想让一个 Java 对象支持 foreach，只要实现 Iterable 接口，然后就可以像集合那样，通过 Iterator iterator = strings.iterator() 方式，或者使用 foreach，进行遍历了。

Iterator

Iterator 是 foreach 遍历的主体，它的代码实现如下：

// 判断一个对象集合是否还有下一个元素
boolean hasNext();

// 获取下一个元素
E next();

// 删除最后一个元素。
// 默认是不支持的，因为在很多情况下其结果不可预测，比如数据集合在此时被修改
default void remove(){...}

// 主要将每个元素作为参数发给 action 来执行特定操作
default void forEachRemaining(Consumer<? super E> action){...}

Iterator 还有一个子接口，是为需要双向遍历数据时准备的，在后续分析 ArrayList 和 LinkedList 时都会看到它。它主要增加了以下几个方法：

// 是否有前一个元素
boolean hasPrevious();

// 获取前一个元素
E previous();

// 获取下一个元素的位置
int nextIndex();

// 获取前一个元素的位置
int previousIndex();

// 添加一个元素
void add(E e);

// 替换当前元素值
void set(E e);

总结

在 Java 中有许多特性都是通过接口来实现的，foreach 循环也是。foreach 主要是解决 for 循环依赖下标的问题，为高效遍历更多的数据结构提供了支持。如果你清楚数组和链表的区别，应该就可以回答以下问题了：for 与 foreach 有何区别，哪个更高效？

1.16 - CH16-Collection

Collection 是 List、Queue 和 Set 的超集，它直接继承于 Iterable，也就是所有的 Collection 集合类都支持 for-each 循环。除此之外，Collection 也是面向接口编程的典范，通过它可以在多种实现类间转换，这也是面向对象编程的魅力之一。

方法定义

在阅读源码前，我们可以先自行想象一下，如果我们想封装下数组或链表以方便操作，我们需要封装哪些功能呢？比如：统计大小、插入或删除数据、清空、是否包含某条数据，等等。而 Collection 就是对这些常用操作进行提取，只是其很全面、很通用。下面我们看看它都提供了哪些方法。

//返回集合的长度，如果长度大于 Integer.MAX_VALUE，返回Integer.MAX_VALUE
int size();

//如果集合元素总数为0，返回true
boolean isEmpty();

//判断集合中是否包含指定的元素，其依据是equals()方法
boolean contains(Object o);

//返回一个包含集合中所有元素的数组
Object[] toArray();

//与上个类似，只是增加了类型的转换
<T> T[] toArray(T[] a);

//向集合中加入一个元素，如果成功加入则返回true，如果加入失败，或者因集合本身已经包含同个元素而不再加入时，返回false
boolean add(E e);

//从集合中删除指定元素的单个实例
boolean remove(Object o);

//如果集合包含指定集合中的所有元素，返回true
boolean containsAll(Collection<?> c);

//把指定集合中的所有元素添加到集合中，但在此期间，如果指定的集合发生了改变，可能出现意想不到的事情
boolean addAll(Collection<? extends E> c);

//从集合中删除所有包含在指定集合中的元素
boolean removeAll(Collection<?> c);

//仅保留集合中包含在指定集合中的元素
boolean retainAll(Collection<?> c);

//清空集合
void clear();

//将此方法抽象，是保证所有子类都覆写此方法，以保证equals的正确行为
boolean equals(Object o);

//同上
int hashCode();

//这个方法在JDK1.8中提供了默认的实现，会使用Iterator的形式删除符合条件的元素
default boolean removeIf(Predicate<? super E> filter){
    Objects.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while (each.hasNext()) {
        if (filter.test(each.next())) {
            each.remove();
            removed = true;
        }
    }
    return removed;
}

超级实现类——AbstractCollection

在 Collection 中定义的许多方法，根据现有的定义以及继承的 Iterable，都可以在抽象类中实现，这样可以减少实现类需要实现的方法，这个抽象类就是 AbstractCollection。

首先我们关注下其文档，里面有两句说明可能会影响我们的继承：

To implement an unmodifiable collection, the programmer needs only to extend this class and provide implementations for the iterator and size methods. (The iterator returned by the iterator method must implement hasNext and next.)

To implement a modifiable collection, the programmer must additionally override this class’s add method (which otherwise throws an UnsupportedOperationException), and the iterator returned by the iterator method must additionally implement its remove method.

大体意思是说，如果要实现一个不可修改的集合，只需要重写 iterator 和 size 接口就可以，并且返回的 Iterator 需要实现 hasNext 和 next。而要实现一个可以修改的集合，还必须重写 add 方法（默认会抛出异常），返回的 Iterator 还需要实现 remove 方法。

方法定义

//这个毫无疑问，是可以直接获取的
public boolean isEmpty() {
    return size() == 0;
}

//这个方法因为Iterator的存在，可以进行一致性封装，
//这里需要注意的是对象的比较是通过equals方法
//因为调用到了it.next()与it.hasNext()，这也是为什么文档注释会写实现集合类需要重写Iterator的这两个方法。
public boolean contains(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

//和contains类似，也是通过Iterator实现的，但其会调用it.remove()方法，这也是为什么文档注释会写实现可以修改的集合类时需要重写Iterator的remove方法。
public boolean remove(Object o) {
    //...省略，这里调用了it.remove()方法
}

类似的方法还有 containsAll(Collection<?> c)、addAll(Collection<? extends E> c)、removeAll(Collection<?> c)、retainAll(Collection<?> c)和 clear() 等，都需要利用到Iterator的特性，这里就不再一一赘述了。

另外还有一个toArray()的方法实现略微不同，可以看看其具体实现。

//这个实现相对复杂一些，可以看到扩容最主要的手段是Arrays.copyOf()方法，
//也就是需要将原数组通过复制到新的数组中来实现的。
//注意这里返回的顺序和Iterator顺序一致
//在这里实现是为了方便不同具体实现类互相转换，我们在后续会多次见到此方法
public Object[] toArray() {
    //先根据当前集合大小声明一个数组
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        //集合元素没那么多，说明不需要那么大的数组
        if (! it.hasNext()) 
            return Arrays.copyOf(r, i); //仅返回赋完值的部分
        r[i] = it.next();
    }
    //元素比从size()中获取的更多，就需要进一步调整数组大小
    return it.hasNext() ? finishToArray(r, it) : r;
}

private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
    //记录当前大小
    int i = r.length;
    while (it.hasNext()) {
        int cap = r.length;
        //r的长度不够，继续分配
        if (i == cap) {
            //扩充方式为cap+cap/2+1，也就是1.5倍扩容
            int newCap = cap + (cap >> 1) + 1;
            // 超过了最大容量，MAX_ARRAY_SIZE=Integer.MAX_VALUE-8
            if (newCap - MAX_ARRAY_SIZE > 0)
                //重新设置cap的值
                newCap = hugeCapacity(cap + 1);
            
            //对r进行扩容
            r = Arrays.copyOf(r, newCap);
        }
        //赋值，进入下一轮循环
        r[i++] = (T)it.next();
    }
    // 由于之前扩容是1.5倍进行的，最后再将其设置到和r实际需要的相同
    return (i == r.length) ? r : Arrays.copyOf(r, i);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // 超过了最大正整数，也就是负数
        throw new OutOfMemoryError
            ("Required array size too large");
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

//和toArray()方法类似，就不再赘述，具体可以查看源码
public <T> T[] toArray(T[] a) {
    //...
}

除了以上这些方法，AbstractCollection还实现了toString方法，其是通过StringBuilder拼接了每个元素的toString完成的，也并不复杂。这里可以看下其源码：

public String toString() {
    Iterator<E> it = iterator();
    if (! it.hasNext())
        return "[]";

    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {
        E e = it.next();
        sb.append(e == this ? "(this Collection)" : e);
        if (! it.hasNext())
            return sb.append(']').toString();
        sb.append(',').append(' ');
    }
}

1.17 - CH17-List

List 是 Collection 三大直接子接口之一，其中的数据可以通过位置检索，用户可以在指定位置插入数据。List 的数据可以为空，可以重复。以下是其文档注释，只看前两段：

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all. It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.

List 特有方法

我们关注其不同于 Collection 的方法，主要有以下这些：

//在指定位置，将指定的集合插入到当前的集合中
boolean addAll(int index, Collection<? extends E> c);

//这是一个默认实现的方法，会通过Iterator的方式对每个元素进行指定的操作
default void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final ListIterator<E> li = this.listIterator();
    while (li.hasNext()) {
        li.set(operator.apply(li.next()));
    }
}

//排序，依据指定的规则对当前集合进行排序，可以看到，排序是通过Arrays这个工具类完成的。
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

//获取指定位置的元素
E get(int index);

//修改指定位置元素的值
E set(int index, E element);

//将指定元素添加到指定的位置
void add(int index, E element);

//将指定位置的元素移除
E remove(int index);

//返回一个元素在集合中首次出现的位置
int indexOf(Object o);

//返回一个元素在集合中最后一次出现的位置
int lastIndexOf(Object o);

//ListIterator继承于Iterator，主要增加了向前遍历的功能
ListIterator<E> listIterator();

//从指定位置开始，返回一个ListIterator
ListIterator<E> listIterator(int index);

//返回一个子集合[fromIndex, toIndex)，非结构性的修改返回值会反映到原表，反之亦然。
//如果原表进行了结构修改，则返回的子列表可能发生不可预料的事情
List<E> subList(int fromIndex, int toIndex);

通过以上对接口的分析可以发现，Collection 主要提供一些通用的方法，而List 则针对线性表的结构，提供了对位置以及子表的操作。

超级实现类——AbstractList

有了分析 AbstractCollection 的经验，我们分析 AbstractList 就更容易了。首先也看下其文档中强调的部分：

To implement an unmodifiable list, the programmer needs only to extend this class and provide implementations for the get(int) and size() methods.

To implement a modifiable list, the programmer must additionally override the set(int, E) method (which otherwise throws an UnsupportedOperationException). If the list is variable-size the programmer must additionally override the add(int, E) and remove(int) methods.

大致意思是说，要实现一个不可修改的集合，只需要复写 get 和 size 就可以了。要实现一个可以修改的集合，还需要复写 set 方法，如果要动态调整大小，就必须再实现 add 和 remove 方法。

然后看下其源码实现了哪些功能吧：

//在AbstractCollection中，add方法默认会抛出异常，
//而在这里是调用了add(int index, E e)方法，但这个方法也是没有实现的。
//这里默认会把元素添加到末尾。
public boolean add(E e) {
    add(size(), e);
    return true;
}

//同上，这个只需要进行一次遍历即可
public boolean addAll(int index, Collection<? extends E> c) {
    //...   
}

接下来，还有几个方法和 Iterator 与 ListIterator 息息相关，在AbstractList 中有具体的实现，我们先看看它是如何把集合转变成 Iterator 对象并支持 foreach 循环的吧。

我们追踪源码发现，在 iterator() 方法中直接返回了一个 Itr 对象:

public Iterator<E> iterator() {
    return new Itr();
}

这样我们就明白了，它是实现了一个内部类，这个内部类实现了 Iterator 接口，合理的处理 hasNext、next、remove 方法。这个源码就不粘贴啦，其中仅仅在 remove 时考虑了一下多线程问题，有兴趣的可以自己去看看。

另外一个就是 ListIterator:

public ListIterator<E> listIterator() {
    return listIterator(0);
}

可以看到，listIterator 方法依赖于 listIterator(int index) 方法。有了上边的经验，我们可以推测，它也是通过一个内部类完成的。

public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);
    return new ListItr(index);
}

事实证明，和我们想的一样，AbstractList 内部还定义了一个 ListItr，实现了 ListIterator 接口，其实现也很简单，就不粘贴源码啦。

接下来我们看看，利用这两个实现类，AbstractList 都做了哪些事情。

//寻找一个元素首次出现的位置，只需要从前往后遍历，找到那个元素并返回其位置即可。
public int indexOf(Object o) {
    ListIterator<E> it = listIterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return it.previousIndex();
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return it.previousIndex();
    }
    return -1;
}

//同理，寻找一个元素最后一次出现的位置，只需要从列表最后一位向前遍历即可。
//看到listIterator(int index)方法是可以传递参数的，这个我想我们都可以照着写出来了。
public int lastIndexOf(Object o) {
    //...
}

//这个方法是把从fromIndex到toIndex之间的元素从集合中删除。
//clear()方法也是调用这个实现的（我认为clear实现意义并不大，因为在其上级AbstractCollection中已经有了具体实现）。
protected void removeRange(int fromIndex, int toIndex) {
    ListIterator<E> it = listIterator(fromIndex);
    for (int i=0, n=toIndex-fromIndex; i<n; i++) {
        it.next();
        it.remove();
    }
}

接下来还有两块内容比较重要，一个是关于 SubList 的，一个是关于 equals 和 hashcode 的。

我们先看看 SubList 相关的内容。SubList 并不是新建了一个集合，只是持有了当前集合的引用，然后控制一下用户可以操作的范围，所以在接口定义时就说明了其更改会直接反应到原集合中。SubList 定义在 AbstractList 内部，并且是 AbstractList 的子类。在 AbstractList 的基础上增加了对可选范围的控制。

equals 和 hashcode 的实现，也关乎我们的使用。在 AbstractList 中，这两个方法不仅与其实例有关，也和其内部包含的元素有关，所以在定义数据元素时，也应该复写这两个方法，以保证程序的正确运行。这里看下其源码加深一下印象吧。

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        //这里用到了数据元素的equals方法
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        //这里用到了数据元素的hashCode方法
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

1.18 - CH18-ArrayList

做了这么多准备，终于到了 ArrayList 了，ArrayList 是我们使用最为频繁的集合类了，我们先看看文档是如何介绍它的：

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

可见，ArrayList 是 Vector 的翻版，只是去除了线程安全。Vector 因为种种原因不推荐使用了，这里我们就不对其进行分析了。ArrayList 是一个可以动态调整大小的 List 实现，其数据的顺序与插入顺序始终一致，其余特性与 List 中定义的一致。

继承结构

可以看到，ArrayList 是 AbstractList 的子类，同时实现了 List 接口。除此之外，它还实现了三个标识型接口，这几个接口都没有任何方法，仅作为标识表示实现类具备某项功能。RandomAccess 表示实现类支持快速随机访问，Cloneable 表示实现类支持克隆，具体表现为重写了 clone 方法，java.io.Serializable 则表示支持序列化，如果需要对此过程自定义，可以重写 writeObject 与 readObject 方法。

一般面试问到与 ArrayList 相关的问题时，可能会问 ArrayList 的初始大小是多少？很多人在初始化 ArrayList 时，可能都是直接调用无参构造函数，从未关注过此问题。例如，这样获取一个对象：

ArrayList<String> strings = new ArrayList<>();

我们都知道，ArrayList 是基于数组的，而数组是定长的。那 ArrayList 为何不需要指定长度，就能使我们既可以插入一条数据，也可以插入一万条数据？回想刚刚文档的第一句话：

Resizable-array implementation of the List interface.

ArrayList 可以动态调整大小，所以我们才可以无感知的插入多条数据，这也说明其必然有一个默认的大小。而要想扩充数组的大小，只能通过复制。这样一来，默认大小以及如何动态调整大小会对使用性能产生非常大的影响。我们举个例子来说明此情形：

比如默认大小为 5，我们向 ArrayList 中插入 5 条数据，并不会涉及到扩容。如果想插入 100 条数据，就需要将 ArrayList 大小调整到 100 再进行插入，这就涉及一次数组的复制。如果此时，还想再插入 50 条数据呢？那就得把大小再调整到 150，把原有的 100 条数据复制过来，再插入新的 50 条数据。自此之后，我们每向其中插入一条数据，都要涉及一次数据拷贝，且数据量越大，需要拷贝的数据越多，性能也会迅速下降。

其实，ArrayList 仅仅是对数组操作的封装，里面采取了一定的措施来避免以上的问题，如果我们不利用这些措施，就和直接使用数组没有太大的区别。那我们就看看 ArrayList 用了哪些措施，并且如何使用它们吧。我们先从初始化说起。

构造方法与初始化

ArrayList 一共有三个构造方法，用到了两个成员变量。

//这是一个用来标记存储容量的数组，也是存放实际数据的数组。
//当 ArrayList 扩容时，其 capacity 就是这个数组应有的长度。
//默认时为空，添加进第一个元素后，就会直接扩展到 DEFAULT_CAPACITY，也就是 10
//这里和size区别在于，ArrayList扩容并不是需要多少就扩展多少的
transient Object[] elementData;

//这里就是实际存储的数据个数了
private int size;

除了以上两个成员变量，我们还需要掌握一个变量，它是:

protected transient int modCount = 0;

这个变量主要作用是防止在进行一些操作时，改变了ArrayList的大小，那将使得结果不可预测。

下面我们看看构造函数：

//默认构造方法。文档说明其默认大小为10，但正如elementData定义所言，
//只有插入一条数据后才会扩展为10，而实际上默认是空的
 public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//带初始大小的构造方法，一旦指定了大小，elementData就不再是原来的机制了。
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+                                         initialCapacity);
    }
}

//从一个其他的Collection中构造一个具有初始化数据的ArrayList。
//这里可以看到size是表示存储数据的数量
//这也展示了Collection这种抽象的魅力，可以在不同的结构间转换
public ArrayList(Collection<? extends E> c) {
    //转换最主要的是toArray()，这在Collection中就定义了
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

重要方法

ArrayList 已经是一个具体的实现类了，所以在 List 接口中定义的所有方法在此都做了实现。其中有些在 AbstractList 中实现过的方法，在这里再次被重写，我们稍后就可以看到它们的区别。

先看一些简单的方法：

//还记得在AbstractList中的实现吗？那是基于Iterator完成的。
//在这里完全没必要先转成Iterator再进行操作
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

//和indexOf是相同的道理
 public int lastIndexOf(Object o) {
    //...
}

//一样的道理，已经有了所有元素，不需要再利用Iterator来获取元素了
//注意这里返回时把elementData截断为size大小
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

//带类型的转换，看到这里a[size] = null;这个用处真不大，除非你确定所有元素都不为空，
//才可以通过null来判断获取了多少有用数据。
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // 给定的数据长度不够，复制出一个新的并返回
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

数据操作最重要的就是增删改查，改查都不涉及长度的变化，而增删就涉及到动态调整大小的问题，我们先看看改和查是如何实现的：

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

//只要获取的数据位置在0-size之间即可
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

//改变下对应位置的值
public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

增和删是ArrayList最重要的部分，这部分代码需要我们细细研究，我们看看它是如何处理我们例子中的问题的：

//在最后添加一个元素
public boolean add(E e) {
    //先确保elementData数组的长度足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

public void add(int index, E element) {
    rangeCheckForAdd(index);

    //先确保elementData数组的长度足够
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //将数据向后移动一位，空出位置之后再插入
    System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
    elementData[index] = element;
    size++;
}

以上两种添加数据的方式都调用到了 ensureCapacityInternal 这个方法，我们看看它是如何完成工作的：

//在定义elementData时就提过，插入第一个数据就直接将其扩充至10
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    
    //这里把工作又交了出去
    ensureExplicitCapacity(minCapacity);
}

//如果elementData的长度不能满足需求，就需要扩充了
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//扩充
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //可以看到这里是1.5倍扩充的
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    //扩充完之后，还是没满足，这时候就直接扩充到minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //防止溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

至此，我们彻底明白了 ArrayList 的扩容机制了。首先创建一个空数组 elementData，第一次插入数据时直接扩充至 10，然后如果 elementData 的长度不足，就扩充 1.5 倍，如果扩充完还不够，就使用需要的长度作为 elementData 的长度。

这样的方式显然比我们例子中好一些，但是在遇到大量数据时还是会频繁的拷贝数据。那么如何缓解这种问题呢，ArrayList为我们提供了两种可行的方案：

• 使用 ArrayList(int initialCapacity) 这个有参构造，在创建时就声明一个较大的大小，这样解决了频繁拷贝问题，但是需要我们提前预知数据的数量级，也会一直占有较大的内存。
• 除了添加数据时可以自动扩容外，我们还可以在插入前先进行一次扩容。只要提前预知数据的数量级，就可以在需要时直接一次扩充到位，与 ArrayList(int initialCapacity) 相比的好处在于不必一直占有较大内存，同时数据拷贝的次数也大大减少了。这个方法就是 ensureCapacity(int minCapacity)，其内部就是调用了 ensureCapacityInternal(int minCapacity)。

其他还有一些比较重要的函数，其实现的原理也大同小异，这里我们不一一分析了，但还是把它们列举出来，以便使用。

//将elementData的大小设置为和size一样大，释放所有无用内存
public void trimToSize() {
    //...
}

//删除指定位置的元素
public E remove(int index) {
    //...
}

//根据元素本身删除
public boolean remove(Object o) {
    //...
}

//在末尾添加一些元素
public boolean addAll(Collection<? extends E> c) {
    //...
}

//从指定位置起，添加一些元素
public boolean addAll(int index, Collection<? extends E> c){
    //...
}

//删除指定范围内的元素
protected void removeRange(int fromIndex, int toIndex){
    //...
}

//删除所有包含在c中的元素
public boolean removeAll(Collection<?> c) {
    //...
}

//仅保留所有包含在c中的元素
public boolean retainAll(Collection<?> c) {
    //...
}

ArrayList 还对父级实现的 ListIterator 以及 SubList 进行了优化，主要是使用位置访问元素，我们就不再研究了。

其他实现方法

ArrayList 不仅实现了 List 中定义的所有功能，还实现了 equals、hashCode、clone、writeObject 与 readObject 等方法。这些方法都需要与存储的数据配合，否则结果将是错误的或者克隆得到的数据只是浅拷贝，或者数据本身不支持序列化等，这些我们定义数据时注意到即可。我们主要看下其在序列化时自定义了哪些东西。

//这里就能解开我们的迷惑了，elementData被transient修饰，也就是不会参与序列化
//这里我们看到数据是一个个写入的，并且将size也写入了进去
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

        // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    //modCount的作用在此体现，如果序列化时进行了修改操作，就会抛出异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

readObject是一个相反的过程，就是把数据正确的恢复回来，并将elementData设置好即可，感兴趣可以自行阅读源码。

总结

总体而言，ArrayList 还是和数组一样，更适合于数据随机访问，而不太适合于大量的插入与删除，如果一定要进行插入操作，要使用以下三种方式：

• 使用 ArrayList(int initialCapacity) 这个有参构造，在创建时就声明一个较大的大小。
• 使用 ensureCapacity(int minCapacity)，在插入前先扩容。
• 使用 LinkedList，我们很快就会介绍这个适合于增删的集合类。

1.19 - CH19-Queue

今天要介绍的 Queue 就不同了，它是一个严格的排队系统。就像许多火车站排队窗口在两侧加了护栏一样，大家只能从队尾进来，从队首离开，我们称之为 FIFO(first in first out)，也就是先进来的人先离开。Queue 就严格遵循了这个原则，使插队和提早离开变得不可能。

当然 Queue 也有很多变种，FIFO 并不是其可以遵循的唯一规则。比如Stack（栈），就遵循 LIFO(last in first out)，这就好比我们叠碗一样，后来者居上。还有我们之后要分析的 Deque，其允许元素从两端插入或删除，比如排队进站时总有人说，“我能不能插个队，我赶时间？”。

超级接口——Queue

队列在软件开发中担任着重要的职责，Java 函数的调用用到了栈的技术，在处理并发问题时，BlockingQueue 很好的解决了数据传输的问题。接下来我们看看 Java 是如何定义队列的吧。

首先，Queue 也继承自 Collection，说明它是集合家族的一员。Queue 接口主要提供了以下方法：

//将元素插入队列
boolean add(E e);

//将元素插入队列，与add相比，在容量受限时应该使用这个
boolean offer(E e);

//将队首的元素删除，队列为空则抛出异常
E remove();

//将队首的元素删除，队列为空则返回null
E poll();

//获取队首元素，但不移除，队列为空则抛出异常
E element();

//获取队首元素，但不移除，队列为空则返回null
E peek();

超级实现类——AbstractQueue

Queue 的定义很简单，所以其实现类也很简单，用简单的代码做复杂的事情，值得我们学习。

AbstractQueue 仅实现了 add、remove 和 element 三个方法，并且分别调用了另外一个仅细微区别的方法，我们这里只看其一：

//这里我们就明白，对于有容量限制的，直接调用offer肯定会更快
public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}

此外，它还实现了 clear 与 addAll 方法，重写这些方法可以使其更符合当前场景。

public void clear() {
    while (poll() != null)
        ;
}

public boolean addAll(Collection<? extends E> c) {
    if (c == null)
        throw new NullPointerException();
    if (c == this)
        throw new IllegalArgumentException();
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}