什么是Hash表
Hash表本质上还是利用数组来存储数据。
但是哈希表解决了数组存在的一些问题：数据插入和删除效率较低、关键在于查找数据时，如果使用元素去查找，时间复杂度是O(n)。
哈希表能够很好的提供插入、查找、删除操作。插入和删除的时间复杂度接近于常量时间，也就是O(1)。查找速度也很快，取决于哈希表的实现方案。基本上两到三次就可以找到查找数据。
那么哈希表的实现：
- 首先是通过将存储值通过哈希化，将一个较大值通过哈希函数计算得到一个存储数组的下标。具体如下：
- 首先计算哈希值，根据霍纳法则，哈希值乘以质数，与将要计算值的每一位进行异或操作，得到最终的哈希值，
- 然后再与存储数组的长度进行取余，获取要存储的下表。
- 然后将值存储到数组的这个下标位置。但是可能会出现多个值有相同的下标，此时就需要解决地址冲突。
- 解决地址冲突的方法分为两种：一种是开放地址法，一种是链地址法。
- 链地址法：数组的每一位存储的不是一个元素，而是一个链表或者数组，每个元素数据存储在对应位置的链表中，发生冲突，新数据添加到链表中即可
- 开放地址法又分为三种：
- 线性探测：如果发生冲突，那么就将向下一个个位置移动查找空白单元，存储数据。但是会出现聚集问题，也就是多个数据集中存储在数组的一块位置，其余位置为空。
- 然后又有二次探测方法：发生冲突时，之前是一个个移动位置，现在通过获取不同的步长，如第一个
，第二次 ，以此类推。但是还是会出现此种步长的聚集。 - 最后的方案是再哈希化法：也就是再次哈细化，将这个值
key用另一个哈希函数处理，得到的值作为步长。工作很好的函数stepSize = constant - (key % constant)，其中 constant 是质数，且小于数组的容量。
- 数组存储在数组中，如果出现冲突过多，就需要进行数组的扩容；或者数组远大于要存储的数据个数，就要进行压缩。那么评判的标准就需要用到装载因子，装载因子等于数据个数除以数组长度。一般情况下，如果装载因子大于
0.75，就扩容两倍，然后如果不是质数，再计算直接累加，直到是质数为止。如果装载因子小于0.25，就需要压缩数组。保证平均查找次数为2次。
实现哈希表，主要解决数据查找的效率问题。
哈希表的问题：
- 空间利用率不高，底层使用数组，有空位
- 数据本身无序的
什么是二叉树
如果树中每个节点最多有两个子节点，这样的树就称为二叉树。
二叉树的特性：
一个二叉树第i层的最大节点数为
深度为k的二叉树最多节点个数为
任何非空二叉树，
二叉搜索树：
- 非空左子树所有键值小于其根节点的值
- 非空右子树所有键值大于其根节点的值
- 左、右子树本身也都是二叉搜索树
红黑树：
节点非黑即红
根节点是黑色的
叶子节点是黑色的Nil节点
红节点的叶子节点是黑色的，也就是说不能有两个连续的红节点
任意节点到叶子节点，路径中包含的黑色节点数是相同的
插入节点 （插入节点是红色节点）
- 插入节点是根节点，直接变为黑色
- 插入节点父节点是黑色节点，直接插入即可
- 插入节点父节点是红色，叔叔节点也是红色，此时祖父节点必为黑色。那么将父叔节点变黑，祖父节点变红。此时视角移到祖父节点，可能遇到其它情况。
- 插入节点父节点红色且是父节点的左子节点，叔叔节点和祖父节点是黑色。此时，父节点变黑，祖父节点变红；以祖父节点为轴进行右旋转。
- 插入节点父节点是红色且是父节点的右子节点，叔叔和祖父节点黑色。父节点左旋转。然后回归到情况4，是左子节点的情况。