说到 SpringBoot 自动装配的原理，可能有的人就要开始 @EnableAutoConfiguration 的长篇大论了，感觉在背源码一样，那么 `自动装配` 的含义你是真的了解吗？它是如何与 Spring 相结合的，又是如何被 Spring 管理的？接下来我将告诉你 `自动装配` 原理的真正打开方式。



# 自动装配的本质

自动装配的本质其实就是将 `starter` 快速依赖包中的 Bean 信息，自动的整合到 Spring IOC 容器中被 Spring 所管理，掌握此本质，就可自由实现自定义的 `starter` 的各种工具包，学习本文以前，需要掌握 Spring 容器中的 Bean 生命周期流程。

# 代码上的核心实现

其实现的方式就是通过 `@SpringApplication` 复合注解中的 `@EnableAutoConfiguration` 注解的 `AutoConfigurationImportSelector` 类中调用 `SpringFactoriesLoader #loadFactoryNames` 方法，加载 `META-INF/spring.factories` 文件实现的

大体了解流程以后，开始分析源码，流程掌握比较简单，但是如何**从 SpringBoot 启动后基于 Spring 扩展进行的自动装配的实现才是最核心重点**。

## 从源码上看实现

查看 `@SpringBootApplication` 源码，可以看到存在一个 `@EnableAutoConfiguration` 注解，此注解即为 SpringBoot 内部注解，为 Spring 上下文提供自动配置的

![image.png](/static/img/f3958c42bcf3202a0644b4c5148e6be8.image.webp)


接着看 `@EnableAutoConfiguration` 注解的实现，内部使用了 `@Import` 注解（Spring 的核心注解，其用于导入一个或多个 Bean 信息），导入了 `AutoConfigurationImportSelector` Bean 信息

![image.png](/static/img/f5171b10991b43bc7f0a6ff2880782f6.image.webp)


此时 `AutoConfigurationImportSelector` 实例已被注册成 Bean，被 Spring 容器所管理，此实例的接口实现了 `DeferredImportSelector` 接口， 查看下源码的实现

![image.png](/static/img/ed03aa97156c5c4b6b91490f86d02674.image.webp)


齿轮开始转动，自动装配的实现也是从此刻开始，一直常说 SpringBoot 启动时会加载 `META-INF/spring.factories` 文件，并且将文件中的实现类加载到 Spring 容器中，那么到的是如何加载的呢？源码看到这，接下来要如何查找呢？

很简单粗暴的方法，一个查找当前源码的类，一个从源码中全局搜索，去查找到 `spring.factories` 文件在哪被定义过，看是否被当前类引用过，就找到了当前的接口调用

![image.png](/static/img/ccd68795061d1c9455499d0bdf062eaf.image.webp)


查看 `SpringFactoriesLoader #loadFactoryNames` 方法，可以看到其内部加载 `META-INF/spring.factories` 文件

![image.png](/static/img/d6037180f4ebc11d863b4d376c2f4133.image.webp)

源码看到这基本就差不多了，在看一眼 `META-INF/spring.factories` 文件内容

![image.png](/static/img/cbdc314d49f29ec9dddfecedf6716dca.image.webp)


## 结合 Spring 的扩展看实现（核心）

看完上面的流程，你以为就这样结束了么，感觉一切这么理所当然，转动脑筋思考下，SpringBoot 启动的时候，是如何来执行到上述的流程呢？接下来我们继续断点分析


### 阅读源码

通过对调用 `SpringFactoriesLoader #loadFactoryNames` 的方法进行断点，发现一切奥秘尽在堆栈之中，有没有看到那个特殊眼熟的 `refresh` 方法，这个是 Spring 容器刷新的入口，不了解的小伙伴可以去看下文章：[Spring 源码分析之 Bean 的全生命周期](https://blog.liushigong.cn/post/11)

![image.png](/static/img/4a10fb63a20b99aa6bc547cfa29e1287.image.webp)


开始看上层堆栈方法的源码，首先将 `META-INF/spring.factories` 文件读取的的内容构建成 `AutoConfigurationEntry` 对象

![image.png](https://blog.liushigong.cn/static/img/577c12eab83775dc506d6e0e0e3dc789.image.webp)


将构建的 `AutoConfigurationEntry` 对象，存储到本地缓存的 `this.autoConfigurationEntries` 集合中

![image.png](/static/img/b95cd347a33a2b16c4f4204b3dfba52b.image.webp)


接着找上层的调用，又打开了新世界的大门，调用到了 `ConfigurationClassParser` 类，此类主要是对配置类的解析，以下是从掘金社区提供的图片

![image.png](/static/img/6b64f9d25517f61d2e787474745f8efb.image.webp)

![image.png](/static/img/084242a2bb010d87267aef20852c4732.image.webp)

了解了 `ConfigurationClassParser` 类的作用，发现其内部调用了 `processImports` 方法，此方法就是解析的核心方法，递归加载，有兴趣可以自行阅读源码

![image.png](/static/img/880d4beb88000db7cabd17db870b345c.image.webp)

可以看出此处进行的for循环，包含我们的核心类  `AutoConfigurationImportSelector` ，那么，其中 `this.groupings.values()` 数据从哪里来呢

![image.png](/static/img/5df88f2f6fe971224cbde4b8594e3c5f.image.webp)

找到上层方法，发现有一个 `register` 方法，内部果然是构建了 `this.groupings.values()` 数据

![image.png](/static/img/2f550935b8b213fd98e03bc094eec833.image.webp)

![image.png](/static/img/dc946c2df6b7cfcdd5579d9fc224bf68.image.webp)


看到此处，发现解析的核心逻辑实现，有兴趣可以自行阅读源码，这里就不再赘述了

![image.png](/static/img/fbcf9aba27beea28f38ff0409e1aeba3.image.webp)

继续查找进入到了 `ConfigurationClassPostProcessor` 类中，见名知意，此类为配置类后置处理的作用，扩展实现了 `BeanDefinitionRegistryPostProcessor` 接口，被调用了 `#postProcessBeanDefinitionRegistry` 方法

![image.png](/static/img/1f13d62a89d90005d24412d202badb6c.image.webp)

![image.png](/static/img/987459505f7ac006524e1ac8f9c4106a.image.webp)


接着往上层查找，走到了 `invokeBeanDefinitionRegistryPostProcessors` 方法，此处是调用 BeanDefinition 注册的后置处理的所有扩展接口，在联想到上述的 `ConfigurationClassPostProcessor` 类实现了其接口，可以理解是在此处将所有的配置类信息以及 `starter` 中的信息加载到了 Spring 容器中

![image.png](/static/img/0efcc4fa7b92f25ebfaad12f853e4fc2.image.webp)

![image.png](/static/img/c571bfd3af83dfb9204ec537abcfe258.image.webp)


找到这，终于看到非常眼熟的 `refresh` 方法，原来这一切都是在 Spring 容器刷新的时候，创建完 BeanFactory 以后，在调用 `invokeBeanFactoryPostProcessors` 方法，进行后置处理中操作的

![image.png](/static/img/ac4cb18857956b6185089a66306a67d3.image.webp)


### 总结

通过上面的源码追溯，我们总结一下 `自动装配` 的扩展流程实现

对于 `starter` 的中加载到的Bean信息，是通过 Spring 提供的 `DeferredImportSelector` 接口进行扩展的，通过 `BeanFactoryPostProcessor #postProcessBeanFactory` 后置处理中调用 `BeanDefinitionRegistryPostProcessor` 后置处理进行实现的

:::tip{title="思考一下"}
根据上面的源码思路，如何实现动态Bean加载呢？ 如何基于Nacos配置中心来实现动态线程池的管理呢？
:::


## SpringBoot 2.7 版本以后得实现

在 `AutoConfigurationImportSelector #getCandidateConfigurations` 方法，由调用的 `SpringFactoriesLoader #loadFactoryNames` 方法变成了 `ImportCandidates #load` 方法，查找的文件也从 `META-INF/spring.factories` 改为了 `META-INF/spring/org.springframework.boot.autoconfigure.AutoConfiguration.imports`

![image.png](/static/img/8961d29b9f830c53a042b78eb2de58b3.image.webp)

其中文件的内容也进行了调整

```yaml
# 变更前 META-INF/spring.factories

org.springframework.boot.autoconfigure.EnableAutoConfiguration=\
  cn.liushigong.cache.redis.RedisCacheAutoConfig

# 变更后 META-INF/spring/org.springframework.boot.autoconfigure.AutoConfiguration.imports

cn.liushigong.cache.redis.RedisCacheAutoConfig

```

# 结尾

我们所了解的 SpringBoot 不是一个全新的框架，而是对 Spring 的一种扩展，回答 `自动装配` 这个问题，除了 @SpringApplication 这千篇一律的逻辑以外，我们还需要能结合 Spring 源码进行有条理的分析出来，才能更好的体现自己的深度。

SpringBoot - 自动装配原理的满分解读

日常开发中使用Map时经常会遇到很多复杂的处理场景，例如：多个键的Map、不仅可以根据键获取值也可以根据值获取键且不用遍历、重复键的Map、数字等范围内映射相同的值、内存中缓存对象等，Guava提供了以上场景的解决方案。





## 实现

根据不同的场景，使用不用的解决方案


|场景	|解决方案	|具体实现|
| --- | --- |--- |
|多个键的Map	|Table	|HashBasedTable、TreeBasedTable、ImmutableTable|
|不仅可以根据键获取值也可以根据值获取键且不用遍历	|BiMap	|HashBiMap、ImmutableBiMap|
|重复键的Map	|Multimap	|ArrayListMultimap、LinkedListMultimap、LinkedHashMultimap、ImmutableListMultimap、ImmutableSetMultimap|
|数字等范围内映射相同的值	|RangeMap	|TreeRangeMap、ImmutableRangeMap|
|内存中缓存对象	|ClassToInstanceMap	|MutableClassToInstanceMap、ImmutableClassToInstanceMap|


## 依赖
截止到今年最新的依赖包版本是 `33.4.6-jre`，很多人不知道如何找maven依赖，提供个[官方仓库地址](https://mvnrepository.com/) `https://mvnrepository.com/`

```xml

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>33.4.6-jre</version>
</dependency>
```

## 示例

以下为具体使用的 Demo

### Table

官方注释翻译：将一对有序键（称为行键和列键）与单个值相关联的集合。


```java
// HashMap
Map<String, Integer> deptMap = new HashMap<>();
deptMap.put("A部门", 10);
deptMap.put("B部门", 20);
Map<String, Map<String, Integer>> companyMap = new HashMap<>();
companyMap.put("xx公司", deptMap);
// HashMap 获取值
Integer val = companyMap.get("xx公司").get("A部门");
System.out.println("HashMap 获取值: " + val);

// 创建Hash类型Table, 基于Hash表实现
// Table<R, C, V>中三个泛型: R-行, C-列, V-值
Table<String, String, Integer> hashTable = HashBasedTable.create();
hashTable.put("xx公司", "A部门", 10);
hashTable.put("xx公司", "B部门", 20);
hashTable.put("xx公司", "C部门", 30);

System.out.println("\nHash Table: " + hashTable);

// 创建Tree类型Table, 基于红黑树实现
Table<String, String, Integer> treeTable = TreeBasedTable.create();
treeTable.put("xx公司", "C部门", 30);
treeTable.put("xx公司", "B部门", 20);
treeTable.put("xx公司", "A部门", 10);

System.out.println("\nTree Table: " + treeTable);

// 创建不可变Table, 无法新增、更新或删除
Table<String, String, Integer> immutableTable = ImmutableTable.<String, String, Integer>builder()
        .put("xx公司", "C部门", 30)
        .put("xx公司", "B部门", 20)
        .put("xx公司", "A部门", 10)
        .build();

System.out.println("\nImmutable Table: " + immutableTable);

// Table 获取值
Integer val2 = hashTable.get("xx公司", "A部门");
System.out.println("\nTable 获取值: " + val2);

// Table 删除值
Integer remove = hashTable.remove("xx公司", "C部门");
System.out.println("\nTable 删除值: " + remove);

// 根据行获取列和值映射
Map<String, Integer> columnvalueMap = hashTable.row("xx公司");
System.out.println("\nTable 列和值 映射: " + columnvalueMap);

// 根据列获取行和值映射
Map<String, Integer> rowvalueMap = hashTable.column("A部门");
System.out.println("\nTable 行和值 映射: " + rowvalueMap);

// 获取key集合
Set<String> rowKeySet = hashTable.rowKeySet();
System.out.println("\nTable Row key 集合: " + rowKeySet);
Set<String> columnKeySet = hashTable.columnKeySet();
System.out.println("\nTable Column key 集合: " + columnKeySet);

// 获取值集合
Collection<Integer> values = hashTable.values();
System.out.println("\nTable 值集合: " + values);

// 判断包含行
boolean containsRow = hashTable.containsRow("xx公司");
System.out.println("\nTable 包含行: " + containsRow);

// 判断包含列
boolean containsColumn = hashTable.containsColumn("A部门");
System.out.println("\nTable 包含列: " + containsColumn);

// 判断包含行和列
boolean contains = hashTable.contains("xx公司", "A部门");
System.out.println("\nTable 包含行和列: " + contains);

// 判断包含值
boolean containsValue = hashTable.containsValue(10);
System.out.println("\nTable 包含值: " + containsValue);

// 行和列转置 - 行 转 列
Table<String, String, Integer> transposeTable = Tables.transpose(hashTable);

// 获取所有的行
Set<Table.Cell<String, String, Integer>> cells = transposeTable.cellSet();

// 遍历输出
System.out.println("\n遍历输出开始----------------------------");
cells.forEach(cell -> System.out.println(cell.getRowKey() + ", " + cell.getColumnKey() + ", " + cell.getValue()));
System.out.println("\n遍历输出结束----------------------------");

// 转换为嵌套的Map
Map<String, Map<String, Integer>> rowMap = hashTable.rowMap();
System.out.println("\nTable RowMap: " + rowMap);
Map<String, Map<String, Integer>> columnMap = hashTable.columnMap();
System.out.println("\nTable ColumnMap: " + columnMap);
```

输出结果

![image.png](/static/img/8f932973adc45ebbb7b86e276c915055.image.webp)


### BiMap

双映射（或“双向映射”）是一种保留其值及其键的唯一性的映射。此约束使双映射能够支持“反向视图”，即另一个双映射，其中包含与此双映射相同的条目，但具有相反的键和值。

```java
//创建BiMap, 底层为两个Hash表的Map
BiMap<Integer, String> biMap = HashBiMap.create();
biMap.put(1, "one");
biMap.put(2, "two");
biMap.put(3, "three");
biMap.put(4, "four");
biMap.put(5, "five");

System.out.println("BiMap: " + biMap);

//创建不可变BiMap, 无法新增、更新或删除
BiMap<Object, Object> immutableBiMap = ImmutableBiMap.builder().put(1, "one").put(2, "two").put(3, "three").put(4, "four").put(5, "five").build();

System.out.println("\nImmutable BiMap: " + immutableBiMap);

//通过key获取value
String value = biMap.get(1);
System.out.println("\nBiMap 根据key获取value: " + value);

Integer key = biMap.inverse().get("one");
System.out.println("\nBiMap 根据value获取key: " + key);

//翻转后修改
biMap.inverse().put("six", 6);
//返回双映射的逆视图, 并没有创建新对象, 还是之前的对象, 所以操作翻转后的BiMap会影响之前的BiMap
System.out.println("\nBiMap 被影响: " + biMap);

//底层是HashMap, key不可重复
//value不可重复
try {
    biMap.put(11, "one");
} catch (Exception e) {
    System.err.println("BiMap 替换value异常: " + e.getMessage());
}

//翻转后key不能重复
try {
    biMap.inverse().put("first", 1);
} catch (Exception e) {
    System.err.println("BiMap 替换key异常: " + e.getMessage());
}

//key和value可为null
biMap.put(null, null);
System.out.println("\nBiMap 根据Null key获取Null value: " + biMap.get(null));
System.out.println("\nBiMap 根据Null value获取Null key: " + biMap.inverse().get(null));

//强制替换key
biMap.forcePut(11, "one");
System.out.println("\nBiMap 获取新key: " + biMap.inverse().get("one"));

//values为Set集合
Set<String> values = biMap.values();
System.out.println("\nBiMap 不重复的value: " + values);
```

输出结果

![image.png](/static/img/4085eecb9e7275d6d4e20e57b7ed4781.image.webp)

### Multimap

将键映射到值的集合，类似于 Map，但其中每个键可能与多个值相关联。

```java
// 创建Multimap, key为HashMap, value为ArrayList
Multimap<String, Integer> arrayListMultimap = ArrayListMultimap.create();
arrayListMultimap.put("张三", 90);
arrayListMultimap.put("张三", 80);
arrayListMultimap.put("张三", 100);
arrayListMultimap.put("李四", 88);

System.out.println("Multimap key为HashMap, value为ArrayList: " + arrayListMultimap);

// 创建Multimap, key为HashMap, value为HashSet
Multimap<String, Integer> hashMultimap = HashMultimap.create();
hashMultimap.put("张三", 90);
hashMultimap.put("张三", 80);
hashMultimap.put("张三", 100);
hashMultimap.put("李四", 88);

System.out.println("Multimap key为HashMap, value为HashSet: " + hashMultimap);

// 创建Multimap, key为LinkedHashMap, value为LinkedList
Multimap<String, Integer> linkedListMultimap = LinkedListMultimap.create();
linkedListMultimap.put("张三", 90);
linkedListMultimap.put("张三", 80);
linkedListMultimap.put("张三", 100);
linkedListMultimap.put("李四", 88);

System.out.println("Multimap key为LinkedHashMap, value为LinkedList: " + linkedListMultimap);

// 创建Multimap, key为LinkedHashMap, value为LinkedHashMap
Multimap<String, Integer> linkedHashMultimap = LinkedHashMultimap.create();
linkedHashMultimap.put("张三", 90);
linkedHashMultimap.put("张三", 80);
linkedHashMultimap.put("张三", 100);
linkedHashMultimap.put("李四", 88);

System.out.println("Multimap key为LinkedHashMap, value为LinkedHashMap: " + linkedHashMultimap);

// 创建Multimap, key为TreeMap, value为TreeSet
Multimap<String, Integer> treeMultimap = TreeMultimap.create();
treeMultimap.put("张三", 90);
treeMultimap.put("张三", 80);
treeMultimap.put("张三", 100);
treeMultimap.put("李四", 88);

System.out.println("Multimap key为TreeMap, value为TreeSet: " + treeMultimap);

// 创建不可变Multimap, 无法新增、更新或删除, key为ImmutableMap, value为ImmutableList
Multimap<String, Integer> immutableListMultimap = ImmutableListMultimap.<String, Integer>builder()
        .put("张三", 90)
        .put("张三", 80)
        .put("张三", 100)
        .put("李四", 88)
        .build();

System.out.println("Multimap key为ImmutableMap, value为ImmutableList: " + immutableListMultimap);

// 创建不可变Multimap, 无法新增、更新或删除, key为ImmutableMap, value为ImmutableSet
Multimap<String, Integer> immutableSetMultimap = ImmutableSetMultimap.<String, Integer>builder()
        .put("张三", 90)
        .put("张三", 80)
        .put("张三", 100)
        .put("李四", 88)
        .build();

System.out.println("Multimap key为ImmutableMap, value为ImmutableSet: " + immutableSetMultimap);

// 获取值
Collection<Integer> values = arrayListMultimap.get("张三");
System.out.println("Multimap 获取值集合: " + values);

// 获取不存在key的值, 返回的是空集合, 而不是null
Collection<Integer> valuesByNotExistsKey = arrayListMultimap.get("王五");
System.out.println("Multimap 获取不存在的Key值集合: " + valuesByNotExistsKey);

// 获取值集合添加值
// 返回的是多重映射中关联的值的视图集合, 并没有创建新对象, 还是之前的对象, 所以操作值集合会影响之前的Multimap
values.add(60);
System.out.println("Multimap 被影响: " + arrayListMultimap);

// 获取大小
System.out.println("Multimap 大小:" + arrayListMultimap.size());

// 判断是否为空
System.out.println("Multimap 是否为空: " + arrayListMultimap.isEmpty());

// 包含key
System.out.println("Multimap 包含key: " + arrayListMultimap.containsKey("张三"));

// 包含value
System.out.println("Multimap 包含value: " + arrayListMultimap.containsValue(60));

// 包含key-value键值对
System.out.println("Multimap 包含key-value对: " + arrayListMultimap.containsEntry("张三", 60));

// 替换value
arrayListMultimap.replaceValues("张三", Arrays.asList(10, 20, 30));
System.out.println("Multimap 替换value: " + arrayListMultimap);

// 根据key-value删除
arrayListMultimap.remove("张三", 10);
System.out.println("Multimap 根据key-value删除: " + arrayListMultimap);

// 根据key删除
Collection<Integer> removeAll = arrayListMultimap.removeAll("张三");
System.out.println("Multimap 根据key删除: " + removeAll);

// 获取key集合
Set<String> keySet = arrayListMultimap.keySet();
System.out.println("Multimap 获取key集合(HashSet): " + keySet);
Multiset<String> keys = arrayListMultimap.keys();
System.out.println("Multimap 获取key集合(MultiSet): " + keys);

// 获取所有的key-value
Collection<Map.Entry<String, Integer>> entries = arrayListMultimap.entries();
System.out.println("遍历key-value开始--------------------------");
entries.forEach(entry -> System.out.println(entry.getKey() + " : " + entry.getValue()));
System.out.println("遍历key-value结束--------------------------");

// 转换为Map<K, Collection<V>>
Map<String, Collection<Integer>> collectionMap = arrayListMultimap.asMap();
System.out.println("Multimap 转换为Map<K, Collection<V>>: " + collectionMap);
```

输出结果

![image.png](/static/img/510345cdc98e33d2aa226e2ed404b541.image.webp)


### RangeMap

从不相交的非空范围到非 null 值的映射。查询查找与包含指定键的范围（如果有）关联的值。

```java
// if-else
int score = 88;
String rank;
if (0 <= score && score < 60) {
    rank = "不及格";
} else if (60 <= score && score <= 84) {
    rank = "及格";
} else if (84 < score && score <= 100) {
    rank = "优秀";
} else {
    rank = "无效";
}

System.out.println("if-else 获取值: " + rank);

// 创建RangeMap, 基于TreeMap（红黑树）实现
RangeMap<Integer, String> treeRangeMap = TreeRangeMap.create();
treeRangeMap.put(Range.closedOpen(0, 60), "不及格");
treeRangeMap.put(Range.closed(60, 84), "及格");
treeRangeMap.put(Range.openClosed(84, 100), "优秀");
treeRangeMap.put(Range.lessThan(0), "无效");
treeRangeMap.put(Range.greaterThan(100), "无效");

rank = treeRangeMap.get(score);
System.out.println("RangeMap 获取值: " + rank);

// 创建不可变RangeMap, 无法新增、更新或删除
ImmutableRangeMap<Integer, String> immutableRangeMap = ImmutableRangeMap.<Integer, String>builder()
        .put(Range.closedOpen(0, 60), "不及格")
        .put(Range.closed(60, 84), "及格")
        .put(Range.openClosed(84, 100), "优秀")
        .put(Range.lessThan(0), "无效")
        .put(Range.greaterThan(100), "无效")
        .build();

rank = immutableRangeMap.get(score);
System.out.println("ImmutableRangeMap 获取值: " + rank);

// 获取key-value对
Map.Entry<Range<Integer>, String> entry = treeRangeMap.getEntry(88);
System.out.println("RangeMap 获取key-value对: " + entry.getKey() + " : " + entry.getValue());

// 返回不可变的升序的Map
Map<Range<Integer>, String> asMapOfRanges = treeRangeMap.asMapOfRanges();
System.out.println("RangeMap 不可变的升序的Map: " + asMapOfRanges);

// 返回不可变的降序的Map
Map<Range<Integer>, String> asDescendingMapOfRanges = treeRangeMap.asDescendingMapOfRanges();
System.out.println("RangeMap 不可变的降序的Map: " + asDescendingMapOfRanges);

// 相连范围合并
RangeMap<Integer, String> treeRangeMap2 = TreeRangeMap.create();
treeRangeMap2.putCoalescing(Range.closedOpen(0, 60), "不及格");
treeRangeMap2.putCoalescing(Range.closed(60, 84), "及格");
treeRangeMap2.putCoalescing(Range.openClosed(84, 100), "及格"); // 或者 [60..84]范围合并
treeRangeMap2.putCoalescing(Range.lessThan(0), "无效");
treeRangeMap2.putCoalescing(Range.greaterThan(100), "无效");
System.out.println("RangeMap 不合并相连范围: " + treeRangeMap.asMapOfRanges());
System.out.println("RangeMap 合并相连范围: " + treeRangeMap2.asMapOfRanges());

// 最小范围
Range<Integer> span = treeRangeMap.span();
System.out.println("RangeMap 最小范围: " + span);

// 子范围Map
RangeMap<Integer, String> subRangeMap = treeRangeMap.subRangeMap(Range.closed(70, 90));
System.out.println("RangeMap 子范围Map: " + subRangeMap);

// 合并范围
treeRangeMap.merge(Range.closed(60, 100), "及格", (s, s2) -> s2);
System.out.println("RangeMap 合并Map: " + treeRangeMap);

// 移除范围
treeRangeMap.remove(Range.open(90, 95));
System.out.println("RangeMap 移除范围: " + treeRangeMap);

// 清除所有范围
treeRangeMap.clear();
System.out.println("RangeMap 清除所有范围: " + treeRangeMap);
```

输出结果

![image.png](/static/img/c71f907f9c6ad4edd542dffdfd1c3800.image.webp)


### ClassToInstanceMap

映射，其每个条目将一个 Java 原始类型 映射到该类型的实例。除了实现 Map之外，还提供额外的类型安全操作 putInstance 和 getInstance 。与任何其他 Map<Class, Object>映射一样，此映射可能包含基元类型的条目，并且基元类型及其相应的包装器类型可以映射到不同的值。

```java
static class UserBean {
    private final Integer id;
    private final String username;

    public UserBean(Integer id, String username) {
        this.id = id;
        this.username = username;
    }

    @Override
    public String toString() {
        return "UserBean{" + "id=" + id + ", username='" + username + '\'' + '}';
    }
}
public static void main(String[] args) {
    // 创建Bean
    UserBean userBean = new UserBean(1, "张三");

    // HashMap
    HashMap<Class, Object> hashMap = new HashMap<>();
    hashMap.put(UserBean.class, userBean);

    // 获取值，需要强转
    UserBean value = (UserBean) hashMap.get(UserBean.class);
    System.out.println("HashMap 获取对象实例: " + value);
    System.out.println("HashMap 获取对象实例等于创建的Bean: " + (value == userBean));

    // 创建ClassToInstanceMap
    ClassToInstanceMap<Object> classToInstanceMap = MutableClassToInstanceMap.create();
    classToInstanceMap.putInstance(UserBean.class, userBean);

    // 获取值，无需强转
    UserBean value2 = classToInstanceMap.getInstance(UserBean.class);
    System.out.println("\nClassToInstanceMap 获取对象实例: " + value2);
    System.out.println("ClassToInstanceMap 获取对象实例等于创建的Bean: " + (value2 == userBean));

    // 创建不可变ClassToInstanceMap, 无法新增、更新或删除
    ClassToInstanceMap<UserBean> immutableClassToInstanceMap = ImmutableClassToInstanceMap.<UserBean>builder()
        .put(UserBean.class, userBean)
        .build();

    // 获取值，无需强转
    UserBean value3 = immutableClassToInstanceMap.getInstance(UserBean.class);
    System.out.println("\nImmutableClassToInstanceMap 获取对象实例: " + value3);
    System.out.println("ImmutableClassToInstanceMap 获取对象实例等于创建的Bean: " + (value3 == userBean));


    // 限制类型，避免使用HashMap存储对象时，因为使用Object值类型而在添加缓存时需要今天类型校验
    ClassToInstanceMap<Collection> classToInstanceMap1 = MutableClassToInstanceMap.create();
    classToInstanceMap1.put(ArrayList.class, new ArrayList());
    classToInstanceMap1.put(HashSet.class, new HashSet());
    // 编译保存: 'put(java.lang.Class<? extends java.util.@org.checkerframework.checker.nullness.qual.NonNull Collection>, java.util.Collection)' in 'com.google.common.collect.MutableClassToInstanceMap' cannot be applied to '(java.lang.Class<java.util.HashMap>, java.util.HashMap)'
    //        classToInstanceMap1.put(HashMap.class, new HashMap());
}
```

输出结果

![image.png](/static/img/196274a8601760add8f03875a4b66478.image.webp)

Guava - Map增强工具类

算法-经典排序算法

# 经典算法思想

## 分治法（Divide and Conquer）

分治法(Divide and Conquer，也称为“分而治之法”)是一种很重要的算法，我们可以应用分治法来逐一拆解复杂的问题，核心思想就是将一个难以直接解决的大问题依照相同的概念分割成两个或更多的子问题，以便名个击破。

![image.png](/static/img/4fb979feaafa2aace274a299c4616224.image.webp)

其实任何一个可以用程序求解的问题所需的计算时间都与其规模与复杂度有关，问题的规模越小，越容易直接求解，因此可以不断分解问题，使子问题规模不断缩小,让这些子问题简单到可以直接解决，再将各子问题的解合并，最后得到原问题的解答。


### 特点与应用

- 子问题相互独立
- 递归实现
- 归并排序：将数组拆分为两半，递归排序后合并有序子数组。
- 快速排序：通过基准值分割数组，递归处理左右分区


### 代码实现（归并排序）

```java
public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);      // 分解左半部分
            mergeSort(arr, mid + 1, right); // 分解右半部分
            merge(arr, left, mid, right);   // 合并有序子数组
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // 输出[2, 3, 4, 5, 8]
    }
}
```

**代码解读：**

分解：递归将数组分为左右两半

合并：将两个有序子数组合并为一个有序数组


## 递归法（Recursion）

递归是一种很特殊的算法，分治法和递归法很像一对孪生兄弟，都是将一个复杂的算法问题进行分解，让规模越来越小，最终使子问题容易求解。只不过递归法通过函数调用自身解决问题，需定义基线条件和递归条件。


![image.png](https://blog.liushigong.cn/static/img/4a68bcefd142ee2600c0599c942798f5.image.webp)


### 特点与应用

- 代码简洁
- 经典应用：树遍历、汉诺塔

### 汉诺塔问题

> 给定三根柱子，记为 A,B,C，其中 A 柱子上有 n 个盘子，从上到下编号为 0 到 n−1 ，且上面的盘子一定比下面的盘子小。问：将 A 柱上的盘子经由 B 柱移动到 C 柱最少需要多少次？打印出每个步骤
> 
> 移动时应注意：
> - 一次只能移动一个盘子
> - 大的盘子不能压在小盘子上


**思路**

先从简单的三个盘子试试，可以先不看答案自己画一画，挺好玩的，注意规则噢

![image.png](/static/img/6ec28eba4b4fb3b7ad9b0b6af3a29077.image.webp)

n个盘子从A柱到C柱最少移动次数

![image.png](/static/img/ba88aa37d5b721c8ae115a3b5b303891.image.webp)

**代码实现**

```java
public class HanoiTower {
    public static void move(int n, char from, char to, char aux) {
        if (n == 1) {
            System.out.println("移动盘子1从" + from + "到" + to);
            return;
        }
        move(n - 1, from, aux, to);
        System.out.println("移动盘子" + n + "从" + from + "到" + to);
        move(n - 1, aux, to, from);
    }

    public static void main(String[] args) {
        move(3, 'A', 'C', 'B'); // 3层汉诺塔解法
    }
}
```

**代码解读**

将n个盘子分解为移动n-1个盘子的子问题

时间复杂度：O(2ⁿ)


## 动态规划（Dynamic Programming, DP）

通过记录子问题的解避免重复计算，适用于有重叠子问题和最优子结构的问题。

动态规划法(Dynamic Programming Algorithm，DPA)类似于分治法，核心思想是如果一个问题的答案与子问题相关，就将大问题拆解成各个小问题，与分治法最大的不同是可以让每一个子问题的答案被存储起来，以供下次求解时直接取用。这样的做法不但可以减少再次计算的时间，而且可以将这些解组合成大问题的解，故而使用动态规划可以解决重复计算的问题。

动态规划法是分治法的延伸。当用递归法分割出来的问题“一而再，再而三”出现时，就可以运用记忆(Memorization)法来存储这些问题。与分治法不同的地方在于，动态规划法增加了记忆机制的使用，将处理过的子问题的答案记录下来，避免重复计算。


### 特点与应用

- 自底向上或自顶向下（记忆化搜索）
- 时间复杂度优化显著
- 最短路径问题（Floyd-Warshall算法）
- 斐波那契数列
- 背包问题
- 最长公共子序列
- 最长公共子串
- 矩阵最大值（和以及积）


### 斐波那契数列

斐波那契数列是指这样一个数列：0，1，1，2，3，5，8，13，21，34，55，89……这个数列从第3项开始 ，每一项都等于前两项之和。


![image.png](/static/img/ecba5aa12fb2385f5676c8f4e29c3f5c.image.webp)

对于斐波那契数列采用的是动态规划法，那么已计算过的数据就不必重复计算了，也不会再往下递归，这样可以提高性能。

![image.png](https://blog.liushigong.cn/static/img/e22182c57ec9087706bce5e8db376cc2.image.webp)

**代码实现**

```java
public class Fibonacci {
    // 动态规划实现
    public static int fibDP(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fibDP(10)); // 输出55
    }
}
```

**代码解读：**

使用数组 dp 存储中间结果

递推公式：dp[i] = dp[i-1] + dp[i-2]


## 枚举法（Brute Force）

枚举法(又称为穷举法)，是我们在日常工作中使用最多的一种算法，核心思想是列举所有的可能。根据问题的要求，逐一列举问题的解答，或者为了便于解决问题把问题分为不重复、不遗漏的有限种情况，逐一列举各种情况，并加以解决，最终达到解决整个问题的目的。像枚举法这种分析问题、解决问题的方法，得到的结果总是正确的，缺点是速度太慢。


### 特点与应用

- 实现简单
- 时间复杂度：O(n)
- 适合小规模的问题
- 密码破解：尝试所有可能的字符组合


### 代码实现

使用穷举法来实现以下题目

> 今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？

```java
public class Permutations {
    public static void enumeratingAlgorithm() {
        int head = 35, foot = 94;
        int j;
        for (int i = 0; i <= 35; i++) {
            // i代表鸡的数量        
            j = head - i;
            // j代表兔子的数量
            if (i * 2 + j * 4 == foot) {
                System.out.printf("鸡的个数为[ %d ]只,兔子的个数为[ %d ]只。", i, j);
                return;
            }
        }
        System.out.println("此题无解！你家鸡和兔子有三只脚的吧？");
    }
}
```

**代码解读：**

通过题目可以知道，鸡和兔的总数量为0-35只(每个动物都是一个脑袋，这就不用说了吧)，我们可以假设鸡为0，兔子为35，用鸡的个数*2+兔子的个数*4就可以得到总的脚的数量，如果等于94，那么便是答案，如果不等，则鸡的数量+1，兔子数量-1，依次类推，穷举所有情况直到得到答案


## 回溯法（Backtracking）

回溯法(Backtracking)也是枚举法的一种，对于某些问题而言，回溯法是一种可以找出所有(或一部分)解的一般性算法，同时避免枚举不正确的数值。一旦发现不正确的数值，就不再递归到下一层，而是回溯到上一层，以节省时间，是一种走不通就退回再走的方式。它的特点主要是在搜索过程中寻找问题的解，当发现不满足求解条件时就回湖(返回)，尝试别的路径，避免无效搜

![image.png](/static/img/b5b06d0bb66eb9de8e87da9303a75d7e.image.webp)

### 特点

- 递归实现
- 时间复杂度高（指数级）
- 数独求解
- 组合数生成
- A*寻路算法（了解）
- 地图着色算法
- N 皇后问题
- 最优加工顺序
- 旅行商问题

回溯法可以应用于以下类型的问题：

- 排列和组合问题：例如求解全排列、子集合等问题，回溯法可以系统地生成所有可能的组合并逐一验证。
- 决策问题：如八皇后问题、数独填充、图的着色问题等，这些问题需要在多个选择中找到符合特定约束的解。
- 优化问题：如旅行商问题（TSP）和其他需要找到最优解的问题，回溯法可以遍历所有可能的解，找到成本最低或收益最高的解。
- 分割问题：例如分割等和子集、装箱问题等，需要将集合分割成满足特定条件的多个子集。


### N皇后问题

八皇后问题，是一个古老而著名的问题.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法?


![image.png](https://blog.liushigong.cn/static/img/1ecce3e32c9cedaf6a4faa5d212e53c4.image.webp)

将8皇后问题推演一下，就可以得到我们的N皇后问题了。

N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，使其不能互相攻击。(同一行、同一列、同一斜线上的皇后都会自动攻击)那么问，有多少种摆法？


**代码解读：**

```java
public class NQueens {
    private static List<List<String>> result = new ArrayList<>();

    public static List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(board, 0);
        return result;
    }

    private static void backtrack(char[][] board, int row) {
        if (row == board.length) {
            result.add(convertBoard(board));
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1);
                board[row][col] = '.'; // 回溯
            }
        }
    }

    private static boolean isValid(char[][] board, int row, int col) {
        // 检查列、左上对角线、右上对角线
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
            int left = col - (row - i), right = col + (row - i);
            if (left >= 0 && board[i][left] == 'Q') return false;
            if (right < board.length && board[i][right] == 'Q') return false;
        }
        return true;
    }

    private static List<String> convertBoard(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board) res.add(new String(row));
        return res;
    }

    public static void main(String[] args) {
        System.out.println(solveNQueens(4).size()); // 输出2（4皇后有2种解法）
    }
}
```

**代码解读：**

逐行放置皇后，检查冲突

回溯时重置棋盘状态（board[row][col] = '.'）



## 贪心法（Greedy Algorithm）

贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

### 思路

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，其选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时， 就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

> 贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。
> 
> 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

**题解思路可分为3个步骤**

1. 将问题分解为多个子问题。
2. 选择合适的贪心策略，得到每一个子问题的局部最优解。
3. 将子问题的局部最优解合并成原问题的最优解。


:::tip{title="贪心算法存在的问题"}
贪心算法是把求解的问题分成若干个子问题求最优解，不能保证 **最终解是最佳的**。

因为贪心算法总是从局部出发，并没从整体考虑，贪心算法容易过早做出决定，所以只能求出满足某些约東条件的解，而有时在某些问题上还是可以得到最优解的。
:::


### 解题策略

要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解，使用贪心策略解题需要考虑以下两个问题：

- 该问题是否适合使用贪心策略求解，也就是该问题是否具有贪心选择性质
- 制定贪心策略，以达到问题的最优解或较优解

:::info{title="证明的大致过程"}
首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。
:::

### 经典应用

贪心策略的经典算法

#### 分数背包问题

给定 n 个物品，每个物品都有重量 w[i] 和价值 v[i]，同时有一个容量为 C 的背包。与 0-1 背包问题不同的是，在分数背包问题中，物品可以分割成任意比例放入背包，目标是在背包容量限制内选择物品放入背包，使得背包中物品的总价值最大。

![image.png](/static/img/8c15c03393444bb99308bcead4f4228d.image.webp)


**贪心策略确定**

最大化背包内物品总价值，本质上是最大化单位重量下的物品价值。由此便可推理出贪心策略。

1. 将物品按照单位价值从高到低进行排序。
2. 遍历所有物品，每轮贪心地选择单位价值最高的物品。
3. 若剩余背包容量不足，则使用当前物品的一部分填满背包。


![image.png](/static/img/e0230fbd5ca18a3c29b3f060ba1f2d36.image.webp)


**代码实现**

建立了一个物品类 Item ，以便将物品按照单位价值进行排序。循环进行贪心选择，当背包已满时跳出并返回解：

```java
/* 物品 */
class Item {
    int w; // 物品重量
    int v; // 物品价值

    public Item(int w, int v) {
        this.w = w;
        this.v = v;
    }
}

/* 分数背包：贪心 */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
    // 创建物品列表，包含两个属性：重量、价值
    Item[] items = new Item[wgt.length];
    for (int i = 0; i < wgt.length; i++) {
        items[i] = new Item(wgt[i], val[i]);
    }
    // 按照单位价值 item.v / item.w 从高到低进行排序
    Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
    // 循环贪心选择
    double res = 0;
    for (Item item : items) {
        if (item.w <= cap) {
            // 若剩余容量充足，则将当前物品整个装进背包
            res += item.v;
            cap -= item.w;
        } else {
            // 若剩余容量不足，则将当前物品的一部分装进背包
            res += (double) item.v / item.w * cap;
            // 已无剩余容量，因此跳出循环
            break;
        }
    }
    return res;
}
```

内置排序算法的时间复杂度通常为O(logn) ，空间复杂度通常为 O(logn) 或 O(n)，取决于编程语言的具体实现。除排序之外，在最差情况下，需要遍历整个物品列表，因此时间复杂度为O(n)，其中n为物品数量。由于初始化了一个 Item 对象列表，因此空间复杂度为 O(n)。


**正确性证明**

采用反证法。假设物品 x 是单位价值最高的物品，使用某算法求得最大价值为 res ，但该解中不包含物品 x。

现在从背包中拿出单位重量的任意物品，并替换为单位重量的物品x。由于物品x的单位价值最高，因此替换后的总价值一定大于 res 。这与 res 是最优解矛盾，说明最优解中必须包含物品x。

对于该解中的其他物品，我们也可以构建出上述矛盾。总而言之，单位价值更大的物品总是更优选择，这说明贪心策略是有效的。

将物品重量和物品单位价值分别看作一张二维图表的横轴和纵轴，则分数背包问题可转化为“求在有限横轴区间下围成的最大面积”。这个类比可以帮助我们从几何角度理解贪心策略的有效性。

![image.png](/static/img/e5edc129ada714199246facf20cc74e3.image.webp)


#### 找零问题

给定一个总金额和一系列不同面额的零钱，如何以最少的零钱数量来支付这个金额。‌在找零问题中，贪心算法的核心思想是每一步尽可能使用面值最大的零钱，从而减少使用的零钱数量。

**贪心策略确定**

将原问题分解为一系列子问题，每个子问题对应一个具体的找零操作。

- 贪心选择‌：对每个子问题求解时，选择当前看起来“最优”的解法，即尽可能使用面值最大的零钱。
- 合并解‌：累计局部最优解形成全局解，最终得到最少的零钱数量。

**代码实现**

```java
public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        Arrays.sort(coins); // 需降序排序
        int count = 0, index = coins.length - 1;
        while (amount > 0 && index >= 0) {
            if (coins[index] <= amount) {
                int num = amount / coins[index];
                count += num;
                amount -= num * coins[index];
            }
            index--;
        }
        return (amount == 0) ? count : -1;
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25}; // 美分硬币
        System.out.println(minCoins(coins, 63)); // 输出6（25+25+10+1+1+1）
    }
}
```

**正确性证明‌**

通过数学归纳或替换论证验证算法的正确性，尽管贪心策略不一定总是正确的，但在许多情况下能够提供足够好的解决方案。


## 总结

掌握这些算法思想可覆盖90%的编程问题，实际应用中需根据问题特点灵活组合使用。

| 算法思想 |	适用场景	| 时间复杂度 |
| --- | --- | --- |
| 分治法	| 大规模问题分解	| O(n log n)| 
| 递归法	| 树形结构问题	| 取决于问题规模| 
| 动态规划	| 重叠子问题优化	| O(n²) ~ O(n³)| 
| 枚举法	| 小规模暴力求解	| O(2ⁿ) ~ O(n!)| 
| 回溯法	| 组合优化问题	| O(n!)| 
| 贪心法	| 局部最优解场景	| O(n) ~ O(n log n)|

算法-核心算法思想

大家可能会想，怎么评估一个算法的好坏呢？ 本章节就是在学习算法前，先需要掌握一些理论基础。



# 评估算法优劣的核心指标是什么？

## 时间复杂度 O(f(n))

把某个算法执行步骤的计数来作为衡量运行时间的标准

### 衡量标准

在一个完全理想状态下的计算机中，我们定义 T(n)来表示程序执行所要花费的时间，其中n代表数据输入量。当然程序的最坏运行时间(Worse Case Executing Time)或最大运行时间是时间复杂度衡量的标准。

时间复杂度的衡量标准，一般以 Big-Oh 表示。常见的 Big-Oh

| Big-Oh  | 名称 | 描述 |
| --- | --- | --- |
| O(1) | 常数时间(Constant Time) | 表示算法的运行时间是一个常数倍 |
| O(n) | 称为线性时间(Linear Time) | 表示执行的时间会随着数据集合的大小而线性增长|
| O(log2n) | 次线性时间(Sub-Linear Time) | 成长速度比线性时间慢，而比常数时间快 |
| O(n^2) | 平方时间(Quadratic Time) | 称为，算法的运行时间会成二次方的增长 |
| O(n^3) | 立方时间(Cubic Time) | 算法的运行时间会成三次方的增长 |
| O(2^n) | 指数时间(Exponential Time) | 算法的运行时间会成2 的 n 次方增长。例如，解决Nonpolynomial Problem 问题算法的时间复杂度为 O(2") |
| O(nlog2n) | 线性乘对数时间 | 称为，介于线性和二次方增长的中间模式 |


由于在估算算法复杂度时采取“宁可高估不要低估”的原则，因此估计出来的复杂度是算法真正所需运行时间的上限。请大家看以下范例，以了解时间复杂度的意义。

> 范例：假如运行时间 T(n)=3㎡'+2㎡+5n，求时间复杂度。
> 
> 解答：首先找出常数c与 n。当 n=0、c=10 时，若 n>no，则 3n'+2㎡'+5n<10㎡，因此得知时间复杂度为 O(m^3)。


### 时间复杂度的意义

上面的范例中抹掉了好多东西，只剩下了一个最高阶项啊…  那这个东西有什么意义呢？

**时间复杂度的意义在于**

> 当我们要处理的样本量很大很大时，我们会发现低阶项是什么不是最重要的；每一项的系数是什么，不是最重要的。真正重要的就是最高阶项是什么。

这就是时间复杂度的意义，它是衡量算法流程的复杂程度的一种指标，该指标只与数据量有关，与过程之外的优化无关。


### 成长率

在分析算法的时间复杂度时，往往用函数来表示它的成长率(Rate ofGrowth)，其实时间复杂度是一种“渐近表示法”(Asymptotic Notation)

![image.png](https://blog.liushigong.cn/static/img/0081534ba202a6dd65f5d6073456edcb.image.webp)

不同的时间复杂度之间在不同数量下的处理速率

![image.png](https://blog.liushigong.cn/static/img/4626fcc48f3309ee82b9595e5c405704.image.webp)



## 空间复杂度

你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。

- 作为输入参数的空间，不算额外空间。
- 作为输出结果的空间，也不算额外空间。

因为这些都是必要的、和现实目标有关的。所以都不算。

但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间，如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。

### 常见的空间复杂度有下面几种情形。

**常量空间**

当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1)。例如 `int i=3`

**线性空间**

当算法分配的空间是一个线性的集合(如列表)，并且集合大小和输入规模n成正比时，空间复杂度记作O(n)。例如 `int[] array = {1,2,3}`

**二维空间**

当算法分配的空间是一个二维列表集合，并且集合的长度和宽度都与输入规模n成正比时，空间复杂度记作O(n2)。例如 `int[][] array = new int[10][10]`

**递归空间**

递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“函数调用栈”。

![image.png](https://blog.liushigong.cn/static/img/0d664bae820344ce99127069d21608ae.image.webp)

由上面“函数调用栈”的出入栈过程可以看出，执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。


### 时间与空间的取舍

人们之所以花大力气去评估算法的时间复杂度和空间复杂度，其根本原因是计算机的运算速度和空间资源是有限的。虽然目前计算机的CPU处理速度不断飙升，内存和硬盘空间也越来越大，但是面对庞大而复杂的数据和业务，我们仍然要精打细算，选择最有效的使用方式。

但是，正所谓鱼和能掌不可兼得。很多时候，我们不得不在时间复杂度和空间复杂度之间进行取舍。

```java
public class DuplicateExample {
    // 方案 1：暴力法（时间换空间）
    // 时间复杂度 O(n²)，空间复杂度 O(1)
    public static boolean hasDuplicateBruteForce(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    // 方案 2：哈希表（空间换时间）
    // 时间复杂度 O(n)，空间复杂度 O(n)
    public static boolean hasDuplicateHashSet(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        
        // 暴力法：通过双重循环比较所有元素对，省去额外空间，但时间效率低。
        System.out.println("暴力法结果: " + hasDuplicateBruteForce(nums)); // true
        
        // 哈希表：用 HashSet 存储已遍历元素，以空间换时间，效率更高。
        System.out.println("哈希表结果: " + hasDuplicateHashSet(nums));    // true
    }
}


```

在绝大多数时候，时间复杂度更为重要一些，我们宁可多分配一些内存空间，也要提升程序的执行速度。

### 取舍策略总结

1. 时间换空间：当内存资源紧张时（如嵌入式系统），选择低空间复杂度的算法。
2. 空间换时间：当时间要求严格时（如高频交易系统），选择低时间复杂度的算法。
3. 平衡选择：根据实际场景的数据规模（如 n 的大小）和硬件条件灵活调整。

:::info{title="相关信息"}
此外，说起空间复杂度就离不开**数据结构**，可以通过[「算法-数据结构基础」](/post/33)章节去掌握这部分内容。**<span style="color:red">时间复杂度</span> 和 <span style="color:red">空间复杂度</span> 都是学好算法的重要前提，一定要牢牢掌握哦!**
:::


## 常数项时间（实现细节决定）

如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间，称这样的操作为常数时间的操作。

### 常见的常数时间的操作

- 算术运算（+、-、*、/、% 等）
- 位运算（>>、>>>、<<、|、&、^等）
- 赋值、比较、自增、自减操作等
- 数组寻址操作

总之，执行时间固定的操作都是常数时间的操作。反之，执行时间不固定的操作，都不是常数时间的操作。


### 算法流程的常数项

我们会发现，时间复杂度这个指标，是忽略低阶项和所有常数系数的，难道同样时间复杂度的流程，在实际运行时候就一样的好吗？

结果当然不是，时间复杂度只是一个很重要的指标而已，如果两个时间复杂度一样的算法，你还要去在时间上拼优劣，就进入到拼常数时间的阶段，简称拼常数项。


### 算法流程的常数项的比拼方式

放弃理论分析，生成随机数据直接测。

**为什么不去理论分析？**

不是不能纯分析，而是没必要。因为不同常数时间的操作，虽然都是固定时间，但还是有快慢之分的。
比如，位运算的常数时间原小于算术运算的常数时间，这两个运算的常数时间又远小于数组寻址的时间。所以如果纯理论分析，往往会需要非常多的分析过程。都已经到了具体细节的程度，莫不如交给实验数据好了。


**如何确定算法流程的总操作数量与样本数量之间的表达式关系？**

1. 想象该算法流程所处理的数据状况，要按照最差情况来。
2. 把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作。
3. 如果数据量为N，看看基本动作的数量和N是什么关系。


### 位运算

位运算直接操作整数的二进制位，是计算机底层最高效的操作方式之一。Java中支持的位运算符包括：


| 运算符| 名称	| 描述	| 示例（二进制）| 
| --- | --- | --- | --- |
| `&`	| 按位与	| 两数对应位均为1时结果为1	| 1010 & 1100 = 1000| 
| `\|`	| 按位或	| 两数对应位任一为1时结果为1	| 1010 | 1100 = 1110| 
| `^`	| 按位异或	| 两数对应位不同时结果为1	| 1010 ^ 1100 = 0110| 
| `~`	| 按位取反	| 单目运算符，所有位取反	| ~1010 = 0101（补码）| 
| `<<`	| 左移	| 左移指定位数，低位补0	| 1010 << 2 = 101000| 
| `>>`	| 算术右移	| 右移指定位数，高位补符号位	| 1010 >> 2 = 1110| 
| `>>>`	| 逻辑右移	| 右移指定位数，高位补0	| 1010 >>> 2 = 0010| 

#### 示例代码

**位运算的用法**
```java
// 位运算符
int c = 0b1010; // 10（二进制）
int d = 0b0110; // 6（二进制）
System.out.println("\n----- 位运算符 -----");
System.out.println("c & d : " + (c & d));  // AND → 0010 → 2
System.out.println("c | d : " + (c | d));  // OR → 1110 → 14
System.out.println("c ^ d : " + (c ^ d));  // XOR → 1100 → 12
System.out.println("~c : " + (~c));       // 补码 → -11（十进制）
System.out.println("c << 2 : " + (c << 2)); // 左移2位 → 40
System.out.println("c >> 1 : " + (c >> 1)); // 右移1位 → 5
System.out.println("c >>> 1 : " + (c >>> 1)); // 无符号右移 → 5
print(1);
print(0);
print(-1);

// 输出二进制
static void print(int num){
    for (int i = 31; i >= 0; i--) {
        System.out.print((num & (1 << i)) == 0 ? "0" : "1");
    }
    System.out.println();
}

```

**权限控制（位掩码）**
```java
public class PermissionSystem {
    // 权限标志位定义
    public static final int READ = 1 << 0;    // 0001
    public static final int WRITE = 1 << 1;   // 0010
    public static final int EXECUTE = 1 << 2; // 0100

    private int permissions = 0; // 初始无权限

    // 添加权限
    public void addPermission(int perm) {
        permissions |= perm;
    }

    // 移除权限
    public void removePermission(int perm) {
        permissions &= ~perm;
    }

    // 检查权限
    public boolean hasPermission(int perm) {
        return (permissions & perm) != 0;
    }

    public static void main(String[] args) {
        PermissionSystem user = new PermissionSystem();
        user.addPermission(READ | WRITE);
        System.out.println(user.hasPermission(READ));  // true
        System.out.println(user.hasPermission(EXECUTE)); // false
    }
}
```

**交换变量值**
```java
int a = 5, b = 3;
a = a ^ b; // a = 5 ^ 3 = 6
b = a ^ b; // b = 6 ^ 3 = 5
a = a ^ b; // a = 6 ^ 5 = 3
System.out.println(a + ", " + b); // 3, 5
```

#### 位运算实际应用场景

1. 性能优化
- 用位运算替代乘除法：x << 1 等价于 x * 2
- 快速判断奇偶性：(x & 1) == 0

2. 数据压缩
- 将多个布尔值压缩到一个整型变量中（如权限系统）

3. 加密算法
- 异或加密：data ^ key

4. 位图算法（BitMap）
- 海量数据去重与排序（如处理10亿个不重复整数）

:::info{title="相关信息"}
想了想，还是将位运算部分放到了常数项模块中，毕竟在算法的过程中，涉及到常数项时间的极致优化、代码写的如何高大上，都离不开位运算，对于本模块，学好位运算才是实操的基石。
:::

## 面试、比赛、刷题中，一个问题的最优解是什么意思？

一般情况下，认为解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，使用最少的空间的算法流程，叫这个问题的最优解。

一般说起最优解都是忽略掉常数项这个因素的，因为这个因素只决定了实现层次的优化和考虑，而和怎么解决整个问题的思想无关。


## 复杂度的估算

1. 算法的过程，和具体的语言是无关的。
2. 想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉
3. 一定要确保在拆分算法流程时，拆分出来的所有行为都是常数时间的操作。这意味着你写算法时，对自己的用过的每一个系统api，都非常的熟悉。否则会影响你对时间复杂度的估算。

算法-理论基础

baidu-site-verification

本人自己的博客，对工作与学习过程中的总结、一些场景设计的实现方案、遇到过的疑难问题与解决、以及面试总结等。