一、初始集合框架

1.什么是集合框架

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

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

重要接口与类之间的反馈

接口与接口之间的关系叫extends

接口与类之间的关系叫implements

重要接口：【List，Queue、Set】（继承在Collection接口下）、Deque、Map（独立的）

重要类型：图中每一列最下面的模块

每一个具体的类型背后就是一个数据结构

2.面试题

3.宏观了解数据结构

3.1 什么是数据结构

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

3.2 数据结构

3.3 相关Java知识

1.泛型Generic

2.自动装箱autobox和自动拆箱autounbox

3.Object的equals方法

4.Comparable和Comparator接口

3.4 算法

定义良好的计算过程，简单而言，就是一系列的计算步骤，用来将输入数据转化成输出结果。

多刷题：牛客 / LeetCode！！！

二、时间和空间复杂度

1.如何评判一个代码的好与坏

1. 可读性高-->多写注释，命名规范……
2. 效率高-->①时间效率 ②空间效率

2.算法效率

一是时间效率，二是空间效率。时间效率被称为时间复杂度，空间效率被称为空间复杂度。

时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。

3.时间复杂度

3.1 时间复杂度概念

3.2 大O的渐进表示法

计算大概执行次数，用来描述函数渐进性为的数学符号

示例1：

答：O（N）

示例2：

答：O（M+N）

示例4：

答：O（1）

示例5

等差数列

答：O（N^2）

示例6：

答：X = O（logN）

示例7（递归）：

答：X = O（N）

示例8：斐波那契数列

时间复杂度为：2^n

4.空间复杂度

指对一个算法在运行过程中临时占用存储空间大小的量度。算的是变量的个数，与时间复杂度类似，也使用大O渐进表示法。

【实例1】

【实例2】

（N之前的数全部存进来了）

【实例3】

递归多少次，空间复杂度就是几（每递归一次，就要存一次N）

5.常见复杂度

最坏情况下N越来越大，要根据问题规模来分析，因为时间复杂度都是函数，是在一定区间内变化。

如图

，为此要具体问题具体分析谁大谁小。

三、包装类&泛型

1.包装类

在Java中，由于基本类型不是继承自Object（基本类型不是对象，不是对象就不能让数字面向对象，如：将字符串变成整数，得调方法，基本类型不支持），为了在泛型代码中可以支持基本类型，Java给每个基本类型都对应了一个包装类型。

1.1 基本数据类型和对应包装类

【注意】除了Integer和Character，其余基本类型的包装类都是首字母大写。

1.2 装箱和拆箱

又叫做装包和拆包

①装包/装箱

把基本类型转换为包装类型

int a = 10;
Integer i = a;
System.out.println(i);

底层调的都是.valueOf

Integer i1 = Integer.valueOf(a);
System.out.println(i1);

②拆包/拆箱

把包装类型转换为基本类型

// 自动拆箱
Integer i = 100;
int a = i;
System.out.println(a);

// 手动拆箱
int a2 = i.intValue();
System.out.println(a2);

【面试题】

下面代码输出结果？

2.什么是泛型

适用于许多许多类型，对类型实现了参数化。

3.引出泛型

3.1 语法

基础写法：

class 泛型类名称<类型形参列表>{
    // 这里可以使用类型参数
}

class ClassName<T1,T2,...Tn>{
}

其他写法：

class 泛型类名称<类型形参列表> extends 继承类 /* 这里可以使用类型参数 */{
    // 这里可以使用类型参数
}

class ClassName<T1,T2,...Tn> extends ParentClass<T1> {
    // 只可以使用部分类型参数
}

上述代码进行改写如下：

4.泛型类的使用

4.1 语法

泛型类<类型实参> 变量名;		//定义一个泛型类引用
new 泛型类<类型实参>(构造方法实参)		//实例化一个泛型类对象

4.2 示例

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

注意：泛型能接受类，所有的基本数据类型必须使用包装类！

4.3 类型推导（Type Inference）

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

MyArray<Integer> list = new MyArray<>(); //可以推导出实例化需要的类型实参为 Integer

5.裸类型（Raw Type）

是一个泛型类但没有带着类型实参，eg：MyArrayList就是一个裸类型

MyArray list = new MyArray();

6.泛型如何编译

6.1 擦除机制

1,基本概念

泛型是编译时的一种机制，在运行时没有泛型的概念，运行是运行在JVM，JVM当中没有泛型这样的概念。

• 在编译时，java编译器会将泛型类型信息从代码中移除，这个过程就叫做类型擦除。
• 擦除后，泛型类型会被替换为其边界类型（通常是object)或者指定的类型

2,擦除过程

• 将泛型参数替换为其边界或object.
• 在必要的地方插入类型转换以保持类型安全。
• 生成桥接方法以保持多态性

3,示例

上述代码在类型擦除后为如下代码：

擦除前：

擦除后：

【泛型意义】编译的时候，泛型已经帮你检查了，转换了

6.2 关于桥接方法

• 泛型类型擦除可能导致子类方法和父类方法的签名不一致。
• 为了维护ava的多态性，需要桥接方法来确保子类方法能够正确覆盖父类方法。

• 类型擦除后代码变为

此比时stringnode的setdata方法并没有真正覆盖父类的setData方法（参数类型不同）。为了解决这个题，编译器会在stringnode中生成一个桥接方法：

//编译器生成的桥接方法
public void setData(Object data) {
    setData((String) data);
}