《Java版数据结构 & 集合类剖析》复杂度，与泛型篇：“O(n²) 代码写时一时爽，重构火葬场。”

1、初识数据结构

该类专栏的内容主要学习Java集合框架中的容器使用和一部分设计原理，这些容器背后对应的数据结构的知识。数据结构是计算机存储，组织数据的一种方式，所以对于数据结构并不局限于某一种语言。而集合框架又称为容器就是由一群大佬为了方便我们使用其中的数据结构，不用每次每次都手搓轮子写的包，在C++中也有类似的叫做STL库。

2、时间和空间复杂度

对于一个算法，我们怎么去评价好或者不好，我们通常第一看的就是他的效率。
那么对于效率的具体体现就是时间和空间，时间效率就对应着时间复杂度，空间效率就对应着空间复杂度。

• 时间复杂度主要主要衡量的是一个算法的运行速度
• 空间复杂度主要衡量的是该算法使用了多少的额外空间
• 近年来计算机硬件设备的飞速发展，内存和硬盘性能大幅度提高，导致比起空间复杂度，我们更在意时间上的效率，所以在实际开发中，我们通常更接受以空间换时间。

2.1、时间复杂度的概念

算法的时间复杂度是一个函数，定量的描述了一个算法运行所需的时间。理论上来说我们是不能计算出来的，因为具体的运行时间收到的影响因素有很多，物理层面的因素：你CPU的计算能力，损耗程度等等 都导致我们只能通过上机测试才能具体得出。因此为了方便，引进了时间复杂度这个分析方式，

• 一个算法运行所花费的时间与其中语句中的执行次数成正比例
• 算法中基本操作的执行次数为算法的时间的复杂度

2.2、空间复杂度的概念

空间复杂度是用来描述一个算法在运行过程中临时占用存储空间的大小。这个概念很容易误解为这个程序所占空间的大小，讨论这个并没有意义。

• 在一个算法中，空间复杂度的大小是和额外创建的变量所占空间的大小有关

2.3、大O的渐进表示法

无论时间复杂度还是空间复杂度，都是用大O渐进表示法来描述的，这个表示法只需要大概的执行次数

2.3.1、大O表示时间复杂度

具体例子：

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);
 }

以上func1方法中，基本操作就是在循环体中的count++
那么它的基本操作次数就为： F(N) = N^2 + 2N + 10

我们用大O表示法对上述基本操作的次数进行一个化简省略后结果为 O(N^2)

所以我们不难看出，大O表示法去掉了那些对结果影响不大的项，除此之外如果该算法的时间复杂度存在最好，中等，最坏的情况，大O表示法展示的默认为其最坏的情况（用的时间最多的情况）具体的规则如下：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶

掌握其时间复杂度仅仅通过这些还是不够的，以后再写每一个算法都对其时间复杂度进行判断才能慢慢领悟各种复杂的情况

2.3.2、大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;
    }    } } 
    ```

上面的冒泡排序使用了 sorted，end 这两个额外变量，属于常数个，所以空间复杂度为 O(1)

// 计算fibonacci的空间复杂度？
int[] fibonacci(int n) {
  long[] fibArray = new long[n + 1];
  fibArray[0] = 0;
  fibArray[1] = 1;
  for (int i = 2; i <= n ; i++) {
  fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }
  return fibArray;
}

上面的方法使用的额外空间为 fibArray ，这个数组的空间大小是一个变量n，所以其额外空间大小是与n有关的，并非常数个。所以其空间复杂度为O(N)

// 计算阶乘递归Factorial的空间复杂度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}

对于递归，我们看空间复杂度的层面除了看额外变量，最主要的是其函数栈帧的开辟
上述代码中，开辟了N个函数栈帧，每个函数栈帧中的额外变量是常数个，所以其空间复杂度为：O(N)

3、泛型

3.1、包装类

在Java语法篇提到过Java中每个基本类型都增加了对应的包装类

在这里我们要了解其对应的转换：

3.1.1、装箱与拆箱

装箱 ：基本类型 -> 包装类型
拆箱 ：包装类型 -> 基本类型

int i = 10;
// 装箱操作，新建一个 Integer 类型对象，将 i 的值放入对象的某个属性中
Integer ii = Integer.valueOf(i);
Integer ij = new Integer(i);
// 拆箱操作，将 Integer 对象中的值取出，放到一个基本数据类型中
int j = ii.intValue();

3.1.2、自动装箱与自动拆箱

Java对转换提供了 语法糖，赋值直接可以装箱和拆箱

int i = 10;
Integer ii = i; // 自动装箱
Integer ij = (Integer)i; // 自动装箱
int j = ii; // 自动拆箱
int k = (int)ii; // 自动拆箱

3.1.3、面试题：

public static void main(String[] args) {
  Integer a = 127;
  Integer b = 127;
  Integer c = 128;
  Integer d = 128;
  System.out.println(a == b);
  System.out.println(c == d);
}

第一个打印是 true
第二个打印是false

想要知道如何解决这个问题，我们就得对包装类的装箱的底层实现有所了解：

由于在Java中拆箱与装箱特别频繁，所以预先创建了 Integer对象来对其重用，但为了平衡其使用频率和内存开销，所以预先创建的对象 最小为 -128 最大为127，就是1 byte的 大小能表示的数字。超过这个范围就会重新创建个对象进行引用。

所以上面的代码中，a 和 b其实共同引用的是同一个对象
而c 和 d引用对象的大小超过了这个区域，所以他们两个是重新创建了不同的对象，所以不相等

4、泛型

一般的类和方法，只能使用具体的类型: 要么是基本类型，要么是自定义的类。如果要编写可以应用于多种类型的代码，这种刻板的限制对代码的束缚就会很大。
泛型即为参数化类型，能够让你写一套代码，匹配多种不同的类型。

4.1、引出泛型

泛型虽然就是用来适用于许多类型，但是如果自己实现一个类，用Object作为数组类型，让任意类型都能存到一个数组中，这种情况我们在实际开发中的需求很少，泛型更多的是制定当前的容器，要持有什么类型的对象，让编译器去做检查。

4.2、泛型类的创建语法：

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

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

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

代码解释：

• 类名后的代表占位符，表示当前类是一个泛型类
• 了解形参的占用字母含义：
  • E表示Element
  • K表示Key
  • V表示Value
  • N表示Number
  • T表示Type
  • S，U,V 表示第二、第三、第四个类型
• 该泛型占位符不能用来new一个数组

  T[] t = new T[5] //这个写法是不合法的

• 类型后加入这种具体类型就是指定当前类型，且该括号里只能指定引用类型，基本类型不能写进去

5、泛型类的使用

5.1、语法

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

5.2、类型推导

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

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

6、裸类型

裸类型是一个泛型类，但没有带着类型实参

ArrayList就是一个泛型类，通常我们使用ArrayList来指定元素是字符串，如果直接使用ArrayList 不带尖括号，那么就称之为裸类型

6.1、裸类型的问题

• 丢失类型安全：本应限制只能放某类型元素的集合，现在可以放任意对象，容易导致 ClassCastException。

• 编译器无法进行类型检查：泛型带来的编译期类型校验失效。

• 代码可读性下降：阅读者不清楚集合中期望的元素类型。

7、泛型的编译

7.1、擦除机制

通过命令：javap -c 查看字节码文件，发现所有的T都是Object

在编译的过程中，将所有的T转换成Object 这种机制，称之为 擦除机制

7.2、类型擦除机制流程

核心思想：泛型信息只存在于编译期，编译器在生成字节码时会“擦除”具体的类型参数，替换为原始类型，并自动插入必要的类型转换。

工作流程

1. 编译期检查：编译器根据泛型声明进行类型检查，确保类型安全。

2. 擦除替换：

   • 将泛型参数替换为它的上界（若无指定则替换为 Object）。

   • 自动添加 cast 指令（从 Object 转换回实际类型）。

3. 生成字节码：最终 .class 文件中不存在泛型信息（除了少量 Signature 属性保留给反射）。

8、泛型的上界

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

8.1、语法

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

例如：

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

只接受Number 的子类型作为 E 的类型实参

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

E必须是实现了Comparable接口

9、泛型方法

9.1、定义语法

方法限定符<类型参数列表> 返回值类型 方法名称(形参列表){
}

public class Example {

    // 实例泛型方法
    public <T> void print(T value) {
        System.out.println(value);
    }

    public static void main(String[] args) {
        Example example = new Example();
        example.print("Hello");    // 自动推断 T = String
        example.print(123);        // 自动推断 T = Integer
        example.print(3.14);       // 自动推断 T = Double
    }
}

如果是静态方法，则在static后加类型参数列表

public class GenericMethodDemo {

    // 泛型方法：交换数组中两个位置的元素
    public static <T> void swap(T[] array, int i, int j) {
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        String[] words = {"A", "B", "C"};
        swap(words, 0, 2);
        System.out.println(Arrays.toString(words)); // [C, B, A]

        Integer[] numbers = {1, 2, 3};
        swap(numbers, 0, 1);
        System.out.println(Arrays.toString(numbers)); // [2, 1, 3]
    }
}

10、通配符

? 用于在泛型的使用，叫做通配符

10.1、通配符解决什么问题

乍一看通配符就和泛型的作用一样，没什么区别，但是有其特别的意义

import java.util.*;

public class RawPrintDemo {
    // 参数是原始类型 List
    public static void printList(List list) {
        for (Object obj : list) {
            System.out.println(obj);
        }
        // 危险操作：可以随便添加任何东西
        list.add("偷偷塞进来的字符串"); 
    }

    public static void main(String[] args) {
        List<Integer> intList = new ArrayList<>();
        intList.add(1);
        intList.add(2);
        printList(intList);             // 编译警告 unchecked
        System.out.println(intList);    // [1, 2, 偷偷塞进来的字符串]
    }
}

看到以上的代码中，List相当于是裸类型，方法内可以往 List< Integer > 中塞进 String，不报错，但后续操作时可能引发 ClassCastException

那么接下来用泛型来进行优化：

import java.util.*;

public class GenericPrintDemo {
    // 泛型方法：用 <T> 接收任意类型的 List
    public static <T> void printList(List<T> list) {
        for (T t : list) {
            System.out.println(t);
        }
        // list.add("字符串");  // 编译错误：不能添加 String 到 List<T>
        // list.add(123);      // 同样错误
    }

    public static void main(String[] args) {
        List<Integer> intList = new ArrayList<>();
        intList.add(1);
        intList.add(2);
        printList(intList);  // 合法，T 推断为 Integer
    }
}

可以看到，用泛型来指定List，可以避免它私自用其方法，也能保证其安全性，那么通配符到底有什么不一样呢？

• 方法声明了类型参数 T，实际上方法体里完全没有用到这个 T（只是打印，不需要知道具体类型）。

• 这会让阅读代码的人疑惑：“这个 T 是用来干什么的？是不是后面要操作它？” ——引入了不必要的类型变量，增加了概念负担。

• 接口演进的自由度：如果用泛型方法，以后想给类型参数加约束（比如 T extends Comparable），所有调用方都会受影响。

接下来用通配符进行优化：

import java.util.*;

public class WildcardPrintDemo {
    // 使用 List<?>，表示“一个未知类型的列表”
    public static void printList(List<?> list) {
        for (Object obj : list) {
            System.out.println(obj);
        }
        // list.add("字符串"); // 编译错误：不能添加任何非 null 元素
        // list.add(123);
        list.add(null);       // 唯一可以添加的值是 null
    }

    public static void main(String[] args) {
        List<Integer> intList = new ArrayList<>();
        intList.add(1);
        intList.add(2);
        printList(intList);  // 合法

        List<String> strList = new ArrayList<>();
        strList.add("hello");
        printList(strList);  // 同样合法
    }
}

• 一眼就能看出：“这个方法只是读取列表，不关心元素具体类型”。

• 比泛型方法更简洁（少写 和方法签名中的类型声明）。

• List<?> 是完全未知的，它可以接受任何 List，将来无论约束如何变化，只要不涉及类型关联，接口都不需要改动。

10.2、通配符上界

语法：

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

• 直接给出结论：通配符上界是只用于读取数据的情况

接下来通过具体的例子来理解：

public static double sum(List<Number> list) {
    double total = 0;
    for (Number n : list) {
        total += n.doubleValue();
    }
    return total;
}
List<Double> doubles = Arrays.asList(1.5, 2.3, 3.7);
sum(doubles); //  编译错误：List<Double> 不能转为 List<Number>

所以这时我们使用通配符上界：

public static double sum(List<? extends Number> list) {
    double total = 0;
    for (Number n : list) {   // 取出元素时，自动上转型为 Number
        total += n.doubleValue();
    }
    return total;
}
List<Integer> ints = Arrays.asList(1, 2, 3);
List<Double> doubles = Arrays.asList(1.5, 2.3, 3.7);
System.out.println(sum(ints));    // 6.0
System.out.println(sum(doubles)); // 7.5

为什么 List<? extends Number> 只能读，不能写？

现在往 sum 方法里试着加一行代码，你立刻就能看到限制：

extends Number> list) {
   list.add(42);            // ❌ 编译错误！
   list.add(3.14);          // ❌ 编译错误！
   list.add(null);          // ✅ 唯一能添加的是 null
   double total = 0;
   for (Number n : list) {
       total += n.doubleValue();
   }
   return total; } 

因为编译器只知道 list 是“某个 Number 子类的列表”，但不知道具体是哪个子类。所以编译器为了保证绝对安全，干脆禁止所有写入操作（除了 null，因为 null
可以是任何引用类型）。

读取为什么安全？

因为无论实际类型是 List 还是 List，里面的元素都一定是 Number 的子类型。
读取时，你可以统一用父类引用 Number 来接收，这就是多态的天然安全性

• List<? extends Number> 是一个只读的容器，你只能作为“消费者”从中获取 Number，但不能往里存任何东西。

10.3、 通配符下界

语法：

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

• 与上面的通配符上界相反，该通配符下界接收的容器不能读取数据，只能写入数据。

 public static void copy(List<Integer> src, List<Integer> dest)
{
    for (Integer i : src) {
        dest.add(i);
    } } List<Integer> src = Arrays.asList(1, 2, 3);

List<Number> dest = new ArrayList<>(); copy(src, dest); // 
编译错误：List<Number> 不能转为 List<Integer> 

可以看到如果没有泛型，上面的方法就无法复用

采用通配符：

public static void copy(List<? extends Integer> src,
List<? super Integer> dest) {
   for (Integer i : src) {
       dest.add(i);          //  安全写入
   } } List<Integer> src = Arrays.asList(1, 2, 3);

List<Number> dest = new ArrayList<>(); copy(src, dest);             //
// 合法！目标可以是 Number 的列表

List<Object> dest2 = new ArrayList<>(); copy(src, dest2);           
//  也合法Object 也能装 Integer 

这里源使用了上界（只读），目标使用了下界（只写），完美解耦。

为什么 List<? super Integer> 可以写入，但读取受限？

在 copy 方法中，我们往 dest 里添加 Integer 是绝对安全的。 因为无论 dest 实际是List < Integer >、List< Number > 还是 List< Object >，它们都能装下 Integer

复杂度与泛型篇就此结束，下一篇章会在讲解第一个容器前将集合框架的封装和设计进行介绍