删除|字节算法大神熬了三个通宵整理的数据结构与算法笔记（万字长文）( 四 )

1.2 二次探测（Quadratic Probing）
线性探测每次探测的步长是 1 ，二次探测的步长则为“二次方” 。
1.3 双重散列（Double hashing）
使用一组散列函数，当hash1(key)冲突时再用hash2(key)……直至找到空闲的位置。
装载因子计算公式：
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
2. 链表法
该方法更为常用。在散列表中，每个“桶（bucket）”或“槽（slot）”会对应一条链表，所有散列值相同的元素都会放到相同槽位对应的链表中，如图所示：

二者对比
1. 当数据量比较小、装载因子小的时候，适合采用开放寻址法（例如 Java 中的 ThreadLocalMap）。
2. 链表法比较适合存储大对象、大数据量的散列表；而且比开放寻址法更灵活、支持更多的优化策略（比如用红黑树替代链表， JDK 1.8 中 HashMap 的实现）。

PS: 由于链表要存储指针，当存储比较小的对象时内存消耗可能会翻倍；而存储大对象，即存储对象的大小远大于一个指针的大小（4 或 8 个字节）时，链表中指针的内存消耗可以忽略了。

小结
1. 跳表
跳表是在链表的基础上增加索引层来提高查找效率，但同时也增加了存储空间开销，利用“空间换时间”的思想。
常见应用场景：Redis 中的有序集合。
2. 散列表
两个核心问题：散列函数设计和散列冲突解决。
散列冲突常用的解决方法有两种：开放寻址法和链表法。
散列函数设计的好坏决定了散列冲突的概率，也决定了散列表的性能。
数据结构与算法（三）树
数据结构中的树（Tree）与生活中常见的树有些类似，可以类比为生活中的树倒过来。示意图：

相关概念
每个元素称为「节点」，用来连线相邻节点之间的关系叫作「父子关系」。示意图：

其中， A节点是B节点的「父节点」， B节点是A节点的「子节点」。 B、C、D节点有同一个父节点A ，它们互称为「兄弟节点」。没有父节点的节点（E）称为「根节点」，没有子节点的节点（G、H、I、J）称为「叶子节点」或「叶节点」。
高度、深度和层
1. 节点的高度（Height）：节点到叶子节点的最长路径；
2. 节点的深度（Depth）：根节点到这个节点所经历的边的个数；
3. 节点的层数（Level）：节点的深度 + 1；
4. 树的高度：根节点的高度。
示意图：

二叉树
树的结构有多种，其中最常用的是二叉树（Binary Tree）。
二叉树的每个节点最多有两个“叉” ，也就是两个节点，分别为「左子节点」和「右子节点」。如图所示：

1. 左边的二叉树：一棵普通的二叉树；
2. 中间的二叉树：叶子节点全都在最底层，而且除了叶子节点外，每个节点都有左右两个子节点，称为「满二叉树」；
3. 右边的二叉树：叶子节点都在最底下两层，且最后一层的叶子节点都靠左排列，除了最后一层，其他层的节点个数都达到最大，称为「完全二叉树」。
二叉树的存储
两种方式：基于指针（或引用）的链式存储法，基于数组的顺序存储法。
链式存储法：每个节点有三个字段，其中一个存数据，另外两个分别为指向左右子节点的指针。如图所示：

顺序存储法：根节点存储在下标为i= 1 的位置，左子节点下标为 2 *i= 2 ，右子节点下标为 2 *i+ 1 = 3 ，以此类推。如图所示：

值得注意的是，这里存储的是一颗完全二叉树，因此它在数组中只有第一个位置为空。若不是完全二叉树，则其存储结构如下：