什么是Hash表

Hash表本质上还是利用数组来存储数据。

但是哈希表解决了数组存在的一些问题：数据插入和删除效率较低、关键在于查找数据时，如果使用元素去查找，时间复杂度是O(n)。

哈希表能够很好的提供插入、查找、删除操作。插入和删除的时间复杂度接近于常量时间，也就是O(1)。查找速度也很快，取决于哈希表的实现方案。基本上两到三次就可以找到查找数据。

那么哈希表的实现：

1. 首先是通过将存储值通过哈希化，将一个较大值通过哈希函数计算得到一个存储数组的下标。具体如下：
   • 首先计算哈希值，根据霍纳法则，哈希值乘以质数，与将要计算值的每一位进行异或操作，得到最终的哈希值，
   • 然后再与存储数组的长度进行取余，获取要存储的下表。
2. 然后将值存储到数组的这个下标位置。但是可能会出现多个值有相同的下标，此时就需要解决地址冲突。
3. 解决地址冲突的方法分为两种：一种是开放地址法，一种是链地址法。
   • 链地址法：数组的每一位存储的不是一个元素，而是一个链表或者数组，每个元素数据存储在对应位置的链表中，发生冲突，新数据添加到链表中即可
   • 开放地址法又分为三种：
     • 线性探测：如果发生冲突，那么就将向下一个个位置移动查找空白单元，存储数据。但是会出现聚集问题，也就是多个数据集中存储在数组的一块位置，其余位置为空。
     • 然后又有二次探测方法：发生冲突时，之前是一个个移动位置，现在通过获取不同的步长，如第一个$1^2$，第二次$2^2$，以此类推。但是还是会出现此种步长的聚集。
     • 最后的方案是再哈希化法：也就是再次哈细化，将这个值key用另一个哈希函数处理，得到的值作为步长。工作很好的函数stepSize = constant - (key % constant)，其中 constant 是质数，且小于数组的容量。
4. 数组存储在数组中，如果出现冲突过多，就需要进行数组的扩容；或者数组远大于要存储的数据个数，就要进行压缩。那么评判的标准就需要用到装载因子，装载因子等于数据个数除以数组长度。一般情况下，如果装载因子大于0.75，就扩容两倍，然后如果不是质数，再计算直接累加，直到是质数为止。如果装载因子小于0.25，就需要压缩数组。保证平均查找次数为2次。

实现哈希表，主要解决数据查找的效率问题。

哈希表的问题：

• 空间利用率不高，底层使用数组，有空位
• 数据本身无序的

什么是二叉树

如果树中每个节点最多有两个子节点，这样的树就称为二叉树。

二叉树的特性：

• 一个二叉树第i层的最大节点数为$2^{i-1}$

• 深度为k的二叉树最多节点个数为$2^{k} - 1$

• 任何非空二叉树，

二叉搜索树：

• 非空左子树所有键值小于其根节点的值
• 非空右子树所有键值大于其根节点的值
• 左、右子树本身也都是二叉搜索树

红黑树：

• 节点非黑即红

• 根节点是黑色的

• 叶子节点是黑色的Nil节点

• 红节点的叶子节点是黑色的，也就是说不能有两个连续的红节点

• 任意节点到叶子节点，路径中包含的黑色节点数是相同的

• 插入节点 （插入节点是红色节点）

  1. 插入节点是根节点，直接变为黑色
  2. 插入节点父节点是黑色节点，直接插入即可
  3. 插入节点父节点是红色，叔叔节点也是红色，此时祖父节点必为黑色。那么将父叔节点变黑，祖父节点变红。此时视角移到祖父节点，可能遇到其它情况。
  4. 插入节点父节点红色且是父节点的左子节点，叔叔节点和祖父节点是黑色。此时，父节点变黑，祖父节点变红；以祖父节点为轴进行右旋转。
  5. 插入节点父节点是红色且是父节点的右子节点，叔叔和祖父节点黑色。父节点左旋转。然后回归到情况4，是左子节点的情况。