哈希表也叫散列表，是一种可以通过关键码值（Key-Value）直接访问的数据结构，可以实现快速查询、插入、删除。
数组类型的数据结构在插入和删除时时间复杂度高；链表类型的数据结构在查询时时间复杂度高；而哈希表结合了数组与链表的优势。
在jdk8中，Java中经典的HashMap，以数组+链表+红黑树构成。
哈希函数在哈希表中起着关键作用，能够将任意长度的输入转为定长的输出（哈希值）。通过哈希函数，能够快速地对数据元素进行定位。
哈希值并不是具有唯一性，在某些情况下Hash值会冲突，HashMap在Hash冲突时，会将元素在数组的位置上添加为链表元素结点，当链表长度大于8时，链表会转换为 红黑树 。
数组是一种线性表的数据结构， 连续的空间存储相同类型 的数据。
特点：
数组在创建时大小确定，无法扩容。数组只能存储一种类型的数据。添加、删除元素慢。
数组中的每个元素有自己的下标，从0开始，直到数组长度-1 查询速度快；
在内存中顺序存储（在内存中占用了连续完整的存储空间），可以很好的实现逻辑上的顺序表
数组实际元素的数量可能小于数组的长度 ;
适合读操作多，写操作少的场景 ;
数组属于线性的数据结构;
数组内存结构分析：数组是引用数据类型，存放在堆内存中（数组名存放在栈内存中，是一
个地址，数组的内容存放在对堆内存中）
定义：在物理上 非连续、非顺序 的数据结构，由若干节点组成。
单向链表：每一个节点包含两部分。一部分是存放数据的变量 data , 另一部分是指向下一个节点的指针 next ;
双向链表：除了 data 和 next 指针，还有指向前置节点的 pre 指针
特点： 在内存中随机存储（每个节点分布在内存的不同位置，依靠 next 指针关联起来），可以很好的实现逻辑上的顺序表 链表中的数据只能根据指针按顺序进行访问 ; 适合插入删除频繁的场景 ; 链表属于线性的数据结构
定义：是一种线性数据结构，栈中的元素只能先入后出。
特点： 栈中的元素只能先入后出（First In Last Out，简称FILO） 最早进入的元素存放的位置叫做 栈底（bottom）,最后进入的元素存放的位置叫做 栈顶（top） ;
栈属于线性数据结构，既可以用数组来实现，也可以用链表来实现 出栈和入栈只会影响到最后一个元素 栈的输出顺序和输入顺序相反，通常用于“历史”的回溯
栈的基本操作：
入栈（push）：只允许从栈顶一侧放入元素，新元素的位置将会称为新的栈顶。
出栈（pop）：只有栈顶中元素才允许出栈，出栈元素的前一个元素将会称为新的栈顶
举例：一段封闭，一段开口的圆筒，往圆筒里放入乒乓球。先放入的靠近圆筒底部，后放入的靠近圆筒入口。要想取出乒乓球，只能按照和放入顺序相反的顺序来取。
定义：是一种线性数据结构，队列中的元素只能先入先出。
特点： 队列中的元素只能先入先出（First In First Out，简称FIFO） 队列的出口端叫做 队头（front）, 队列的入口端叫做 队尾（rear） ;
队列属于线性数据结构，既可以用数组来实现，也可以用链表来实现 在物理存储上，队尾的位置也可以在队头之前 队列的输出顺序和输入顺序相同，通常用于“历史”的回放
队列的基本操作：
入队（enqueue）：只允许在队尾的位置放入元素，新元素的下一个位置将会称为新的队尾。
出队（dequeue）：只允许在队头一侧移出元素，出队元素的后一个元素将会称为新的队头。
举例：公路上的一条单行隧道，所有通过隧道的车辆只允许从隧道入口驶入，从隧道出口驶出，不允许逆行。要想让车辆驶出隧道，只能按照他们驶入隧道的顺序来驶出。
若其左子树非空，则左子树上所有节点的值都小于根节点的值
若其右子树非空，则右子树上所有节点的值都大于根节点的值
其左右子树都是一棵二叉查找树
二叉查找树的特性：左子树<根<右子树，即二叉查找树的中序遍历是一个递增序列。
删除元素
node的左右子树都是空，则直接删除，让指向它的父结点指向空即可；
node左右子树至少一个不为空，我们需要找到在中序遍历中，node的前驱结点或后继节点来替代它的位置。
如果node的左子树为空，那就使用node的右子树顶替node的位置
否则，如果node的右子树为空，那就使用node的左子树顶替node的位置
否则，即左右子树都不是空，我们可以在左子树上找一个“最右的结点”，或在右子树上找一个“最左”的结点，顶替node的位置
任意节点的子树的高度差都小于等于 1
红黑树是一种二叉查找树，且具有如下特性：
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点。
二叉查找树可能存在不平衡的问题，左子树很长但是右子树很短，或者只是在一边进行插入变成线型的结构，造成查询时性能不佳（logn退化成n），平衡二叉树能保证层数平均，从而查询效率高，但是维护又很麻烦，每次插入和删除有很大的可能要大幅调整树结构。
红黑树是介于完全不平衡和完全平衡之间的一种二叉树，通过每个节点有红黑两种颜色、从节点到任意叶子节点会经过相同数量的黑色节点等一系列规则，数的层数差最大也不会超过一倍，这样既能提高插入和删除的效率，又能让树相对平衡从而有还不错的查询效率。从整体上讲，红黑树就是一种中庸之道的二叉树排序二叉树有不平衡的问题。
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个）
特点：
（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
（2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
（3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
（4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;
