对集合、复杂度以及泛型的认识

文章目录

  • 一、集合框架是什么?
  • 二、复杂度
    • 1.时间复杂度
    • 2.空间复杂度
  • 三、泛型


一、集合框架是什么?

Java 集合框架 Java Collection Framework ,又被称为容器 container ,是定义在 java.util 包下的一组接口 interfaces 和其实现类 classes
类和接口如下:
对集合、复杂度以及泛型的认识_第1张图片

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

二、复杂度

1.时间复杂度

2.空间复杂度

这里请参考之前写的一篇关于复杂度的博客:如何评价一个算法的好坏?-复杂度_crazy_xieyi的博客-CSDN博客大O表示法来描述复杂度,需要忽略常数、系数和低阶。O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)。用尽量小的存储空间,用尽量少的执行步骤。第64个斐波那契数(n=64),用O(n)计算大约耗时6.4*10^(-8)秒,用O(2^n)计算大约耗时584.94年。...https://blog.csdn.net/crazy_xieyi/article/details/126062123?spm=1001.2014.3001.5501

这里看一个非常经典的题目:

// 计算斐波那契递归 的复杂度?
int fifibonacci ( int N ) {
return N < 2 ? N : fifibonacci ( N - 1 ) + fifibonacci ( N - 2 );
}

1.时间复杂度

这里就要分析递归了多少次。

对集合、复杂度以及泛型的认识_第2张图片 计算执行次数,为等比数列求和:2^0+2^1+2^2+......+2^(n-1)=2^n-1

所以时间复杂度为:O(2^N)

 2.空间复杂度

在计算空间复杂度的时候,需要注意一点就是:当一条链路递归完成之后,返回来的时候,其所占的空间就被释放了,所以空间复杂度以最长链路为准,及空间复杂度为:O(N)

三、泛型

泛型是在 JDK1.5 引入的新的语法,通俗讲,泛型 就是适用于许多许多类型 。从代码上讲,就是对类型实现了参数化。 在编译的时候会进行类型的检查和转换
小技巧:设置泛型: shift + F6
语法
泛型类 < 类型实参 > 变量名 ; // 定义一个泛型类引用
new 泛型类 < 类型实参 > ( 构造方法实参 ); // 实例化一个泛型类对象

注意:泛型只能接受类,所有的基本数据类型必须使用包装类!

对集合、复杂度以及泛型的认识_第3张图片

当编译器可以根据上下文推导出类型实参时,可以省略类型实参的填写。

MyArray<Integer> list = new MyArray<>(); 

擦除机制

在编译的时候会进行类型检查,最后在编译完成的字节码文件中,都变成了Object。

泛型的上界

在定义泛型类时,有时需要对传入的类型变量做一定的约束,可以通过类型边界来约束。

public class MyArray < E extends Number > {
...
}

只接受 Number 的子类型作为 E 的类型实参。此时E是 Number的子类或Number本身,因为此时引入了泛型的上界,那么在擦除之后,为Number。

注意: 没有指定类型边界 E,可以视为 E extends Object 

如果涉及到元素的比较,那么E必须是实现了Comparable接口的。

public class MyArray < E extends Comparable < E >> {
...
}

 通配符

? 用于在泛型的使用,即为通配符。
一个例子:
public class TestDemo {
   public static void main ( String [] args ) {
      Message < Integer > message = new Message () ;
      message . setMessage ( 55 );
      fun ( message );
   }
   // 此时使用通配符 "?" 描述的是它可以接收任意类型,但是由于不确定类型,所以无法修改
   public static void fun ( Message temp ){
      //temp.setMessage(100); 无法修改!
      System . out . println ( temp . getMessage ());
   }
}

1.通配符上界

? extends 类:设置泛型上界

extends 上界 >
例子: extends Number > // 可以传入的实参类型是 Number 或者 Number 的子类

 通配符的上界,不能进行写入数据(不确定具体类型),只能进行读取数据(因为一定可以用Number接收)

2.通配符下界

super 下界 >
例子: super Integer > // 代表 可以传入的实参的类型是 Integer 或者 Integer 的父类类型

相反,通配符的下界,不能进行读取数据(因为无法知道取出的数据类型具体是什么),只能写入数据(此时可以放入Integer的父类)

你可能感兴趣的