Java 个人学习笔记—数据结构

谁借莪１个温暖的怀抱￠ 2021-12-20 00:29 217阅读 0赞

## 数据结构: ##

1.  Data\_Structure，它是储存数据的一种结构体，在此结构中储存一些数据，而这些数据之间有一定的关系。
2.  而各数据元素之间的相互关系，又包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。
3.  而一个数据结构的设计过程分成抽象层、数据结构层和实现层。

数据结构在Java的语言体系中按逻辑结构可以分为两大类：线性数据结构和非线性数据结构。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NDE4NTE4_size_16_color_FFFFFF_t_70][]

## 线性数据结构 ##

**1：一维数组**

在Java里面常用的util有：String \[\],int \[\],ArrayList,Vector,CopyOnWriteArrayList等。及可以同过一维数组\[\]自己实现不同逻辑结构的Util类。而ArrayList封装了一些\[\]的基本操作方法。ArrayList和Vector的区别是:Vector是线程安全的，方法同步。CopyOnWriteArrayList也是线程安全的但效率要比Vector高很多。(PS:如果不懂出门右拐看另一篇chat)。

数组这种数据结构典型的操作方法，是根据下标进行操作的，所以insert的的时候可以根据下标插入到具体的某个位置，但是这个时候它后面的元素都得往后面移动一位。所以插入效率比较低,更新，删除效率也比较低，而查询效率非常高,查询效率时间复杂度是1。

**2： 线性表**

线性表是有序的储存结构、链式的储存结构。链表的物理储存空间是不连续的，链表的每一个节点都知道上一个节点、或者下一个节点是谁，通常用Node表示。常见的有顺序链表(LinkedList、Linked\*\*\*)，单项链表（里面只有Node类），双向链表(两个Node类)，循环链表(多个Node类)等。

操作方法：插入效率比较高，插入的时候只需要改变节点的前后节点的连接即可。而查询效率就比较低了，如果实现的不好，需要整个链路找下去才能找到应该找的元素。所以常见的方法有：add(index,element),addFirst(element),addLast(element)。getFirst(),getLast(),get(element)等。

常见的Uitil有：LinkedList，LinkedMap等，而这两个JDK底层也做了N多优化，可以有效避免查询效率低的问题。当自己实现的时候需要注意。其实树形结构可以说是非线性的链式储存结构。

**3: 栈Stack**

栈,最主要的是要实现先进后出，后进先出的逻辑结构。来实现一些场景对逻辑顺序的要求。所以常用的方法有push(element)压栈，pop()出栈。

java.util.Stack。就实现了这用逻辑。而Java的Jvm里面也用的到了此种数据结构，就是线程栈，来保证当前线程的执行顺序。

//初始化
        Stack stack=new Stack();
    
        /**
         * 判断是否为空 stack.empty()
         * 取栈顶值（不出栈）stack.peek()
         * 进栈 stack.push(Object);
         * 出栈 stack.pop();
         * @param args
         */
        public static void main(String[] args) {
            Stack stack = new Stack();
            //1.empty()栈是否为空
            System.out.println(stack.empty());
            //2.peek()栈顶值    3.进栈push()
            stack.push(new Integer(1));
            stack.push("b");
            System.out.println(stack.peek());
            //4.pop()出栈
            stack.pop();
            System.out.println(stack.peek());
        }

**4：队列**

队列，队列是一种特殊的线性数据结构，队列只能允许在队头，队尾进行添加和查询等相关操作。队列又有单项有序队列，双向队列，阻塞队列等。

Queue这种数据结构注定了基本操作方法有：add(E e)加入队列，remove(),poll()等方法。

队列在Java语言环境中是使用频率相当高的数据结构，所有其实现的类也很多来满足不同场景。

![queue][]

> 使用场景也非常多，如线程池，mq，连接池等。

**5：串**

串：也称字符串，是由N个字符组成的优先序列。在Java里面就是指String,而String里面是由chat\[\]来进行储存。

> KMP算法： 这个算法一定要牢记，Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是：在字符串比对的时候，主串的比较位置不需要回退的问题。

## 非线性数据结构 ##

非线性数据结构：常见的有：多维数组，集合，树，图，散列表(hash).

**1：多维数组**

一维数组前面咱也提到了，多维数组无非就是String \[\]\[\],int\[\]\[\]等。Java里面很少提供这样的工具类，而java里面tree和图底层的native方法用了多维数组来储存。

**2：集合**

由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。

![Collection][]

**3：树**

> 树形结构，作者觉得它是一种特殊的链形数据结构。最少有一个根节点组成，可以有多个子节点。树，显然是由递归算法组成。

树的特点：

1.  在一个树结构中，有且仅有一个结点没有直接父节点，它就是根节点。
2.  除了根节点，其他结点有且只有一个直接父节点
3.  每个结点可以有任意多个直接子节点。

树的数据结构又分如下几种：

*  1) 自由树/普通树：对子节点没有任何约束。
    
    ![自由树][format_png]
 *  2) 二叉树：每个节点最多含有两个子节点的树称为二叉树。
    
    2.1) 一般二叉树：每个子节点的父亲节点不一定有两个子节点的二叉树成为一般二叉树。
    
    2.2) 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
    
    2.3) 满二叉树：所有的节点都是二叉的二叉树成为满二叉树。
    
    ![二叉树][format_png 1]
 *  3) 二叉搜索树/BST：binary search tree,又称二叉排序树、二叉查找树。是有序的。要点：如果不为空，那么其左子树节点的值都小于根节点的值；右子树节点的值都大于根节点的值。
    
    ![二叉搜索树][format_png 2]
    
    3.1) 二叉平衡树：二叉搜索树，是有序的排序树，但左右两边包括子节点不一定平衡，而二叉平衡树是排序树的一种，并且加点条件，就是任意一个节点的两个叉的深度差不多（比如差值的绝对值小于某个常数，或者一个不能比另一个深出去一倍之类的）。这样的树可以保证二分搜索任意元素都是O(log n)的，一般还附带带有插入或者删除某个元素也是O(log n)的的性质。
    
    为了实现，二叉平衡树又延伸出来了一些算法，业界常见的有AVL、和红黑算法，所以又有以下两种树：
    
    3.1.1) AVL树：最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。
    
    3.1.2) 红黑树：通过制定了一些红黑标记和左右旋转规则来保证二叉树平衡。
    
    > 红黑树的5条性质：
    > 
    > 1.  每个结点要么是红的，要么是黑的。
    > 2.  根结点是黑的。
    > 3.  每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
    > 4.  如果一个结点是红的，那么它的俩个儿子都是黑的。
    > 5.  对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。
    
    ![红黑树][format_png 3]
 *  4) B-tree：又称B树、B-树。又叫平衡(balance)多路查找树。树中每个结点最多含有m个孩子（m>=2）。它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。
    
    ![B-tree][]
 *  4) B+tree：又称B+。是B-树的变体，也是一种多路搜索树。
    
    ![B+tree][B_tree]

> 树总结：  
> 树在Java里面应用的也比较多。非排序树，主要用来做数据储存和展示。而排序树，主要用来做算法和运算，HashMap里面的TreeNode就用到了红黑树算法。而B+树在数据库的索引原理里面有典型的应用。

**4：Hash**

Hash概念：

*  Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），变换成固定长度的输出，该输出就是散列值。一般通过Hash算法实现。
 *  所谓的Hash算法都是散列算法，把任意长度的输入，变换成固定长度的输出，该输出就是散列值.（如：MD5,SHA1,加解密算法等）
 *  简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

Java中的hashCode：

*  我们都知道所有的class都是Object的子类，既所有的class都会有默认Object.java里面的hashCode的方法，如果自己没有重写，默认情况就是native方法通过对象的内存的+对象的值然后通过hash散列算法计算出来个int的数字。
 *  最大的特性是：不同的对象，不同的值有可能计算出来的hashCode可能是一样的。

Hash表：

*  Java中数据存储方式最底层的两种结构，一种是数组，另一种就是链表。而Hash表就是综合了这两种数据结构。
 *  如：HashTable,HashMap。这个时候就得提一下HashMap的原理了，默认16个数组储存，通过Hash值取模放到不同的桶里面去。（注意：JDK1.8此处算法又做了改进，数组里面的值会演变成树形结构。）
 *  哈希表具有较快（常量级）的查询速度，及相对较快的增删速度，所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”，我们可以理解为“链表的数组”。
    
    ![哈希表][format_png 4]

一致性Hash：

*  我们查看一下HashMap的原理，其实发现Hash很好的解决了单体应用情况下的数据查找和插入的速度问题。但是毕竟单体应用的储存空间是有限的，所有在分布式环境下，应运而生了一致性Hash算法。
 *  用意和hashCode的用意一样，只不过它是取模放在不同的IP机器上而已。具体算法可以找一下相关资料。
 *  而一致性Hash需要注意的就是默认分配的桶比较多些，而当其中一台机器挂了，影响的面比较小一些。
 *  需要注意的是，相同的内容算出来的hash一定是一样的。既：幂等性。
 *  ![一致性Hash][Hash]

### 图 ###

现实的图结构模型有通信网络，交通网络，人际关系网络等，图结构的组织形式比树结构更为复杂，因此，图结构对存储和遍历的要求更高。

1.图：.在计算机程序设计中，图是最常用的数据结构之一。对于存储一般的数据问题，一般用不到图。但对于某些（特别是一些有趣的问题），图是必不可少的。图是一种与树有些相像的数据结构，从数学意义上来讲，树是图的一种。而在计算机程序设计中，图的应用方式与树不同。图通常有一个固定的形状，这是由物理或抽象的问题所决定的。例如图中节点表示城市，而边可能表示城市间的班机航线。当讨论图时，节点通常叫做顶点，

2.一些概念：

图：![format_png 5][]

说明：为引入概念，我们用图13.1a来表示美国某处的简化高速公路网，图13.1b来表示模拟这些告诉公路的图。在图中，圆圈代表高速公路的交汇点，连接圆圈的直线代表告诉公路段，圆圈是顶点，线是边。顶点通常用一些方法来标识----正如图中表示的那样，用字母表中的字母来表示。每条边由两个顶点作为两边。图并不是要试图反映地图上的地理位置。它只是反映了顶点和边的关系----即那些边连接着哪些顶点。它本身不涉及物理的远近和方向。而且一条边可能表示几条可能的公路。两个交叉点之间的连通性（或不连通性）是重要的，而实际的路线并不重要。

a.邻接：如果两个顶点被同一条边连接，就称这两个顶点是邻接的。图13.1中，顶点I 和G是邻接的，但I 和 F 就不是。和某个指定顶点邻接的顶点有时叫它的邻居。如G 的邻居是I，H和F.

b.路径：路径是边的序列，图13.1显示了一条从顶点B到顶点J的路径，这条路径通过了A,E,这条路径称作BAEJ。这两个顶点之间还有其他路径，如BCDJ.

![format_png 6][]

c.连通图：如果至少有一条路径，可以连接起所有的顶点，那么这个图被称作连通的，如图13.2a。如果不能从这里到那里，那么这个图就是非连通的。如13.2b。非连通图包含几个连通子图。在图13.2b中，A和B是一个连通子图，C和D也是一个连通子图。

d.有向图和带权图：图13.1和图13.2中的图是无向图，这说明图中的边没有方向----可以从任意一边到另为一边。所以可以从顶点A到顶点B,或者从顶点B到顶点A。两者是等价的（无向图很好的反映了高速公路网，因为在一条公路上可以按两个方向行驶），然而图还经常被用来模拟另一种情况，即只能沿着边向一个方向行驶。这样的图被称作是有向的。允许移动的方向通常是用一端带有箭头的方向表示。在某些图中，边被赋予一个权值，权值是一个数字，他能代表两个顶点间的物理距离，或从一个顶点到另一个顶点的时间，或者是两点间的花费（如飞机航班），这样的图称为带权图。

3.程序中如何表示图：

3.1.顶点：在非常抽象的图的问题中，知识简单的把顶点编号，从0->n-1,不需要任何变量类型来存储顶点，因为他们的用处来自于他们之间的相互关系，但大多数情况下，顶点表示某个真实世界的对象。顶点对象能放在数组中，然后用下标指示。

3.2.边：图并不像树，拥有几种固定的结构，二叉树中顶点最多有两个子节点，但图的每个顶点可以与任意多个顶点相连。为此，一般用两个方法表示图，邻接矩阵和邻接表。（如果一条边连接两个顶点，那么这两个顶点就是邻接的）

3.2.1.邻接矩阵：它是一个二维数组，数据项表示两点间是否存在边，如果图有N个顶点，邻接矩阵就是N \* N 的数组。表13.1显示了图13.1a中图的邻接矩阵。

图：![format_png 7][]

说明：顶点被用作行和列的标题，这两个顶点间右边则标识为1，无边则标识为0.（也可用boolean值表示），如图所示，顶点A 和另为3个顶点邻接，B和A,D邻接，C只与A邻接。而D与A和B邻接。从A-A到D-D称为主对角线，顶点和自身的连接设为0。也可设为1.

3.2.2.邻接表：表指的是链表，实际上，邻接表是一个链表数组。每个单独的链表表示了有哪些顶点和当前顶点邻接。表13.2显示了13.2a中图的邻接表。

图：![format_png 8][]

说明：本表中符号-->表示链表中的一个节点，链表中每个节点都是一个顶点，链表中的每个节点都是一个顶点，在这里的每个链表中，顶点按字母顺序排列，不过这并不是必须的。不要把邻接表的内容与路径混淆，邻接表表示了当前节点与那些节点相连------即，两个节点间存在边，而不是表示顶点间的路径。

4.图的搜素：图中实现的最基本的操作之一就是搜索从一个指定顶点可以到达那些顶点。有两种常用的方法来搜索树，深度优先搜索（DFS）和广度优先搜索（BFS）,他们最终都会到达所有连通的顶点，深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。

4.1.深度优先搜索：找到一个起始点---本例为顶点A,需要做三件事情，首先访问该节点，然后把该点放入栈中，以便记住它，最后标记该点，这样就不会再访问它了。

4.1.1.图解：![format_png 9][]

4.1.2.主要规则：

4.1.2.1.规则1：如果可能，访问一个邻接的未访问顶点，标记它，并把他放入栈中。

4.1.2.2.规则2：当不能执行规则1时，如果栈非空，就从栈中弹出一个顶点。

4.1.2.3.规则3：如果不能执行规则1和规则2，就完成了整个搜索过程。

4.2.广度优先搜索：首先访问起始顶点的所有邻接点，然后再访问较远的区域，用队列来实现它。（A是起始点，所以访问它，并标记为当前顶点，然后应用规则）

4.2.1图解：![format_png 10][]

4.2.2.主要规则：

4.2.2.1.规则1：访问下一个问来访问的邻接点（如果存在），这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。

4.2.2.2.规则2：如果因为已经没有未访问顶点而不能执行规则1，那么从队列头取一个顶点（如果存在），并使其成为当前顶点。

4.2.2.3.规则3：如果因为队列为空而不能执行规则2，则搜索结束。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NDE4NTE4_size_16_color_FFFFFF_t_70]: /images/20211219/13b0842ecb134f4bbeb5e8d14b68a7a3.png
[queue]: /images/20211219/9d2263dd81bc4fd1baa5441b41815ec7.png
[Collection]: /images/20211219/f60e4458ff284640ad0d5b8c67da5f9c.png
[format_png]: /images/20211219/9f708aa3827143f59f495605725928e3.png
[format_png 1]: /images/20211219/1a7c1e67c160445389f4dadead2725a6.png
[format_png 2]: /images/20211219/99b231548dd545dda06afbcedab07ec3.png
[format_png 3]: /images/20211219/2db8cd23e040432088bc80f28084f71b.png
[B-tree]: /images/20211219/db7303e4359a47db90cb51594b6fcc01.png
[B_tree]: /images/20211219/60d791d608014998bd6370695b0c9f4b.png
[format_png 4]: /images/20211219/f6ed1b8ec9c148148e5b16c55921c61d.png
[Hash]: /images/20211219/8ba2a02ff90f475ba3fb8c1fb28f042e.png
[format_png 5]: /images/20211219/df099e608f5644e191a609fa68acc4a7.png
[format_png 6]: /images/20211219/2dd8d19d385d404b867c729888b922d6.png
[format_png 7]: /images/20211219/88873f80b16c4f50a46813e524e41561.png
[format_png 8]: /images/20211219/6bbeefa4eda94ebf89645fc22e5742d3.png
[format_png 9]: /images/20211219/4ff1d22fd41442058068262ae1269a1f.png
[format_png 10]: /images/20211219/b1cd10932c3a45f2ad1309a1af0fa1d1.png