什么是数据结构？
    数据结构就是用来存储数据与数据之间关系的一种集合，是计算机用来管理和组织数据的一种方式。

    一.集合结构
    List ：ArrayList、LinkedList、Vector
    Set ：HashSet、TreeSet
    Map ：HashMap、TreeMap、ConcurrentHashMap
    二.线性结构
    数组
    链表
    栈
    队列
    String、StringBuffer、StringBuilder
    三.树形结构
    1.二叉树
    二叉树又可以分为满二叉树和完全二叉树
    满二叉树：除了叶子节点以外，所有的节点的度都是2
    完全二叉树：就是说最后一层叶子节点缺了，如果存在得叶子节点是从左到右依次排列，那就是完全二叉树，如果中间有断开那就是非完全二叉树。

    1.1二叉排序树
    1.1.1 其左侧节点小于父节点的值
    1.1.2 其右侧节点大于父节点的值
    1.1.3 其他的左右子树也分别是二叉查找树
    其查找和插入的时间复杂度为O（logN）

    1.2平衡二叉树（AVL）
    其根节点的左右子树的深度差不超过1，那就是平衡二叉树。平衡二叉树是为了解决二叉树在添加时只添加到一侧导致退化成链表的问题。
    1.2.1 平衡二叉树根节点的左右子树的深度差不超过1
    1.2.2 平衡二叉树其左右子树也时平衡二叉树

    1.3红黑树
    红黑树是一种特殊的平衡二叉树，在其基础上给每个节点增加了颜色的属性。
    1.3.1 所有节点要么时红色，要么是黑色
    1.3.2 根节点必须是黑色
    1.3.3 叶子节点必须是黑色
    1.3.4 如果一个节点是红色，其父节点必须是黑色，其两个子节点也必须是黑色
    红色节点不能连续出现
    从根节点到任意叶子节点不能出现两个连续的红色节点
    1.3.5 从根节点走到任意一个叶子节点所经历的黑色节点是相同的

    红黑树的查询效率略微低于平衡二叉树，但是插入和删除的效率高于平衡二叉树。平衡二叉树在增删的时候会进行大量的平衡度计算，而红黑树是通过颜色改变+左旋右旋的方式来达到自适应平衡。

    1.4哈夫曼树

    2.多叉树
    什么是多叉树？为什么要使用多叉树？
    传统的二叉树在面对数据量过大的情况下树的层级会过深，会导致频繁的发生磁盘IO。为了避免这种情况的出现，所以我们需要使用到多叉树，而多叉树就是使用在存储大量的数据或者管理文件的时候使用。其通过每个节点保存多个元素，采用更多分叉，这两种方式来减少树的深度。
    多叉树又分为B树和B+树

    B树：
    1.节点中保存的元素是K-V形式，将值保存在元素中。
    2.每个节点中能存放的元素数量为最大层级-1个，每个节点能拥有的子节点数量等于最大层级。
    3.每个节点中可以保存2个或2个以上的元素。
    B树多用于文件系统以及部分数据库索引，如MongoDB，而大部分数据库使用B+树，如MySQL。
    B树算法的执行时间主要是读，写磁盘的次数来决定，1次IO应尽可能读多的数据。所以，B树的节点规模一般是以一个磁盘页为单位，某个节点的关键字和其拥有的子节点个数取决于磁盘页的大小。

    B+树：
    1.节点只保存K做索引，而具体的数据保存在叶子节点。
    2.每个节点存放的元素和其子节点的个数是一样的。
    3.其叶子节点会形成一个有序的链表。

    B+树相比B树的优点：
    1.因为B+树只存放索引，所以在同样的磁盘页大小的情况下，B+树能存放更多的元素，这样树的高度就会更小，查询效率也会更高。
    2.因为B+树的具体数据都是存放在叶子节点，所以它总会查到叶子节点，所以它的查询稳定性也优于B树。
    3.因为其叶子节点会形成一个有序链表，所以更利于范围查询和排序。

    三、算法
    1.Hash算法
    Hash算法又被称为散列算法，就是输入任意长度的值通过散列算法转换为固定长度，它最终的输出就是散列值，这种转换通常是压缩映射。也就是说，输出的值占用空间比输入的更小。但是不同的值通过Hash算法得到的散列值有可能相等，这就会造成哈希冲突，所以我们不能只靠散列值来确认其唯一性，还要比较其值本身。

    Hash算法大致原理：
    散列算法就是通过其节点的关键码值去计算存储地址，以它的K为变量，通过哈希函数，计算出一个哈希值，就这个值作为节点的存储地址。查询的时候也是一样，通过同样的方式计算地址，然后再去对应的地址中找到节点。

    Hash冲突解决方法：
    1.拉链法
    Java中HashMap就是使用的拉链法
    当发生Hash冲突的时候，如果这两个对象的k计算出的hash值相等，equals不等，就会在其后形成链表
    优点：
    1.因为其空间都是动态生成的，适合用于事先不确定长度的场景
    2.删除方便，只需要去链表上删除对应节点的记录即可
    缺点：
    1.指针需要额外的空间，在规模较小时，开发地址法更节省空间
    2.因为使用了指针，记录不容易进行序列化

    2.开发地址法
    当发生哈希冲突时，以当前地址为基准，通过探测技术找到下一个地址，如果冲突继续寻找，直到找到一个空位置位置。
    优点：
    1.记录更容易进行序列化
    2.如果能够提前记录总数，可以提交建立完美的哈希函数，这个时候的效率是非常高的
    探测分为线性探测和二次探测

    缺点：
    1.删除更麻烦。如果删除A节点，其后的B节点是在和A冲突以后重新计算找到的位置，如果这个时候删除A，就会导致A的位置变成空值，而空是查找结束的条件，这就会导致A以后的参数不可见。所以会在A的位置上打上删除标记，这就需要额外的空间和操作。
    2.使用探测技术，有可能其计算成本过高，导致Hash表的效率下降
    3.数组存放长度是有限的，如果超过就需要扩容，如果扩容，就会导致某次探测的时间成本极大增加。

    3.再哈希法
    如果发生哈希冲突，更换一个哈希函数重新计算哈希值，重新确定位置

    4.建立公共溢出区
    将Hash表分为了基本表和溢出表，发生哈希冲突的全部移除到溢出表。

    2.排序算法
    冒泡算法 时间复杂度O（n2），但是使用简单且稳定
    快速排序 时间负责度O（logn），但是使用复杂且不稳定
    选择排序
    堆排序
    归并排序

    3.查询算法
    顺序查找 相当于就是遍历
    二分查找 每次把集合分成一半进行查找，效率高
    斐波那契查找

    时间复杂度
    O(1) 常数阶< O(logn)对数阶 < O(n)线性阶 < O(nlogn)线性对数阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指阶