java数据结构（1）：集合框架，时间,空间复杂度，初识泛型

一 java数据结构的集合框架

1.什么是数据结构

2.集合框架

2.1什么是集合框架：

1. 接口 (Interfaces)

2. 实现类 (Implementations)

3. 算法 (Algorithms)

4. 并发集合 (Concurrent Collections)

2.2集合框架的优点：

二时间和空间复杂度

1.算法效率

2.常用集合类的时间复杂度和空间复杂度：

1. List

ArrayList

LinkedList

2. Set

HashSet

LinkedHashSet

TreeSet

3. Map

HashMap

LinkedHashMap

TreeMap

4. Queue

PriorityQueue

LinkedList（作为Queue使用）

5. 并发集合（Concurrent Collections）

ConcurrentHashMap

CopyOnWriteArrayList

3.时间复杂度

3.1大O的渐进表示法

3.2 推导大O阶方法

3.3最好、平均和最坏情况

4.时间复杂度的例题分析

4.1 例一

4.2.例二

4.3例三

4.4例四

4.5例五

5 空间复杂度

三初识泛型

一 java数据结构的集合框架

1.什么是数据结构

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。

2.集合框架

2.1什么是集合框架：

Java 集合框架（Java Collections Framework，JCF）是 Java 标准库中用于处理集合（如列表、集合和映射）的架构。集合框架提供了多种数据结构和算法的实现，使得开发人员能够方便地操作数据集合。以下是 Java 集合框架的一些关键组件：

1. 接口 (Interfaces)

Java 集合框架定义了一组标准接口，以支持不同类型的集合。主要接口包括：

Collection：是最基本的集合接口，所有集合类都实现这个接口。
List：有序集合，允许重复元素。主要实现类有 ArrayList、LinkedList。
Set：不允许重复元素的集合。主要实现类有 HashSet、LinkedHashSet、TreeSet。
Queue：用于表示先进先出（FIFO）队列。主要实现类有 LinkedList、PriorityQueue。
Deque：双端队列，允许在两端进行插入和删除操作。主要实现类有 ArrayDeque、LinkedList。
Map：键值对映射，键不允许重复。主要实现类有 HashMap、LinkedHashMap、TreeMap。

2. 实现类 (Implementations)

Java 集合框架提供了各种集合接口的实现类：

ArrayList：基于数组的列表，实现了 List 接口，支持快速随机访问。
LinkedList：基于链表的列表，实现了 List 和 Deque 接口，适合频繁插入和删除操作。
HashSet：基于哈希表的集合，实现了 Set 接口，不保证顺序。
LinkedHashSet：基于哈希表和链表的集合，实现了 Set 接口，维护插入顺序。
TreeSet：基于红黑树的集合，实现了 NavigableSet 接口，按自然顺序或提供的比较器排序。
HashMap：基于哈希表的映射，实现了 Map 接口，键值对无序。
LinkedHashMap：基于哈希表和链表的映射，实现了 Map 接口，维护插入顺序或访问顺序。
TreeMap：基于红黑树的映射，实现了 NavigableMap 接口，按自然顺序或提供的比较器排序。
PriorityQueue：基于优先级堆的队列，实现了 Queue 接口，元素按自然顺序或提供的比较器排序。

3. 算法 (Algorithms)

集合框架还提供了一组算法（静态方法），主要位于 Collections 类中，如排序、搜索和修改集合的方法：

排序：Collections.sort(list) 用于对列表进行自然排序。
二分查找：Collections.binarySearch(list, key) 用于在排序列表中执行二分查找。
打乱：Collections.shuffle(list) 用于随机打乱列表中的元素。
反转：Collections.reverse(list) 用于反转列表中的元素顺序。
交换：Collections.swap(list, i, j) 用于交换列表中两个位置的元素。
最大最小值：Collections.max(collection) 和 Collections.min(collection) 用于找到集合中的最大和最小值。

4. 并发集合 (Concurrent Collections)

为了支持多线程环境，Java 集合框架还提供了一些线程安全的集合类，位于 java.util.concurrent 包中：

ConcurrentHashMap：线程安全的哈希表，允许高效的并发访问。
CopyOnWriteArrayList：线程安全的列表，适用于读多写少的场景。
CopyOnWriteArraySet：线程安全的集合，基于 CopyOnWriteArrayList 实现。

Java 集合框架通过这些接口、实现类和算法，提供了丰富的数据结构和操作方法，极大地简化了集合数据的处理。

2.2集合框架的优点：

使用成熟的集合框架，有助于我们便捷、快速的写出高效、稳定的代码

二时间和空间复杂度

1.算法效率

算法的好与坏，取决于算法的效率。

2.常用集合类的时间复杂度和空间复杂度：

在Java集合框架中，不同数据结构和算法的效率是关键考虑因素。了解这些效率可以帮助你选择最适合特定应用场景的数据结构。下面列出了一些常用集合类的时间复杂度和空间复杂度：

1. List

ArrayList

访问（get）：O(1)
插入（add）：O(1)（摊销时间复杂度）
删除（remove）：O(n)（平均情况下，需要移动元素）
空间复杂度：O(n)

LinkedList

访问（get）：O(n)
插入（add）：O(1)
删除（remove）：O(1)
空间复杂度：O(n)

2. Set

HashSet

插入（add）：O(1)（在负载因子合理的情况下）
删除（remove）：O(1)
查找（contains）：O(1)
空间复杂度：O(n)

LinkedHashSet

插入（add）：O(1)
删除（remove）：O(1)
查找（contains）：O(1)
空间复杂度：O(n)

TreeSet

插入（add）：O(log n)
删除（remove）：O(log n)
查找（contains）：O(log n)
空间复杂度：O(n)

3. Map

HashMap

插入（put）：O(1)（在负载因子合理的情况下）
删除（remove）：O(1)
查找（get）：O(1)
空间复杂度：O(n)

LinkedHashMap

插入（put）：O(1)
删除（remove）：O(1)
查找（get）：O(1)
空间复杂度：O(n)

TreeMap

插入（put）：O(log n)
删除（remove）：O(log n)
查找（get）：O(log n)
空间复杂度：O(n)

4. Queue

PriorityQueue

插入（add）：O(log n)
删除（remove）：O(log n)
查找（peek）：O(1)
空间复杂度：O(n)

LinkedList（作为Queue使用）

插入（add）：O(1)
删除（remove）：O(1)
查找（peek）：O(1)
空间复杂度：O(n)

5. 并发集合（Concurrent Collections）

ConcurrentHashMap

插入（put）：O(1)
删除（remove）：O(1)
查找（get）：O(1)
空间复杂度：O(n)

CopyOnWriteArrayList

访问（get）：O(1)
插入（add）：O(n)（需要复制整个数组）
删除（remove）：O(n)（需要复制整个数组）
空间复杂度：O(n)

选择合适的数据结构和算法时需要根据具体的使用场景来考虑，尤其是数据量和操作的频率。例如，若需要频繁访问元素，ArrayList 是更好的选择；若需要频繁插入和删除元素，LinkedList 更为适合；若需要快速查找和删除元素，HashSet 或 HashMap 是不错的选择。

了解这些效率能够帮助你在开发过程中做出更明智的决策，从而提高应用程序的性能和效率。

3.时间复杂度

3.1大O的渐进表示法

    void fun(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=0;while ((M--)>0){count++;}System.out.println(count);}

Func 执行的基本操作次数：

3.2 推导大O阶方法

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

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

3.3最好、平均和最坏情况

另外有些算法的时间复杂度存在最好、平均和最坏情况：最坏情况：任意输入规模的最大运行次数(上界) 平均情况：任意输入规模的期望运行次数最好情况：任意输入规模的最小运行次数(下界)

4.时间复杂度的例题分析

4.1 例一

void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}
System.out.println(count);
}

4.2.例二

void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
count++;
}
for (int k = 0; k < N ; k++) {
count++;
}
System.out.println(count);
}

4.3例三

void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
System.out.println(count);
}

4.4例四

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

4.5例五

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;
else
return mid;
}
return -1;
}

空间复杂度：最好：1

最坏：最坏次

5 空间复杂度

空间复杂度（Space Complexity）是计算机科学中用于描述算法在运行过程中所需存储空间的一个指标。它通常表示为输入大小 nnn 的函数，即随着输入数据量的增加，算法所需要的额外内存空间如何变化。

5.1例题

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)

三初识泛型

1. 什么是泛型

在Java中，泛型（Generics）是一个强大的特性，它允许在定义类、接口和方法时使用类型参数。这意味着你可以编写代码时不必指定具体的数据类型，而是使用泛型参数来创建更通用和可重用的代码。

2.泛型的优势

类型安全：在编译时进行类型检查，防止类型转换错误。
代码重用：编写一次代码，可以用于多种不同的数据类型。
可读性和可维护性：代码更清晰，减少类型转换的复杂性。

3.泛型的基本语法

3.1定义泛型类

public class Box<T> {private T item;public void set(T item) {this.item = item;}public T get() {return this.item;}
}

3.2使用泛型类

Box<String> stringBox = new Box<>();
stringBox.set("Hello");
String value = stringBox.get();

3.3.1 定义泛型方法

public class Util {public static <T> void printArray(T[] array) {for (T element : array) {System.out.println(element);}}
}

3.3.2使用泛型方法

Integer[] intArray = {1, 2, 3, 4, 5};
Util.printArray(intArray);String[] stringArray = {"A", "B", "C"};
Util.printArray(stringArray);

3.4.1 定义泛型接口

public interface Container<T> {void add(T item);T get();
}

3.4.2 实现泛型接口：

public class MyContainer<T> implements Container<T> {private T item;@Overridepublic void add(T item) {this.item = item;}@Overridepublic T get() {return item;}
}

希望能对大家有所帮助

谢谢观看 ! ! ! !