Java中常见数据结构
一、 8种数据结构
Java中有8种常见数据结构
- 哈希表(Hash)
- 队列(Queue)
- 树(Tree)
- 堆(Heap)
- 数组(Array)
- 栈(Stock)
- 链表(Linked List)
- 图(Graph)
哈希表(Hash)
哈希表也叫散列表，是一种可以通过关键码值（Key-Value）直接访问的数据结构，可以实现快速查询、插入、删除。
数组类型的数据结构在插入和删除时时间复杂度高；链表类型的数据结构在查询时时间复杂度高；而哈希表结合了数组与链表的优势。
在jdk8中，Java中经典的HashMap，以数组+链表+红黑树构成。
哈希函数在哈希表中起着关键作用，能够将任意长度的输入转为定长的输出（哈希值）。通过哈希函数，能够快速地对数据元素进行定位。
哈希值并不是具有唯一性，在某些情况下Hash值会冲突，HashMap在Hash冲突时，会将元素在数组的位置上添加为链表元素结点，当链表长度大于8时，链表会转换为红黑树。
队列(Queue)
类比水管，两端放开，一端入水，一端出水。
队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。
树(Tree)
树是一种非线性结构，由n(n>0)个有限结点组成有层次关系的集合。
术语：
-
二叉树：每个结点最多含有2个子树。
-
完全二叉树：除了最外层的结点，其他各层结点都达到最大数。
-
满二叉树：
- 国内定义：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
- 国外定义：如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。
-
二叉查找树：
- 任意结点的左子树不为空，左子树所有结点的值均小于根结点的值。
- 任意结点的右子树不为空，右子树所有结点的值均大于根节点的值。
- 任意结点的左右子树也是一颗二叉查找树。
-
平衡二叉树：也称AVL树，当且仅当任何结点的两棵子树的高度差不大于1的二叉树。Java中HashMap的红黑树就是平衡二叉树！！！
-
B树：一种对读写优化的自平衡二叉树，在数据库的索引中常见的BTREE就是自平衡二叉树。
-
B+树：B+树是应文件系统所需而产生的B树的变形树。
- 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字
- 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。
- 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引。
Java8中HashMap的红黑树
实质上就是平衡二叉树，通过颜色约束二叉树的平衡：
1）每个节点都只能是红色或者黑色
2）根节点是黑色
3）每个叶节点（NIL 节点，空节点）是黑色的。
4）如果一个节点是红色的，则它两个子节点都是黑色的。也就是说在一条路径上不能出现相邻的两个红色节点。
5）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
堆（Heap）
堆可以被看成一个树的数组对象，具有如下特点：
- 堆是一颗完全二叉树。
- 最大堆/大根堆：某个结点的值不大于父结点的值。
- 最小堆/小根堆：某个结点的值不小于父结点的值。
数组（Array）
数组是一种线性表的数据结构，连续的空间存储相同类型的数据。
优点：查询速度快。
缺点：数组在创建时大小确定，无法扩容。数组只能存储一种类型的数据。添加、删除元素慢。
栈(Stock)
栈可以类比为水桶，只有一端能够进出，遵循的先进后出的规则。
栈先进的元素进入栈底，读元素的时候从栈顶取元素。
链表(Linked List)
链表是一种线性表的链式存储方式，链表的内存是不连续的，前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的元素串起来。
- 单向链表：单向链表是最简单的链表形式。我们将链表中最基本的数据称为节点(node)，每一个节点包含了数据块和指向下一个节点的指针。
- 双向链表：顾名思义，双向链表就是有两个方向的链表。同单向链表不同，在双向链表中每一个节点不仅存储指向下一个节点的指针，而且存储指向前一个节点的指针。通过这种方式，能够通过在O(1)时间内通过目的节点直接找到前驱节点，但是同时会增加大量的指针存储空间。
- 循环链表：循环链表与双向链表相似，不同的地方在于：在链表的尾部增加一个指向头结点的指针，头结点也增加一个指向尾节点的指针，以及第一个节点指向头节点的指针，从而更方便索引链表元素。
图(Graph)
一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。