接下来博主会持续更新JavaSE、Java数据结构、MySQL、JavaEE、微服务、Redis等等内容的知识点整理。后续我也会精心制作算法解析、项目经验系列内容，内容绝对干货。相信这些文章能够成为我和大家的“葵花宝典”，喜欢的话就关注一下吧！敬请期待！

什么是集合框架？

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

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

类和接口总览：

集合框架的重要性

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

学习背后的数据结构知识，有助于我们理解各个集合的优缺点及使用场景

我们再来回忆一下数据结构的概念：

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

那什么是算法呢？

算法(Algorithm):就是定义良好的计算过程，它取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。算法也可以理解为解决问题的方法、逻辑 。

时间复杂度

时间复杂度的概念

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

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

推导大O阶方法

1. 总执行次数可以分为两种：与参数相关项，可直接计算的常数项。
2. 用常数1取代运行中的所有执行次数的常数项。
3. 在修改后的运行次数函数中，只保留最高阶项。
4. 如果最高阶项存在且不是1，则去除这个项的系数。得到的结果就是大O阶。
5. 一定一定要结合算法逻辑去踏踏实实推算时间复杂度！！！不能一看代码上来就给出所谓的结果。因为算法逻辑会影响到执行过程，那语句执行次数就不是表面上那么简单。

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表 示出了执行次数。

• 在实际中一般情况关注的是算法的最坏运行情况，所以数组中遍历法搜索数据时间复杂度为O(N)

时间复杂度计算举例：

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(n²)

• 总共是n趟，每趟比较的次数从n-1递减到1，每趟减少1次，那么总执行次数就可以转化为一个前n项和的结果，在按规则简化，最终得到O(n^2)

这就需要根据算法逻辑去推算，而不是看见循环就得出O(n)之类的结果。

2.二分查找

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

• 时间复杂度：O(logN)

• 这个问题就更需要结合算法逻辑来推算了，要是又看到循环直接脱口而出结果肯定错。

• 问题的关键在于每次执行查找操作之后，都会砍掉一半的数据，直到最后只剩下一个数据（最坏的情况）就得到了目标数据。这样就是计算所有数据要经历多少次（次数设为x）折半，剩一个数据。也就是N/(2^x)=1，得到x为log₂N，那么时间复杂度就是log₂N（简写为logN）。

空间复杂度

• 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以@@@空间复杂度算的是变量的个数及创建的方法栈帧个数，也包括二者嵌套情况。
• 空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

要注意：空间复杂度主要衡量的是算法在运行过程中除了初始数据外，额外开辟的临时存储空间。

什么不算“额外空间”？

• 输入数据本身所占用的空间：比如，你要排序的原始数组所占据的内存，是不计入空间复杂度的。我们所关注的是算法“工作”时产生的额外开销。另外，也包括程序代码本身占用的空间

那“额外空间”又主要包括什么？

• 显式声明的变量和数据结构：比如在循环中定义的索引变量 i ，或者为了完成算法中的计算而显式创建的临时数组、对象，还有递归所创建的栈帧空间等。

觉得文章对你有帮助的话就点个赞，收藏起来这份免费的资料吧！也欢迎大家在评论区讨论技术、经验