Java数据结构之集合框架与常用算法有哪些

云晨小哥_8651

云晨小哥_8651

2023-05-26

1332人浏览

转载

    1 集合框架

    1.1 集合框架概念

    java 集合框架 java collection framework ,又被称为容器 container ,是定义在 java.util 包下的一组接口 interfaces和其实现类 classes 。

    其主要表现为将多个元素 element 置于一个单元中,用于对这些元素进行快速、便捷的存储 store 、检索 retrieve 、管理 manipulate ,即平时我们俗称的增删查改 CRUD 。

    类和接口总览:

    Java数据结构之集合框架与常用算法有哪些

    1.2 容器涉及的数据结构

    Collection:是一个接口,包含了大部分容器常用的一些方法

    List:是一个接口,规范了ArrayList 和 LinkedList中要实现的方法

    • ArrayList:实现了List接口,底层为动态类型顺序表

    • LinkedList:实现了List接口,底层为双向链表

    Stack:底层是栈,栈是一种特殊的顺序表

    Queue:底层是队列,队列是一种特殊的顺序表

    Deque:是一个接口

    Set:集合,是一个接口,里面放置的是K模型

    • HashSet:底层为哈希桶,查询的时间复杂度为O(1)

    • TreeSet:底层为红黑树,查询的时间复杂度为O( ),关于key有序的

    Map:映射,里面存储的是K-V模型的键值对

    • HashMap:底层为哈希桶,查询时间复杂度为O(1)

    • TreeMap:底层为红黑树,查询的时间复杂度为O( ),关于key有序

    2 算法

    2.1 算法概念

    算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。算法是由一系列计算步骤组成的,其目的在于将输入数据转化为输出结果。

    2.2 算法效率

    算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。随着计算机行业的急速发展,计算机的存储容量已经达到了相当高的水平。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

    3 时间复杂度

    3.1 时间复杂度概念

    时间复杂度是计算机科学中的一个数学函数,表示算法的运行时间,其定量描述了算法的时间效率。在理论上无法计算一个算法的执行时间,只有在将程序实际运行在计算机上之后才能得知其耗时。尽管每个算法都可以进行上机测试,但这样很繁琐,因此才有了通过时间复杂度进行分析的方式。算法的时间复杂度是基于其中语句执行次数的花费时间成正比例,时间复杂度取决于算法中基本操作的执行次数。

    3.2 大O的渐进表示法

    // 请计算一下func1基本操作执行了多少次?
    void func1(int N){
    	int count = 0;
    	for (int i = 0; i  0) {
    		count++;
    	} 
    	System.out.println(count);
    }

    Func1 执行的基本操作次数 :F(N)=N^2+2*N+10

    • N = 10 F(N) = 130

    • N = 100 F(N) = 10210

    • N = 1000 F(N) = 1002010

    实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。

    大O符号(Big O notation):是用于描述函数渐进行为的数学符号

    使用 Husky 在 JavaScript 仓库中强制执行本地 Git 钩子检查
    使用 Husky 在 JavaScript 仓库中强制执行本地 Git 钩子检查

    使用 Husky 将 pre-commit、pre-push 和 commit-msg 检查集成到仓库中,以便代理和开发人员在更改离开工作站之前运行相同的本地防护措施。

    下载

    3.3 推导大O阶方法

    • 用常数1取代运行时间中的所有加法常数。

    • 在修改后的运行次数函数中,只保留最高阶项。

    • 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

    使用大O的渐进表示法以后,Func1的时间复杂度为:O(n^2)

    • N = 10 F(N) = 100

    • N = 100 F(N) = 10000

    • N = 1000 F(N) = 1000000

    通过上述内容,我们可以看出大O渐进表示法排除了在结果上影响不大的项,从而简洁明确地表示了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况:

    最坏情况:任意输入规模的最大运行次数(上界)

    平均情况:任意输入规模的期望运行次数

    最好情况:任意输入规模的最小运行次数(下界)

    例如:在一个长度为N数组中搜索一个数据x

    最好情况:1次找到

    最坏情况:N次找到

    平均情况:N/2次找到

    在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

    4 空间复杂度

    对于一个算法而言,空间复杂度表示它在执行期间所需的临时存储空间大小。空间复杂度的计算方式并非程序所占用的字节数量,因为这并没有太大的意义;实际上,空间复杂度的计算基于变量的数量。大O渐进表示法通常用来计算空间复杂度,其计算规则类似于实践复杂度的计算规则。

    实例1:

    // 计算bubbleSort的空间复杂度?
    void bubbleSort(int[] array) {
    	for (int end = array.length; end > 0; end--) {
    		boolean sorted = true;
    		for (int i = 1; i  array[i]) {
    				Swap(array, i - 1, i);
    				sorted = false;
    			}
    		} 
    		if(sorted == true) {
    		break;
    		}
    	}
    }

    实例2:

    // 计算fibonacci的空间复杂度?
    int[] fibonacci(int n) {
    	long[] fibArray = new long[n + 1];
    	fibArray[0] = 0;
    	fibArray[1] = 1;
    	for (int i = 2; i <p>实例3:</p><pre class="brush:java;">// 计算阶乘递归Factorial的空间复杂度?
    long factorial(int N) {
    	return N 
    • 实例1使用了常数个额外空间,所以空间复杂度为 O(1)

    • 实例2动态开辟了N个空间,空间复杂度为 O(N)

    • 实例3递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)

    Java免费学习笔记:立即使用
    解锁 Java 大师之旅:从入门到精通的终极指南

    相关文章

    java速学教程(入门到精通)
    java速学教程(入门到精通)

    java怎么学习?java怎么入门?java在哪学?java怎么学才快?不用担心,这里为大家提供了java速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

    下载

    相关标签:

    java

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

    相关专题

    更多
    treenode的用法
    treenode的用法

    ​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

    2023.12.01

    3041

    7

    C++ 高效算法与数据结构
    C++ 高效算法与数据结构

    本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

    2025.12.22

    416

    20

    深入理解算法:高效算法与数据结构专题
    深入理解算法:高效算法与数据结构专题

    本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

    2026.01.06

    457

    22

    C++ 数据结构与算法实现教程合集
    C++ 数据结构与算法实现教程合集

    以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

    2026.05.09

    512

    25

    硬盘接口类型介绍
    硬盘接口类型介绍

    硬盘接口类型有IDE、SATA、SCSI、Fibre Channel、USB、eSATA、mSATA、PCIe等等。详细介绍:1、IDE接口是一种并行接口,主要用于连接硬盘和光驱等设备,它主要有两种类型:ATA和ATAPI,IDE接口已经逐渐被SATA接口;2、SATA接口是一种串行接口,相较于IDE接口,它具有更高的传输速度、更低的功耗和更小的体积;3、SCSI接口等等。

    2023.10.19

    3288

    3

    PHP接口编写教程
    PHP接口编写教程

    本专题整合了PHP接口编写教程,阅读专题下面的文章了解更多详细内容。

    2025.10.17

    5689

    12

    php8.4实现接口限流的教程
    php8.4实现接口限流的教程

    PHP8.4本身不内置限流功能,需借助Redis(令牌桶)或Swoole(漏桶)实现;文件锁因I/O瓶颈、无跨机共享、秒级精度等缺陷不适用高并发场景。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

    2025.12.29

    3909

    9

    java接口相关教程
    java接口相关教程

    本专题整合了java接口相关内容,阅读专题下面的文章了解更多详细内容。

    2026.01.19

    506

    15

    堆和栈的区别
    堆和栈的区别

    堆和栈的区别:1、内存分配方式不同;2、大小不同;3、数据访问方式不同;4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容,供大家免费下载体验。

    2023.07.18

    7387

    5

    热门下载

    更多
    网站特效
    /
    网站源码
    /
    网站素材
    /
    前端模板

    精品课程

    更多
    相关推荐
    /
    热门推荐
    /
    最新课程
    dev.java 官方:Learn Java
    dev.java 官方:Learn Java

    共0课时 | 0人学习

    Java JDBC数据库连接官方教程
    Java JDBC数据库连接官方教程

    共0课时 | 0人学习