精华内容
下载资源
问答
  • java数据结构
    千次阅读
    2021-02-23 17:06:40

    目录

    Java 数据结构与算法

    数据结构

    数据结构的定义

    数据的逻辑结构

    数据的物理结构

    数据存储结构

    数据结构的分类

    线性结构

    非线性结构

    常用的数据结构

    数组(Array)

    栈( Stack)

    队列(Queue)

    链表( Linked List)

    树( Tree)

    图(Graph)

    堆(Heap)

    散列表(Hash)

    常用算法

    算法

    特征

    要素

    一、数据对象的运算和操作:

    二、算法的控制结构:

    算法评定

    时间复杂度

    空间复杂度

    正确性

    可读性

    鲁棒性

    常用方法简介

    递推法

    递归法

    穷举法

    贪心算法

    分治法

    动态规划法

    迭代法

    分支界限法

    回溯法


    Java 数据结构与算法

    数据结构

            数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法索引技术有关。

    数据结构的定义

            数据结构(data structure)是带有结构特性的数据元素的集合,它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法,并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之,数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系,分为逻辑结构和存储结构。同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构,而算法的实现依赖于指定的存储结构

    数据的逻辑结构

          指反映数据元素之间的逻辑关系的数据结构,其中的逻辑关系是指数据元素之间的前后间关系,而与他们在计算机中的存储位置无关。逻辑结构包括:

    1.集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;

    2.线性结构:数据结构中的元素存在一对一的相互关系; 

    3.树形结构:数据结构中的元素存在一对多的相互关系;

    4.图形结构:数据结构中的元素存在多对多的相互关系。

    数据的物理结构

    指数据的逻辑结构在计算机存储空间的存放形式。

    数据的物理结构是数据结构在计算机中的表示(又称映像),由于具体实现的方法有顺序、链接、索引、散列等多种,所以,一种数据结构可表示成一种或多种存储结构。

    数据存储结构

    数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。一般来说,一种数据结构的逻辑结构根据需要可以表示成多种存储结构,

    常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。

    数据的顺序存储结构的特点是:借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系;非顺序存储的特点是:借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

    数据结构的分类

    线性结构

    简单地说,线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述,线性结构应该包括如下几点:

    1、线性结构是非空集。

    2、线性结构有且仅有一个开始结点和一个终端结点。

    3、线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。

    线性表就是典型的线性结构,数组、还有栈、队列和串等都属于线性结构。

    非线性结构

    简单地说,非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述,非线性结构应该包括如下几点:

    1、非线性结构是非空集。

    2、非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。 

    在实际应用中,二位数组、多维数组、广义表、树结构和图结构等数据结构都属于非线性结构。

    常用的数据结构

    数组(Array)

            数组是一种聚合数据类型,它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构,在各种编程语言中都有对应。一个数组可以分解为多个数组元素,按照数据元素的类型,数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。

    栈( Stack)

            是一种特殊的线性表,它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据,也就是说,先插入的数据将被压入栈底,最后插入的数据在栈顶,读出数据时,从栈顶开始逐个读出。栈在汇编语言程序中,经常用于重要数据的现场保护。栈中没有数据时,称为空栈。

    队列(Queue)

            队列和栈类似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作。一般来说,进行插入操作的一端称为队尾,进行删除操作的一端称为队头。队列中没有元素时,称为空队列。

    链表( Linked List)

            链表是一种数据元素按照链式存储结构进行存储的数据结构,这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成,每个数据结点包括数据域和指针域两部分。其中,指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。 [

    树( Tree)

            树是典型的非线性结构,它是包括,2个结点的有穷集合K。在树结构中,有且仅有一个根结点,该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点,而且可以有两个后继结点,m≥0。

    图(Graph)

           图是另一种非线性数据结构。在图结构中,数据结点一般称为顶点,而边是顶点的有序偶对。如果两个顶点之间存在一条边,那么就表示这两个顶点具有相邻关系。

    堆(Heap)

          是一种特殊的树形数据结构,一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的,并且根结点的两个子树也是一个堆结构。  

    散列表(Hash)

          散列表源自于散列函数(Hash function),其思想是如果在结构中存在关键字和T相等的记录,那么必定在F(T)的存储位置可以找到该记录,这样就可以不用进行比较操作而直接取得所查记录。

    常用算法

            数据结构研究的内容:就是如何按一定的逻辑结构,把数据组织起来,并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据,提高数据运算效率。数据的运算是定义在数据的逻辑结构上,但运算的具体实现要在存储结构上进行。一般有以下几种常用运算:

    (1)检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值,找具有该字段值的节点。 

    (2)插入。往数据结构中增加新的节点。  

    (3)删除。把指定的结点从数据结构中去掉。

    (4)更新。改变指定节点的一个或多个字段的值。

    (5)排序。把节点按某种指定的顺序重新排列。例如递增或递减。

    算法

            算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度时间复杂度来衡量。

    特征

    一个算法应该具有以下五个重要的特征:

    有穷性 :算法的有穷性是指算法必须能在执行有限个步骤之后终止;

    确切性 :算法的每一步骤必须有确切的定义;

    输入项 :一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件;

    输出项 :一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;

    可行性 :算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤,即每个计算步骤都可以在有限时间内完成(也称之为有效性)。

    要素

    一、数据对象的运算和操作

    计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类:

    1.算术运算:加减乘除等运算

    2.逻辑运算:或、且、非等运算

    3.关系运算:大于、小于、等于、不等于等运算

    4.数据传输:输入、输出、赋值等运算  

    二、算法的控制结构:

    一个算法的功能结构不仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。

    算法评定

           同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度空间复杂度来考虑。

    时间复杂度

    算法的时间复杂度是指执行算法所需要的计算工作量。

    空间复杂度

    算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

    正确性

    算法的正确性是评价一个算法优劣的最重要的标准。

    可读性

    算法的可读性是指一个算法可供人们阅读的容易程度。

    鲁棒性

    鲁棒性是指一个算法对不合理数据输入的反应能力和处理能力,也称为容错性

    常用方法简介

    递推法

          递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项,通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复,该算法利用了计算机速度快和不知疲倦的机器特点。

    递归法

            程序调用自身的编程技巧称为递归(recursion)。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

    注意:

    (1) 递归就是在过程或函数里调用自身;

    (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。

    穷举法

            穷举法,或称为暴力破解法,其基本思路是:对于要解决的问题,列举出它的所有可能的情况,逐个判断有哪些是符合问题所要求的条件,从而得到问题的解。它也常用于对于密码的破译,即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码,其可能共有10000种组合,因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码,问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率,有些人辅以字典来缩小密码组合的范围。

    贪心算法

            贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。

            用贪心法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。

           贪婪算法是一种改进了的分级处理方法,其核心是根据题意选取一种量度标准,然后将这多个输入排成这种量度标准所要求的顺序,按这种顺序一次输入一个量,如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解,则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。

    对于一个给定的问题,往往可能有好几种量度标准。初看起来,这些量度标准似乎都是可取的,但实际上,用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解,而是次优解。因此,选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。

    一般情况下,要选出最优量度标准并不是一件容易的事,但对某问题能选择出最优量度标准后,用贪婪算法求解则特别有效。

    分治法

            分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

    分治法所能解决的问题一般具有以下几个特征:

    (1) 该问题的规模缩小到一定的程度就可以容易地解决;

    (2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;

    (3) 利用该问题分解出的子问题的解可以合并为该问题的解;

    (4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。

    动态规划法

            动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。

    动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不像前面所述的那些搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解决各类最优化问题。因此读者在学习时,除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。

    迭代法

           迭代法也称辗转,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。

    分支界限法

           分枝界限法是一个用途十分广泛的算法,运用这种算法的技巧性很强,不同类型的问题解法也各不相同。

    分支定界法的基本思想是对有约束条件最优化问题的所有可行解(数目有限)空间进行搜索。该算法在具体执行时,把全部可行的解空间不断分割为越来越小的子集(称为分支),并为每个子集内的解的值计算一个下界或上界(称为定界)。在每次分支后,对凡是界限超出已知可行解值那些子集不再做进一步分支,这样,解的许多子集(即搜索树上的许多结点)就可以不予考虑了,从而缩小了搜索范围。这一过程一直进行到找出可行解为止,该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解

    贪心算法一样,这种方法也是用来为组合优化问题设计求解算法的,所不同的是它在问题的整个可能解空间搜索,所设计出来的算法虽其时间复杂度贪婪算法高,但它的优点是与穷举法类似,都能保证求出问题的最佳解,而且这种方法不是盲目的穷举搜索,而是在搜索过程中通过限界,可以中途停止对某些不可能得到最优解的子空间进一步搜索(类似于人工智能中的剪枝),故它比穷举法效率更高。 [2] 

    回溯法

            回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

    其基本思想是,在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。 若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

    算法是程序的灵魂,优秀的程序可以在海量的计算时仍保持高速计算

    如果不想永远当代码工人  写出简洁 优雅 高效的代码必须对算法和数据结构有所研究。

    数据结构是一门研究组织数据的方式的学科,有了编程语言也就有了数据结构

    程序 = 数据结构 + 算法!

     

     

     

    更多相关内容
  • Java数据结构和算法中文第二版源码

    热门讨论 2015-09-01 12:02:09
    Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么不用数组表示一切? 小结 问题 实验...
  • java数据结构和算法(第二版)

    千次下载 热门讨论 2012-11-29 21:12:37
    Java数据结构的类库 小结 问题 第2章数组 Array专题Applet Java中数组的基础知识 将程序划分成类 类接口 Ordered专题applet 有序数组的Java代码 对数 存储对象 大O表示法 为什么不用数组表示一切? 小结 问题 实验 ...
  • Java数据结构和算法

    2017-09-09 21:50:29
    Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法
  • Java数据结构与算法——图

    千次阅读 2022-03-21 17:53:19
    1.关于图这种数据结构 为什么要有图? 前面我们学了线性表和树,线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了图。 图...

    1.关于图这种数据结构

    为什么要有图?

    前面我们学了线性表和树,线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了图。

    图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图:

    图的表示方式有两种:二维数组表示(邻接矩阵);链表表示(邻接表)。

    • 邻接矩阵:邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于n个顶点的图而言,矩阵是的row和col表示的是1....n个点。

    • 邻接表:邻接矩阵需要为每个顶点都分配n个边的空间,其实有很多边都是不存在,会造成空间的一定损失。邻接表的实现只关心存在的边,不关心不存在的边。因此没有空间浪费,邻接表由数组+链表组成。


    2.代码案例

    我们就以下面这张图为例,对图进行一个简单的实现。 这里我们采用基于邻接矩阵的方式来实现。

    package com.szh.graph;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    /**
     *
     */
    class Graph {
        public List<String> vertexList; //存储图中所有顶点的集合
        public int[][] edges; //存储图对应的邻接矩阵
        public int numOfEdges; //表示图中边的数目
    
        public Graph(int numOfEdges) {
            this.numOfEdges = numOfEdges;
            edges = new int[numOfEdges][numOfEdges];
            vertexList = new ArrayList<>();
            numOfEdges = 0;
        }
    
        //返回图中结点的个数
        public int getNumOfVertex() {
            return vertexList.size();
        }
    
        //显示图对应的邻接矩阵
        public void showGraph() {
            for (int[] link : edges) {
                System.out.println(Arrays.toString(link));
            }
        }
    
        //获取图中边的数目
        public int getNumOfEdges() {
            return numOfEdges;
        }
    
        //返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"
        public String getValueByIndex(int i) {
            return vertexList.get(i);
        }
    
        //返回v1和v2的权值
        public int getWeight(int v1, int v2) {
            return edges[v1][v2];
        }
    
        //向图中插入新的结点
        public void insertVertex(String vertex) {
            vertexList.add(vertex);
        }
    
        //向图中添加新的边
        public void insertEdge(int v1, int v2, int weight) {
            edges[v1][v2] = weight;
            edges[v2][v1] = weight;
            numOfEdges++;
        }
    }
    
    public class GraphDemo {
        public static void main(String[] args) {
            int n = 5; //定义图中结点的个数
            //定义图中的结点 (A=0, B=1, C=2, D=3, E=4)
            String[] vertexs = {"A", "B", "C", "D", "E"};
            //创建图对象
            Graph graph = new Graph(n);
            //循环向图中添加结点
            for (String vertex : vertexs) {
                graph.insertVertex(vertex);
            }
            System.out.println("此时图中共有 " + graph.getNumOfVertex() + " 个结点");
            //向图中添加边
            graph.insertEdge(0, 1, 4); // A -> B
            graph.insertEdge(0, 2, 2); // A -> C
            graph.insertEdge(1, 2, 5); // B -> C
            graph.insertEdge(1, 3, 8); // B -> D
            graph.insertEdge(1, 4, 1); // B -> E
            System.out.println("此时图中共有 " + graph.getNumOfEdges() + " 条边");
            //显示整个图
            graph.showGraph();
            //获取B和D两个结点之间边的权值
            System.out.println(graph.getValueByIndex(1) + " 和 " + graph.getValueByIndex(3)
                    + " 两个结点之间边的权值为:" + graph.getWeight(1, 3));
        }
    }
    

    展开全文
  • Java数据结构与算法入门

    万次阅读 多人点赞 2018-04-29 11:53:50
    第一部分:Java数据结构要理解Java数据结构,必须能清楚何为数据结构?数据结构:Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。而各数据元素之间的相互关系,又...

    第一部分:Java数据结构

    要理解Java数据结构,必须能清楚何为数据结构?

    数据结构:

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

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

    一、Java数据结构之:线性数据结构

    线性数据结构:常见的有一维数组,线性表,栈,队列,双队列,串。

    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里面也用的到了此种数据结构,就是线程栈,来保证当前线程的执行顺序。

    4:队列

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

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

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


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

    5:串

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

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

    二、Java数据结构之:非线性数据结构

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

    1:多维数组

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

    2:集合

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

    Collection

    3:树

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

    树的特点:

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

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

    • 1) 自由树/普通树:对子节点没有任何约束。

      自由树

    • 2) 二叉树:每个节点最多含有两个子节点的树称为二叉树。

      2.1) 一般二叉树:每个子节点的父亲节点不一定有两个子节点的二叉树成为一般二叉树。

      2.2) 完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;

      2.3) 满二叉树:所有的节点都是二叉的二叉树成为满二叉树。

      二叉树

    • 3) 二叉搜索树/BST:binary search tree,又称二叉排序树、二叉查找树。是有序的。要点:如果不为空,那么其左子树节点的值都小于根节点的值;右子树节点的值都大于根节点的值。

      二叉搜索树

      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指针的每一条路径都包含相同数目的黑结点。

      红黑树

    • 4) B-tree:又称B树、B-树。又叫平衡(balance)多路查找树。树中每个结点最多含有m个孩子(m>=2)。它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。

      B-tree

    • 4) B+tree:又称B+。是B-树的变体,也是一种多路搜索树。

      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此处算法又做了改进,数组里面的值会演变成树形结构。)

    • 哈希表具有较快(常量级)的查询速度,及相对较快的增删速度,所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”,我们可以理解为“链表的数组”。

      哈希表

    一致性Hash:

    • 我们查看一下HashMap的原理,其实发现Hash很好的解决了单体应用情况下的数据查找和插入的速度问题。但是毕竟单体应用的储存空间是有限的,所有在分布式环境下,应运而生了一致性Hash算法。

    • 用意和hashCode的用意一样,只不过它是取模放在不同的IP机器上而已。具体算法可以找一下相关资料。

    • 而一致性Hash需要注意的就是默认分配的桶比较多些,而当其中一台机器挂了,影响的面比较小一些。

    • 需要注意的是,相同的内容算出来的hash一定是一样的。既:幂等性。

    • 一致性Hash

    第二部分:Java基本算法

    理解了Java数据结构,还必须要掌握一些常见的基本算法。 理解算法之前必须要先理解的几个算法的概念:

    空间复杂度:一句来理解就是,此算法在规模为n的情况下额外消耗的储存空间。

    时间复杂度:一句来理解就是,此算法在规模为n的情况下,一个算法中的语句执行次数称为语句频度或时间频度。

    稳定性:主要是来描述算法,每次执行完,得到的结果都是一样的,但是可以不同的顺序输入,可能消耗的时间复杂度和空间复杂度不一样。

    一、二分查找算法

    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。这个是基础,最简单的查找算法了。

        public static void main(String[] args) {
            int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
            System.out.println(binSearch(srcArray, 28));
        }
        /**
         * 二分查找普通循环实现
         *
         * @param srcArray 有序数组
         * @param key 查找元素
         * @return
         */
        public static int binSearch(int srcArray[], int key) {
            int mid = srcArray.length / 2;
    //        System.out.println("=:"+mid);
            if (key == srcArray[mid]) {
                return mid;
            }
    
    //二分核心逻辑
            int start = 0;
            int end = srcArray.length - 1;
            while (start <= end) {
    //            System.out.println(start+"="+end);
                mid = (end - start) / 2 + start;
                if (key < srcArray[mid]) {
                    end = mid - 1;
                } else if (key > srcArray[mid]) {
                    start = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
    

    二分查找算法如果没有用到递归方法的话,只会影响CPU。对内存模型来说影响不大。时间复杂度log2n,2的开方。空间复杂度是2。一定要牢记这个算法。应用的地方也是非常广泛,平衡树里面大量采用。

    二、递归算法

    递归简单理解就是方法自身调用自身。

        public static void main(String[] args) {
            int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
            System.out.println(binSearch(srcArray, 0,15,28));
        }
        /**
         * 二分查找递归实现
         *
         * @param srcArray  有序数组
         * @param start 数组低地址下标
         * @param end   数组高地址下标
         * @param key  查找元素
         * @return 查找元素不存在返回-1
         */
        public static int binSearch(int srcArray[], int start, int end, int key) {
            int mid = (end - start) / 2 + start;
            if (srcArray[mid] == key) {
                return mid;
            }
            if (start >= end) {
                return -1;
            } else if (key > srcArray[mid]) {
                return binSearch(srcArray, mid + 1, end, key);
            } else if (key < srcArray[mid]) {
                return binSearch(srcArray, start, mid - 1, key);
            }
            return -1;
        }
    

    递归几乎会经常用到,需要注意的一点是:递归不光影响的CPU。JVM里面的线程栈空间也会变大。所以当递归的调用链长的时候需要-Xss设置线程栈的大小。

    三、八大排序算法

    • 一、直接插入排序(Insertion Sort)
    • 二、希尔排序(Shell Sort)
    • 三、选择排序(Selection Sort)
    • 四、堆排序(Heap Sort)
    • 五、冒泡排序(Bubble Sort)
    • 六、快速排序(Quick Sort)
    • 七、归并排序(Merging Sort)
    • 八、基数排序(Radix Sort)

    八大算法,网上的资料就比较多了。

    吐血推荐参考资料:git hub 八大排序算法详解。此大神比作者讲解的还详细,作者就不在这里,描述重复的东西了,作者带领大家把重点的两个强调一下,此两个是必须要掌握的。

    1:冒泡排序

    基本思想:

    冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    冒泡排序

    以下是冒泡排序算法复杂度:

    平均时间复杂度最好情况最坏情况空间复杂度
    O(n²)O(n)O(n²)O(1)

    冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).

    Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

    /**
     * 冒泡排序
     *
     * ①. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
     * ②. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
     * ③. 针对所有的元素重复以上的步骤,除了最后一个。
     * ④. 持续每次对越来越少的元素重复上面的步骤①~③,直到没有任何一对数字需要比较。
     * @param arr  待排序数组
     */
    public static void bubbleSort(int[] arr){
        for (int i = arr.length; i > 0; i--) {      //外层循环移动游标
            for(int j = 0; j < i && (j+1) < i; j++){    //内层循环遍历游标及之后(或之前)的元素
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    System.out.println("Sorting: " + Arrays.toString(arr));
                }
            }
        }
    }
    

    2:快速排序

    快速排序

    快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:

    ①. 从数列中挑出一个元素,称为”基准”(pivot)。

    ②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

    ③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

    代码实现:

    用伪代码描述如下:

    ①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。

    ②.j--,由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

    ③.i++,由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

    ④.再重复执行②,③二步,直到i==j,将基准数填入a[i]中。

    快速排序采用“分而治之、各个击破”的观念,此为原地(In-place)分区版本。

    快速排序 In-place

    /**
     * 快速排序(递归)
     *
     * ①. 从数列中挑出一个元素,称为"基准"(pivot)。
     * ②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
     * ③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
     * @param arr   待排序数组
     * @param low   左边界
     * @param high  右边界
     */
    public static void quickSort(int[] arr, int low, int high){
        if(arr.length <= 0) return;
        if(low >= high) return;
        int left = low;
        int right = high;
        int temp = arr[left];   //挖坑1:保存基准的值
        while (left < right){
            while(left < right && arr[right] >= temp){  //坑2:从后向前找到比基准小的元素,插入到基准位置坑1中
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= temp){   //坑3:从前往后找到比基准大的元素,放到刚才挖的坑2中
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = temp;   //基准值填补到坑3中,准备分治递归快排
        System.out.println("Sorting: " + Arrays.toString(arr));
        quickSort(arr, low, left-1);
        quickSort(arr, left+1, high);
    }
    

    以下是快速排序算法复杂度:

    平均时间复杂度最好情况最坏情况空间复杂度
    O(nlog₂n)O(nlog₂n)O(n²)O(1)(原地分区递归版)

    快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.


    最后,作者希望让大家对《Java数据结构》整体有个全面的了解,知道什么是数据结构,离我们工作中有多远,而不是一个深不可测的神秘物件。里面的细节,篇幅有限可能不能描述完,但是只要同学们的方向没有搞错,那只要针对每个点再详细的看看即可。

    面试和工作,这些都是离不开的,当同学们有个完整的认识之后,一定要在工作中留心,留意每个用到的地方。

    更多精彩教程,请关注公众号:Java开发教程视频      


    展开全文
  • 16 张图带你搞懂 Java 数据结构,从此想不飘都难!

    千次阅读 多人点赞 2021-04-06 11:07:31
    今天我们来学一下数据结构方面的知识,对扎实 Java 的基本功非常有用,学会了就会有一种自带大佬的感觉,嘿嘿。数据结构,也就是 Data Structure,是一种存储数据的结构体,数据与数据之间存在着一定的关系,这样的...

    CSDN 的小伙伴们,大家好,我是沉默的王二。

    假期结束了,需要快速切换到工作的状态投入到新的一天当中。放假的时候痛快地玩耍,上班的时候积极的工作,这应该是我们大多数“现代人”该有的生活状态。

    今天我们来学一下数据结构方面的知识,对扎实 Java 的基本功非常有用,学会了就会有一种自带大佬的感觉,嘿嘿。数据结构,也就是 Data Structure,是一种存储数据的结构体,数据与数据之间存在着一定的关系,这样的关系有数据的逻辑关系、数据的存储关系和数据的运算关系。

    在 Java 中,数据结构一般可以分为两大类:线性数据结构和非线性数据结构。哈哈,这个非字很有灵魂吧?

    先来说线性数据结构吧。

    1)数组

    一眼看上去就知道的,像 String []int [] 这种;还有需要看两眼才能看透的(看源码了),像 ArrayList,内部对数组进行了封装。

    数组这种数据结构最大的好处,就是可以根据下标(或者叫索引)进行操作,插入的时候可以根据下标直接插入到具体的位置,但与此同时,后面的元素就需要全部向后移动,需要移动的数据越多,就越累。

    假设现在已经有了一个 ArrayList 了,准备在第 4 个位置(下标为 3)上添加一个元素 55。

    此时 ArrayList 中第 5 个位置以后的元素将会向后移动。

    准备把 23 从 ArrayList 中移除。

    此时下标为 7、8、9 的元素往前挪。

    简单总结一下 ArrayList 的时间复杂度,方便大家在学习的时候作为参考。

    1、通过下标(也就是 get(int index))访问一个元素的时间复杂度为 O(1),因为是直达的,无论数据增大多少倍,耗时都不变。

    2、添加一个元素(也就是 add())的时间复杂度为 O(1),因为直接添加到末尾。

    3、删除一个元素的时间复杂度为 O(n),因为要遍历列表,数据量增大几倍,耗时也增大几倍。

    4、查找一个未排序的列表时间复杂度为 O(n),因为要遍历列表;查找排序过的列表时间复杂度为 O(log n),因为可以使用二分查找法,当数据增大 n 倍时,耗时增大 logn 倍(这里的 log 是以 2 为底的,每找一次排除一半的可能)。

    2)链表

    链表在物理存储空间是不连续的,但每个节点要么知道它的下一个节点是谁,要么知道它的上一个节点是谁,仿佛就像我们之间隔着千山万水,却心有灵犀一点链。像 LinkedList 就是最典型的链表结构,通过引用相互链接。

    LinkedList 中的每一个元素都可以称之为节点(Node),每一个节点都包含三个项目:其一是元素本身,其二是指向下一个元素的引用地址,其三是指向上一个元素的引用地址。

    LinkedList 看起来就像下面这个样子:

    • 第一个节点由于没有前一个节点,所以 prev 为 null;
    • 最后一个节点由于没有后一个节点,所以 next 为 null;
    • 这是一个双向链表,每一个节点都由三部分组成,前后节点和值。

    相比 ArrayList,LinkedList 有以下优势:

    1、LinkedList 允许内存进行动态分配,这就意味着内存分配是由编译器在运行时完成的,我们无需在 LinkedList 声明的时候指定大小。

    2、LinkedList 不需要在连续的位置上存储元素,因为节点可以通过引用指定下一个节点或者前一个节点。也就是说,LinkedList 在插入和删除元素的时候代价很低,因为不需要移动其他元素,只需要更新前一个节点和后一个节点的引用地址即可。

    3)栈

    栈是一种非常有用的数据结构,它就像一摞盘子,第一个放在最下面,第二个放在第一个上面,第三个放在第二个上面,最后一个放在最上面。栈遵循后进先出的原则,也就是“Last In First Out”(简称 LIFO)——最后的一个进的,最先出去。

    对于栈这样一个数据结构来说,它有两个常见的动作:

    • push,中文释义有很多种,我个人更喜欢叫它“压入”,非常形象。当我们要把一个数据放入栈的顶部,这个动作就叫做 push

    • pop,同样的,我个人更喜欢叫它“弹出”,带有很强烈的动画效果,有没有?当我们要从栈中移除一个数据时,这个动作就叫做 pop

    4)队列

    队列,只允许在队尾添加数据,队首移除数据。队列在 Java 中的出现频率非常高,有各种不同的类来满足不同的场景需求。像优先级队列 PriorityQueue、延时队列 DelayQueue 等等。队列遵循的是 First In First Out,缩写为 FIFO,也就是先进先出,第一个进入队列的第一个先出来。

    再来说非线性数据结构。

    1) 树

    树是一种典型的非线性结构,它是由 n(n>0)个有限节点组成的一个具有层次关系的集合。之所以叫“树”,是因为这种数据结构看起来就像是一个倒挂的树,只不过根在上,叶在下。树形数据结构有以下这些特点:

    • 每个节点都只有有限个子节点或无子节点;
    • 没有父节点的节点称为根节点;
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树。

    下图展示了树的一些术语:

    根节点是第 0 层,它的子节点是第 1 层,子节点的子节点为第 2 层,以此类推。

    • 深度:对于任意节点 n,n 的深度为从根到 n 的唯一路径长,根的深度为 0。
    • 高度:对于任意节点 n,n 的高度为从 n 到一片树叶的最长路径长,所有树叶的高度为 0。

    树又可以细分为下面几种:

    1、普通树:对子节点没有任何约束。

    2、二叉树:每个节点最多含有两个子节点的树。 二叉树按照不同的表现形式又可以分为多种。

    2.1、普通二叉树:每个子节点的父节点不一定有两个子节点的二叉树。

    2.2、完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第 d 层外,其它各层的节点数目均已达最大值,且第 d 层所有节点从左向右连续地紧密排列。

    2.3、满二叉树:一颗每一层的节点数都达到了最大值的二叉树。有两种表现形式,第一种,像下图这样(每一层都是满的),满足每一层的节点数都达到了最大值 2。

    3、二叉查找树:英文名叫 Binary Search Tree,即 BST,需要满足以下条件:

    • 任意节点的左子树不空,左子树上所有节点的值均小于它的根节点的值;
    • 任意节点的右子树不空,右子树上所有节点的值均大于它的根节点的值;
    • 任意节点的左、右子树也分别为二叉查找树。

    3.1、平衡二叉树:当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树,根据科学家的英文名也称为 AVL 树。

    平衡二叉树本质上也是一颗二叉查找树,不过为了限制左右子树的高度差,避免出现倾斜树等偏向于线性结构演化的情况,所以对二叉搜索树中每个节点的左右子树作了限制,左右子树的高度差称之为平衡因子,树中每个节点的平衡因子绝对值不大于 1。

    平衡二叉树的难点在于,当删除或者增加节点的情况下,如何通过左旋或者右旋的方式来保持左右平衡。

    红黑树是一种常见的平衡二叉树,节点是红色或者黑色,通过颜色的约束来维持着二叉树的平衡:

    • 每个节点都只能是红色或者黑色
    • 根节点是黑色
    • 每个叶节点(NIL 节点,空节点)是黑色的。
    • 如果一个节点是红色的,则它两个子节点都是黑色的。也就是说在一条路径上不能出现相邻的两个红色节点。
    • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

    4、B 树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多于两个的子树。

    5、B+ 树:B 树的变体。

    HashMap 里面的 TreeNode 就用到了红黑树,而 B 树、B+ 树在数据库的索引原理里面有典型的应用。

    2)哈希表

    哈希表(Hash Table),也叫散列表,是一种可以通过关键码值(key-value)直接访问的数据结构,它最大的特点就是可以快速实现查找、插入和删除。其中用到的算法叫做哈希,就是把任意长度的输入,变换成固定长度的输出,该输出就是哈希值。像 MD5、SHA1 都用的是哈希算法。

    每一个 Java 对象都会有一个哈希值,默认情况就是通过调用本地方法执行哈希算法,计算出对象的内存地址 + 对象的值的关键码值。

    数组的最大特点就是查找容易,插入和删除困难;而链表正好相反,查找困难,而插入和删除容易。哈希表很完美地结合了两者的优点, Java 的 HashMap 在此基础上还加入了树的优点。

    哈希表具有较快(常量级)的查询速度,以及相对较快的增删速度,所以很适合在海量数据的环境中使用。

    对于任意两个不同的数据块,其哈希值相同的可能性极小,也就是说,对于一个给定的数据块,找到和它哈希值相同的数据块极为困难。再者,对于一个数据块,哪怕只改动它的一个比特位,其哈希值的改动也会非常的大——这正是 Hash 存在的价值!

    尽管可能性极小,但仍然会发生,如果哈希冲突了,Java 的 HashMap 会在数组的同一个位置上增加链表,如果链表的长度大于 8,将会转化成红黑树进行处理——这就是所谓的拉链法(数组+链表)。

    3)图

    图是一种复杂的非线性结构,由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G 表示一个图,V 是图 G 中顶点的集合,E 是图 G 中边的集合。

    上图共有 V0,V1,V2,V3 这 4 个顶点,4 个顶点之间共有 5 条边。

    在线性结构中,数据元素之间满足唯一的线性关系,每个数据元素(除第一个和最后一个外)均有唯一的“前驱”和“后继”;

    在树形结构中,数据元素之间有着明显的层次关系,并且每个数据元素只与上一层中的一个元素(父节点)及下一层的多个元素(子节点)相关;

    而在图形结构中,节点之间的关系是任意的,图中任意两个数据元素之间都有可能相关。

    最后,希望大家都能把 Java 数据结构学好,从一键三连做起吧

    推荐阅读:

    V4.0 《JavaGuide 面试突击版》来啦!GitHub 上标星 98.1k,帮你成功上岸!

    学弟学妹们,学会霍夫曼编码后,再也不用担心网络带宽了!

    展开全文
  • java数据结构算法

    千人学习 2019-11-22 10:12:46
    做一门精致,全面详细的 java数据结构与算法!!! 让天下没有难学的数据结构, 让天下没有难学的算法, 不吹不黑,我们的讲师及其敬业,可以看到课程视频,课件,代码的录制撰写,都是在深夜,如此用心,其心可鉴,他不掉头发,谁...
  • 线性结构和非线性结构 队列 顺序队列 循环队列 链表 链表(Linked List)介绍 链表是有序的列表,但是它在内存中是存储如下 小结: 1) 链表是以节点的方式来存储,是链式存储 2)每个节点包含 data 域, ...
  • 头歌JAVA数据结构答案

    千次阅读 多人点赞 2021-11-28 13:54:22
    头歌JAVA数据结构答案 一、Java数据结构-循环链表的设计与实现 第1关 单循环链表的实现—链表的添加、遍历 package step1; /** * Created by sykus on 2018/1/15. */ public class MyCircleLinkedList { private...
  • Java数据结构及原理实现

    万次阅读 2017-07-21 16:18:03
    程序设计主要是数据结构+算法,而数据结构在面向对象思维里是“容器”的意思,数据结构主要...所以下面就简单介绍java数据结构的体系和部分原理实现java集合体系结构图集合父接口Collection,Map和集合工具类Collect
  • Java数据结构和算法.(第二版).rar 免积分下载
  • Java从入门到精通七(Java数据结构--Collection集合)

    千次阅读 多人点赞 2022-02-03 18:31:29
    数组也是java中的一种数据结构,数据的长度是固定的,存储方式是线性的。并且是可以存储基本的数据类型和对象,基本数据对象可以按照基本类型的装箱处理并存储。而我们的数组是属于引用数据类型的。 集合是java中的...
  • 图解Java数据结构和算法

    万人学习 2019-06-21 10:09:16
    教程内容:本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀...
  • java数据结构之Set

    千次阅读 2018-09-07 10:07:12
    先来一张UML图: 如上,Set最重要的是HashSet、LinkedHashSet、TreeSet和CopyOnWriteArraySet几个实现类。Set中的元素是不能重复的。...参考:《java程序性能优化——让你java程序更快、更稳定》
  • Java 数据结构

    千次阅读 2016-11-17 09:29:05
    Java 数据结构 Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类: 枚举(Enumeration) 位集合(BitSet) 向量(Vector) 栈(Stack) 字典(Dictionary) 哈希表...
  • java数据结构有哪些?

    万次阅读 多人点赞 2018-12-28 17:26:11
    Java中有几种常用的数据结构,主要分为Collection和map两个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。 Collection----&gt;Collections Map--...
  • java数据结构之选择排序

    千次阅读 2018-11-19 19:07:22
    作为java排序算法中的一种经典的排序算法,选择排序的思想还是比较容易理解的,其主要的排序过程为: 每一趟从待排序记录中选出最小元素,顺序放在已排好序的最后,直到全部记录排序完毕。也就是:每一趟在n+1(i=1...
  • Java数据结构与算法

    千人学习 2019-04-19 14:49:09
  • 如何理解并掌握 Java 数据结构

    千次阅读 多人点赞 2019-11-13 11:11:45
    Jack和大家一起来重温《Java数据结构》经典之作。 第一部分:Java数据结构 要理解Java数据结构,必须能清楚何为数据结构? 数据结构: Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些...
  • Java数据结构与算法之学习路线

    万次阅读 多人点赞 2016-09-28 17:19:21
    目录: 1.前言 2.数据结构与算法学习大纲(粗糙) 3.线性结构分类 4.各个线性类型数据结构的特点以及使用场景 5.数组与队列的区别 1.前言: ...去做了两道面试题,全是数据结构和算法的题,由于我的java
  • 课程介绍:基于JAVA语言的数据结构算法视频教程,非常经典的java数据结构基础理论课程,是学习java的必备技能。课程目录:01.第一讲数组02.第二讲简单排序03.第三讲栈和队列04.第四讲链表05.第五讲双端链表和双向链表...
  • java常用数据结构有哪些

    千次阅读 2022-03-31 14:04:18
    java数据结构有:1、数组;2、链表,一种递归的数据结构;3、栈,按照“后进先出”、“先进后出”的原则来存储数据;4、队列;5、树,是由 n(n>0)个有限节点组成的一个具有层次关系的集合;6、堆;7、图;8、...
  • 链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息。 线性结构常见的有:数组、队列、链表和栈。 非线性结构 非线性结构包括:二维数组,多维数组,广义表...
  • Java数据结构和算法(第二版)pdf

    千次阅读 2018-02-28 09:51:00
    下载地址:网盘下载内容简介······《Java数据结构和算法》(第2版)以一种易懂的方式教授如何安排和操纵数据的问题,其中不乏一些难题:了解这些知识以期使计算机的应用获得最好的表现。不管使用何种语言或平台...
  • Java常见的8种数据结构

    千次阅读 2022-01-25 14:48:57
    数据结构是指数据在计算机内存空间中或磁盘中的组织形式 算法是完成特定任务的过程 二分法查找 r=2^s s:查找步数 r查找范围 幂函数 s=log2® 已知范围获取需要的次数 对数 算法复杂度使用O(N)函数进行标示 主要是...
  • 数据结构与算法(JAVA语言版,内含源代码)
  • java数据结构(Java版)(第3版)[叶核亚] 全套资料

    千次下载 热门讨论 2013-08-18 12:01:48
    java数据结构(Java版)(第3版)[叶核亚] 全套资料包含:[电子教案] [配套资料] [习题解答与试题库] 内容相当丰富 不收藏肯定后悔呀
  • 书籍推荐:《Java数据结构与算法》

    千次阅读 2017-12-13 15:46:00
    Data Structures and Algorithms in Java (2nd Edition) ...现在市面上关于数据结构和算法的书的描述语言一般是C、C++和Java,我只见过一本是C#的:《Data Structures and Algorithms with Object-Oriented ...
  • JAVA高级技术】Java 处理结构数据多种解决方案

    万次阅读 多人点赞 2022-04-23 23:07:18
    Java 处理结构数据多种解决方案

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,729,436
精华内容 691,774
关键字:

java数据结构

数据结构 订阅