java数据结构及算法总结( 二 ) _java

散列表无论是Set还是Map，我们会发现都会有对应的-->HashSet,HashMap
首先我们也先得回顾一下数据和链表：

链表和数组都可以按照人们的意愿来排列元素的次序，他们可以说是有序的(存储的顺序和取出的顺序是一致的)
这会带来缺点：想要获取某个元素，就要访问所有的元素，直到找到为止，会消耗很多时间。

所以我们需要另外的存储结构：不在意元素顺序，能快速查找元素。其中就有一种常见方式：散列表。
散列表工作原理
散列表为每个对象计算出一个整数，称为散列码。根据这些计算出来的整数(散列码)保存在对应的位置上！即，散列码就是索引。
在Java中，散列表用的是链表数组实现的，每个列表称之为桶。
红黑树是一种平衡二叉树，TreeSet、TreeMap底层都是红黑树来实现的。
二叉查找树也有个例(最坏)的情况(线性)：

文章插图

上面符合二叉树的特性，但是它是线性的，完全没树的用处，树是要“均衡”才能将它的优点展示出来，比如下面这种:

文章插图

因此，就有了平衡树这么一个概念~红黑树就是一种平衡树，它可以保证二叉树基本符合均衡的金字塔结构。都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它的统计性能要好于平衡二叉树
上图就是一个红黑树，红黑树就字面上的意思，有红色的节点，有黑色的节点。

性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3. 每个叶节点（NIL节点，空节点）是黑色的。
性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

b树：平衡二叉树的查找效率为O（log2N）与树的深度相关，通过降低树的深度，可以提高查找效率，但是还有一个瓶颈就是，每次查找一次就只能得到一个节点元素，如果查找一次能得到多个节点元素，那么在同样的高度就能够查找更多的元素，从而提高查找效率，因此提出多路查找树。
多路查找树（muitl-way search tree），其每一个结点的孩子数可以多于两个，且每个结点出可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
B树就是一种平衡的多路查找树。
B-树中所有结点中孩子结点个数的最大值成为B-树的阶，通常用m表示，从查找效率考虑，一般要求m>=3 。一棵m阶B-树或者是一棵空树，或者是满足以下条件的m叉树。
1）每个结点最多有m个分支（子树）；而最少分支数要看是否为根结点，如果是根结点且不是叶子结点，则至少要有两个分支，非根非叶结点至少有ceil(m/2)个分支，这里ceil代表向上取整。
2）如果一个结点有n-1个关键字，那么该结点有n个分支。这n-1个关键字按照递增顺序排列。
3）每个节点的结构为
节点个数：n；
关键字数组： k[n]，这n个关键字按照递增顺序排列
孩子指针数组：p[n + 1], p0<=k1, 之后所有 ki < pi <= ki+1;
B+树1）在B+树中，具有n个关键字的结点有n个分支，而在B-树中，具有n个关键字的结点含有n+1个关键字。
2）在B+树中，每个结点（除根结点外）中的关键字个数n的取值为ceil(m/2) <= n <=m,根结点的取值范围为1<=n<=m，b树他们的取值范围分别是ceil(m/2) -1<= n <=m-1和1<=n<=m-1 。
3）在B+树中叶子结点包含信息，并且包含了全部关键字，叶子结点引出的指针指向记录。
4）在B+树中的所有非叶子结点仅起到一个索引的作用，即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针。
算法：1.二分查找：又称折半查找；优点是比较次数少，查询速度快，平均性能好，占用系统内存较少，其缺点是：要求待查表为有序表，且插入删除困难。
2.递归算法
递归简单理解就是方法自身调用自身。
排序算法：1.直接插入排序；2.希尔排序，3，选择排序，4.堆排序；5，冒泡排序6，快速排序，7，归并排序，8.基数排序
1.冒泡排序：他重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来，走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成、整个算法的名字由来是因为越小的元素会经由交换慢慢‘浮’到数列的顶端。