java数据结构前置知识以及认识泛型

目录

什么是集合框架

容器

时间复杂度

空间复杂度

包装类

装箱

拆箱

引出泛型

泛型类的使用

类型推导

泛型如何编译的

泛型的上界

泛型方法静态泛型方法以及泛型上界


什么是集合框架

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

如何理解这张图?

所有的这些从某种意义上说都实现了Iterable这个接口,然后collection继承extends了它也可以说拓展了它这个接口相当于collection这个接口具备了Iterable这个接口的功能,相当于这个接口定义的类型可以引用下面具体的对象,例如List list=new ArrayList()暂且这样写,后面同样一个道理

这张图描述了java当中 类与类 类与接口之间的关系

说明:java的集合类和关系不一定只有上图,上图只是描述了部分重要的常见的类


容器

每个容器其实都是对某种特定数据结构的封装

1. Collection : 是一个接口,包含了大部分容器常用的一些方法
2. List : 是一个接口,规范了 ArrayList 和 LinkedList 中要实现的方法
ArrayList : 实现了 List 接口,底层为动态类型顺序表
LinkedList :实现了 List 接口,底层为双向链表
3. Stack :底层是栈,栈是一种特殊的顺序表
4. Queue :底层是队列,队列是一种特殊的顺序表
5. Deque :是一个接口
6. Set :集合,是一个接口,里面放置的是 K 模型
HashSet :底层为哈希桶,查询的时间复杂度为 O(1)
TreeSet :底层为红黑树,查询的时间复杂度为 O(Log2N ),关于 key 有序的
7. Map :映射,里面存储的是 K-V 模型的键值对
HashMap :底层为哈希桶,查询时间复杂度为 O(1)
TreeMap :底层为红黑树,查询的时间复杂度为O(Log2N ),关于key 有序


时间复杂度

时间效率被称为时间复杂度,算法中的基本操作的执行次数一般找执行语句最多的,为算法的时间复杂度

大O的渐进表示法:

用法例子:

// 请计算一下func1基本操作执行了多少次?void func1(int N){int count = 0;for (int i = 0; i < N ; i++) {for (int j = 0; j < N ; j++) {count++;
}
}for (int k = 0; k < 2 * N ; k++) {count++;
}int M = 10;while ((M--) > 0) {count++;
}System.out.println(count);
}

只需要大概执行次数,那么这里我们使用大O的渐进表示法

满足三点:

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

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

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

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


空间复杂度

而空间效率被称作空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes 的空 间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似,也 使用大 O 渐进表示法。
用法例子:
/ 计算bubbleSort的空间复杂度?
void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;
}
}if (sorted == true) {break;
}
}
}

注意

如果算法中使用了固定数量的额外变量或数组,不随输入规模的增加而变化,则空间复杂度是O(1)。

如果算法使用了和输入规模相关的额外空间,比如创建了一个大小与输入规模相等的数组来存储结果,那么空间复杂度通常是 O(N)。

对于递归算法,需要考虑递归调用所使用的栈空间。

每次递归调用都会占用一定的栈空间,因此递归算法的空间复杂度通常是 O(N) 或者 O(log N),取决于递归调用的深度


包装类

在 Java 中,由于基本类型不是继承自 Object ,为了在泛型代码中可以支持基本类型, Java 给每个基本类型都对应了 一个包装类型
基本数据类型 包装类
byte       Byte
short      Short
int        Integer
long       Long
float      Float
double     Double
char       Character
boolean    Boolean

装箱

public static void main1(String[] args) {//装箱/装包:把一个 基本数据类型 转变为 包装类型Integer a = 10;// 隐式装箱/自动装箱int i = 99;Integer b = i;System.out.println(b);Integer aa = Integer.valueOf(10);//显示装箱System.out.println(aa);}
}

拆箱

  public static void main2(String[] args) {//拆箱/拆包:把一个 包装类型 转变为 基本数据类型Integer a = 66;int b = a;//自动拆箱System.out.println(b);int aa = a.intValue();//显示拆箱double d = a.doubleValue();//拆成double类型}


下列代码输出什么,为什么?
public class Test {public static void main(String[] args) {Integer a = 100;Integer b = 100;System.out.println(a == b);Integer a1 = 200;Integer b1 = 200;System.out.println(a1 == b1);}

解释如下:

Java 中的 Integer 类在范围为 [-128, 127] 内的整数上具有缓存功能,即当创建一个范围内的 Integer 对象时,会从缓存中获取已经存在的对象而不是新创建一个对象。这是因为在此范围内的整数被频繁使用,因此缓存可以提高性能和节省内存。

但是,当整数超出范围 [-128, 127] 时,每次创建的 Integer 对象都会是一个新的对象,因此这些对象的地址不同,即使它们的值相同。因此,对于超出范围的整数,使用 == 比较两个 Integer 对象时,结果通常会是 false。

结果:

a 和 b 的值都在范围内,因此它们的地址相同,a == b 返回 true。
c 和 d 的值超出范围,因此它们的地址不同,c == d 返回 false。


引出泛型

实现一个类,类中包含一个数组成员,使得数组中可以存放任何类型的数据,也可以根据成员方法
返回数组中某个 下标的值?
泛型语法例子:
/*** @param <T> 代表当前类 是一个 泛型类,<T>是一个占位符*/
class MyArray<T> {//public T[] array = (T[]) new Object[10];public Object[] array = new Object[10];public void setValue(int pos, T val) {this.array[pos] = val;}public T getValue(int pos) {return (T) array[pos];//把返回类型 强转为指定类型}}public class Test2 {public static void main(String[] args) {//泛型其实就是将 类型 进行 传递MyArray<Integer> myArray = new MyArray<>();myArray.setValue(1, 10);System.out.println(myArray.getValue(1));MyArray<String> myArray1 = new MyArray<>();myArray1.setValue(0, "hello");System.out.println(myArray1.getValue(0));}
}
以上代码实现后 发现 任何类型数据都可以存放
1. 类名后的 <T> 代表占位符,表示当前类是一个泛型类
注意【规范】类型形参一般使用一个大写字母表示,常用的名称有:
2.不能new泛型类型的数组
虽然在这种情况下,当前数组任何数据都可以存放,但是,更多情况下,我们还是希望他只能够持有一种数据类 型。而不是同时持有这么多类型。所以,泛型的主要目的:就是指定当前的容器,要持有什么类型的对象。让编译 器去做检查。此时,就需要把类型,作为参数传递。需要什么类型,就传入什么类型

泛型类的使用

例子:
MyArray<Integer> list = new MyArray<Integer>();
注意:泛型只能接受类,所有的基本数据类型必须使用包装类!
类型推导
例子:
MyArray<Integer> list = new MyArray<>(); // 可以推导出实例化需要的类型实参为 Integer
小结:
1. 泛型是将数据类型参数化,进行传递
2. 使用 <T> 表示当前类是一个泛型类。
3. 泛型目前为止的优点:数据类型参数化,编译时自动进行类型检查和转换

泛型如何编译的

擦除机制

通过命令:javap -c 查看字节码文件,所有的T都是Object

在编译的过程当中,将所有的 T 替换为 Object 这种机制,我们称为: 擦除机制
Java 的泛型机制是在编译级别实现的。编译器生成的字节码在运行期间并不包含泛型的类型信息

泛型的上界

语法:
class 泛型类名称<类型形参 extends 类型边界> {
...
}

例子:

public class MyArray<E extends Number> {
...
}
上述例子表示只接受 Number 的子类型作为 E 的类型实参
MyArray<Integer> l1; // 正常,因为 Integer 是 Number 的子类型
MyArray<String> l2; // 编译错误,因为 String 不是 Number 的子类型

泛型方法静态泛型方法以及泛型上界

定义语法:

方法限定符 <类型形参列表> 返回值类型 方法名称(形参列表) { ... }
例子:
class Person1 implements Comparable<Person1> {@Overridepublic int compareTo(Person1 o) {return 0;}
}//泛型类
//T一定是实现了Comparable这个接口
class A<T extends Comparable<T>> {//将来你指定这个A泛型类传入的类型参数一定是实现了Comparable这个接口public T findMax(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if (max.compareTo(array[i]) < 0) {max = array[i];}}return max;}
}//泛型方法
class B {public <T extends Comparable<T>> T findMax(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if (max.compareTo(array[i]) < 0) {max = array[i];}}return max;}
}//静态泛型方法
class B1 {public static <T extends Comparable<T>> T findMax(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if (max.compareTo(array[i]) < 0) {max = array[i];}}return max;}
}public class Test4 {public static void main(String[] args) {//静态泛型方法Integer[] integers2 = {1, 2, 3, 4};Integer integer3 = B1.findMax(integers2);System.out.println(integer3);//泛型方法B b = new B();Integer[] integers1 = {1, 2, 3, 4};//类型推导:根据实参传值 来推导 此时的类型Integer integer1 = b.findMax(integers1);//两种写法Integer integer2 = b.<Integer>findMax(integers1);//两种写法,这个全一点,可以省略System.out.println(integer1);//泛型类A<Integer> a = new A<>();Integer[] integers = {1, 2, 3, 4};Integer integer = a.findMax(integers);System.out.println(integer);A<Person1> a1 = new A<>();}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.tpcf.cn/news/683153.html

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

算法训练营day24(补),回溯4-2

import ( "fmt" "sort" ) 78. 子集 func subsets(nums []int) [][]int { //存储全部集合 result : make([][]int, 0) if len(nums) 0 { return result } //存储单次集合 path : make([]int, 0) var backtrace func(numList []int, startIndex int) bac…

变量与运算符

目录 1. 关键字&#xff08;keyword&#xff09; 2. 标识符( identifier) 3. 变量 3.1 为什么需要变量 3.2 初识变量 3.3 Java中变量的数据类型 3.4 变量的使用 3.4.1 步骤1&#xff1a;变量的声明 3.4.2 步骤2&#xff1a;变量的赋值 4. 基本数据类型介绍 4.1 整数…

cool Nodejs后端框架 如何快速入门 写一个接口

1.cool 框架 js前端开发者 想自己写后端接口 快速入门的就是node.js 了 可以用这个框架自己做一些东西 或者实现前后端的开发 2.目录结构 这个基本上 就是cool 框架的项目结构 主要是 这个src 中的modules 文件夹 这个文件夹 主要是一些接口模块 比如 business 中 相当于…

OJ_深度优先搜索

题干 c代码 #include <iostream> #include <algorithm> using namespace std; #define Max_M 100 #define Max_N 100 char a[Max_M][Max_N],M,N; void dfs(int x,int y) {//先把w替换成.//然后遍历8个方向a[x][y] .;for(int dx -1;dx < 1;dx){for(int dy -1…

基于 Python 的大数据的电信反诈骗系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

车载诊断协议DoIP系列 —— 车载以太网诊断需求规范(网关、路由)

车载诊断协议DoIP系列 —— 车载以太网诊断需求规范(网关、路由) 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师(Wechat:gongkenan2013)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 本就是小人物,输了就是输了,不要在意别人怎么看自…

Springboot加载bootstrap和application原理

Springboot加载bootstrap和application原理 bootstrap.yml能被springboot加载导入依赖 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.4.6</version><rel…

Bitcoin Bridge:治愈还是诅咒?

1. 引言 主要参考&#xff1a; Bitcoin Bridges: Cure or Curse? 2. 为何需关注Bitcoin bridge&#xff1f; 当前的Bitcoin bridge&#xff0c;其所谓bridge&#xff0c;实际是deposit&#xff1a; 在其它链上的BTC情况为&#xff1a; 尽管当前约有43.7万枚BTC在其它链上…

防御保护---防火墙的带宽管理

文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 一.带宽管理概述 带宽管理是指限制网络流量的速率或控制网络流量的优先级&#xff0c;以确保网络的性能和可用性。 防火墙带宽管理核心&#xff1a; 带宽限制&#xff1a;限制非关键业务的流量…

PR:视频源素材的截取操作

导入素材后&#xff0c;双击视频素材&#xff0c;打开源视频 1&#xff1a;设置入点 2&#xff1a;设置出点&#xff0c;设置完出入点&#xff0c;抓取视频就可以将入点至出点的片段拖至时间轴上 3&#xff1a;转到入点 4&#xff1a;后退一帧 5&#xff1a;播放 6&#x…

全面理解JVM虚拟机

为什么要学JVM&#xff1f; ​ 首先&#xff1a;面试需要。面试题层出不穷&#xff0c;难道每次面试都靠背几百上千条面试八股&#xff1f; ​ 其次&#xff1a;基础决定上层建筑。自己写的代码都不知道是怎么回事&#xff0c;怎么可能写出靠谱的系统&#xff1f; ​ 然后&a…

【算法设计与分析】反转链表 ||

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;算法分析与设计 ⛺️稳中求进&#xff0c;晒太阳 题目 给你单链表的头指针 head 和两个整数 left 和 right &#xff0c;其中 left < right 。请你反转从位置 left 到位置 right 的链表…

机器学习入门--循环神经网络原理与实践

循环神经网络 循环神经网络&#xff08;RNN&#xff09;是一种在序列数据上表现出色的人工神经网络。相比于传统前馈神经网络&#xff0c;RNN更加适合处理时间序列数据&#xff0c;如音频信号、自然语言和股票价格等。本文将介绍RNN的基本数学原理、使用PyTorch和Scikit-Learn…

【网络攻防实验】【北京航空航天大学】【实验四、防火墙配置(Firewall Configuration)实验】

实验四、防火墙配置(Firewall Configuration)实验 一、 实验环境搭建 1. Kali Linux网络配置 将Kali Linux虚拟机网卡1设置为NAT网络模式,ip地址为10.0.2.5,如下图所示: 配置NAT网络端口转发: 将Kali Linux网卡2设置为内部网络模式: 配置Kali Linux网卡1: 类似地,配…

Spring Cloud 路由和消息传递 (HTTP 路由)

Spring Cloud 路由 Spring Cloud 路由是指将请求路由到特定服务的机制。Spring Cloud 提供了多种路由机制&#xff0c;包括&#xff1a; Ribbon: 一个基于 HTTP 和 TCP 的客户端负载均衡工具&#xff0c;提供软负载均衡、故障转移等功能。Feign: 一个声明式的 HTTP 客户端&am…

在中国做 DePIN?你需要明白风险与机遇

撰文&#xff1a;肖飒团队 来源Techub News专栏作者 随着科技的发展&#xff0c;我们正在日益进入一个资源相对过剩的时代&#xff0c;这使我们在日常生活中虽然支付了该部分资源的使用费&#xff0c;但却时常不能将其「物尽其用」&#xff0c;难免出现资源浪费。例如&#x…

【More Effective C++】条款19:了解临时对象的来源

临时对象&#xff1a;没有命名&#xff0c;不会出现在源代码中 帮助隐式类型转换成功而创建的对象 编译器创建一个类型为string的临时对象&#xff0c;以buffer作为参数&#xff0c;调用string的构造函数&#xff1b;str绑定到了这个临时对象上函数返回时&#xff0c;这个临时…

PHP+vue+mysql校园学生社团管理系统574cc

运行环境:phpstudy/wamp/xammp等 开发语言&#xff1a;php 后端框架&#xff1a;Thinkphp 前端框架&#xff1a;vue.js 服务器&#xff1a;apache 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat/phpmyadmin 前台功能&#xff1a; 首页&#xff1a;展示社团信息和活动…

C#,二项式系数(Binomial Coefficient)的七种算法与源代码

1 二项式系数&#xff08;binomial coefficient&#xff09; 二项式系数&#xff08;binomial coefficient&#xff09;&#xff0c;或组合数&#xff0c;在数学里表达为&#xff1a;(1 x)ⁿ展开后x的系数&#xff08;其中n为自然数&#xff09;。从定义可看出二项式系数的值…

立体库库存数量统计(SCL代码)

立体库库存物体检测由光电开关完成&#xff0c;每个储物格都有一个检测光电。5*6的仓库需要30个光电检测开关组成检测矩阵。找出矩阵中的最大元素并返回其所在的行号和列号和我们今天介绍的算法有很多相似的地方&#xff0c;大家可以对比学习。具体链接地址如下&#xff1a; h…