1. 动态数组
动态数组属于线性表的一种，所有元素的内存地址是连续的
动态数组的缺点：插入元素时重新排序索引，数组扩容时浪费存储空间
2. 链表(单向链表)
链表是一种链式存储的线性表，所有元素的内存地址不是连续的，前一个元素存储下一个元素的地址。
3. 双向链表
使用双向链表可以提升链表的总和性能
当双向链表只有一个元素时的结构如下
4. 双向链表 vs 动态数组
动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费
双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间浪费
- 如果频繁在尾部进行添加、删除操作，动态数组和双向链表均可选择
- 如果频繁在头部进行添加、删除操作，建议使用双向链表
- 如果有频繁的(在任意位置)添加、删除操作，建议使用双向链表
- 如果有频繁的查询操作(随机访问操作)，建议使用动态数组
5. 栈(Stack)
栈是一种特殊的线性表，只能在一端进行操作
栈采用后进先出的原则
往栈中添加元素的操作，一般叫做push，入栈 。如下图所示
从栈中移出元素的操作，一般叫做pop，出栈(只能移出栈顶元素)。如下图所示
6. 队列(Queue)
队列时一种线性表，只能在头尾两端进行操作
对尾(rear): 只能从队尾添加元素，一般叫做入队(add)
对头(front): 只能从队头移出元素，一般叫做出队(remove或者poll)
队列采用先进先出的原则
7. 树(Tree)
使用树形结构可以大大提高效率
7.1 树的基本概念
会以上图为例来讲解树的基本概念
节点
每一个圆圈都代表一个节点
根节点
每一个树只会有一个根节点，上图中1是根节点
一棵树可以只有一个节点，也就是只有根节点
父节点
1节点是2,3,4,5,6的父节点
2节点是21,22的父节点
22节点是221,222,223的父节点
子节点
2,3,4,5,6是1节点的子节点
31是3的子节点
兄弟节点
兄弟节点是同一个父节点的节点为兄弟节点
例如2,3,4,5,6是兄弟节点
21,22是兄弟节点
22，31不是兄弟节点，因为他们的父节点不是一个节点
空树
一棵树可以没有任何节点，称为空树
子数
2,21,22,221,222,223也是一棵树，这一棵树属于1节点的子树，同理3,31也是一棵子树，4也是一棵子树，5,51,52也是一棵子树，6,61也是一棵子树
这几棵树都是1的子树
左子树、右子树
51节点可以称为5节点的左子树，52节点可以称为5节点的右子树
像2节点，2节点的左子树是21,2节点的右子树是22,221,222,223
节点的度(degree)
节点的度相当于是子树的个数。
1的节点的度为5，因为1节点有5棵子树
2节点的度为2，因为2节点有2棵子树
6节点的度为1，因为有1棵子树
61节点的度为0，因为没有子树
树的度
树的度为所有节点度中的最大值，可以理解为树的根节点代表树的度
叶子节点
度为0的节点
比如说是21节点，没有子节点
非叶子节点
度不为0的节点
层数
根节点在第1层，根节点的子节点为第2层，以此类推。
上图的树的层数是4层
节点的深度
从根节点到当前节点的唯一路径上的节点总数
以2节点举例，2节点的节点深度为2，从根节点到当前节点的节点有1,2，所以2节点的深度为2。
同理222节点的节点深度为4
节点的高度
从当前节点到最远叶子节点的路径上的节点总数
以2节点举例，2节点的节点高度为3，2节点到最远叶子节点的目标为221,222,223节点中的任意节点。需要经理2节点，22节点，221节点三个节点。所以2节点的节点高度为3
树的深度
所有节点深度中的最大值
上图中树的深度为4（根节点的深度）
树的高度
所有节点高度中的最大值
上图中输的高度为4（根节点的高度）
有序树
数中任意节点的子节点之间有顺序关系
如下图所示，图中的树是有序树
无序树
树中任意节点的子节点之间没有顺序关系，也称为自由树
森林
由m（m≥0）棵互不相交的树组成的集合
8. 二叉树
二叉树的特点为每个节点的度最大为2(每个节点最多拥有2棵子树)
左子树和右子树是有顺序的
即使某接单只有一棵子树，也要区分左右子树
二叉树属于有序树
非空二叉树的第i层，最多有2^(i-1)个节点（i≥1）
在高度为h的二叉树上最多有2^h - 1个节点（h≥1）
二叉树的特性
对于任何一个非空二叉树，如果叶子节点个数为A，度为1的节点个数为B， 度为2的节点个数为C
那么A = C + 1（下边会演算为何会有这个结论）
二叉树的节点总数为 N = A + B + C
如下图所示画圈线为二叉树的边
二叉树的总边数计算公式为 T = B + 2 * C
如上图所示会发现每个节点的顶部都会有一条边，除了根节点
所以二叉树总边数又可以为T = N - 1。
由于N = A + B + C
所以 T = A +B + C - 1
B + 2 * C = A +B + C - 1
演算得到 A = C + 1 和上边计算的叶子节点个数等于节点个数加1相同
8.1 真二叉树
所有节点的度要么为0，要么为2
下图左边的是真二叉树，右边的不是真二叉树，因为有一个节点的度为1
8.2 满二叉树
所有节点的度都要么为0，要么为2。而且所有的叶子节点都在最后一层。
满二叉树也属于真二叉树，真二叉树不一定是满二叉树
在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多
8.3 完全二叉树
叶子节点只会出现最后2层，且最后1层的叶子节点都靠左对齐
完全二叉树从根节点到倒数第2层是一棵满二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
完全二叉树中度为1的节点只有左子树
度为1的节点要么是1个要么是0个，讲解如下图
8.4 二叉搜索树 (Binary Search Tree)
二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为BST
又被称为：二叉查找树、二叉排序树
任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一颗二叉搜索树
二叉搜索树可以大大提高搜索数据的效率
二叉搜索树存储的元素必须具有可比较性，比如int,double等。如果是自定义类型，需要指定比较方式，不允许为null
8.5 二叉树的遍历
根据节点的访问顺序不同, 二叉树的常见遍历方式有4种
- 前序遍历(Preorder Traversal)
- 中序遍历(Inorder Traversal)
- 后序遍历(Postorder Traversal)
- 层序遍历(Level Order Traversal)
8.5.1 前序遍历
前序遍历优先访问根节点，访问完根节点再访问左子树，再去访问右子树
以下图二叉树为例，查询顺序为
- 查询根节点7
- 查询根节点的左子树的根节点4
- 查询4节点的左子树的根节点2
- 查询2节点的左子树的根节点1
- 由于1节点没有左子树和右子树，查询2节点的右子树的根节点3
- 由于3节点没有左子树和右子树，查询4节点的右子树的根节点5
- 有与5节点没有子树，查询根节点的右子树的根节点9
- 以此类推
查询顺序总结为 7、 4、 2、 1、 3、 5、9、 8、 11、 10、 12
8.5.2 中序遍历
中序遍历先访问左子树，再访问根节点，再访问右子树
以上图为例，查询顺序为
1,2,3,4,5,7,8,9,10,11,12
或者反过来，中序遍历先访问右子树，再访问根节点，再访问左子树
以上图为例，查询顺序为
12,11,10,9,8,7,5,4,3,2,1
二叉搜索树的中序遍历结果可以是升序或者降序
8.5.3 后序遍历
后序遍历先访问左子树，再访问右子树，再访问根节点
以上图为例，查询顺序为
1,3,2,5,4,8,10,11,12,9,7
8.5.4 层序遍历
层序遍历从上到下，从左到右依次访问每一个节点
以上图为例，查询顺序为
7,4,9,2,5,8,11,1,3,10,12
8.6 二叉搜索树的问题
如果二叉搜索树添加元素时，按从小到大添加节点，那么二叉搜索树会退化为链表，那么效率大大退化。不光是添加元素，删除节点时，二叉搜索树也有可能退化为单向链表。二叉搜索树的查询和添加或者删除元素的时间复杂度为O(h), h是树的高度，那么退化为链表之后，添加查询等时间复杂度为0(n)。因此二叉搜索树需要优化和改进。
改进方案为，在节点的添加和删除操作之后，想办法让二叉搜索树变为平衡二叉搜索树，相当于减少树的高度。平衡二叉搜索树的根节点的左右子树高度越接近，代表这棵二叉树越平衡。
如下图所示，可以将左边的二叉搜索树改进为右边的二叉搜索树，减少树的高度
但是如果以上图为例，如果继续调整节点的位置，完全可以达到理想平衡，但是付出的代价可能会很大，比如调整的次数会比较多，反而增加了时间复杂度，总结来说，比较合理的改进方案是：用尽量少的调整次数达到适度平衡即可。
一棵达到适度平衡的二叉搜索树；可以称之为平衡二叉搜索树
经典常见的平衡二叉搜索树有AVL树和红黑树
AVL树在Windows NT内核中广泛使用
红黑树的应用场景：
- C++ STL(比如map、set)
- Java的TreeMap、TreeSet、HashMap、HashSet
- Linux的进程调度
- Nginx的timer管理
一般也称他们俩为：自平衡的二叉搜索树
8.7 AVL树
AVL树是最早发明的自平衡二叉搜索树之一，AVL树取名于两位发明者的名字。
AVL树有个概念叫平衡因子(Balance Factor)
平衡因子: 某节点的左右子树的高度差（左子树高度-右子树高度=平衡因子）
以下图的二叉搜索树讲解如何计算平衡因子
5,10,14节点的平衡因子是0，因为他们三个是叶子节点，没有子节点
12节点的平衡因子是1,12的左子树高度为1，12节点没有右子树，左子树高度-右子树高度=平衡因子
9节点的平衡因子是-3，左子树高度为0，右子树高度为3，所以平衡因子是-3
AVL树的特点为，每个节点的平衡因子只可能是1、0、-1（绝对值小于等于1，如果超过1，称之为失衡）
这种限制下AVL树的左右子树的高度差不超过1，因此搜索、添加、查询的时间复杂度还是O(logn)
例如输入数据：35, 37, 34, 56, 25, 62, 57, 9, 74, 32, 94, 80, 75, 100, 16, 82
左边的是普通二叉搜素树，右侧的是AVL树
8.8 B树
B树也是一种平衡的多路搜索树，多用于文件系统、数据库的实现。
下图是示例图：
观察B树示例图，有以下特点：
- 1个节点可以存储超过2个元素、可以超过2个子节点
- 拥有二叉搜索树的一些性质（以3阶B树图举例，12、10、15节点都小于18节点。48、45、47、50、52节点都大于33节点。23、30、20、21、24、31节点大于18小于33）
- 平衡，每个节点的所有子树高度一致
- B树比较矮，存储的数据比较多，但是树的高度不是很高
什么叫3阶B树？什么叫4阶B树？什么叫N阶B树？
3阶B树是一个节点最多拥有3个子节点
4阶B树是一个节点最多拥有4个子节点
N阶B数是一个节点最多拥有N个子节点
N阶B数的N必须大于等于2，因为要满足树形结构的特性
N阶B树的节点特性：
假设一个节点存储的元素个数为X
根节点: 1 ≤ X ≤ N - 1
非根节点：┌ m/2 ┐ ? 1 ≤ x ≤ N ? 1
┌和┐的意思为向上取整
如果有子节点，子节点个数为y = x + 1
根据根节点和子节点的特性可以推论出 2 ≤ y ≤ N
根据非根节点和子节点的特性可以推论出 ┌ m/2 ┐ ≤ y ≤ N
如果N=3，子节点 2 ≤ y ≤ 3 ，因此可以称为(2,3)树、又可以称为2-3树
如果N=4，子节点 2 ≤ y ≤ 4 ，因此可以称为(2,4)树、 又可以称为2-3-4树
如果N=5，子节点 3 ≤ y ≤ 5，因此可以称为(3,5)树、 又可以称为3-4-5树
如果N=2时，根节点数量为1，子节点数量为2，因此N=2时B树变回了二叉搜素树。一般来说使用B树时不会用到N=2的场景，而且一般使用场景中N都是比较大的。
数据库中一般使用200~300阶B树
8.8.1 B树和二叉搜索树
观察下方二叉搜索树和B树时会发现两颗树存储的元素是一样的
给你一棵二叉搜索树将某些父子节点进行合并，就能变成B树。合并节点如下图所示。可以说B树和二叉搜索树的逻辑完全是等价的。
8.8.2 B树的搜索
跟二叉搜索树的搜索方式类似
- 先在节点内部从小到大搜索元素
- 如果命中，搜索结束
- 如果未命中，再去对应的子节点中搜索元素，重复步骤1
8.8.3 B树的添加
B树的添加元素需要满足一点，新添加的元素必定是添加到叶子节点
以上图的B树举例
插入55之后的B树如下
插入95之后的B树如下
再加入98呢？假设这是一棵4阶B树。4阶B数的特点是每个子节点最多拥有3个元素，所以无法将98插入到90,95,100节点当中。这种现象可以称为上溢
8.8.3.1 上溢的解决
我们以5阶B数为举例
当添加34时，会添加到如上图位置区域，但是由于我们设定的B树5阶B数，子节点最多拥有4个元素。
解决上溢方案如下
- 当添加元素之后节点的元素个数等于N的时候（N代表几阶B树）
- 设定上溢节点最中间元素的位置为K，将K的位置与父节点进行合并
- 将[0, k-1]和[k+1,N-1]位置的元素分裂成2个节点，这2个子节点元素个数必然都会低于最低限制
- 如上图所示一次分裂完毕后，有可能导致父节点上溢，依然按照上述方案解决。最极端的情况，有可能一直分裂到根节点。
8.8.4 B树的删除
如果我们要删除的元素在叶子节点中，那么直接删除即可。
假如需要删除的元素在非叶子节点中。
举例我们要删除下图B树中的60
我们不能直接删除60，因为一个元素不能拥有3个子节点。
那么怎么做呢？
- 先找到前驱或后继元素，覆盖所需删除元素的值
什么是前驱元素？
前驱元素是找到他的左子树，再一路往右，找到最右侧元素。 60元素的前驱元素是55元素
什么是后继元素？
后继元素是找到他的右子树，再一路往左，找到最左侧元素，60元素的后继元素是70元素
2. 使用前驱或后继元素覆盖要删除的元素之后，再把前驱或后继元素删除。如下图所示使用前驱元素55覆盖60元素之后，再删除55元素
非叶子节点的前驱或后继元素，必定在叶子节点中
所以这里的删除前驱或后继元素，就是最开始提到的情况，删除的元素在叶子节点中。真正的删除元素都是发生在叶子节点中
总结：添加的元素必定在叶子节点中，真正的删除元素在叶子节点中
8.8.4.1 下溢的解决
我们以下图5阶B树举例。
当删除22节点
5阶B树的非根节点元素限制为 2 ≤ x ≤ 4, 若直接删除22节点，该叶子节点元素个数为1，不满足5阶B数的非根节点元素限制。
这种现象称为：下溢（underflow）
下溢节点的元素数量必然等于┌ N/2 ┐ ? 2
下溢的解决方案为，如果下溢节点的临近的兄弟节点，有至少┌ N/2 ┐个元素，可以向其借一个元素。
假例如下图，绿色节点删除元素之后出现了下溢现象
将父节点的元素F插入到下溢节点0位置(最小位置)
用兄弟节点的元素C（最大的元素）替代父节点的元素F
这种操作其实就是：旋转
上图是第一种情况，正好下溢节点的兄弟节点的元素个数至少有┌ N/2 ┐个元素。但是如果下溢节点的兄弟节点的元素个数只有┌ N/2 ┐-1个元素时，
将父节点的元素D挪下来跟左右子节点进行合并。合并后的节点元素个数等于┌ N/2 ┐+┌ N/2 ┐-2，不超过N-1
这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播
8.8.5 B树的总结
- B树比较矮，存储的数据比较多，但是树的高度不是很高
- 假设一个节点存储的元素个数为X, 根节点: 1 ≤ X ≤ N - 1, 非根节点：┌ m/2 ┐ ? 1 ≤ x ≤ N ? 1
- 子节点个数为┌ m/2 ┐ ≤ y ≤ N
- B树新添加的元素必定是添加到叶子节点
- B树上溢为添加元素之后节点的数量等于N时，出现了上溢现象
- 上溢的解决方案为将上溢节点最中间元素的位置为K，将K的位置与父节点进行合并
- B树的删除，如果我们要删除的元素在叶子节点中，那么直接删除即可。
- B树的删除，如果需要删除的元素在非叶子节点中，先找到前驱或后继元素，覆盖所需删除元素的值
- 前驱元素：前驱元素是找到他的左子树，再一路往右，找到最右侧元素
- 后继元素：后继元素是找到他的右子树，再一路往左，找到最左侧元素
- B树的删除是删除的元素在叶子节点中。真正的删除元素都是发生在叶子节点中，删除的目标只会被覆盖
- 添加的元素必定在叶子节点中，真正的删除元素在叶子节点中
- 删除元素之后节点的元素不满足┌ m/2 ┐ ? 1 ≤ x ≤ N ? 1 条件时该现象为下溢
- 下溢的解决方案参照8.9.4.1
8.9 红黑树
红黑树也是自平衡的二叉搜索树
红黑树会让原来度为0或者度为1的节点变为度为2节点(增加1个或者2个空节点)。
红黑树必须满足以下7个条件
- 节点是 RED 或者 BLACK
- 根节点必须是BLACK
- 叶子节点(空节点)都是BLACK
- RED节点的子节点都是BLACK
- RED节点的parent都是BLACK
- 从根节点到叶子节点的所有路径上不能有2个连续的RED节点
- 从任一节点到叶子节点的所有路径都包含相同数目的BLACK
8.9.1 红黑树与4阶B树的等价性
以上图的一个红黑树(省略NULL节点)为示例，若将上图的红黑树的BLACK节点与RED子节点融合在一起，形成1个B树节点。
红黑树中BLACK节点个数与4阶B树的节点总个数相等。
多种红黑树的等价变换
8.9.2 红黑树的添加
以下图的红黑树来进行讲解添加的情况
由于红黑树等价于4阶B树，添加元素会添加到叶子节点中。
由于添加元素只会添加到叶子节点，新的元素只会添加到17节点的左右，33节点的左右，46节点的左，50节点的左右，72节点的左右，76节点的右，88节点的左右。一共12种添加的情况。
新添加的节点为RED节点，因为新添加的节点设定为RED节点的情况下，更容易满足红黑树的特性。
添加元素之后parent为BLACK节点时的添加情况，这时添加后满足红黑树的性质, 无需修复，不用做任何处理，同样也满足4阶B树的性质。
一共12种添加情况，除去上边的4种添加情况，剩下的8种添加情况不满足红黑树的性质。
如下图所示将元素添加到parent节点为RED情况时，需要修复添加后的红黑树
将上边的场景进行拆分，我们先看添加52和60的情况，如何进行修复
这种情况可以归类为修复性质中的LL或RR场景
这种场景修复步骤为
我们需要将
52的parent(父节点)进行染色变成BLACK，grand(祖父节点)进行染色变成红色。
60的(父节点)进行染色变成BLACK，grand(祖父节点)进行染色变成红色。
进行染色之后
将46和52成为50节点的子节点，50节点成为38的子节点
将60和76成为72节点的子节点，72节点成为55的子节点
经过这样一系列修复之后就能满足红黑树的性质。
再来看一下添加48和74的情况，如下图所示
这种情况可以归类为修复性质中的LR或RL场景
这种场景修复步骤为
我们需要将
48节点染色成BLACK,grand(祖父节点)进行染色变成RED。
74节点染色成BLACK,grand(祖父节点)进行染色变成RED。
进行染色之后
让46和50节点变为48的子节点，48成为38的子节点
让72和76节点变为74的子节点，74成为55的子节点
经过这样一系列修复之后就能满足红黑树的性质。
修复成如下图所示
再来看一下添加10的情况，如下图所示
这种情况可以归类为修复性质中的LL-上溢
从B树角度出发，添加 10之后，4阶B树产生了上溢现象，因为4阶B树只能存储3个元素。
上溢的解决办法为如8.8.3.1所示，挑出中间的元素向上合并，左右分裂。这里为了省事，将25向上合并，因为25本就是38的子节点，17向上合并处理步骤比较多，因此选25向上合并，10,17,33分裂开来。向上合并之后25,38,55中38必定成为主节点。
具体步骤如下
- 25节点向上合并
- 25节点染色为RED，38节点染色为BLACK节点，55节点染色为RED节点，并38节点修改为55的父节点。
- 17节点修改未BLACK
- 33节点染色为BLACK
修改结果如下，修改完之后满足红黑树的所有特性。
再来看一下添加36的情况
这种情况可以归类为修复性质中的RR-上溢
添加36节点之后出现了上溢，和处理LL-上溢情况类似，还是将25节点向上合并，25的左右节点进行分裂，具体步骤和LL-上溢的修复流程类似
具体步骤如下
- 25节点向上合并
- 25节点染色为RED，38节点染色为BLACK节点，55节点染色为RED节点，并38节点修改为55的父节点。
- 17节点修改未BLACK
- 33节点染色为BLACK
修复结果如下
添加20节点，30节点也都是一样的。不再继续举例。
红黑树的添加总结来说其实就三种情况，父节点是BLACK，父节点是BLACK叔父节点不是RED，父节点是BLACK叔父节点是RED。以上三种情况已在上边讲解。若讲解文案不太清晰，可以到数据结构可视化网站进行模拟添加过程。
8.9.3 红黑树的删除
回顾B树的删除，B树中真正被删除的元素都在叶子节点中。
以下图的红黑树进行讲解红黑树的节点删除。
8.9.3.1 删除叶子节点的RED节点
删除红黑树中删除叶子节点中的RED节点，不需要进行修复，依然满足红黑树的性质。
8.9.3.2 删除叶子节点中的BLACK节点
删除这些节点有3种情况
- 拥有2个RED子节点的BLACK节点(图中的25节点)
- 拥有1个RED子节点的BLACK节点(图中46节点或76节点)
- 拥有0个RED子节点的BLACK节点(图中88节点)
删除拥有2个RED子节点的BLACK节点(图中的25节点)
这种情况不可能会直接删除，因为它会找它的子节点替代删除。如下图所示17或33节点会直接覆盖25节点
删除拥有1个RED子节点的BLACK节点(图中46节点或76节点)
将要删除的BLACK节点的parent节点的子节点指向为将要删除的BLACK节点的RED子节点，并将RED节点进行染色成BLACK。如下图所示
删除拥有0个RED子节点的BLACK节点(图中88节点)
删除拥有0个RED子节点的BLACK节点也分很多种情况
8.9.3.2.1 删除拥有0个RED子节点的BLACK节点为根节点时
若只删除的BLACK节点为根节点时直接删除即可
8.9.3.2.2 删除拥有0个RED子节点的BLACK节点的sibling节点为BLACK节点时
如下图所示我们要删除的88节点的sibling节点76节点是BLACK节点
如果删除88节点直接相当于B树的删除的下溢现象，处理方式就按B树的下溢进行处理就即可。
引用B树的下溢操作如下
将父节点插入到下溢节点88节点位置(最小位置)
用兄弟节点的最大的元素替代父节点的元素
操作结果如下
以下两种情况和上边情况相同。
但是此修复过程需要满足删除的BLACK节点的兄弟节点必须有RED节点。
8.9.3.2.3 删除拥有0个RED子节点的BLACK节点的sibling节点为BLACK节点并没有子节点时
如下图情况所示删除88节点，但是88节点的兄弟节点没有RED子节点
将88的兄弟节点染成RED，将88的父节点染成BLACK就能满足红黑树的性质。修复结果如下图
8.9.3.2.4 删除拥有0个RED子节点的BLACK节点的sibling节点为RED节点时
处理步骤如下
将兄弟节点55染成BLACK,将要删除的88节点的父节点染色成RED，然后进行旋转，将80节点的父节点指向55节点，将76节点的父节点指向80节点
变化为如下图所示
变化成如上图所示之后情况就变成了8.9.3.2.3 的情况，要删除的节点的兄弟节点是BLACK节点，并兄弟节点没有RED子节点。下边操作就按8.9.3.2.3步骤继续执行即可
最后红黑树的机构和8.9.3.2.3的结果是一样的。
9. 集合
集合的特点不存放重复的元素，常用于去重
10. 映射(Map)
Map在有些编程语言中也叫做字段。一个key对应一个value。
Map的每一个key都是唯一的。
11. 哈希表(Hash Table)
哈希表也叫作散列表。
首先来看看哈希表是如何实现数据处理的？
put(“jack”, 666)
put(“rose”, 777)
put(“kate”, 888)
当要存放值时，如下图所示会对key进行hash计算，将计算出来的数值作为索引存到table的对应位置中，哈希表的底层是通过数组来存储元素的。
哈希表是空间换时间的典型应用。如上图所示虽然我们只添加了三个元素，但是实际上事先申请了大于三个元素的内存。
哈希函数也经常叫做散列函数。
哈希表内部的数组元素，很多地方叫做Bucket(桶)，整个数组叫Buckets或者Bucker Array。
11.1 哈希冲突
哈希冲突也叫做哈希碰撞，2个不同的key经过哈希计算出相同的结果
如下图，对Rose和Kate进行哈希计算之后，有可能得到的哈希值是相同的，这时候就出现了哈希碰撞现象。
解决哈希冲突的常见方法:
- 开放定址法(Open Addressing)
开放定址法就是按照一定规则向其他地址探测，直到遇到空桶。比如添加完Rose为key的值之后，已经在下标为3的地方存好了对应的值。当再添加Kate为key的值时，发现下标为3的地方已经有了其他元素，这时候按一定探测规则找寻空桶，直到发现空桶之后保存Kate对应的值。
探测规则可以是线性探测，比如一个一个往下查询。探测规则还有平方探测等规则，就不一 一举例。 - 再哈希法(Re-Hashing)
再哈希法是设计多个哈希函数，当发生哈希碰撞之后，再使用其他的哈希函数进行计算获取新的哈希值。 - 链地址法(Separate Chaining)
链地址法是通过链表将相同索引元素串起来
在JDK1.8中使用链地址法解决哈希冲突，并且使用的是单向链表将元素串起来。在添加元素时单向链表可能转变为红黑树来存储元素。
那么什么时候由链表转换为哈希表呢？
比如当哈希表容量>64且单向链表的节点数量大于8时，当日当红黑树的节点少到一定数量时，又会转变为单向链表。
所以JDK1.8中的哈希表是使用链表+红黑树解决哈希冲突
12. 二叉堆(Heap)
堆(Heap)也是一种一种树状的数据结构(不要跟内存模型中堆空间混淆)。
场景的堆实现有:
- 二叉堆(Binary Heap, 完全二叉堆)
- 多叉堆(D-heap、D-ary Heap)
- 索引堆(Index Heap)
- 二项堆(Binomial Heap)
- 斐波那契堆(Fibonacci Heap)
- 左倾堆(Leftist Heap)
- 斜堆(Skew Heap)
这里只讲解二叉堆，但是不管什么堆都满足一个重要性质，任意节点的值总是≥或≤子节点的值。
如果任意节点的值总是≥子节点的值，也称为最大堆、大根堆、大顶堆
下图的堆就是一个二叉堆也是最大堆
如果任意节点的值总是≤子节点的值，也称为最小堆，小根堆，小顶堆
下图的堆就是一个二叉堆也是最小堆
堆顶元素不是最大值就是最小值，取决于这个堆是最大堆还是最小堆。
二叉堆的逻辑结构就是一颗完全二叉树，所以也叫完全二叉堆
鉴于完全二叉树的一些特性，二叉堆的底层(物理结构)一般用数组实现即可。
由于二叉堆的元素摆放特点是从上到下，从左到右，所以可以考虑用数组存储这些元素
索引i的规律
如果i=0, 它是根节点
如果i > 0, 它的父节点索引为floor((i - 1) / 2), floor函数为向下取整
如果2i + 1 ≤ n - 1， 它的左子节点索引为 2i + 1， n是元素个数
如果2i + 1 ＞ n - 1，它没有左子节点
如果2i + 2 ≤ n - 1， 它的右子节点索引为 2i + 2
如果2i + 2 ＞ n - 1，它没有右子节点
12.1 二叉堆的添加
由于任意节点的值总是≥或≤子节点的值，并且二叉堆的元素摆放特点是从上到下，从左到右，因此添加元素之后会有可能不满足二叉堆的特性。如下图所示，添加80元素。不满足二叉堆的任意节点的值总是≥或≤子节点的值的特性。
我们需要将80元素不断的往上移，来满足二叉堆的特性。
将80节点与父节点进行比较，若大于父节点，将父节点与80节点进行交换，如下图所示
交换之后再将80与交换之后的位置的父节点进行比较，若大于父节点，将父节点与80节点进行交换，如下图所示
交换之后再将80与交换之后的位置的父节点进行比较，若大于父节点，将父节点与80节点进行交换，如下图所示
直到满足二叉堆的特性或没有父节点可以进行比较，就算元素添加完成。
总结二叉堆的添加循环执行以下操作
如果node > 父节点
与父节点交换位置
如果node ≤ 父节点，或者node没有父节点
退出循环
这是最大堆的添加，最小堆也同理判断node < 父节点即可
这个过程也叫做上滤(Sift Up)
12.2 二叉堆的删除
对于二叉堆来说，每次删除都是删除堆顶的元素，最大或者最小的元素，本次我们以最大堆来讨论
比如要删除80元素，如果按照数组的删除思维，直接删除80，那么所有元素都必须要往前挪，这个时候时间复杂度是O(n), 这样就无法达到高效率。
因此换一种方案，删除栈顶元素时，拿到最后一个元素，覆盖栈顶元素的位置
交换元素的时间复杂度是O(1),但是交换之后发现不满足二叉堆的性质。
发现目前的栈顶元素小于左右子节点的元素，挑出最大子节点进行交换。
交换之后再判断43元素是否大于左右子节点。若不满足进行如上操作，挑出最大子节点进行交换
交换之后再判断43元素是否大于左右子节点，这时满足二叉堆的性质，无需再进行操作。如上步骤是二叉堆的删除操作步骤。
这个过程也叫作下滤(Sift Down)
12.3 批量建堆
批量建堆（Heapify）：就是将已经存在n个元素的数组批量添加至堆中，而不是遍历数组一个一个将元素添加至堆中。如果一个一个添加元素效率会比较低，所以不推荐一个一个添加。
批量建堆有2种实现方式
- 自上而下的上滤，每个节点从上到下进行上滤操作
- 自下而上的下滤，每个节点从下而上进行下滤操作
12.3.1 最大堆-批量建堆-自上而下的上滤
最大堆-批量建堆-自上而下的上滤具体操作如下
- 30元素是根节点，无需上滤操作
- 34元素进行上滤操作，与父节点进行比较，大于父节点进行交换
- 73元素进行上滤操作，与父节点进行比较，大于父节点进行交换
- 60元素进行上滤操作，与父节点进行比较，大于父节点进行交换，交换之后还有父节点可比较，继续上滤操作
- 以此类推。。。。。
12.3.2 最大堆-批量建堆-自下而上的下滤
自下而上的下滤如下图所示，从43,68,60,73,34,30的顺序进行操作，具体操作步骤不再具体讲解。
自下而上的下滤比自上而下的上滤效果高。因为自上而下的上滤操作时，叶子节点的数量就有近n/2个，每一个叶子节点往上移动之后要多次进行上滤操作，所以自上而下的上滤效率比自下而上的下滤效率低。
13. 优先级队列(Priority Queue)
优先级队列也是个队列，普通队列是FIFO原则，也就是先进先出。
优先级队列则是按照优先级高低进行出队，比如将优先级最高的元素作为队头优先出队。
根据优先队列的特点，可以将最大堆作为优先队列的底层实现。
