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> {
    @Override
    public 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<>();
    }
}