Java数据结构：1. 数据结构前置知识

一、初识数据结构

什么是数据结构？
数据结构是一门单独的学科，和语言没关系。
数据结构就是：数据+结构，结构是用来描述和组织数据的。总而言之，数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构有很多种，所以我们描述和组织数据的方式有很多种，以便用来应对不同的场景来使用。
数组也能描述和组织数据，可以说数组是最简单的数据结构。

什么是集合类？
Java当中的集合类，其实就是被封装好的数据结构。

二、初识集合框架

1. 什么是集合框架

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

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

例如，一副扑克牌(一组牌的集合)、一个邮箱(一组邮件的集合)、一个通讯录(一组姓名和电话的映射关系)等等。

类和接口总览

这张图描述了Java当中类与类、类与接口之间的关系。
【说明】
Java的集合类和关系，不一定只有上图，上图只是描述了部分重要的常见类。
重要的接口有4个：List、Queue、Set、Map其他的类都是实现了这些接口。

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

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₂ N),关于key有序的;
7. Map： 映射，里面存储的是 K-V 模型的键值对；
   ① HashMap： 底层为哈希桶，查询时间复杂度为O(1)；
   ② TreeMap： 底层为红黑树，查询的时间复杂度为O(log₂N)，关于key有序。

2. 集合框架的重要性

1. 使用成熟的集合框架，有助于我们便捷、快速的写出高效、稳定的代码；
2. 学习背后的数据结构知识，有助于我们理解各个集合的优缺点及使用场景。

3. 背后所涉及的数据结构以及算法

【相关Java知识】

1. 泛型Generic
2. 自动装箱 autobox 和自动拆箱 autounbox
3. Object 的 equals 方法
4. Comparable 和 Comparator 接口

【什么是算法】
算法(Algorithm)：就是定义良好的计算过程，他取一个或者一组的值为输入，并产生出一个或一组作为输出。
简单的来说，算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

算法和数据结构相辅相成！

三、时间复杂度空间复杂度

1. 算法效率

public static long Fib(int N){if(N < 3){return 1;}return Fib(N-1) + Fib(N-2);
}

上述求斐波那契数列的算法好还是不好，如何衡量一个算法的好坏呢？
这就引出了我们的算法效率。

算法效率分两种：：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。
在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

复杂度的计算，不能只通过看代码来计算，还需要结合思想！

2. 时间复杂度

（1）概念

在计算机科学中，算法的时间复杂度是一个数学函数， 它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

（2）大O的渐进表示法

不是准确的，是渐进的，一般找的是执行此处最多的那个语句！！

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

Func1 执行的基本操作次数 ：
F(N) = N² + 2 * N + 10

• N = 10 F(N) = 130
• N = 100 F(N) = 10210
• N = 1000 F(N) = 1002010

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

（3）推导大O阶方法

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

使用大O的渐进表示法以后，Func1的时间复杂度为：O(N²)

• N = 10 F(N) = 100
• N = 100 F(N) = 10000
• N = 1000 F(N) = 1000000
  通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

对于复杂度来说存在最好、平均和最坏的情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
我们以后讨论复杂度的时候，默认说的都是最坏情况下。

例：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。

（4）常见时间复杂度计算举例

【实例1】

// 计算func2的时间复杂度？
void func2(int N) {int count = 0;for (int k = 0; k < 2 * N ; k++) {count++; //2N}int M = 10;while ((M--) > 0) {count++; //10}System.out.println(count);
}

【答案】

基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为O(N)。

【实例2】

// 计算func3的时间复杂度？
void func3(int N, int M) {int count = 0;for (int k = 0; k < M; k++) {count++; //M}for (int k = 0; k < N ; k++) {count++; //N}System.out.println(count);
}

【答案】
此时M和N都属于问题规模。
基本操作执行了M+N次，通过推导大O阶方法知道，时间复杂度为O(M+N)。

【实例3】

// 计算func4的时间复杂度？
void func4(int N) {int count = 0;for (int k = 0; k < 100; k++) {count++; //100}System.out.println(count);
}

【答案】

基本操作执行了100次，通过推导大O阶方法知道，时间复杂度为O(1)。

【实例4】
时间复杂度的计算，一定要结合代码的思想，而不能单纯只看代码。

// 计算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;}}
}

【解析】

	for (int end = array.length; end > 0; end--) {  //暂且把array.length看成Nboolean sorted = true;for (int i = 1; i < end; i++) { //end=N, i执行了N-1次//end--, end=N-1, i执行了N-2次//end--, end=N-2, i执行了N-3次//……//end--, end=2, i执行了1次//end--, end=1, i执行了0次
}

从上述代码可以看出，i 的执行次数为：
N-1 + N-2 + N-3 + ……+ 1 + 0 = 1/2 * (N² - N)，故通过推导大O阶方法知道，时间复杂度为O(N²)，此时是最坏情况下。
最好情况下是O(N)，就是至少比较了一轮。

【答案】
基本操作执行了1/2 * (N² - N)次，通过推导大O阶方法知道，时间复杂度为O(N²)。

【实例5】

// 计算binarySearch的时间复杂度？(二分查找)
int binarySearch(int[] array, int value) {int begin = 0;int end = array.length - 1;while (begin <= end) {int mid = begin + ((end-begin) / 2); if (array[mid] < value)begin = mid + 1;else if (array[mid] > value)end = mid - 1;elsereturn mid;}return -1;
}

【解析】
二分查找最坏的情况是查找到最后一个数字才找到。

设一共砍了y次。
n / x = 1;
因为第一次是 n/2，第二次是n/4，所以第y次为 2 ^y = n。
故：y = log²N
所以基本操作执行了 log²N 次，通过推导大O阶方法知道，时间复杂度为O(log²N)。

【答案】

基本操作执行了log²N次，通过推导大O阶方法知道，时间复杂度为O(log²N)。

【实例6】

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

【解析】
递归的时间复杂度 = 递归的次数 * 每次递归后执行的次数
所以由阶乘代码可知：递归了（N-1）次，每次递归后执行的都是三目运算符，所以每次递归后都执行了1次。
故基本操作执行了 N-1 次

【答案】

基本操作执行了 N-1 次，通过推导大O阶方法知道，时间复杂度为O(N)。

【实例7】

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

当N=5时：

由图可以看出，可以将其类比成二叉树，所以：

这里可以理解为是二叉树，我们可以看到图中的二叉树并不是满的，因为时间复杂度是近似于，所以我们可以把他看成是一个满的。
所以递归一共执行了1+2+4+……+2^N-1次，即2⁰+2¹+2²+2^N-1，运用等比数列求和公式可得：递归一共执行了 2^N-1 次。
递归的时间复杂度 = 递归的次数 * 每次递归后执行的次数
因为每次递归后执行的是三目运算符，为一次。
所以：基本操作执行了 2^N-1次。

【答案】

基本操作执行了 2^N-1次，通过推导大O阶方法知道，时间复杂度为O(2^N)。

3. 空间复杂度

（1）概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也
使用大O渐进表示法。

（2）常见空间复杂度计算举例

【例1】

// 计算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(1)

【例2】

// 计算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;
}

【解析】
求第N个斐波那契数字，long[] fibArray = new long[n + 1];它申请了一个比较长的数组，动态开辟了N个空间，空间复杂度为O(N)
【答案】
O(N)
【例3】

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

【解析】
每一次递归都会在栈上开辟空间，递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间，其空间复杂度为O(N)。
【答案】
O(N)

三、初识泛型

1. 包装类

（1）概述

在Java中，由于基本类型不是继承自Object，为了在泛型代码中可以支持基本类型，Java给每个基本类型都对应了一个包装类型。
也可以理解为我们希望基本类型也能面向对象，所以有了包装类。

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

（2）装箱和拆箱

【装箱和拆箱】

装箱：也叫装包，把基本类型的数据转变为引用类型。

Integer a = 10; //装包int i = 99;
Integer b = i; //装包 

拆箱：将Integer对象中的值取出，放到一个基本数据类型中。

Integer a = 10;
int i = a;

【自动装箱和自动拆箱】

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

【面试题】
下面代码输出什么？

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

分析：
赋值的时候在装包，装包的底层代码为

其中的low为-128，high为127，也就是在[-128,127]之间的256个数字可以存。

2. 泛型

（1）什么是泛型？

一般的类和方法，只能使用具体的类型：要么是基本类型，要么是自定义的类。如果要编写可以应用于多种类型的代码，这种刻板的限制对代码的束缚就会很大。
泛型：就是适用于许多类型，从代码上讲，就是对类型实现了参数化。

【引出泛型】
实现一个类，类中包含一个数组成员，使得数组中可以存放任何类型的数据，也可以根据成员方法返回数组中某个下标的值。

class MyArray {public Object[] array = new Object[10]; //定义一个可以存放任意数据类型的数组//默认放到数组的最后一个位置public void setValue(int pos,Object val) {array[pos] = val;}public Object getValue(int pos) {return array[pos];}}
public class Test {public static void main(String[] args) {MyArray myArray = new MyArray();myArray.setValue(0,10);myArray.setValue(1,"hello");//String str = myArray.getValue(1); //报错String str = (String) myArray.getValue(1); //getValue返回Object,向上转型，这里是要强转}
}

上述代码，如果数组中元素很多，每次访问都要强转太麻烦。并且虽然在这种情况下，任何数组数据都可以存放，但是，更多情况下，我们还是希望他只能够持有一种数据类型，而不是同时持有这么多类型。所以，泛型的主要目的：就是指定当前的容器，要持有什么类型的对象。让编译器去做检查。 此时，就需要把类型，作为参数传递。需要什么类型，就传入什么类型！

//<T>当前类，是一个泛型类，它只是一个占位符
class MyArray<T> {//public T[] array = new T[10]; //不能new泛型类型的数组，泛型是编译时期存在的，当程序运行起来到JVM之后，就没有泛型的概念了。public Object[] array = new Object[10];//默认放到数组的最后一个位置public void setValue(int pos,T val) { //放元素时，放T类型array[pos] = val;}public T getValue(int pos) { //取元素时，也取T类型return (T)array[pos]; //把返回的类型，强转为指定的类型}
}
public class Test {public static void main(String[] args) {MyArray<Integer> myArray = new MyArray<>();myArray.setValue(0,10);MyArray<String> myArray1 = new MyArray<>();myArray1.setValue(1,"hello");String ret = myArray1.getValue(1);}
}

泛型实际上来说，就是将类型进行了传递！

（2）泛型语法

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

如：

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

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

（3）泛型是如何编译的—擦除机制

在编译过程中，将所有的T替换为Object这种机制，我们称为：擦除机制。
所以JVM里不存在泛型，因为在运行的时候，泛型是编译时期存在的，当程序运行起来到JVM之后，就没有泛型这个概念了。

（4）泛型的上界

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

【语法】

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

【例】

//T一定是Number或者Number的子类
class TestGeneric <T extends Number> {
//在Number里面有一些定义好的代码 
}public class Test {public static void main(String[] args) {TestGeneric<Number> testGeneric1 = new TestGeneric<>();TestGeneric<Integer> testGeneric2 = new TestGeneric<>();TestGeneric<String> testGeneric3 = new TestGeneric<>(); //报错，因为String不是Numberde 子类，这就是泛型的上界}

（5）一个复杂的例子

写一个泛型类，求一个数组中的最大值。

//报错！！
class Alg<T>{public T findMaxValue(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if (array[i] > max) { //报错max = array[i];}}return max;}}

T一定是引用数据类型，最终被擦除为了Object类型，而Object类型一定是不能被比较的，而T类型，一定是可以被比较的。

问题：怎么能够约束，才能让T一定是可以比较大小的？
T实现Comparable接口
【方法一：泛型类】

class Alg<T extends Comparable>{public T findMaxValue(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if (max.compareTo(array[i]) < 0) { //max比array[i]大，返回>0，max比array[i]小，返回<0max = array[i];}}return max;}
}public class Test {public static void main(String[] args) {Alg<Integer> alg = new Alg<>();Integer[] integers = {1,2,3,4,5,6,7};Integer ret = alg.findMaxValue(integers);System.out.println(ret); //7
}

【方法二：泛型方法】

class Alg2 {public <T extends Comparable<T>> T findMaxValue(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if (max.compareTo(array[i]) < 0) { //max比array[i]大，返回>0，max比array[i]小，返回<0max = array[i];}}return max;}
}public class Test {public static void main(String[] args) {Alg2 alg2 = new Alg2();Integer[] integers1 = {1,2,3,4,5};//类型推导：根据实参传值，来推导此时的类型Integer ret1 = alg2.findMaxValue(integers1);System.out.println(ret1);  //5}

【方法三：静态泛型方法】

class Alg2 {public static <T extends Comparable<T>> T findMaxValue(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if (max.compareTo(array[i]) < 0) { //max比array[i]大，返回>0，max比array[i]小，返回<0max = array[i];}}return max;}
}public class Test {public static void main(String[] args) {Integer[] integers = {1,2,3,4,5,10};Integer ret = Alg2.<Integer>findMaxValue(integers);System.out.println(ret); //10}