动态数组属于线性表的一种，所有元素的内存地址是连续的
动态数组的缺点：插入元素时重新排序索引，数组扩容时浪费存储空间
链表是一种链式存储的线性表，所有元素的内存地址不是连续的，前一个元素存储下一个元素的地址。
3. 双向链表使用双向链表可以提升链表的总和性能
当双向链表只有一个元素时的结构如下
动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费
双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间浪费
- 如果频繁在尾部进行添加、删除操作，动态数组和双向链表均可选择
- 如果频繁在头部进行添加、删除操作，建议使用双向链表
- 如果有频繁的(在任意位置)添加、删除操作，建议使用双向链表
- 如果有频繁的查询操作(随机访问操作)，建议使用动态数组
栈是一种特殊的线性表，只能在一端进行操作
栈采用后进先出的原则
往栈中添加元素的操作，一般叫做push，入栈 。如下图所示
从栈中移出元素的操作，一般叫做pop，出栈(只能移出栈顶元素)。如下图所示
队列时一种线性表，只能在头尾两端进行操作
对尾(rear): 只能从队尾添加元素，一般叫做入队(add)
对头(front): 只能从队头移出元素，一般叫做出队(remove或者poll)
队列采用先进先出的原则
使用树形结构可以大大提高效率
会以上图为例来讲解树的基本概念
节点
每一个圆圈都代表一个节点
根节点
每一个树只会有一个根节点，上图中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）棵互不相交的树组成的集合
二叉树的特点为每个节点的度最大为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相同
所有节点的度要么为0，要么为2
下图左边的是真二叉树，右边的不是真二叉树，因为有一个节点的度为1
所有节点的度都要么为0，要么为2。而且所有的叶子节点都在最后一层。
满二叉树也属于真二叉树，真二叉树不一定是满二叉树
在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多
叶子节点只会出现最后2层，且最后1层的叶子节点都靠左对齐
完全二叉树从根节点到倒数第2层是一棵满二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
完全二叉树中度为1的节点只有左子树
度为1的节点要么是1个要么是0个，讲解如下图
二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为BST
又被称为：二叉查找树、二叉排序树
任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一颗二叉搜索树
二叉搜索树可以大大提高搜索数据的效率
二叉搜索树存储的元素必须具有可比较性，比如int,double等。如果是自定义类型，需要指定比较方式，不允许为null
8.5 二叉树的遍历根据节点的访问顺序不同, 二叉树的常见遍历方式有4种
- 前序遍历(Preorder Traversal)
- 中序遍历(Inorder Traversal)
- 后序遍历(Postorder Traversal)
- 层序遍历(Level Order Traversal)
前序遍历优先访问根节点，访问完根节点再访问左子树，再去访问右子树
以下图二叉树为例，查询顺序为
- 查询根节点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
中序遍历先访问左子树，再访问根节点，再访问右子树
以上图为例，查询顺序为
1,2,3,4,5,7,8,9,10,11,12
或者反过来，中序遍历先访问右子树，再访问根节点，再访问左子树
以上图为例，查询顺序为
12,11,10,9,8,7,5,4,3,2,1
二叉搜索树的中序遍历结果可以是升序或者降序
后序遍历先访问左子树，再访问右子树，再访问根节点
以上图为例，查询顺序为
1,3,2,5,4,8,10,11,12,9,7
层序遍历从上到下，从左到右依次访问每一个节点
以上图为例，查询顺序为
7,4,9,2,5,8,11,1,3,10,12
如果二叉搜索树添加元素时，按从小到大添加节点，那么二叉搜索树会退化为链表，那么效率大大退化。不光是添加元素，删除节点时，二叉搜索树也有可能退化为单向链表。二叉搜索树的查询和添加或者删除元素的时间复杂度为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树
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树和二叉搜索树的逻辑完全是等价的。
跟二叉搜索树的搜索方式类似
- 先在节点内部从小到大搜索元素
- 如果命中，搜索结束
- 如果未命中，再去对应的子节点中搜索元素，重复步骤1
B树的添加元素需要满足一点，新添加的元素必定是添加到叶子节点
以上图的B树举例
插入55之后的B树如下
插入95之后的B树如下
再加入98呢？假设这是一棵4阶B树。4阶B数的特点是每个子节点最多拥有3个元素，所以无法将98插入到90,95,100节点当中。这种现象可以称为上溢
我们以5阶B数为举例
当添加34时，会添加到如上图位置区域，但是由于我们设定的B树5阶B数，子节点最多拥有4个元素。
解决上溢方案如下
- 当添加元素之后节点的元素个数等于N的时候（N代表几阶B树）
- 设定上溢节点最中间元素的位置为K，将K的位置与父节点进行合并
- 将[0, k-1]和[k+1,N-1]位置的元素分裂成2个节点，这2个子节点元素个数必然都会低于最低限制
- 如上图所示一次分裂完毕后，有可能导致父节点上溢，依然按照上述方案解决。最极端的情况，有可能一直分裂到根节点。
如果我们要删除的元素在叶子节点中，那么直接删除即可。
假如需要删除的元素在非叶子节点中。
举例我们要删除下图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
这个操作可能会导致父节点下溢，依然按照上述方法解决，下溢现象可能会一直往上传播
- 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
红黑树也是自平衡的二叉搜索树
红黑树会让原来度为0或者度为1的节点变为度为2节点(增加1个或者2个空节点)。
红黑树必须满足以下7个条件
- 节点是 RED 或者 BLACK
- 根节点必须是BLACK
- 叶子节点(空节点)都是BLACK
- RED节点的子节点都是BLACK
- RED节点的parent都是BLACK
- 从根节点到叶子节点的所有路径上不能有2个连续的RED节点
- 从任一节点到叶子节点的所有路径都包含相同数目的BLACK
以上图的一个红黑树(省略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树中真正被删除的元素都在叶子节点中。
以下图的红黑树进行讲解红黑树的节点删除。
删除红黑树中删除叶子节点中的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节点。
如下图情况所示删除88节点，但是88节点的兄弟节点没有RED子节点
将88的兄弟节点染成RED，将88的父节点染成BLACK就能满足红黑树的性质。修复结果如下图
处理步骤如下
将兄弟节点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的结果是一样的。
集合的特点不存放重复的元素，常用于去重
10. 映射(Map)Map在有些编程语言中也叫做字段。一个key对应一个value。
Map的每一个key都是唯一的。
哈希表也叫作散列表。
首先来看看哈希表是如何实现数据处理的？
put(“jack”, 666)
put(“rose”, 777)
put(“kate”, 888)
当要存放值时，如下图所示会对key进行hash计算，将计算出来的数值作为索引存到table的对应位置中，哈希表的底层是通过数组来存储元素的。
哈希表是空间换时间的典型应用。如上图所示虽然我们只添加了三个元素，但是实际上事先申请了大于三个元素的内存。
哈希函数也经常叫做散列函数。
哈希表内部的数组元素，很多地方叫做Bucket(桶)，整个数组叫Buckets或者Bucker Array。
哈希冲突也叫做哈希碰撞，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，它没有右子节点
由于任意节点的值总是≥或≤子节点的值，并且二叉堆的元素摆放特点是从上到下，从左到右，因此添加元素之后会有可能不满足二叉堆的特性。如下图所示，添加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种实现方式
- 自上而下的上滤，每个节点从上到下进行上滤操作
- 自下而上的下滤，每个节点从下而上进行下滤操作
最大堆-批量建堆-自上而下的上滤具体操作如下
- 30元素是根节点，无需上滤操作
- 34元素进行上滤操作，与父节点进行比较，大于父节点进行交换
- 73元素进行上滤操作，与父节点进行比较，大于父节点进行交换
- 60元素进行上滤操作，与父节点进行比较，大于父节点进行交换，交换之后还有父节点可比较，继续上滤操作
- 以此类推。。。。。
自下而上的下滤如下图所示，从43,68,60,73,34,30的顺序进行操作，具体操作步骤不再具体讲解。
自下而上的下滤比自上而下的上滤效果高。因为自上而下的上滤操作时，叶子节点的数量就有近n/2个，每一个叶子节点往上移动之后要多次进行上滤操作，所以自上而下的上滤效率比自下而上的下滤效率低。
优先级队列也是个队列，普通队列是FIFO原则，也就是先进先出。
优先级队列则是按照优先级高低进行出队，比如将优先级最高的元素作为队头优先出队。
根据优先队列的特点，可以将最大堆作为优先队列的底层实现。
