首页  思维导图  详情

数据结构

2021-06-24 16:16:03   0  举报





AI智能生成

数据结构源码详解

计算机类

数据结构

学霸笔记

学习笔记

作者其他创作

大纲/内容

Java

数据结构

定义    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行速度和存储效率。

数据结构主要包含4种逻辑结构

（1）线性结构：数据可以按照某种规则排列成线性的形式。

（2）集合结构：数据元素间除“同属于一个集合”外，没有其他的任何关系。

（3）树形结构：数据元素之间呈现倒立的树形结构，每个元素有一个双亲，每个元素有0个或多个孩子，数据元素间呈现一对多的关系。

（4）网状结构：每个数据元素都有可能有多个相邻的数据元素，数据元素之间呈现一种多对多的关系。

线性表

线性表的定义

线性表是由N个相同数据类型的数据元素组成的有限序列，其中除了第一个数据元素外，每个元素有且仅有一个直接前驱结点，除最后一个数据元素外，每个元素有且仅有一个直接后继结点。

线性表数据类型主要包括两个方面

数据元素集合

数据元素集合可以表示为A0,A1,A2,...,An-1大小为N的数据集合。

该数据元素集合上的操作集合

（1）向线性表插入元素。

（2）从线性表删除元素。

（3）从线性表查找元素。

（4）判断线性表是否为空。

（5）求线性表的元素个数。

线性表的类型

线性表是一种逻辑结构，这种逻辑结构在计算机中的表现形式（存储结构）主要有以下两种

（1）线性存储：用顺序结构存储的线性表叫作顺序线性表，一般称作顺序表。顺序表一般通过高级语言中的数组类型实现。

（2）链式存储：用链式结构存储的线性表叫作链式线性表，一般称作链表。链表通常是通过定义结点的方式，通过指针（Java语言中使用的是引用）将各个数据元素和数据元素之间的关系体现出来的。

线性表常见面试考点

（1）线性表的概念。

（2）线性表的存储方式和实现方式。

（3）在线性表中操作元素的时间复杂度。

顺序表

定义   顺序表采用顺序结构存储数据，在Java语言中常用的顺序存储结构是数组。

顺序表常见面试考点

（1）顺序表的概念：顺序表是使用顺序结构存储的线性表。

（2）顺序表的存储：顺序表必须使用一块连续的存储空间存储数据。

（3）顺序表的优点：顺序表是使用顺序结构存储数据的，通过索引访问元素的时间复杂度为O(1)。

（4）顺序表的缺点：

·　顺序表的存储空间必须是连续的，如果在顺序表中存储大量数据，那么对存储介质的容量是一个挑战。

·　顺序表的存储容量是有限的、固定的，超过顺序表的存储容量将无法进行数据存储。

·　顺序表中按值查找元素的时间复杂度为O(n)。

·　在顺序表的非末尾位置添加元素将导致顺序表此位置后的元素依次向后移动。

·　在顺序表的非末尾位置删除元素将导致顺序表此位置后的元素依次向前移动。

（5）JDK中的实现：JDK中的ArrayList实现了顺序表，并提供了动态扩容等高级特性

单链表

定义  单向链表也称作单链表，是链表中很简单的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。

组成   单链表中的数据是以结点来表示的。每个结点的构成包括元素值和指向下一个结点（通常称作后继结点）的引用。单链表中第一个结点通常称作头结点。

单链表常见面试考点

（1）单链表的概念：单链表是使用链式结构存储的线性表。单链表只有一个方向。

（2）单链表的存储：单链表是使用离散的存储结构存储数据的。每个结点都保存了数据和指向后继结点的引用。

（3）单链表的优点：

·　单链表不需要使用连续的存储空间存储数据。

·　单链表没有固定的容量限制。

·　添加或删除单链表中的元素只需修改相关结点的引用，无须移动其他元素。

（4）单链表的缺点：

·　访问链表中的元素所需的时间复杂度为O(n)。

·　每个结点保存下一个结点的引用，占用更多存储空间。

·　单链表只能从头结点向后查找元素，不能从后向前查找元素。

双向链表

定义   双向链表也称作双链表，是链表的一种。双向链表是有前后两个方向的。与单链表不同的是，双向链表带有两个引用：一个是指向后一个结点（通常称作后继结点）的引用；另一个是指向前一个结点（通常称作前驱结点）的引用。

双向循环链表

双向链表的头结点没有前驱结点，双向链表的尾结点没有后继结点。为了解决头尾结点的问题，诞生了双向循环链表。双向循环链表在双向链表的基础上将头结点和尾结点进行首尾相连。双向链表只是在单链表的基础上增加了一个“反向单链表”。双向循环链表是在双向链表的基础上使双向链表首尾相连。

双向链表常见面试考点

（1）双向链表的概念：双向链表可以看成是由两个方向相反的单链表组成的。双向链表既可以从前向后遍历，又可以从后向前遍历。

（2）双向链表的存储：双向链表是使用离散的存储结构存储数据的。双向链表中每个结点都有一个指向前驱结点的引用和指向后继结点的引用。

（3）双向链表的优点：

·　双向链表不需要使用连续的存储空间存储数据。

·　双向链表没有固定的容量。

·　添加或删除单链表中的元素只需修改相关结点的引用，无须移动其他元素。

·　双向链表可以从正反两个反向进行遍历。

·　双向循环链表相比于双向链表，每个结点的属性都是完整的，没有需要单独处理的结点（不存在前驱结点或者后继结点为空的结点）。

（4）双向链表的缺点：

·　访问双向链表中的元素必须从第一个结点或者从最后一个结点开始遍历，依次访问下一个结点，直至找到所需的元素位置。因此，访问双向链表的时间复杂度为O(n)。

·　双向链表每个结点保存了前驱结点和后继结点的引用，每个结点占用更多的存储空间。

（5）JDK中的实现：JDK中的LinkedList实现了双向链表，并提供更多高级特性

栈

定义   栈的结构示意图栈是一种只允许在一端进行插入或删除的线性表，即栈只允许先进后出（First In Last Out，FILO）或者后进先出（Last In First Out，LIFO）。

栈基础知识点

栈的操作端通常被称为栈顶，另一端被称为栈底

栈的插入操作称为压栈（Push）

压栈是把新元素放到当前栈顶元素的上面，并使之成为新的栈顶元素

栈的删除操作称为出栈（Pop）

出栈则是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素

栈的实现方式（主要分为2种）

一种是基于顺序结构实现的

基于顺序结构存储的栈称为顺序栈（基于数组实现）

一种是基于链式结构实现的

基于链式结构存储的栈称为链式栈

总结    无论是基于何种形式实现的栈，一般都要实现这几个方法，分别是判断栈是否为空、判断栈是否已满、压栈操作和出栈操作。

值得说明的是，由于链表离散存储的特性，在链式栈中无须检测栈是否已满，只要内存足够大，理论上链式栈是不会满的。

栈常见面试考点

（1）栈的概念：栈是只允许在一端进行操作的线性表。

（2）栈的特点：先进后出／后进先出。

（3）栈的存储：

·　顺序栈：顺序存储结构。

·　链式栈：链式存储结构。

·　栈的相关算法：如软件开发人员使用的编辑器中的括号匹配问题。

（4）JDK中的实现：JDK中的Stack类实现了栈，并实现了线程安全的API供开发人员使用。

对应总结文档中   栈应用之括号匹配问题

队列

队列    定义：队列是在一端进行插入操作，另一端进行删除操作的线性表。队列只允许先进先出（First In First Out，FIFO）。

1.顺序队列  顺序队列是基于顺序结构实现的队列

实现方式

（1）队列头部不移动，队列头部后的所有元素向前移动，以这种方式实现的出队缺点是每次队列头部的元素出队后，需要依次移动队列头部后的所有元素，出队效率不高。

（2）队列头部移动，出队后队列头部向后移动一个位置，这种方式实现的出队会造成“假溢出现象”，即顺序队列因多次入队列和出队列操作后出现尚有存储空间但不能进行入队列操作的溢出

2.循环队列   为了有效解决假溢出的问题，当顺序结构存储的队列中的元素到达最大容量后，从头开始重新利用未使用的存储空间，即形成头尾相连的循环。这种首尾相连的存储结构实现的队列称为循环队列

出现问题：循环队列在队列为空和队列已满时，队头和队尾都会相遇。此时仅用队头和队尾相遇这个条件将不能有效区分队列是否为空或者队列是否已满。为了解决以上问题，可以使用如下改进方案。假设队尾位置是tail，队头位置为head，队列最大容量为capacity。

【方案1】设置一个标志位flag，初始时flag=0，每当入队成功设置flag=1，每当出队成功设置flag=0。在【方案1】的前提下，重新分析队列为空和队列已满的情况。

（1）队列为空的条件为：head=tail并且flag=0。

（2）队列已满的条件为：head=tail并且flag=1。

【方案2】预留一个存储空间不使用。在【方案2】的前提下，重新分析队列为空和队列已满的情况。

（1）队列为空的条件为：(head+1) % capacity = tail。

（2）队列已满的条件为：(tail+1) % capacity = head。

方案3】设计一个计数器count，统计队列中的元素个数。在【方案3】的前提下，重新分析队列为空和队列已满的情况。

（1）队列为空的条件为：count=0。

（2）队列已满的条件为：count=capacity。

3.链式队列   链式队列是使用链式存储方式实现的队列

4.优先队列   在优先队列中，元素被赋予优先级。优先队列入队与其他队列没有差别。当出队时，具有最高优先级的元素最先出队。优先队列具有最高级先出（First In LargestOut）的特点。

实现方法

（1）最大优先队列：无论入队顺序，当前最大的元素优先出队

（2）最小优先队列：无论入队顺序，当前最小的元素优先出队。

队列常见面试考点

（1）队列的概念：队列是在一端进行插入操作，另一端进行删除操作的线性表。

（2）队列的特点：先进先出。

（3）队列的存储：

顺序队列

链式队列

（4）JDK中的实现：JDK中的LinkedList实现了队列，PriorityQueue实现了优先队列。

树

树     定义：树（Tree）是n（n≥0）个结点组成的有限集合。当n=0时，称为空树。当n>0时，称为非空树。

非空树的特性

（1）有且仅有一个根（Root）结点。

（2）当n>1时，除根结点以外的其他结点可以分为m（m>0）个互不相交的有限集合S1,S2,S3,...,Sm，每个集合本身也是一棵树，这些树称为根结点的子树。

从以上非空树的特性可知，树结构是一个递归的过程。根结点拥有子树，子树中的每个结点也可以拥有子树。

树结构的相关概念

1．结点的度

结点拥有的子树的数量称为结点的度。

2．结点的关系

结点子树的根结点称作该结点的子结点（也可以称作孩子结点）。相应地，该结点称作孩子结点的父结点（也可以称作双亲结点）。

同一个父结点的所有子结点之间互相称作兄弟结点。

3．结点的层次

从根结点开始，根结点称为第1层，根结点的孩子称为第2层，以此类推。

4．树的高度

树中结点的最大层次称为树的高度（或者称为深度）。

5．树的叶结点

如果一个结点没有任何子结点，那么称这个结点为叶结点。

二叉树

定义：二叉树是n（n≥0）个结点组成的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的子树组成，这两棵子树分别称为根结点的左子树和右子树

二叉树的特点

（1）二叉树中每个结点最多有两棵子树，即二叉树中不存在度大于2的结点。

（2）二叉树是区分左子树和右子树的，左子树和右子树不能随意颠倒。

（3）即使二叉树中某个结点只有一棵子树，这棵子树也是要区分左子树和右子树的。

（4）在二叉树中，第i层最多有2i-1个结点（i≥1）。

（5）高度为h的二叉树，最多有2h-1个结点（h≥1）。

（6）n0=n2+1，其中n0表示度为0的结点数，n2表示度为2的结点数。

其他特殊二叉树

斜树  斜树的定义是基于二叉树的，即斜树仍然是一棵二叉树。

（1）左斜树：是一种所有的结点都只有左子树的二叉树或者没有子树的一种特殊的二叉树。

（2）右斜树：是一种所有的结点都只有右子树或者没有子树的一种特殊的二叉树。

满二叉树

定义   所有结点都存在左子树和右子树，并且所有的叶子结点都在同一层上的二叉树，称为满二叉树。

满二叉树的特点

（1）所有的叶子必须出现在最后一层。

（2）非叶子结点的度一定是2。

（3）在同样高度的二叉树中，满二叉树的总结点数最多，满二叉树的叶子结点数最多。

完全二叉树

定义   完全二叉树是由满二叉树引出的。对一棵高度为h，具有n个结点的二叉树，当且仅当每个结点都与深度为h的满二叉树中编号为1～n的结点一一对应时，称这棵二叉树为完全二叉树。

完全二叉树的特点

（1）叶子结点只能在最后一层或者倒数第二层。

（2）最下层的叶子结点集中在完全二叉树的左边。

（3）倒数第二层如果存在叶子结点，那么一定集中在完全二叉树的右边。

（4）如果结点的度为1，那么该结点只能有左子树，没有右子树。

（5）同样结点数目的二叉树，完全二叉树高度最小。

（6）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

二叉排序树

定义    二叉排序树又称二叉查找树或二叉搜索树。二叉排序树是一种特殊的二叉树

二叉排序树的特点

（1）如果左子树非空，那么左子树上所有结点的值都小于根结点的值。

（2）如果右子树非空，那么右子树上所有结点的值都大于根结点的值。

（3）每个结点的左子树和右子树都必须是二叉排序树。

（4）二叉树的所有结点中没有值相等的结点。

二叉排序树增删改查

1．二叉排序树查找元素  过程如下

（1）判断根结点的值是否等于查找的值，如果相等，就返回，否则执行（2）。

（2）如果查找的值小于结点的值，就递归查找左子树。

（3）如果查找的值大于结点的值，就递归查找右子树。

（4）二叉排序树中不存在值相等的结点。

总结：二叉排序树的查找过程的时间复杂度是O(log2n)。

2．二叉排序树添加元素

二叉排序树添加元素需要经历查找过程，通过二叉排序树的查找过程找到待添加元素的合适的位置，以保证添加元素后仍满足二叉排序树的要求。

3．二叉排序树删除元素   二叉排序树删除元素分为3种情况（删除代码还没会）(已会)

（1）删除的结点是叶子结点

在二叉排序树中删除叶子结点不会破坏二叉排序树的结构，可以直接删除。

（2）删除的结点只有左子树或者右子树

在二叉排序树中删除的结点仅有左子树或者右子树，使用左子树或者右子树的根结点替换删除的结点，删除指定的结点。

（3）删除的结点有左子树和右子树

删除的结点有左子树和右子树，删除该结点后，需要对二叉排序树进行调整。

调整的方式有两种

【方案1】从删除的结点的左子树中，找到左子树最右边的结点，即左子树中最大的结点，替换删除的结点；然后进行后续的调整。

【方案2】从删除的结点的右子树中，找到右子树最左边的结点，即右子树中最小的结点，替换删除的结点；然后进行后续的调整。

AVL树

定义    AVL树本质上是一棵自平衡的二叉排序树。

AVL树特点

（1）AVL树是一棵空树或它的左右两棵子树的高度差的绝对值不超过1。

（2）AVL树每个结点的左右两棵子树都是一棵平衡二叉树。

总结：AVL树中有一个重要的概念叫作平衡因子。平衡因子指左子树与右子树高度差的绝对值。

平衡因子=|左子树高度-右子树高度|

AVL树的平衡因子的取值范围是：-1≤平衡因子≤1。

AVL树的基本操作

AVL树的插入和删除可能会破坏AVL树的平衡性。在插入或删除元素后，从变更的结点开始向根结点回溯，遇到的第一个不平衡的结点称为“最低失衡根结点”。从最低失衡根结点向下分析，不平衡的情况可以分为4种情况：

（1）导致失衡的结点出现在最低失衡根结点的左子树的左子树中。

（2）导致失衡的结点出现在最低失衡根结点的左子树的右子树中。

（3）导致失衡的结点出现在最低失衡根结点的右子树的右子树中。

（4）导致失衡的结点出现在最低失衡根结点的右子树的左子树中。

两种调整AVL树使之平衡的基本操作

①左旋转

当向AVL树插入元素后，右子树的高度减去左子树的高度大于1，此时发生左旋转，即AVL树向左旋转（大的上来）

②右旋转

当向AVL树插入元素后，左子树的高度减去右子树的高度大于1，此时发生右旋转，即AVL树向右旋转（小的上来）

对各种不平衡的情况进行分析

（1）LL情况旋转

LL（Left-Left）旋转即导致失衡的结点出现在最低失衡根结点的左子树的左子树中而发生结点旋转的情况。旋转方式是找到最低失衡根结点，将最低失衡根结点右旋转

（2）LR情况旋转

LR（Left-Right）旋转即导致失衡的结点出现在最低失衡根结点的左子树的右子树中而发生旋转的情况。旋转方式是找到最低失衡根结点，先对最低失衡根结点的左孩子进行左旋转，然后对最低失衡根结点进行右旋转

（3）RR情况旋转

RR（Right-Right）旋转即导致失衡的结点出现在最低失衡根结点的右子树的右子树中而发生旋转的情况。旋转方式是找到最低失衡根结点，将最低失衡根结点左旋转

（4）RL情况旋转

RL（Right-Left）旋转即导致失衡的结点出现在最低失衡根结点的右子树的左子树中而发生旋转的情况。旋转方式是找到最低失衡根结点，先对最低失衡根结点的右孩子进行右旋转，然后对最低失衡根结点进行左旋转

2-3-4树

定义    2-3-4树是一棵单个结点可以存储多个元素值的完美平衡（Perfect Balance）的查找树。所谓完美平衡，指的是从2-3-4树的根结点到每个叶子结点的路径的高度都是相等的。2-3-4树是一种进阶的二叉树，是一种自平衡的数据结构，它可以保证O(log2n)的时间内完成查找、插入和删除操作。

2-3-4树特点

（1）每个结点可以存储1个、2个或者3个元素值，相应的称这些结点为2（孩子）结点、3（孩子）结点、4（孩子）结点。

（2）根结点到所有的叶子结点的路径长度相等。

（3）每个结点的元素值从左到右保持了从小到大的顺序。两个元素值之间的子树中所有结点的元素值一定大于其父结点的左边的元素值，小于其父结点的右边的元素值。

（4）2结点的左子树上的所有元素值小于其父结点的元素值。2结点右子树上的所有元素值大于其父结点的元素值。

（5）3结点的左子树的所有元素值小于其父结点最小的元素值。3结点中间子树的所有元素值大于其父结点最小的元素值，小于其父结点最大的元素值。3结点的右子树上的所有元素值大于其父结点的最大元素值。同理，4结点也满足这样的性质。

2-3-4树的查找元素

2-3-4树查找元素的过程与二叉排序树类似，首先比较查找的元素值与根结点的大小，如果元素值不存在于根结点中，就选择元素值所在的子树，递归上述过程，直至找到元素

2-3-4树添加元素

（1）如果2-3-4树中已存在当前插入的key，就会插入失败，否则通过查找过程找到合适的位置，在叶子结点中进行插入操作。

（2）如果待插入的结点不是4结点，那么直接在该结点插入新元素即可。

（3）如果待插入的结点是4结点，那么应该先分裂该结点再插入。一个4结点可以分裂成一个根结点和两个子结点（这3个结点各含一个元素值），然后在子结点中插入，可以把分裂形成的根结点中的元素值看成向上层结点插入的一个元素值。

（4）重复第2步和第3步，直至2-3-4树达到完美平衡。

2-3-4树删除元素

步骤：

（1）如果删除的元素不存在于2-3-4树中，就会删除失败。

（2）删除的元素不存在于叶子结点，用后继结点替代删除的结点。

（3）删除的元素位于叶子结点，如果叶子结点不是2结点，那么直接删除元素即可。如果删除的元素是2结点，那么删除该结点后需要进行如下调整：

①如果兄弟结点不是2结点，就将父结点中的一个元素值下移到该结点，兄弟结点中的一个元素值上移到父结点。

②如果兄弟结点是2结点，父结点是3结点或者4结点，父结点中的元素值就与兄弟结点中的元素值合并。

③如果兄弟结点是2结点，父结点是2结点，父结点中的元素值就与兄弟结点中的元素值合并，形成一个新的3结点，以新的3结点作为当前结点，重复①和②的步骤进行调整。

执行效率

（1）2-3-4树高度的最坏情况（全是2结点），相当于演变成了平衡二叉树，其查询的时间复杂度为O(log2n)。

（2）2-3-4树高度的最好情况（全是4结点），O(log4n )= 1/2 O(log2n)（但这种情况是不可能出现的，因为4结点的父结点或者子结点不能是4结点）。

（3）对于100万个结点，2-3-4树的高度为10～20。

4）对于10亿的结点，2-3-4树的高度为15～30。

由此来看，2-3-4树的效率比平衡二叉树要好，但是问题在于2-3-4树并不好实现。首先，需要用3种不同类型的结点代表2结点、3结点和4结点。其次，在插入结点时，可能需要进行大量的切分4结点的工作，也可能需要频繁地在3种结点之间进行转换。   为了更好地利用2-3-4树平衡高度的特点，同时又便于实现，于是诞生了红黑树

红黑树

定义    红黑树是与2-3-4树一一对应的树形结构，由于大部分编程语言直接实现2-3-4树很烦琐，因此一般是通过红黑树来实现2-3-4树的。红黑树同样可以保证在O(log2n)时间内完成查找、插入和删除操作。红黑树是每个结点都带有红色或黑色属性的平衡二叉排序树。红黑树除了满足一般二叉排序树的要求外，红黑树还需要满足以下要求：

（1）每个结点必须带有颜色，红色或者黑色。

（2）根结点一定是黑色。

（3）每个叶子结点都带有两个空的黑色子结点（NIL结点，又称为黑色哨兵）。

（4）每个红色结点的两个子结点都是黑色结点，即从根结点到叶子结点的所有路径上，不存在两个连续的红色结点。

（5）从任一结点到其所能到达的叶子结点的所有路径含有相同数量的黑色结点。

红黑树是一个基本平衡的二叉排序树，红黑树并没有像AVL树一样保持绝对平衡，但是同样数量的结点组成的红黑树比AVL树少了很多旋转操作，且红黑树的删除效率比AVL树更高

红黑树同2-3-4树的等价关系

（1）3结点与红黑树的对应关系（可以红黑也可以黑红，导致一棵红黑树对应一棵唯一形态的2-3-4树，但是一棵2-3-4树可以对应多种形态的红黑树）

（2）4结点与红黑树的对应关系

红黑树添加元素

（1）如果红黑树中已存在待插入的值，那么插入操作失败，否则一定是在叶子结点进行插入操作，执行步骤（2）。

（2）插入一个新结点后，将该结点涂红（涂红操作，从2-3-4树的角度来看，就是向上层结点进位一个元素值），由于插入操作可能破坏了红黑树的平衡性，因此需要不断回溯，进行调整。调整过程就是颜色变换和旋转操作，而这些操作都可以结合2-3-4树来理解。

插入新结点时，可以分为以下几种情况

（1）父结点是黑色结点

如果父结点是黑色结点，插入新结点后，给结点涂红色即可

（2）父结点是红色的且叔叔结点是黑色的

这种情况需要对当前的红黑树进行相应的调整，以使红黑树恢复平衡。这种情况相当于2-3-4树中，容纳进位的父结点为3结点，还有空间可以容纳新的元素值，所以到这里就不用继续回溯了。

这种情况分别有以下4种形态：

①不平衡的红色结点是左子树中红色父结点的左孩子

需要进行一次右旋转

②不平衡的红色结点是左子树中红色父结点的右孩子

需要进行一次左旋转，再进行一次右旋

③不平衡的红色结点是右子树中红色父结点的右孩子

需要进行一次左旋转

④不平衡的红色结点是右子树中红色父结点的左孩子

需要进行一次右旋转，再进行一次左旋

（3）父结点是红色的且叔叔结点是红色的

这种情况相当于2-3-4树中，向上进位的父结点为4结点，所以先分裂，再插入新的元素并继续回溯，把分裂出的父结点看成向更上一层进位的结点继续回溯。

这种情况分别有以下4种形态：

①不平衡的红色结点是左子树中红色父结点的左孩子

②不平衡的红色结点是左子树中红色父结点的右孩子

③不平衡的红色结点是右子树中红色父结点的右孩子。

④不平衡的红色结点是右子树中红色父结点的左孩子。

红黑树删除元素

（1）如果在红黑树中不存在要删除的元素值，就会删除失败，否则执行（2）。

（2）如果删除的结点不是叶子结点，就用删除结点的后继结点替换，颜色不需要改变。

删除结点可以分为以下几种情况

（1）要删除的结点为红色叶子结点

直接删除该结点即可

（2）要删除的结点是一个黑色结点且只有一个孩子结点

如果要删除的结点只有一个孩子结点，那么这个孩子结点一定是红色结点。删除此结点后，孩子结点上移并涂黑色。

（3）要删除的结点是一个黑色叶子结点

删除黑色叶子结点后需要对红黑树进行调整，使之重新达到平衡。调整的情况分为以下a、b、c和d所示的4种。其中未着色的结点可以为红色或黑色。

a）删除的结点的兄弟结点为黑色结点且侄子结点为红色，这种情况分为以下1、2、3和4这四种不同的情况。

①删除的黑色叶子结点是父结点的右子结点，且其兄弟结点为黑色结点，且左侄子结点为红色的情况

②删除的黑色叶子结点是父结点的右子结点，且其兄弟结点为黑色结点，且右侄子结点为红色的情况。

③删除的黑色叶子结点是父结点的左子结点，且其兄弟结点为黑色结点，且右侄子结点为红色的情况。

④删除的黑色叶子结点是父结点的左子结点，且其兄弟结点为黑色结点，且左侄子结点为红色的情况。

b）删除的结点的兄弟结点为黑色结点，且侄子结点为黑色结点，且父结点是红色结点（侄子结点只能是NIL结点，因为删除的结点是叶子结点）。

c）删除的结点的兄弟结点、侄子结点、父结点都是黑色结点（侄子结点只能是NIL结点，因为删除的结点是叶子结点）。

d）删除的结点的兄弟结点是红色结点，父结点是黑色结点。

哈夫曼树

定义     哈夫曼树（Huffman Tree）又称最优二叉树，是一种带权路径长度最短的树。

哈夫曼树的特性

（1）满二叉树不一定是哈夫曼树。

（2）哈夫曼树中权越大的叶子离根越近。

（3）相同带权结点生成的哈夫曼树不唯一。

（4）哈夫曼树的结点的度数为0或2，没有度为1的结点。

（5）包含n个叶子结点的哈夫曼树中共有2n–1个结点。

（6）包含n棵树的森林要经过n–1次合并才能形成哈夫曼树，共产生n–1个新结点。

哈夫曼树的应用

哈夫曼编码就是哈夫曼树在电信通信中的应用之一。哈夫曼树广泛地用于数据文件压缩，其压缩率通常为20%～90%。在电信通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。

二叉树存储结构

1．二叉树顺序存储结构

定义：二叉树的顺序存储结构使用一维数组存储二叉树中的结点，并且通过数组下标表示结点在二叉树中的位置。

缺点：当用顺序存储结构存储左斜树或者右斜树时，将会造成更大的空间浪费。因此，顺序存储结构仅适用于完全二叉树的存储。

2．二叉树链式存储结构

data表示结点的数据域，leftChild表示结点的左子树的引用，rightChild表示结点的右子树的引用。（名字自己定义）

二叉树的遍历

定义    二叉树的遍历指从二叉树的根结点出发，按照某种次序依次访问二叉树中所有结点的过程。

遍历方法

（1）二叉树前序遍历

前序遍历的顺序是：首先遍历根结点，然后递归遍历左子树，最后递归遍历右子树。

（2）二叉树中序遍历

中序遍历的顺序是：首先递归遍历左子树，然后遍历根结点，最后递归遍历右子树。

（3）二叉树后序遍历

后序遍历的顺序是：首先递归遍历左子树，然后递归遍历右子树，最后遍历根结点。

（4）二叉树层次遍历

层次遍历是按照树的层次自上而下遍历二叉树中的所有结点。

树常见面试考点

（1）二叉树的概念。

（2）二叉树的存储。

（3）二叉树的遍历。

·　前序遍历。

·　中序遍历。

·　后序遍历。

·　层次遍历。

（4）二叉排序树的实现及其优缺点。

（5）AVL树的优缺点。

（6）红黑树的原理及JDK对红黑树的应用。

（7）哈夫曼的编码及解码。

树和森林

普通树转化为二叉树

转化步骤如下

（1）在普通树的兄弟结点之间加一条线，使兄弟结点互连

（2）对于树中的每个结点，只保留其与第一孩子结点的连线，删除结点与其他孩子结点之间的连线

（3）调整树的层次结构。以树的根结点为轴心，将整棵树旋转一定的角度，使树结构层次分明

森林转化为二叉树

森林由多棵树组成。森林可以转化为二叉树，转化步骤如下

（1）将森林中的每棵树转化为二叉树

（2）保持第一棵不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来

（3）调整树的层次结构。以树的根结点为轴心，将整棵树旋转一定的角度，使树结构层次分明

树的遍历

树的遍历分为以下两种

（1）先根遍历。先访问树的根结点，再依次先根遍历根的每棵子树。

（2）后根遍历。先依次遍历每棵子树，再访问根结点。

森林的遍历

森林的遍历也分为先跟遍历和后根遍历，其实就是按照树的先根遍历和后根遍历依次访问森林的每一棵树。

树和森林常见面试考点

（1）普通树与二叉树间的转换。

（2）森林与二叉树间的转换。

（3）树的遍历方式。

（4）森林的遍历方式。

图

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

图的相关概念

（1）顶点。顶点是图的基本单元之一，相当于树中的结点。

（2）边。图中顶点之间的关联关系。

（3）无向边。若两个顶点之间的边没有方向，则称这条边为无向边。

（4）无向图。任意两个顶点之间的边都是无向边的图称为无向图。

（5）有向边。若两个顶点之间的边是有方向的，则称为有向边。

（6）有向图。任意两个顶点之间的边都是有向边的图称为有向图。

（7）简单图。不存在自环（指向顶点自身的边）和重边（完全相同的多条边）的图。

（8）无向完全图。任意两个顶点间都存在边的无向图称为无向完全图。

（9）有向完全图。任意两个顶点间都存在方向相反的两条边的有向图称为有向完全图。

（10）稀疏图。只有很少条边组成的图称为稀疏图。

（11）稠密图。有很多条边组成的图称为稠密图。

（12）权重。从图中一个顶点到另一个顶点的距离或耗费。

（13）带权图。带有权重的图称为带权图。

（14）度。与顶点相连接的边的数目称为度。

（15）出度。有向图中的概念，出度表示以此顶点为起点的边的数目。

（16）入度。有向图中的概念，入度表示以此顶点为终点的边的数目。

（17）环。开始顶点和结束顶点相同的路径称为环。

（18）简单环。除去第一个顶点和最后一个顶点后没有重复顶点的环。

（19）连通图。任意两个顶点都互相连通的图。

（20）非连通图。存在不能互相连通的顶点的图称为非连通图。

（21）极大连通子图。加入任何一个不在图的点都会导致图不再连通，此时的图就是极大连通子图。连通图的极大连通子图是自身，非连通图存在多个极大连通子图。

（22）连通分量。无向图的极大连通子图称为连通分量。任何连通图的连通分量只有一个，就是其自身，非连通的无向图有多个连通分量。

（23）生成树。对连通图进行遍历，过程中所经过的边和顶点的组合可看作一棵普通树，通常称为生成树。

（24）最小生成树：对连通图来说，边的权重之和最小的生成树称为最小生成树。

（25）AOV网。用顶点表示活动，用边表示活动间的优先关系的有向图称为AOV网。

（26）AOE网。带权有向图中以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图称为AOE网。

图的存储

分析

图的结构比较复杂，任意两个顶点之间都可能存在关系，因此用简单的顺序存储来表示图是很难实现的，而若使用多重链表的方式（一个数据域、多个指针域的结点来表示），则会出现严重的空间浪费或操作不便。图的常用存储结构有邻接矩阵、邻接表和十字链表。

常用存储结构

图的邻接矩阵存储结构

邻接矩阵（Adjacency Matrix）使用两个数组存储图，其中一个一维数组用于存储图中的顶点，另一个二维数组存储顶点之间的边的信息。

邻接矩阵的优点

邻接矩阵的结构简单，操作方便。

邻接矩阵的缺点

邻接矩阵存储稀疏图，将会造成大量的空间浪费。

图的邻接表存储结构

邻接表是一种将数组与链表相结合的存储方法。其具体实现为：将图中顶点用一个一维数组存储，每个顶点所有邻接点用一个单链表来存储。

图的十字链表存储结构

十字链表（Orthogonal List）是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。

图的遍历

定义  从图的某个顶点出发，遍历图中其余顶点，且使每个顶点仅被访问一次，这个过程叫作图的遍历（Traversing Graph）。

对于图的遍历通常有两种方法

深度优先遍历

图的深度优先遍历思想：从图中某个顶点出发，首先访问此顶点，然后依次从该顶点相邻的顶点出发深度优先遍历，直至图中所有与该顶点路径相通的顶点都被访问；若此时图中还有顶点未被访问，则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。

实现步骤

（1）将该顶点标记为已访问。

（2）以递归地方式访问该顶点的所有未被标记过的邻接点。

广度优先遍历

广度优先遍历（Breadth First Search，BFS）又称为广度优先搜索。图的广度优先遍历思想：从图的某个顶点出发，首先访问该顶点，然后依次访问与该顶点相邻的未被访问的顶点，接着分别从这些顶点出发，进行广度优先遍历，直至所有的顶点都被访问完。

最小生成树

图的生成树是图的一个含有其所有顶点的无环连通子图。一幅加权图的最小生成树（Minimum Spanning Tree，MST）是其权值（所有边的权值之和）最小的生成树

Prim算法求解最小生成树

定义  普里姆（Prim）算法，是用来求加权连通图的最小生成树的算法。

Prim算法的基本思想：对于图G及其所有顶点的集合V，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有U和V-U（V-U表示V中除去U的所有顶点）的边中选取权值最小的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。

Kruskal算法求解最小生成树

定义   克鲁斯卡尔（Kruskal）算法是一种用来求加权连通图的最小生成树的算法。

Kruskal算法的核心思想：依权值从小到大从连通图中选择边加入森林中，并使森林中不产生回路，直至森林变成一棵树为止。

Dijkstra算法求解最短路径

迪杰斯特拉（Dijkstra）算法是用于计算一个顶点到其他顶点的最短路径的算法。Dijkstra的主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。

图的常见面试考点

（1）图的概念。

（2）图的存储方式。

（3）图的遍历方式。

（4）图的最小生成树算法。

（5）图的最短路径算法。

集合框架

Java集合框架的基础接口

（1）Collection为集合框架的基础接口之一。一个集合代表一组对象，这些对象即为集合的元素。Java平台不提供这个接口任何直接的实现。

（2）Set是一个不能包含重复元素的集合。

（3）List是一个可以包含重复元素的集合。

（4）Map是一个将key映射到value的对象。一个Map不能包含重复的key，每个key最多只能映射一个value。

（5）Queue是JDK对数据结构中队列结构的实现。

（6）Iterable接口的实现类可以通过for-each语法进行遍历。

ArrayList

定义    ArrayList是允许含有重复元素的集合工具

ArrayList类的声明

ArrayList是顺序表的一种实现，在顺序表的基础上提供了更加丰富的功能。ArrayList继承了AbstractList类，实现了List、RandomAccess、Cloneable、Serializable接口。

ArrayList类的属性

// 默认的初始化容量 private static final int DEFAULT_CAPACITY = 10; // 空数组。无参构造器中创建空对象时用到 private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组。用于控制当ArrayList加入新元素时，计算扩容的容量 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // ArrayList存放元素的数组 transient Object[] elementData; // ArrayList包含的元素个数 private int size;

从ArrayList类的属性可以看出，ArrayList类是基于数组实现的线性表，并且用size属性记录ArrayList对象中包含的元素的个数，因此获取ArrayList对象的大小的时间复杂度为O(1)，因为不需要对ArrayList对象中的每个元素进行遍历。

ArrayList类的方法

ArrayList类的构造器

数组的初始容量为10

ArrayList类添加元素的方法

add(E e)

add(int index, Eelement)

总结：grow()扩容方法首先将容量扩容到原容量的1.5倍，如果扩容后的新容量newCapacity仍然小于最小容量minCapacity，就设置新的容量newCapacity为最小的容量minCapacity。如果新的容量newCapacity大于MAX_ARRAY_SIZE，就需要通过hugeCapacity()方法再次计算新的容量newCapacity的大小。确定了新的容量newCapacity后，Arrays.copyOf()方法将旧数组中的元素拷贝到新的数组中，返回新容量的数组。 /** * int newCapacity = oldCapacity + (oldCapacity >> 1); * 即 newCapacity = 1.5 * oldCapacity； * @param newCapacity 新的容量 */

ArrayList类查询元素方法

已知位置信息，查询ArrayList中的元素

get()方法

已知元素信息，查询ArrayList中的位置信息或者ArrayList是否包含指定元素

indexOf()方法

lastIndexOf()方法

contains()方法

ArrayList类更新元素方法

set()方法

ArrayList类删除元素方法

remove(int index)

remove(Object o)

ArrayList类批量方法

addAll(Collection<? extends E> c)方法

批量将另一个集合中的元素加入ArrayList的末尾

addAll(int index, Collection<? extends E> c)方法

可以指定将另一个集合中的元素插入ArrayList指定的位置后

removeAll(Collection<?> c)方法

删除ArrayList与另一个集合c的交集部分。

retainAll(Collection<?> c)方法

与removeAll(Collection<?> c)方法互为相反操作

ArrayList类导出数组方法

toArray()方法

toArray()方法用于返回一个包含ArrayList中所有元素的数组。

toArray(T[] a)方法

用于返回一个包含ArrayList中所有元素的指定类型的数组

ArrayList类排序方法

ArrayList提供的sort()方法可以实现对ArrayList中的元素进行排序

sort()方法根据传入的比较器Comparator调用Arrays.sort()方法进行排序。

TimSort.sort()使用自定义比较器进行排序 /** * 判断是否使用JDK1.6之前的经典算法(LegacyMergeSort 经典归并排序) * 如果JDK在1.6之后，使用TimSort算法 */ if (Arrays.LegacyMergeSort.userRequested) legacyMergeSort(a, fromIndex, toIndex, c); else TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);

如果不指定比较器，就会通过Arrays类的重载的sort()方法进行排序。

ComparableTimSort.sort()使用元素的自然顺序进行排序。所谓的自然顺序，即实现了Comparable接口的类，如Integer类或者String类等，这些类的对象可以直接进行大小比较，因为没有自定义的比较器也可以对其进行排序。

ArrayList类的迭代器

iterator()方法

iterator()方法用于遍历和迭代ArrayList中的元素，iterator()方法将返回一个内部类Itr对象

listIterator()方法

ListIterator接口比Iterator接口多了向前迭代和添加、修改元素等操作。返回一个内部类ListItr类的对象

Itr类属性

int cursor; // 下一个将要返回的元素的索引位置

int lastRet = -1; // 上一个返回的元素的索引位置。如果没有就返回-1

int expectedModCount = modCount; // expectedModCount初始值等于父类AbstractList中的modCount

Itr类方法

hasNext()方法

用于判断是否还有下一个元素可以迭代。

next()方法

用于返回ArrayList中的下一个元素。有checkForComodification()方法

remove()方法

用于删除此迭代器返回的最后一个元素。有checkForComodification()方法

forEachRemaining()方法

用于对剩余元素执行给定操作。有checkForComodification()方法

总结：  源码中的checkForComodification()方法用于检测迭代器执行过程中是否有并发修改，如果有并发修改，就会抛出ConcurrentModificationException异常。此异常的作用通常是阻止并发修改ArrayList对象。例如，当一个线程通过迭代器修改一个ArrayList时，另一个线程修改ArrayList是不允许的。迭代器通过ConcurrentModificationException异常阻止这种情况的发生，这种迭代器也称作fast-fail迭代器。

ListItr类方法

hasPrevious()方法

判断迭代器是否还有前一个元素。

nextIndex()方法

返回下一个将返回的元素的位置。

previousIndex()方法

用于返回前一个元素的索引位置。

previous()方法

用于返回前一个元素

set()方法

用于更新元素值

add()方法

用于添加元素。

ArrayList常见面试考点

（1）ArrayList是基于顺序表实现的容器。

（2）ArrayList存储模型。

（3）ArrayList查找的时间复杂度。

（4）ArrayList迭代器。

（5）ArrayList线程安全问题及与之对应的并发容器。

LinkedList

定义  LinkedList是实现了List接口和Deque接口的双向链表。

LinkedList类的声明

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

从声明可知，LinkedList实现了List接口和Deque接口，因此LinkedList既可以当作链表使用，又可以当作队列使用。

LinkedList类的属性

// 链表元素(结点)的个数 transient int size = 0; // 指向第一个结点的引用，即链表的头结点 transient Node<E> first; // 指向最后一个结点的引用，即链表的尾结点 transient Node<E> last;

LinkedList类的内部类Node

Node类是LinkedList的静态内部类，也是组成LinkedList最小的基本单元。

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

LinkedList的方法

ArrayList类的构造器

无参构造器

带有集合参数的构造器LinkedList(Collection<? extends E> c)

public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

LinkedList类添加元素方法

add(E element)方法

向链表的尾部添加元素。

add(int index, E element)方法

在index位置添加元素。

LinkedList类查询元素的方法

get(int index)方法

返回链表指定位置存储的元素值。

indexOf(Object o)方法

返回在链表中指定元素第一次出现的位置。

lastIndexOf(Object o)方法

返回指定元素在链表中最后一次出现的位置。

contains(Object o)方法

用于判断链表中是否含有指定的元素。

LinkedList类更新元素方法

set(int index, E element)方法

用于将LinkedList指定位置的元素更新为新的值。

LinkedList类删除元素的方法

remove()方法用于从LinkedList中删除元素。remove()方法有两个重载的方法

remove(int index)

用于删除链表指定位置的元素。

remove(Object o)

用于删除链表中的指定元素。

LinkedList类批量方法

addAll()方法。addAll()方法有两个重载的方法

addAll(Collection<? extends E> c)

默认将集合c中的所有元素添加到链表的尾部。

addAll(int index, Collection<? extends E> c)

指定集合c插入的位置

clear()方法

从链表中删除所有元素。

LinkedList类的迭代器

（第一步）LinkedList类的父类AbstractSequentialList中含有iterator()方法，iterator()方法返回LinkedList类的迭代器（第三步）。 public Iterator<E> iterator() { return listIterator(); }

（第二步）iterator()方法调用的listIterator()方法位于其父类AbstractList中。 public ListIterator<E> listIterator() { return listIterator(0); }

（第三步）listIterator()方法在LinkedList类中的实现如下： public ListIterator<E> listIterator(final int index) { // 效验index的有效性 rangeCheckForAdd(index); // 返回ListItr对象 return new ListItr(index); }

ListItr类

ListItr类的声明

ListItr类实现了ListIterator接口，ListIterator接口继承了Iterator接口。 private class ListItr extends Itr implements ListIterator<E>

ListItr类实现的方法

hasNext()方法

用于判断是否还有下一个元素可以迭代。

next()方法

用于输出下一个元素。有checkForComodification()方法

hasPrevious()方法

用于判断是否有前一个元素。

previous()方法

用于返回前一个元素。有checkForComodification()方法

nextIndex()方法

用于返回下一个将要输出的元素的位置。

previousIndex()方法

用于返回前一个输出的元素的位置。

remove()方法

用于删除迭代器上一次输出的元素。有checkForComodification()方法

set()方法

用于迭代器更新元素。有checkForComodification()方法

forEachRemaining()方法

用于对剩余元素执行给定操作。

反向迭代器

LinkedList提供了反向迭代器DescendingIterator类，DescendingIterator迭代器主要是通过ListItr迭代器的previous()实现从链表尾结点向前迭代的。

LinkedList常见面试考点

（1）LinkedList是基于双向链表实现的容器。

（2）LinkedList的存储模型。

（3）LinkedList查找时间复杂度。

（4）LinkedList迭代器。

（5）LinkedList线程安全问题及与之对应的并发容器。

（6）LinkedList作为队列使用时的相关考点。

Deque

定义  Deque（Double Ended Queue）支持在队列两端插入和移除元素的特殊队列，该接口定义了访问双端队列两端的元素的方法。

Deque接口声明    public interface Deque<E> extends Queue<E>

Queue接口继承自Collection接口。Queue接口的方法如下：

/** * 在没有超出队列容量限制的前提下，向队列添加新元素 * 添加成功就返回true。如果空间不足，就抛出IllegalStateException异常 */ boolean add(E e);

/** * 在没有超出队列容量限制的前提下，向队列添加新元素 * 对于有容量限制的队列，此方法比add()方法更好 */ boolean offer(E e);

/** * 检索并删除此队列的头 * 此方法与poll()方法的不同之处在于，如果队列为空，就抛出异常 */ E remove();

/** * 检索并删除此队列的头 * 如果队列为空，就返回null */ E poll();

/** * 检索但不删除此队列的头 * 此方法与peek()方法的不同之处在于，如果队列为空，就抛出异常 */ E element();

/** * 检索但不删除此队列的头 * 如果队列为空，就返回null */ E peek();

创建一个队列：Deque<String> queue = new LinkedList<>();

Deque接口

总结  Deque是一个双向队列，可以在队头和队尾分别进行入队和出队等操作。除此之外，Deque还可以当作栈数据结构使用，实现入栈和出栈。

Deque接口的实现类

LinkedList类

实现方法

addFirst()方法

在队列头部添加元素。（无返回值）

addLast()方法

在队列尾部添加元素。（无返回值）

offerFirst()方法

在队列头部添加新元素。（返回布尔值）

offerLast()方法

在队列尾部添加新元素。（返回布尔值）

removeFirst()方法

删除队列头结点。

removeLast()方法

删除队列尾结点。

pollFirst()方法

删除队列头部元素。(在队列为空时返回null)

pollLast()方法

删除队列尾部元素。(在队列为空时返回null)

getFirst()方法

获取头结点存储的元素值。(抛出NoSuchElementException异常)

getLast()方法

获取尾结点存储的元素值。(抛出NoSuchElementException异常)

peekFirst()方法

用于获取但不删除队列头部元素。

peekLast()方法

用于检索但不删除此双端队列的最后一个元素。

add()方法

用于在队列尾部添加元素。此方法等效于addLast。

offer()方法

用于在队列尾部添加元素。

remove()方法

用于检索并删除此队列的头部。此方法等效于removeFirst

poll()方法

用于检索并删除此队列的头部。

element()方法

用于检索但不删除此双端队列的头部。此方法等效于getFirst

peek()方法

用于检索但不删除此双端队列的头部。

removeFirstOccurrence()方法

用于从队列删除第一次出现的指定元素。

removeLastOccurrence()方法

用于从队列移除最后一次出现的指定元素。

push()方法

将元素压入此双端队列表示的栈上。

public void push(E e) { addFirst(e); }

pop()方法

从此双端队列表示的栈中弹出一个元素。

public E pop() { return removeFirst(); }

总结  

1、offer()和add()的区别

add()和offer()都是向队列中添加一个元素。但是如果想在一个满的队列中加入一个新元素，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。可以据此在程序中进行有效的判断！

2、peek()和element()的区别

peek()和element()都将在不移除的情况下返回队头，但是peek()方法在队列为空时返回null，调用element()方法会抛出NoSuchElementException异常。

3、poll()和remove()的区别

poll()和remove()都将移除并且返回对头，但是在poll()在队列为空时返回null，而remove()会抛出NoSuchElementException异常。

Deque常见面试考点

（1）Deque是一种可以在两端插入和移除元素的特殊队列。

（2）LinkedList对Deque的支持和实现。

（3）Deque查找时间复杂度。

（4）JDK并发编程框架对Deque的支持和实现。

PriorityQueue

定义   PriorityQueue是优先级队列，PriorityQueue的作用是保证每次出队的元素都是队列中权值最小的。PriorityQueue中元素大小的比较可以通过元素本身的自然顺序（Natural Ordering）实现，也可以通过构造时传入的比较器实现。

PriorityQueue类的声明

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable

PriorityQueue实现了Queue接口，不允许存储null元素。PriorityQueue通过小顶堆实现功能。

PriorityQueue类的属性

// 优先级队列的默认初始容量为11 private static final int DEFAULT_INITIAL_CAPACITY = 11;

/** * 存放优先级队列数据的数组 * 此数组存储的是小顶堆 * 元素queue[n]的孩子分别是queue[2*n+1]和queue[2*(n+1)] */ transient Object[] queue;

// 优先级队列中元素的数量 private int size = 0;

// 用于比较元素大小的比较器，如果使用自然序，就可以为空 private final Comparator<? super E> comparator;

// 优先级队列发生结构变化的次数 transient int modCount = 0;

// 数组的最大容量 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

PriorityQueue类的构造器

1．无参构造器

创建一个容量DEFAULT_INITIAL_CAPACITY，即默认容量的优先级队列，其中的元素使用自然序进行排序。

public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); }

2．指定容量的构造器

此构造器指定优先级队列的容量，其中的元素使用自然序进行排序。

public PriorityQueue(int initialCapacity) { this(initialCapacity, null); }

3．指定比较器的构造器

创建指定比较器的构造器，此优先级队列的容量为DEFAULT_INITIAL_CAPACITY，即默认容量。

public PriorityQueue(Comparator<? super E> comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); }

4．指定容量和比较器的构造器

public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

5．使用集合参数的构造器

public PriorityQueue(Collection<? extends E> c)

最终生成小顶堆结构

6．使用优先级队列参数的构造器

public PriorityQueue(PriorityQueue<? extends E> c)

最终生成小顶堆结构

7．使用有序集合参数的构造器

public PriorityQueue(SortedSet<? extends E> c)

最终生成小顶堆结构

PriorityQueue类的方法

add()方法

用于向优先级队列添加元素。(添加空对象为flase)

注：这里和deque的实现类ArrayList不同，因为重写方法不同

offer()方法

用于向优先级队列添加元素。(添加空对象报异常)

poll()方法

用于检索并删除队列头部元素。

peek()方法

用于检索但不删除优先级队列的头部元素

PriorityQueue常见面试考点

（1）PriorityQueue是基于小顶堆实现的优先级队列。

（2）添加／删除元素时，PriorityQueue需要对小顶堆做出调整。

（3）PriorityQueue的使用场景。

（4）PriorityQueue线程安全问题及与之对应的并发容器。

HashMap

定义   HashMap是开发中使用频率很高的用于映射（Key-Value，键值对）处理的工具类。JDK1.8中，HashMap的实现进行了多处优化，如引入红黑树数据结构和扩容优化等。

HashMap的实现

类的声明

public class HashMap<K,V> extends AbstractMap<K,V>     implements Map<K,V>, Cloneable, Serializable

Map接口

声明  public interface Map<K,V>

Map接口的两个泛型

第一个泛型K用于约束键的类型

第二个泛型V用于约束值的类型

在Map接口中定义内部接口Entry

声明     interface Entry<K,V>

要实现的方法

K getKey();

V getValue();

V setValue(V value);

boolean equals(Object o);

int hashCode();

public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey()

public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue()

public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp)

public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp)

总结：   HashMap实现了Map接口，用于存储Key-Value结构的键值对。

HashMap静态内部类Node

声明  static class Node<K,V> implements Map.Entry<K,V>

HashMap的静态内部类Node实现了Map.Entry<K,V>接口，表示一个键值对。Node类除了有键（key属性）、值（value属性）、哈希码（hash属性）外，还有一个重要的属性next属性。当HashMap出现“哈希碰撞”时，HashMap使用链表的方式处理“哈希碰撞”，因此这个next属性表示的是当前Node结点在链表中的下一个结点。

HashMap静态内部类TreeNode

JDK1.8对HashMap的“哈希碰撞”做了优化，当链表到达一定长度后，HashMap会使用红黑树处理“哈希碰撞”的结点。红黑树的基本存储单元是TreeNode。

声明  static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>

LinkedHashMap.Entry类的声明   static class Entry<K,V> extends HashMap.Node<K,V>

结论：  从TreeNode的继承结构关系可知，TreeNode其实是HashMap.Node类的子类。

HashMap的存储结构

数组+链表(红黑树)

当少量键值对发生哈希碰撞时，HashMap会将碰撞的Node对象与原哈希桶数组table指定位置的Node对象组成一个链表结构进行存储。当链表长度达到限定值后，链表将会转为红黑树。table数组通常也称为哈希桶数组。哈希桶数组的每个位置称为桶位。

HashMap的类构造器

1.无参构造器(DEFAULT_LOAD_FACTOR 负载因子默认为0.75F，其余属性都是使用默认值)

public HashMap() {     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }

注：loadFactor是哈希表的加载因子

2.指定初始容量的构造器

public HashMap(int initialCapacity) {     this(initialCapacity, DEFAULT_LOAD_FACTOR); }

如果在开发中预先知道需要存入HashMap的键值对数量，就应该指定HashMap的初始容量，以避免在使用HashMap的过程中出现频繁扩容而影响HashMap的性能。此构造器使用默认的负载因子DEFAULT_LOAD_FACTOR=0.75f。

3.指定初始容量和负载因子的构造器

public HashMap(int initialCapacity, float loadFactor)

4.可以根据具体的使用场景设置HashMap的初始容量和负载因子。创建一个与指定的映射含有相同键值对的新的HashMap的构造器

public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

HashMap类的方法

put()方法

将一组键值对存放在映射中。如果该映射已经包含与该键相对应的键值对，就会更新该键值对的值。

hash()方法

用于计算键的哈希值并将键的哈希值的高位和低位进行运算。

总结：无论是增加、删除还是查找键值对，定位到哈希桶数组table的位置都是很关键的第一步。HashMap中的元素分布应当尽可能均匀，尽量使每个哈希桶数组的位置上的元素只有一个，那么通过hash()方法求得这个位置的时候，马上就可以知道对应位置的元素是不是想要的元素，而不用遍历链表或者红黑树，大大优化了查询的效率。------为什么哈希表又称散列表

源码： static final int hash(Object key) {     int h;     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

hash()方法代码执行步骤分为3步

（1）h = key.hashCode()，将h赋值为key对应的哈希值。

（2）h >>> 16是将h无符号右移16位，即获得h的高16位。

（3）h和(h >>> 16)进行异或运算。这么做可以在哈希桶数组table的length比较小的时候，也能保证考虑到高低位都参与到哈希的计算中，同时不会有太大的开销。

putVal()方法

添加一个键值对。如果键值对已经存在就会覆盖键值对   put()方法通过调用putVal()方法实现功能。

1.putVal()方法通过hash()方法的返回值计算对应的键值对在哈希桶数组中的存储位置。hash()方法的返回值需要与哈希桶数组table的长度进行取模运算，决定键值对在哈希桶数组table中的存储位置。因为哈希桶数组table的长度总是2的整数次幂，所以计算位置的算法(n-1) & hash就是对hash()方法的结果进行取模运算，但是&运算比%(取余)运算具有更高的效率。

2.计算出的结果在putVal()方法中用变量i存储。如果哈希桶数组table的位置i处没有任何元素，就通过newNode()方法创建一个新的Node对象并存储在哈希桶数组table的位置i处。

3.如果哈希桶数组table的位置i处已经存储了Node对象，即出现了哈希碰撞。

（1）如果位置i处存储的Node对象的hash属性等于当前putVal()方法参数中的hash值，并且位置i处存储的Node对象的key属性等于putVal()方法参数的key值，就说明putVal()方法当前操作的键值对在映射中已经存在，其存储位置就是哈希桶数组table的第i个位置。

（2）如果不满足（1）中的条件，就会判断哈希桶数组table位置i处存储的Node对象是不是TreeNode类型的对象。如果是，就说明哈希桶数组table的第i个位置存储的是一棵红黑树，调用putTreeVal()方法对红黑树进行插入操作。

（3）若（1）和（2）都不满足，则哈希桶数组table的第i个位置存储的是链表。创建新的Node结点并插入链表中。若链表的长度大于或等于TREEIFY_THRESHOLD，则通过treeifyBin()方法将链表转化为红黑树。

resize()方法

用于对哈希桶数据扩容。

jdk1.7中采用头插法，扩容的时候，旧链表迁移到新链表的时候会造成链表元素倒置的问题 jdk1.8中采用尾插法解决

扩容案例分析

1.【注意：JDK1.8优化，原链表中的元素批量迁移】这部分的do-while循环不易理解，下面通过案例介绍这部分优化的逻辑。 假设现在哈希桶数组的容量是16，有{5,1}、{21,5}、{37,9}、{53,6}四个键值对。 用扩容前的哈希桶数组分别存储这4个键值对。 （1）{5,1}的存储位置是00000101&(16-1)，即{5,1}存储在哈希桶数组的第5个位置。 （2）{21,5}的存储位置是00010101&(16-1)，即{21,5}存储在哈希桶数组的第5个位置。 （3）{37,9}的存储位置是00100101&(16-1)，即{37,9}存储在哈希桶数组的第5个位置。 （4）{53,6}的存储位置是00110101&(16-1)，即{53,6}存储在哈希桶数组的第5个位置。

2.假设发生扩容，哈希桶数组的容量从16变成32。此时代码执行到do-while循环，对原链表判断链表中的元素是移动到新的链表还是留在原链表中。

lo是扩容后仍然在原地的元素组成的链表。 hi就是扩容后下标为原位置加原容量的元素组成的链表。 扩容后计算存储位置使用hash&(32-1)，即取hash的后5位。do-while循环中使用(e.hash & oldCap) == 0判断是否需要转移（原哈希桶数组的容量是16，即二进制10000，e.hash和二进制10000做与运算即可得到第5位上的数字）。通过这样的优化，不需要再重新计算链表中每个元素的存储位置。扩容后原链表中各个元素的分布情况如下： （1）{5,1}通过00000101&16得到0，即{5,1}留在原位置，存储在lo链表中。 （2）{21,5}通过00010101&16得到非0，即{21,5}需要发生移动，存储在hi链表中。 （3）{37,9}通过00100101&16得到0，即{37,9}留在原位置，存储在lo链表中。 （4）{53,6}通过00110101&16得到非0，即{53,6}需要发生移动，存储在hi链表中。

putTreeVal()方法

红黑树中插入键值对

通过(n-1) & hash找到哈希桶数组指定位置已经存储的元素，如果这个元素是TreeNode类型的，就通过putTreeVal()方法在红黑树上插入键值对。

treeifyBin()方法

链表转换为红黑树

如果哈希桶数组中“哈希碰撞”形成的链表的长度大于或等于TREEIFY_THRESHOLD，就通过treeifyBin()将链表转化为红黑树。

实现步骤

1.通过treeify()方法构建红黑树。

treeify()方法仅仅是根据键的hash属性值在红黑树上查找合适的位置并将TreeNode插入红黑树。插入结点后可能会破坏红黑树的平衡性。treeify()方法通过调用balanceInsertion()方法使红黑树重新达到平衡

2.balanceInsertion()方法，使红黑树达到平衡

balanceInsertion()方法通过左旋转和右旋转等方式使红黑树重新达到平衡。

左旋转方法rotateLeft()

右旋转方法rotateRight()

3.moveRootToFront()方法确保红黑树的根结点存放在哈希桶中

通过treeifyBin()方法将链表转化为红黑树后，并不能保证红黑树的根结点恰好存储在哈希桶中，有可能是平衡后的红黑树的某个叶子结点存放在哈希桶中。因为访问红黑树需要从根结点递归访问，如果哈希桶中存放的不是根结点，就无法访问这棵红黑树。因此，需要通过moveRootToFront()方法确保红黑树的根结点存放在哈希桶中。

remove()方法

用于从此映射中删除指定键值对。

实现步骤

1.通过removeNode()完成删除操作。

如果哈希桶中使用链表处理“哈希碰撞”，那么删除过程较为简单，只需修改待删除结点的前驱结点和后继结点的关系即可。如果哈希桶中使用红黑树处理“哈希碰撞”，就稍微复杂一些。删除后需要对红黑树进行相应的调整。

2.红黑树的删除方法removeTreeNode()方法

注：  removeTreeNode()方法可能会调用untreeify()方法将红黑树退化为链表。

get()方法

用于根据键查找对应的值

实现步骤

通过getNode()方法查找对应的结点，如果找到对应的结点就返回结点存储的value值，否则返回null。

HashMap常见面试考点

（1）HashMap的容量和负载因子的设置。

（2）HashMap的扩容过程以及尽可能避免扩容的处理方式。

（3）HashMap“哈希碰撞”的概念。

（4）HashMap解决“哈希碰撞”的处理方式。

（5）不同JDK版本HashMap对哈希碰撞的处理方式对比。

（6）哈希碰撞时链表与红黑树互相转换。

（7）红黑树相关操作。

（8）HashMap、LinkedHashMap和TreeMap的原理和性能对比。

（9）什么时候应该重写对象的equals()和hashCode()方法及重写的原因。

（10）在不使用HashMap已有的“哈希碰撞”的处理方案的前提下，提供多种可以处理“哈希碰撞”的解决方案。

（11）HashMap与HashSet的关系对比。

（12）HashMap、Hashtable和ConcurrentHashMap的对比。

（13）自己实现一个简单的HashMap并提供核心代码。

（14）table 的初始化时机是什么时候，初始化的 table.length 是多少、阀值（threshold）是多少，实际能容下多少元素

一般情况下，在第一次 put 的时候，调用 resize 方法进行 table 的初始化（懒初始化，懒加载思想在很多框架中都有应用！）

默认情况下，table.length = 16

默认情况下，threshold = 12;

默认情况下，能存放 12 个元素，当存放第 13 个元素后进行扩容

（15）table 的 length 为什么是 2 的 n 次幂

为了利用位运算 & 求 key 的下标

（16）求索引的时候为什么是：h&(length-1)，而不是 h&length，更不是 h%length

h%length 效率不如位运算快

h&length 会提高碰撞几率，导致 table 的空间得不到更充分的利用、降低 table 的操作效率

HashMap是面试中常见的考点之一，读者应该予以重视。

LinkedHashMap

定义  LinkedHashMap是HashMap的子类，LinkedHashMap内部使用一个双向链表维护键值对的顺序，每个键值对既位于哈希表中，又位于双向链表中。

LinkedHashMap支持两种顺序：插入顺序和访问顺序。

插入顺序指先添加的在前面，后添加的在后面。修改操作不影响顺序。

访问顺序指对一个键执行get/put操作后，其对应的键值对会移动到链表末尾，所以靠近链表末尾的元素是最近访问的元素，靠近链表头部的是最久没有被访问的元素。

应用：  通过LinkedHashMap访问顺序的特性可以实现LRU（Least Recently Used，最近最少使用）算法。LRU算法是很多缓存框架都提供的算法，如Redis提供了volatile-lru配置项淘汰最近最少使用的键值对。

LinkedHashMap的实现

LinkedHashMap类的声明

public class LinkedHashMap<K,V>     extends HashMap<K,V>     implements Map<K,V>

LinkedHashMap静态内部类Entry

LinkedHashMap的内部类Entry是HashMap.Node类的子类。LinkedHashMap类的内部类Entry在HashMap.Node类的基础上增加了before和after两个属性用于实现双向链表。因此，LinkedHashMap可以实现按照插入顺序访问元素。

static class Entry<K,V> extends HashMap.Node<K,V> {     Entry<K,V> before, after;     Entry(int hash, K key, V value, Node<K,V> next) {         super(hash, key, value, next);     } }

LinkedHashMap类的属性

// 双向队列的头结点 transient LinkedHashMap.Entry<K,V> head;

// 双向队列的尾结点 transient LinkedHashMap.Entry<K,V> tail;

/* * 访问LinkedHashMap元素的方式 * true:按照访问顺序访问 * false:按照插入顺序访问 */ final boolean accessOrder;

LinkedHashMap类的构造器

无参构造器

/* * 无参构造器 * 初始容量16，负载因子0.75f * false:按照插入顺序访问 */ public LinkedHashMap() {     super();      // accessOrder 为false     // 按照插入顺序访问其中的元素     accessOrder = false; }

指定初始容量的构造器

/* * 指定初始容量构造器 * 负载因子0.75f * false:按照插入顺序访问 */ public LinkedHashMap(int initialCapacity) {     super(initialCapacity);     accessOrder = false; }

指定初始容量和负载因子的构造器

/* * 指定初始容量和负载因子构造器 * false:按照插入顺序访问 */ public LinkedHashMap(int initialCapacity, float loadFactor) {     super(initialCapacity, loadFactor);     accessOrder = false; }

通过给定的Map对象创建LinkedHashMap对象的构造器

/* * 创建与指定映射含有相同键值对的LinkedHashMap对象的构造器 * false:按照插入顺序访问 */ public LinkedHashMap(Map<? extends K, ? extends V> m) {     super();     accessOrder = false;     putMapEntries(m, false); }

指定初始容量、负载因子和元素访问方式的构造器

/* * 指定初始容量、负载因子和元素访问方式 * * @param initialCapacity 初始容量 * @param loadFactor 负载因子 * @param accessOrder true:按照访问顺序访问 *                                     false:按照插入顺序访问 */ public LinkedHashMap(int initialCapacity,     float loadFactor,     boolean accessOrder) {     super(initialCapacity, loadFactor);     this.accessOrder = accessOrder; }

LinkedHashMap类的方法

put()方法

1.因为LinkedHashMap继承了HashMap，所以LinkedHashMap使用父类HashMap的put()方法添加元素

2.put()调用putVal()方法，putVal()方法调用newNode()方法创建单链表Node结点。此方法在LinkedHashMap被重写，LinkedHashMap的newNode()方法调用linkNodeLast()方法将新结点链接到双向链表的尾部。

被重写的原因是LinkedHashMap是双向链表

如果put()方法操作的键值对在映射中不存在，那么在映射中添加新的键值对成功后，将会执行afterNodeInsertion()方法。afterNodeInsertion()方法是预留方法

// 结构变化次数加1 ++modCount; // 如果改变后的长度大于之前的容量，则扩容 if (++size > threshold)     resize(); // 预留方法，可以设置回调 // evict-如果为false，则表处于创建模式。 afterNodeInsertion(evict);

这段代码中的afterNodeInsertion()方法是预留方法，在HashMap中并没有具体的方法实现。

HashMap中的afterNodeInsertion()方法代码

void afterNodeInsertion(boolean evict) { }

此处使用模板方法设计模式，使HashMap的子类可以重写afterNodeInsertion()方法，增加子类的逻辑。

afterNodeInsertion()方法调用的removeEldestEntry()方法的作用是判断是否删除映射中比较旧的键值对。如果removeEldestEntry()返回true，那么删除比较旧的键值对，否则不删除

LinkedHashMap类的removeEldestEntry()方法返回固定值false，不会删除其中比较旧的键值对。因此，afterNodeInsertion()方法将不会执行removeNode()方法。

removeEldestEntry()应用

LRUCache类重写了removeEldestEntry()方法，实现了LRU(最近最少使用)算法。

@Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {     return size() > maxEntries; }

LRUCache类的removeEldestEntry()方法在判断当前保存的键值对大于maxEntries时将会返回true。此时，afterNodeInsertion()方法因removeEldestEntry()方法返回true而执行removeNode()方法。因为removeEldestEntry()方法中调用removeNode()方法传入的参数是first（双向链表的头结点），即删除了“最近最少使用”的结点，从而实现了LRU算法。

void afterNodeInsertion(boolean evict) {     LinkedHashMap.Entry<K,V> first;     if (evict && (first = head) != null && removeEldestEntry(first)) {         K key = first.key;         removeNode(hash(key), key, null, false, true);     } }

removeEldestEntry()应用LRU算法会解释此处

3.如果原映射中键值对已存在，那么此次调用put()方法只会更新键对应的值，并返回旧的值。

// 如果结点e非空，说明在映射中找到了与键对应的键值对 if (e != null) {     // 获取结点e的旧的value值     V oldValue = e.value;     // 如果允许修改旧的value或者旧的value为空     if (!onlyIfAbsent || oldValue == null)         // 更新结点e的value为新的值         e.value = value;     // 预留方法，可以设置回调     afterNodeAccess(e);     // 返回旧的value值     return oldValue; }

这段代码中的afterNodeAccess()方法是预留方法，在HashMap中并没有具体的方法实现。

HashMap中的afterNodeAccess()方法代码

void afterNodeAccess(Node<K,V> p) { }

此处使用模板方法设计模式，使HashMap的子类可以重写afterNodeAccess()方法，增加子类的逻辑。

在HashMap的子类LinkedHashMap中，重写afterNodeAccess()

afterNodeAccess()方法的作用是将当前更新的键值对对应的结点对象调整到双向链表的尾部，其大体思路是首先将结点e从双向链表中摘除，然后维护双向链表，使摘除结点e后的其余结点连接成新的双向链表，最后将摘除的结点e连接到新的双向链表的尾部。

注：removeNode()方法中也有一个与afterNodeAccess()和afterNodeInsertion()类似的方法afterNodeRemoval()，此方法也是由HashMap的子类实现的

在LinkedHashMap中afterNodeRemoval()方法的作用是删除结点e后对双向链表做一些维护工作

get()方法

用于获取键对应的值

如果未找到对应的结点就返回null；否则判断accessOrder，如果accessOrder为true，将会执行afterNodeAccess()方法更新双向链表。

accessOrder   哈希映射的迭代排序方法：true表示访问顺序，false表示插入顺序。

getOrDefault()方法

用于获取键对应的值，如果不存在就返回默认值。

containsValue()方法

用于判断LinkedHashMap中是否存在一个或者多个键映射指定的value，如果存在就返回true，否则返回false。

public boolean containsValue(Object value) {     for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {         V v = e.value;         if (v == value || (value != null && value.equals(v)))             return true;     }     return false; }

从containsValue()方法代码可知，containsValue()方法遍历双向链表，搜索每个结点的value值，如果存在value等于指定的value就返回true，否则返回false。

removeEldestEntry()方法

用于控制LinkedHashMap是否删除较陈旧的键值对。如果想实现删除较陈旧的键值对的功能，那么使removeEldestEntry()返回true即可 删除较陈旧的键值对在LinkedHashMap作为缓存使用时非常有用，可以有效减少控制LinkedHashMap的内存消耗。

LinkedHashMap类常见面试考点

（1）LinkedHashMap与HashMap的比较。

（2）LinkedHashMap的两种元素访问方式。

（3）基于LinkedHashMap实现LRU算法。

TreeMap

存在的背景：  HashMap和LinkedHashMap都不具备按键排序的功能，因此要想从HashMap和LinkedHashMap中搜索最大或最小键，需要遍历所有的键值对，这会造成从HashMap和LinkedHashMap搜索最大或最小键的时间复杂度比较高，此时需要使用TreeMap。TreeMap是基于红黑树的NavigableMap实现的，该映射根据其键的自然顺序进行排序或者根据创建映射时提供的比较器进行排序。

时间复杂度对比

TreeMap的键按照自然顺序或根据创建时提供的比较器进行排序，TreeMap新增、修改、删除和查找操作的时间复杂度是O(log2n)。从存取角度而言，TreeMap比HashMap与LinkedHashMap的O(1)时间复杂度要差些。但如果需要保证统计功能或者对键按照一定的规则进行排序，那么使用TreeMap是一种更好的选择。

TreeMap的实现

TreeMap类的声明

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable

与HashMap不同的是，TreeMap实现了NavigableMap接口。 NavigableMap继承SortedMap，使用导航的方法扩展SortedMap，返回与给定搜索目标最接近的匹配元素。

public interface NavigableMap<K,V> extends SortedMap<K,V>

NavigableMap接口继承SortedMap接口

public interface SortedMap<K,V> extends Map<K,V>

SortedMap接口继承Map接口

SortedMap是在Map基础之上对键实现排序的高级Map接口

SortedMap接口的实现

/* * 返回Map中键值对进行排序 * 如果使用key的自然排序，就返回null */ Comparator<? super K> comparator();

/* * 返回此Map的部分映射 * 其键的范围是[fromKey,toKey)左闭右开区间 */ SortedMap<K,V> subMap(K fromKey, K toKey);

/* * 返回此Map的部分映射，其键严格小于toKey */ SortedMap<K,V> headMap(K toKey);

/* * 返回此Map的部分映射，其key大于或等于fromKey */ SortedMap<K,V> tailMap(K fromKey);

/* * 返回此Map中当前的第一个键 */ K firstKey();

/* * 返回此Map中当前的最后一个键 */ K lastKey();

/* * 返回此Map中包含的键的Set集合 * Set的迭代器按升序返回key */ Set<K> keySet();

/* * 返回此Map中包含的值的集合 * Set的迭代器以相应键的升序返回value */ Collection<V> values();

/* * 返回此Map中包含的Entry集合 * Set的迭代器以键的升序顺序返回Entry */ Set<Map.Entry<K, V>> entrySet();

TreeMap静态内部类Entry

TreeMap类的属性

// 键的比较器，用于对键排序 private final Comparator<? super K> comparator;

// 红黑树的根结点 private transient Entry<K,V> root;

// 红黑树的大小 private transient int size = 0;

// 结构性变化的次数 private transient int modCount = 0;

// Map的Entry视图 private transient EntrySet entrySet;

// Map中可导航的键的集合 private transient KeySet<K> navigableKeySet;

// 按照键的降序排序的Map private transient NavigableMap<K,V> descendingMap;

// 定义红黑树的颜色 // 红色 private static final boolean RED = false; // 黑色 private static final boolean BLACK = true;

TreeMap类的构造器

/* * 无参构造器 * 使用键的自然顺序构造一个新的、空的Map * 插入该Map的所有键都必须实现Comparable接口 * 所有这些key都必须是可比较大小的 */ public TreeMap() {     comparator = null; }

/* * 指定比较器的构造器 */ public TreeMap(Comparator<? super K> comparator) {     this.comparator = comparator; }

/* * 指定Map对象作为参数的构造器 * 构造一个与给定Map具有相同映射关系的新Map * 该Map根据其键的自然顺序进行排序 */ public TreeMap(Map<? extends K, ? extends V> m) {     comparator = null;     putAll(m); }

/* * 指定SortedMap对象作为参数的构造器 * 构造一个与指定SortedMap具有相同映射关系和相同排序顺序的新Map */ public TreeMap(SortedMap<K, ? extends V> m)

TreeMap类的方法

putAll()

将给定的Map对象中的键值对复制到TreeMap中 如果给定的Map对象是SortedMap类型的对象，就通过buildFromSorted()方法构建TreeMap对象。 否则就调用AbstractMap类的putAll()方法

buildFromSorted()

1.调用computeRedLevel()方法计算一棵完全二叉树的高度。

2.buildFromSorted()方法调用其重载的方法构建红黑树。

put()

put()方法会从根结点开始查找，如果插入的键小于根结点，就在左子树中搜索，否则在右子树中搜索。如果找到已经存在的键值对，就覆盖旧值，否则插入新的键值对。插入成功后，将通过fixAfterInsertion()方法调整红黑树，使之重新达到平衡。

get()

get()方法通过getEntry()方法查找对应的Entry对象。

如果有比较器，就通过指定的比较器查找Entry对象 在getEntry()方法中调用getEntryUsingComparator()方法

remove()

调用deleteEntry()方法删除Entry对象后对红黑树进行调整。

deleteEntry()方法删除Entry对象后，通过fixAfterDeletion()方法调整红黑树使之平衡。

firstKey()

用于返回TreeMap中最小的键。 public K firstKey() {     return key(getFirstEntry()); }

1.firstKey()方法通过getFirstEntry()方法获取第一个Entry对象。

getFirstEntry()方法从根结点开始向左子树搜索最左边的Entry对象。

2.找到Entry对象后，通过key()方法获取Entry对象的键。

lastKey()

用于返回TreeMap中最大的键。 public K lastKey() {     return key(getLastEntry()); }

1.lastKey()方法通过getLastEntry()方法获取最后一个Entry对象。

getLastEntry()方法从根结点开始向右子树搜索最右边的Entry对象。

2.找到Entry对象后，通过key()方法获取Entry对象的键。

TreeMap类常见面试考点

（1）TreeMap的实现原理。

（2）TreeMap操作的时间复杂度。

TreeMap新增、修改、删除和查找操作的时间复杂度是O(log2n)。

（3）红黑树的相关操作。

（4）HashMap、LinkedHashMap和TreeMap三者对比。

LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的；遍历比 HashMap 慢。 TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序(默认按键值升序排序，也可以指定排序的比较器)

HashSet

定义  HashSet是不能包含相同元素的无序集合。

HashSet元素并不是按照写入的顺序存储元素的。HashSet主要借助HashMap实现功能。

HashSet类的实现

HashSet类的声明

public class HashSet<E>     extends AbstractSet<E>     implements Set<E>, Cloneable, java.io.Serializable

HashSet类的属性

// HashSet借助HashMap存储元素 private transient HashMap<E,Object> map;

// HashMap中与每个键值相对应的虚拟值 private static final Object PRESENT = new Object();

HashSet类的构造器

/* * 无参构造器 * 初始化的HashMap的初始容量和负载因子都是默认值 */ public HashSet() {     map = new HashMap<>(); }

/* * 指定初始容量的构造器 * 指定HashMap的初始容量 */ public HashSet(int initialCapacity) {     map = new HashMap<>(initialCapacity); }

/* * 指定初始容量和负载因子的构造器 * 指定HashMap的初始容量和负载因子 */ public HashSet(int initialCapacity, float loadFactor) {     map = new HashMap<>(initialCapacity, loadFactor); }

/* * 指定集合的构造器 * 初始化与指定集合含有相同的元素的HashSet对象 */ public HashSet(Collection<? extends E> c) {     map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));     addAll(c); }

/* * 创建一个新的空的LinkedHashSet * 此构造器仅用来构造LinkedHashSet * @param initialCapacity 初始容量 * @param loadFactor 负载因子 * @param dummy 用于跟其他构造器区分开 */ HashSet(int initialCapacity, float loadFactor, boolean dummy) {     map = new LinkedHashMap<>(initialCapacity, loadFactor); }

HashSet类的方法

add()

用于当指定的元素尚不存在时，将其添加到该集合中。

add()方法调用HashMap的put()方法保存元素，如果HashMap的put()方法返回null，那么添加成功，否则添加失败。 add()方法调用HashMap的put()方法传入的参数是e和PRESENT。 当HashMap的put()方法添加新的键值对时，将返回null。当HashMap的put()方法更新键值对时，将返回旧的值。因此，当HashMap的put()方法更新键值对时，说明HashMap已经存在相同的键值对，此时HashSet添加新元素失败。

public boolean add(E e) {     return map.put(e, PRESENT)==null; }

remove()

从该集合中删除指定的元素。

HashSet的remove()方法通过调用HashMap的remove()方法删除元素。 如果HashMap的remove()方法返回的键值对的值等于PRESENT，那么删除成功。

public boolean remove(Object o) {     return map.remove(o)==PRESENT; }

contains()

用于判断集合中是否包含指定的元素。

HashSet的contains()方法通过调用HashMap的containsKey()方法实现。

HashMap的containsKey()方法代码通过getNode()方法查找对应的键值对。

public boolean containsKey(Object key) {     return getNode(hash(key), key) != null; }

public boolean contains(Object o) {     return map.containsKey(o); }

iterator()

是返回此集合中元素的迭代器。

HashSet的iterator()方法调用HashMap的keySet()方法获取一个KeySet对象，并调用这个KeySet对象的iterator()方法，得到一个迭代器对象。

HashMap的keySet()方法返回一个KeySet类的对象。

KeySet对象的iterator()方法返回一个KeyIterator类的对象。

KeyIterator类继承自HashIterator类。

final class KeyIterator extends HashIterator     implements Iterator<K> {     public final K next() { return nextNode().key; } }

public final Iterator<K> iterator() { return new KeyIterator(); }

public Set<K> keySet() {     Set<K> ks;     return (ks = keySet) == null ? (keySet = new KeySet()) : ks; }

public Iterator<E> iterator() {     return map.keySet().iterator(); }

HashSet类常见面试考点

（1）HashSet存储的元素是无序的。

（2）HashSet是通过HashMap实现功能的。

（3）HashSet在其内部的HashMap对象中存储的键值对的值是固定的值。（还未理解）

解释：当调用HashSet的方法时，实际上是向HashMap中增加了一个键值对，key就是set增加的那个对象，value是一个Object类型的对象

LinkedHashSet

定义   LinkedHashSet是HashSet的子类，基于链表实现。LinkedHashSet可以保证存储在其中的元素的有序性。

LinkedHashSet类的实现

LinkedHashSet类的声明

LinkedHashSet继承自HashSet类并实现Set接口

public class LinkedHashSet<E>     extends HashSet<E>     implements Set<E>, Cloneable, java.io.Serializable

LinkedHashSet类构造器

/* * 创建初始容量为16和负载因子为0.75f的LinkedHashSet */ public LinkedHashSet() {     super(16, .75f, true); }

/* * 创建指定初始容量和负载因子为0.75f的LinkedHashSet */ public LinkedHashSet(int initialCapacity) {     super(initialCapacity, .75f, true); }

/* * 创建指定初始容量和负载因子的LinkedHashSet */ public LinkedHashSet(int initialCapacity, float loadFactor) {     super(initialCapacity, loadFactor, true); }

/* * 创建一个与指定集合包含相同元素的LinkedHashSet */ public LinkedHashSet(Collection<? extends E> c) {     super(Math.max(2*c.size(), 11), .75f, true);     addAll(c); }

以上4种构造器都调用父类HashSet中的构造器 HashSet中的这个构造器使用LinkedHashMap类初始化HashMap对象。由此可知，LinkedHashSet是借助LinkedHashMap类实现功能的。

LinkedHashSet类常见面试考点

（1）LinkedHashSet是按照插入顺序存储元素的。

2）LinkedHashSet是借助LinkedHashMap实现功能的。

（3）LinkedHashSet与HashSet和TreeSet的对比。

在TreeSet中总结

TreeSet

TreeSet类的实现

TreeSet类的声明

public class TreeSet<E> extends AbstractSet<E>     implements NavigableSet<E>, Cloneable, java.io.Serializable

TreeSet继承自AbstractSet类，实现NavigableSet接口。

TreeSet类的属性(与hashmap类似) TreeSet是借助NavigableMap存储元素的。 TreeSet中的元素即NavigableMap中存储的键值对的键，NavigableMap键值对的值为PRESENT。

// TreeSet借助NavigableMap存储元素 private transient NavigableMap<E,Object> m;

// NavigableMap中与每个键值相对应的虚拟值 private static final Object PRESENT = new Object();

TreeSet类的构造器

/*   * 无参构造器   */ public TreeSet() {     this(new TreeMap<E,Object>()); }

/*   * 通过指定的NavigableMap对象新建一个空的TreeSet对象   */ TreeSet(NavigableMap<E,Object> m) {     this.m = m; }

/*   * 通过指定的比较器新建一个空的TreeSet对象   */ public TreeSet(Comparator<? super E> comparator) {     this(new TreeMap<>(comparator)); }

/*   * 通过指定的集合新建一个TreeSet对象   */ public TreeSet(Collection<? extends E> c) {     this();     addAll(c); }

/*   * 通过指定的SortedSet对象新建一个TreeSet对象   */ public TreeSet(SortedSet<E> s) {     this(s.comparator());     addAll(s); }

TreeSet类的方法

add()

用于向TreeSet中添加元素。 插入成功返回true 如果值已存在返回false

add()方法将调用TreeMap类的put()方法实现添加功能。添加的键值对的值是PRESENT。 插入成功返回null 如果值已存在返回旧值

public boolean add(E e) {     return m.put(e, PRESENT)==null; }

first()

用于从TreeSet中查找第一个键。

firstKey()方法调用getFirstEntry()方法查找第一个Entry对象，即查找红黑树最左边的结点。

public E first() {     return m.firstKey(); }

last()

用于从TreeSet中查找最后一个键。

以TreeSet的无参构造器为例，last()方法通过TreeMap的lastKey()方法查找最后一个键。

TreeMap的lastKey()方法通过getLastEntry()方法查找最后一个Entry对象，即红黑树最右边的结点。

public K lastKey() {     return key(getLastEntry()); }

public E last() {     return m.lastKey(); }

descendingIterator()

以降序方式返回此集合中元素的迭代器。

以TreeSet的无参构造器为例，descendingIterator()方法 1.首先调用TreeMap类的descendingKeySet()方法获取一个NavigableSet对象

descendingKeySet()方法 1.首先调用descendingMap()方法

descendingMap()方法返回一个DescendingSubMap对象。 注： DescendingSubMap类是NavigableSubMap类的子类；DescendingSubMap类是TreeMap类的内部类

DescendingSubMap类的声明

static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V>

DescendingSubMap类的构造器

DescendingSubMap(TreeMap<K,V> m,                                 boolean fromStart, K lo, boolean loInclusive,                                 boolean toEnd, K hi, boolean hiInclusive) {     super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); }

说明DescendingSubMap通过父类构造器创建对象，也就是NavigableSubMap类的构造器

NavigableSubMap(TreeMap<K,V> m,                               boolean fromStart, K lo, boolean loInclusive,                               boolean toEnd, K hi, boolean hiInclusive)

NavigableSubMap类是TreeMap的内部类，继承AbstractMap类

abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>                                                                       implements NavigableMap<K,V>, java.io.Serializable

public NavigableMap<K, V> descendingMap() {     NavigableMap<K, V> km = descendingMap;     return (km != null) ? km : (descendingMap = new DescendingSubMap<>(this,                                                                                                                 true, null, true,                                                                                                                 true, null, true)); }

2.接下来将调用NavigableSubMap类的navigableKeySet()方法。

navigableKeySet()方法将返回一个KeySet()对象。

public final NavigableSet<K> navigableKeySet() {     KeySet<K> nksv = navigableKeySetView;     return (nksv != null) ? nksv : (navigableKeySetView = new TreeMap.KeySet<>(this)); }

public NavigableSet<K> descendingKeySet() {     return descendingMap().navigableKeySet(); }

2.然后调用NavigableSet的iterator()方法得到迭代器。 注：由上可知，m.descendingKeySet().iterator()即调用KeySet的iterator()方法。

iterator()方法将会调用DescendingSubMap的keyIterator()方法。

Iterator<K> keyIterator() {     return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); }

keyIterator()方法返回一个DescendingSubMapKeyIterator对象。

final class DescendingSubMapKeyIterator extends SubMapIterator<K>                                                                    implements Spliterator<K>

注意，DescendingSubMapKeyIterator类的next()方法通过prevEntry()方法查找前一个Entry。

public K next() {     return prevEntry().key; }

prevEntry()调用predecessor()方法在红黑树中查找前驱结点。

因此，再使用降序的迭代器就可以实现从大到小输出TreeSet中的元素。

public Iterator<E> iterator() {     if (m instanceof TreeMap)         return ((TreeMap<E,?>)m).keyIterator();     else         return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator(); }

public Iterator<E> descendingIterator() {     return m.descendingKeySet().iterator(); }

TreeSet类常见面试考点

（1）TreeSet的有序性。

（2）TreeSet默认使用TreeMap实现其功能

（3）TreeSet、HashSet和LinkedHashSet对比。

1、Set接口

Set不允许包含相同的元素，如果试图把两个相同元素加入同一个集合中，add方法返回false。 Set判断两个对象相同不是使用==运算符，而是根据equals方法。也就是说，只要两个对象用equals方法比较返回true，Set就不会接受这两个对象。 HashSet和TreeSet都是Set接口的实现类。

2、HashSet

有如下特点： 不能保存元素的排列顺序 不是同步的 元素可以是null，但是只能设置一个null

当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。 简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值相等。 注意，如果要把一个对象放入HashSet中，重写该对象对应类的equals方法，也应该重写其hashCode()方法。其规则是如果两个对象通过equals方法比较返回true时，其   hashCode也应该相同。另外，对象中用作equals比较标准的属性，都应该用来计算 hashCode的值。

3、LinkedHashSet

LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

4、TreeSet

可以实现自动排序的类型。 TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0。