简述

IoC是指控制反转，是指有容器来控制对象的生命周期和对象之间的关系。简单来说就是之前使用对象首先需要new一个对象，而现在直接从容器中取就可以了。这就像有小农经济转变到商品经济。

小农经济：自给自足，什么东西都需要自己动手也就类似于对象需要自己new。

商品经济：需要啥去商店买就行，这里的商店就相当于容器，商品就相当于对象，生成商品的工厂就相当于对象工厂等。

Spring IOC 的简单实现

分析

1、首先我们得有一个容器，这个容器负责保存和生成bean，这也就是对象工厂BeanFactory 。

2、其次，得有一个bean注册器，这负责bean的注册和真正生成。

3、然后，还得有一个资源加载器，用来加载bean的定义

4、最后，得有一个bean的定义模型和配置文件。

实现

分析为倒叙分析，实现就得看正序实现了，不然依赖就颠倒了。

1、配置文件和bean模型

先准备一个示例的bean

1
2
3
4
5

public class BeanExample {
    public void print(String string){
        System.out.println("test out: " + string);
    }
}

配置文件，偷懒使用一个<key,value>键值对代替

1

beanExample:com.shopmall.springIoc.BeanExample

bean模型定义

1
2
3
4
5
6
7
8

@Getter
@Setter
public class BeanDefinition {
    private String beanName;

    private Class beanClass;
}

2、资源加载器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class ResourceLoader {
    public static Map<String, BeanDefinition> getResource() {
        Map<String, BeanDefinition> beanDefinitionMap = new HashMap<>();
        Properties properties = new Properties();
        try {
            InputStream inputStream = ResourceLoader.class.getResourceAsStream("/beans.properties");
            properties.load(inputStream);
            for (String key : properties.stringPropertyNames()) {
                String className = properties.getProperty(key);
                BeanDefinition beanDefinition = new BeanDefinition();
                beanDefinition.setBeanName(key);
                Class clazz = Class.forName(className);
                beanDefinition.setBeanClass(clazz);
                beanDefinitionMap.put(key, beanDefinition);
            }
            inputStream.close();
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
        }
        return beanDefinitionMap;
    }
}

3、对象注册器

简化过程，都用单例了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class BeanRegister {

    //单例Bean缓存
    private final Map<String, Object> singletonBeanMap = new HashMap<>();

    /**
     * 获取单例Bean
     *
     * @param beanName bean名称
     * @return Object 单例Bean
     */
    public Object getSingletonBean(String beanName) {
        return singletonBeanMap.get(beanName);
    }

    /**
     * 注册单例bean
     *
     * @param beanName bean名称
     * @param bean 单例bean
     */
    public void registerSingletonBean(String beanName, Object bean) {
        if (singletonBeanMap.containsKey(beanName)) {
            return;
        }
        singletonBeanMap.put(beanName, bean);
    }

}

4、容器bean工厂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

public class BeanFactory {
    private Map<String, BeanDefinition> beanDefinitionMap = new HashMap<>();

    private BeanRegister beanRegister;

    public BeanFactory() {
        //创建bean注册器
        beanRegister = new BeanRegister();
        //加载资源
        this.beanDefinitionMap = new ResourceLoader().getResource();
    }

    /**
     * 获取bean
     *
     * @param beanName bean名称
     * @return Object Bean
     */
    public Object getBean(String beanName) {
        //从bean缓存中取
        Object bean = beanRegister.getSingletonBean(beanName);
        if (bean != null) {
            return bean;
        }
        //根据bean定义，创建bean
        return createBean(beanDefinitionMap.get(beanName));
    }

    /**
     * 创建Bean
     *
     * @param beanDefinition bean定义
     * @return Object Bean
     */
    private Object createBean(BeanDefinition beanDefinition) {
        try {
            Object bean = beanDefinition.getBeanClass().newInstance();
            //缓存bean
            beanRegister.registerSingletonBean(beanDefinition.getBeanName(), bean);
            return bean;
        } catch (InstantiationException | IllegalAccessException e) {
            e.printStackTrace();
        }
        return null;
    }
}

5、测试运行

简述

都知道spring的自动加载是通过注解实现的，但是这注解又是怎么实现的呢？

通过@SpringBootApplication注解开启，读取配置文件中的配置类，然后过滤掉不需要的配置类，最后将剩余的配置类加载配置。

具体过程

上面说了一下大概的概念，接下来我们分析一下具体的执行过程。

1、开启自动加载

都知道自动开启加载注解@SpringBootApplication，但是这个注解是个复合注解，他是由多个注解合并而成，但是主要的是三个注解：

1
2
3

@SpringBootConfiguration // 配置文件
@EnableAutoConfiguration // 开启自动配置
@ComponentScan // 扫描

@EnableAutoConfiguration注解继续下钻，主要有@AutoConfigurationPackage和@Import({AutoConfigurationImportSelector.class})两个注解，@AutoConfigurationPackage继续下钻主要有@Import({AutoConfigurationPackages.Registrar.class})这个注解。

所以基本可以理解

@EnableAutoConfiguration = @Import({AutoConfigurationImportSelector.class}) + @Import({AutoConfigurationPackages.Registrar.class})

即自动加载主要是依赖AutoConfigurationImportSelector.class，AutoConfigurationPackages.Registrar.class两个类。

2、@EnableAutoConfiguration下的两个类

AutoConfigurationPackages.Registrar.class：作用就是获取要扫描的包路径

1
2
3
4
5
6
7
8
9
10
11
12

static class Registrar implements ImportBeanDefinitionRegistrar, DeterminableImports {
    Registrar() {
    }

    public void registerBeanDefinitions(AnnotationMetadata metadata, BeanDefinitionRegistry registry) {
        AutoConfigurationPackages.register(registry, (String[])(new PackageImports(metadata)).getPackageNames().toArray(new String[0]));
    }

    public Set<Object> determineImports(AnnotationMetadata metadata) {
        return Collections.singleton(new PackageImports(metadata));
    }
}

AutoConfigurationImportSelector.class：可以看到AutoConfigurationImportSelector实现了3种接口

1、DeferredImportSelector接口，继承了ImportSelector接口，用于bean的注入

2、以Aware结尾的接口，这类接口时为了完成某类资源的设置。

3、Ordered接口，用于指定bean的加载顺序。

1

public class AutoConfigurationImportSelector implements DeferredImportSelector, BeanClassLoaderAware, ResourceLoaderAware, BeanFactoryAware, EnvironmentAware, Ordered

3、AutoConfigurationImportSelector

AutoConfigurationImportSelector实现了DeferredImportSelector接口，我们先看一下DeferredImportSelector接口。

接口里就包含了要加载的bean信息，再回到实现类，主要方法process。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

@Override
public void process(AnnotationMetadata annotationMetadata, DeferredImportSelector deferredImportSelector) {
	Assert.state(deferredImportSelector instanceof AutoConfigurationImportSelector,
			() -> String.format("Only %s implementations are supported, got %s",
					AutoConfigurationImportSelector.class.getSimpleName(),
					deferredImportSelector.getClass().getName()));
					
	// 获取自动配置的类
	AutoConfigurationEntry autoConfigurationEntry = ((AutoConfigurationImportSelector) deferredImportSelector)
			.getAutoConfigurationEntry(annotationMetadata);
	this.autoConfigurationEntries.add(autoConfigurationEntry);
	// 遍历自动配置的bean
	for (String importClassName : autoConfigurationEntry.getConfigurations()) {
		// 如果存在这个类就进行加入
		this.entries.putIfAbsent(importClassName, annotationMetadata);
	}
}

其中，主要的就是获取自动配置类：getAutoConfigurationEntry方法

protected AutoConfigurationEntry getAutoConfigurationEntry(AnnotationMetadata annotationMetadata) {
    if (!isEnabled(annotationMetadata)) {
        return EMPTY_ENTRY;
    }
    AnnotationAttributes attributes = getAttributes(annotationMetadata);
    List<String> configurations = getCandidateConfigurations(annotationMetadata, attributes); // 关键
    configurations = removeDuplicates(configurations);
    Set<String> exclusions = getExclusions(annotationMetadata, attributes);
    checkExcludedClasses(configurations, exclusions);
    configurations.removeAll(exclusions);
    configurations = getConfigurationClassFilter().filter(configurations);
    fireAutoConfigurationImportEvents(configurations, exclusions);
    return new AutoConfigurationEntry(configurations, exclusions);
}

根据关键代码继续下钻

protected List<String> getCandidateConfigurations(AnnotationMetadata metadata, AnnotationAttributes attributes) {
    List<String> configurations = new ArrayList<>(
            SpringFactoriesLoader.loadFactoryNames(getSpringFactoriesLoaderFactoryClass(), getBeanClassLoader()));
    ImportCandidates.load(AutoConfiguration.class, getBeanClassLoader()).forEach(configurations::add);
    Assert.notEmpty(configurations,
            "No auto configuration classes found in META-INF/spring.factories nor in META-INF/spring/org.springframework.boot.autoconfigure.AutoConfiguration.imports. If you "
                    + "are using a custom packaging, make sure that file is correct.");
    return configurations;
}

继续下钻

到这就基本清楚了，这里加载了META-INF/spring.factories文件下的配置，然后返回到getAutoConfigurationEntry方法里进行过滤，当然过滤的方式也是按条件注解@ConditionalOnxxx过滤生效。

总结

@SpringBootApplication下分三个注解，@EnableAutoConfiguration注解负责自动加载配置，

@EnableAutoConfiguration注解又引入两个类，AutoConfigurationImportSelector.class 和 AutoConfigurationPackages.Registrar.class

主要逻辑都在AutoConfigurationImportSelector.class中，此类中有个getAutoConfigurationEntry方法，

这个方法调用了两个方法getCandidateConfigurations 加载 和 getConfigurationClassFilter().filter 过滤。

如此加载进了配置文件中的配置，过滤了条件不满足的配置，以达到开箱即用。

代理模式

Spring AOP 就是基于代理模式，被代理对象有实现某个接口，则用JDK Proxy创建对象，没有实现接口则用Cglib创建代理对象。

当然也可以使用AspectJ，AspectJ是Java生态系统中最完整的AOP框架。

Spring AOP属于运行时增强，AspectJ是编译时增强。

两者异同：https://developer.aliyun.com/article/720402

模板方法

父类定义算法骨架或者关键步骤，而具体实现延迟到子类中，使子类再不改变父类结构的情况下可重定义某些特定步骤的实现。

Spring 中 JdbcTemplate、HibernateTemplate 等以 Template 结尾的对数据库操作的类，它们就使用到了模板模式。一般情况下，我们都是使用继承的方式来实现模板模式，但是 Spring 并没有使用这种方式，而是使用 Callback 模式与模板方法模式配合，既达到了代码复用的效果，同时增加了灵活性。定义了资源获取、执行SQL、释放资源这些基本流程，执行sql的具体方式又以回调函数的形式开放。

参考文献：https://blog.csdn.net/zhangweiocp/article/details/115486257

观察者模式

观察者模式是一种对象行为型模式。它表示的是一种对象与对象之间具有依赖关系，当一个对象发生改变的时候，依赖这个对象的所有对象也会做出反应。Spring 事件驱动模型就是观察者模式很经典的一个应用。Spring 事件驱动模型非常有用，在很多场景都可以解耦我们的代码。比如我们每次添加商品的时候都需要重新更新商品索引，这个时候就可以利用观察者模式来解决这个问题。

事件驱动模型中的三种角色：事件角色、事件监听者角色、事件发布者角色。

spring的事件流程总结

1、定义一个事件: 实现一个继承自ApplicationEvent，并且写相应的构造函数

2、定义一个事件监听者：实现 ApplicationListener 接口，重写 onApplicationEvent() 方法

3、使用事件发布者发布消息: 可以通过 ApplicationEventPublisher 的 publishEvent() 方法发布消息

example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// 定义一个事件,继承自ApplicationEvent并且写相应的构造函数
public class DemoEvent extends ApplicationEvent{
    private static final long serialVersionUID = 1L;

    private String message;

    public DemoEvent(Object source,String message){
        super(source);
        this.message = message;
    }

    public String getMessage() {
         return message;
          }


// 定义一个事件监听者,实现ApplicationListener接口，重写 onApplicationEvent() 方法；
@Component
public class DemoListener implements ApplicationListener<DemoEvent>{

    //使用onApplicationEvent接收消息
    @Override
    public void onApplicationEvent(DemoEvent event) {
        String msg = event.getMessage();
        System.out.println("接收到的信息是："+msg);
    }

}
// 发布事件，可以通过ApplicationEventPublisher  的 publishEvent() 方法发布消息。
@Component
public class DemoPublisher {

    @Autowired
    ApplicationContext applicationContext;

    public void publish(String message){
        //发布事件
        applicationContext.publishEvent(new DemoEvent(this, message));
    }
}

当调用 DemoPublisher 的 publish() 方法的时候，比如 demoPublisher.publish("你好") ，控制台就会打印出:接收到的信息是：你好 。

装饰者模式

装饰者模式可以动态地给对象添加一些额外的属性或行为。相比于使用继承，装饰者模式更加灵活。简单点儿说就是当我们需要修改原有的功能，但我们又不愿直接去修改原有的代码时，设计一个 Decorator 套在原有代码外面。最典型的就是JDK中的InputStream,OutputStream，两个类下的所有子类都是再不修改父类代码的情况下扩展了他的功能。

总结

Spring 框架中用到了哪些设计模式？

• 工厂设计模式 : Spring 使用工厂模式通过 BeanFactory、ApplicationContext 创建 bean 对象。
• 代理设计模式 : Spring AOP 功能的实现。
• 单例设计模式 : Spring 中的 Bean 默认都是单例的。
• 模板方法模式 : Spring 中 jdbcTemplate、hibernateTemplate 等以 Template 结尾的对数据库操作的类，它们就使用到了模板模式。
• 包装器设计模式 : 我们的项目需要连接多个数据库，而且不同的客户在每次访问中根据需要会去访问不同的数据库。这种模式让我们可以根据客户的需求能够动态切换不同的数据源。
• 观察者模式: Spring 事件驱动模型就是观察者模式很经典的一个应用。
• 适配器模式 :Spring AOP 的增强或通知(Advice)使用到了适配器模式、spring MVC 中也是用到了适配器模式适配Controllerl

分支定义

1. master

   1 2 3

   长期分支，存在与整个项目开发过程。 由项目主要技术负责人管理该分支。

2. release/xxx

   1 2 3 4

   release/test 和 release/prod 既可以为长期分支也可以为短期分支，可能存在于一个或者多个版本之间. 由测试负责人负责人管理该分支。

3. feature/fixbug/hotfix

   1 2 3 4 5

   临时分支 用于开发的具体功能特性和修复bug的分支，功能完成后删除. 格式为：feature_$date_$name_$description fixbug_$date_$name_$description hotfix_$date_$name_$description

技术面试复习清单（Java 后端 + AI 应用方向）

✅ 第一部分：Java 后端面试重点复习

🍃 Java 核心

• Java基础：

  • 集合类实现原理（HashMap 的哈希冲突解决、负载因子、扩容机制）

    • 示例：HashMap源码剖析

    • 属性	说明
      哈希冲突解决	链表法 + 红黑树
      默认负载因子	0.75
      扩容阈值	当前容量 × 负载因子
      扩容倍数	每次扩容为原来的 2 倍
      红黑树转化阈值	链表长度 > 8，且桶数组长度 > 64

  • List 与 Set 的区别，线程安全集合使用（CopyOnWriteArrayList、ConcurrentHashMap）

    • 说明：集合类对比总结

    • 项目	List	Set
      是否允许重复元素	✅ 允许	❌ 不允许
      是否有顺序	✅ 有插入顺序	❌ 无顺序（HashSet），但TreeSet有排序
      常见实现类	ArrayList, LinkedList, Vector	HashSet, LinkedHashSet, TreeSet
      底层结构	ArrayList: 数组LinkedList: 双向链表	HashSet: HashMap 实现TreeSet: 红黑树
      查找效率	ArrayList 是 O(1)（索引查找）	HashSet 是 O(1)，TreeSet 是 O(logN)
      使用场景	需要按顺序存储、可重复数据	要求元素唯一性、不关注顺序

• 多线程与并发：

  • 线程创建方式（Thread、Runnable、Callable）及线程池（Executors）
  • synchronized 与 ReentrantLock 区别
  • volatile 原理、内存可见性、指令重排序
    • 案例：并发可见性例子
  • 原子类（AtomicInteger、LongAdder）与 CAS 实现
  • 并发工具类：CountDownLatch、CyclicBarrier、Semaphore
    • 示例：并发工具类实战

• JVM：

  • JVM 内存区域（堆、栈、方法区、直接内存）
  • 类加载机制（双亲委派）、类卸载机制
    • 参考：JVM类加载机制详解
  • GC 垃圾回收算法（标记-清除、复制、CMS、G1）
    • 可视化演示：JVM GC动画讲解
  • 性能调优工具（jstack、jmap、jvisualvm）

🌐 Spring & Spring Boot

• IOC / AOP原理：BeanFactory 与 ApplicationContext，动态代理、切面编程
• Bean 生命周期：构造 -> set 属性 -> 初始化 -> 销毁
• 常用注解原理（@Transactional 的事务传播行为与回滚机制）
• 自动配置原理：SpringFactoriesLoader、条件注解（@ConditionalOnMissingBean）
  • 案例：Spring Boot 自动配置原理

🛠️ 数据库 & 缓存

• MySQL：
  • 索引类型（B+树）、覆盖索引、联合索引与最左匹配原则
  • SQL 调优（explain 分析、慢查询日志）
  • 事务隔离级别（Read Uncommitted、Repeatable Read 等）与幻读、MVCC 实现
    • MVCC讲解：图解MVCC
• Redis：
  • 数据结构（String、List、Set、Hash、ZSet）典型应用场景
  • 持久化机制（RDB vs AOF）、主从复制、哨兵机制
  • 缓存击穿（互斥锁）、穿透（布隆过滤器）、雪崩（过期时间错开）处理
    • 案例：Redis缓存问题解决方案
  • 分布式锁（SET NX PX 实现原理、Redlock 分布式算法）
    • 源码分析：Redlock 机制

🧱 中间件

• Kafka：
  • Producer/Consumer 原理、分区机制、消费位移管理
  • 消费模式（at most once、at least once）、幂等性保证
• RabbitMQ：
  • 交换机类型（Direct、Fanout、Topic）、消息确认与重试
• Netty：事件驱动模型、零拷贝、Reactor 模式
• Nginx：反向代理、负载均衡、location 匹配规则、缓存设置
  • 配置案例：Nginx使用详解
• 分布式ID：UUID 特点、雪花算法结构（时间戳+机器ID+序列号）

⚙️ 系统设计 / 分布式

• 微服务架构：服务注册发现（Eureka/Nacos）、配置中心（Spring Cloud Config）
• 分布式事务：
  • TCC（Try-Confirm-Cancel）原理与应用
  • 可靠消息最终一致性（RocketMQ事务消息）
  • SAGA 状态机模式（流程编排）
• 限流熔断降级：
  • Hystrix：断路器、舱壁、降级策略
  • Sentinel：滑动窗口限流、预热、熔断规则设置
    • 官方示例：Sentinel 使用文档

✅ 第二部分：AI 应用相关知识点

🤖 LLM 应用开发基础（LangChain / Flowise / OpenAI API）

• Prompt Engineering：角色设定、上下文拼接、few-shot 提示设计
  • 指南：OpenAI Prompt Best Practices
• LangChain 模块：
  • LLMChain：单轮调用链
  • RetrievalQA：向量搜索增强问答
  • Agent：动态任务调度
  • Memory：对话历史上下文管理（BufferMemory、SummaryMemory）
    • 文档：LangChain Memory
• 向量数据库：
  • Faiss：本地索引（Flat、IVF、HNSW）、Index 保存/加载方式
  • Chroma / Weaviate：文档分片、元数据存储与过滤检索
    • 参考：Weaviate 向量数据库
• Embedding：
  • OpenAI text-embedding-ada-002 使用方式、维度、成本
  • HuggingFace Sentence Transformers 示例（all-MiniLM）
    • 示例项目：Sentence Transformers 快速上手
• RAG：文档分片 ➝ embedding ➝ 存入向量库 ➝ 查询补全 context ➝ LLM 回答
• OpenAI 接口：API Key、temperature、top_p、stream 流式输出、速率限制处理
  • 官方文档：OpenAI API

💾 向量库与检索应用

• Faiss 操作：
  • 构建索引：IndexFlatL2、IndexIVFFlat
  • 插入数据：add_with_ids
  • 查询相似向量：search(query, k)
  • 快速入门：Faiss官方示例
• 向量检索原理：L2距离、Cosine 相似度、内积
• 本地 vs 云部署：FastAPI + Uvicorn 封装 Faiss API 远程调用
  • 项目示例：本地部署Faiss + FastAPI

🧠 Java 接入 AI 方向

• 接入方式：
  • 使用 WebClient / OkHttp / Feign 调用 OpenAI 接口
  • 解析 JSON 响应并集成流式 SSE 输出
• LangChain4j：
  • 使用 PromptTemplate + OpenAiLanguageModel 构建聊天功能
  • 与 Redis / 向量库集成构建知识问答
    • 项目参考：LangChain4j
• Demo 项目：
  • Java ChatPDF 实现：上传 PDF ➝ 分词 ➝ embedding ➝ 存储 ➝ 问答接口

📋 Bonus：系统设计类面试常见题目（准备简要方案）

1. 高并发电商下单系统：库存缓存、异步削峰（MQ）、分布式锁、防重提交
2. 聊天记录搜索：切分聊天文本 ➝ embedding ➝ 存 Faiss ➝ 模糊匹配
3. 智能问答机器人系统：文档预处理 ➝ 向量库 ➝ RAG 模式 ➝ LLM 调用
4. Java 服务接 GPT-4 生成摘要：接口设计、鉴权、token 管控、缓存存储
5. 简易 LangChain Chat Bot：Java 封装接口 + LangChain4j agent + memory 实现

两段式提交是MySQL数据持久化的保证。

两种日志

binlog和redolog

binlog记录了数据库表结构和表数据变更，主要有两个作用：复制和恢复数据

redo log 是 Innodb 引擎独有的日志模块，它只记录有关 Innodb 引擎的事务日志，记录内容为 对数据页的物理操作

两段式提交

两种日志虽然都保证持久化，但是侧重点不同。

1、redo log（重做日志）让InnoDB存储引擎拥有了崩溃恢复能力。

2、binlog（归档日志）保证了MySQL集群架构的数据一致性，主从节点的同步都是通过binlog保证的。

如果单独提交
先写 redo log 后写 binlog，也就是事务可能还没有提交，系统崩溃了，虽然可以通过redo log恢复，但是binlog还没有这条数据，就会造成主从不一致 先写 binlog 后写 redo log，这个过程说明事务已经提交了，系统崩溃了，虽然binlog里面有数据，但是redo log里面没有，也会发生主从不一致，并且redo log因为不全，即使重新恢复的时候也不是最新的数据

两段式提交

就是将redolog的提交拆为两各阶段，prepare阶段和commit阶段，在中间插入binlog提交。

发生异常

1、在prepare阶段写入redolog的时候发生异常，那不管redolog有没有写完，都会回滚，因为binlog没有写入，会导致日志不一样，主从数据不一致。

2、在commit阶段写入binlog的时候发生异常

    如果在写完之前，那也会回滚，毕竟没写完和没写一样，会导致日志不一样，主从数据不一样。

    如果在写完之后，那就不会回滚了，两种日志都写完了，能保证数据一致了。

3、在commit阶段提交redolog的时候发生异常，前面写完binlog就不会回滚了，那这里也不会回滚，能保证数据一致性。

简述

说起回表，肯定要说起MySQL的存储结构B+树。

每条数据是以主键和数据的形式存放在B+树的节点上，如果我们通过主键查询的话，直接通过和节点上的主键比较判断，相等的话直接取。

其他索引是将索引和主键值放在一起的，通过索引查到主键，在通过主键去查找数据。这也就是为什么主键索引会比其他索引快。

主键查询

主键和数据是通过B+数的形式存储的，查的时候肯定也是通过树的查询方式查询的。如下图查询主键Id为4的数据，先根据根节点查询，4小于10，再往子节点查找，然后跟子节点的值比较，在2、4之间，再寻找这区间的节点，第一个值是3，不匹配，在查找下一个，值是4匹配，放回数据记录data。

非主键索引查询

其实和主键查询差不多，只不过相当于两次主键索引查询，第一个查询到的不是数据，是主键值，再根据主键值，按照主键索引查询再来一次。如图，如果数据有一条数据是2019-04-01创建的，数据的主键id为4，我们想根据这个创建时间（不知道主键id）找到这条数据。那就是先根据创建时间找到主键4，后根据主键4找到记录数据data。

回表

分主键索引相当于两次查询，第一次查询主键，第二次查询数据，将第二次查询的数据结果放回给第一次查询结果，就叫回表。按照上面的图示，就是将data放回到创建时间的查询中。

覆盖查询

使用非主键查询的时候，也会存在不用回表的情况，这种叫做覆盖查询。

什么是覆盖查询呢，就是在我们使用索引的时候，索引本身包含的数据字段已经满足查询要求的字段了，就不用具体根据主键去找具体的记录数据了。

如果有一份人员信息数据，存有名称，性别，出生日期和其他一些字段。由于通过出生日期和性别的查询较多，我们用这两个字段构建了一个联合索引。现在我们要查询2019-04-01出生的女孩人数。

如图，联合索引按出生日期和性别联合构建的索引，先按出生日期排序，再按性别排序。通过索引，查询到只有一个主键为4满足，这时候我们需要计数，因为主键是唯一的，也不需要我们通过主键再次查询了，计算主键数量就够了，直接返回1。这就不用回表。

最左覆盖原则

上面我们说到根据联合索引查询，其实联合索引有两个值，我们只根据一个值去查询的，但也查询到了。这是为啥呢，这就是最左覆盖原则。根据我们的查询条件，会匹配索引，从左边第一个字段开始，所以我们查询的时候有条件过滤最好和索引顺序一直。如上图，我们查询的是整个表里面有女生多少人就没办法走联合索引了。

扩展

是不是觉得这个B+树还挺好用的，思路挺清晰的。但是如果我们的B+树层级很深，是不是查询比较的次数就多了，耗时也就多了，也就不好用了。所以大家知道B+树有多少层吗？

B+树一般是34层，为啥说34层呢，这也是个计算值，我们看一下具体怎么计算的。

MySQL的引擎是InnoDB，InnoDB默认页大小是16k，当然也可以设置，B+树的每个节点都是一页。从上面可以知道，节点分为数据节点和非数据节点，

在数据节点中，通常数据大小为1k，16k / 1k = 16，也就是每个数据页中大概会存放16条数据。

在非数据节点中，主要存放的是主键ID和指针，主键大概8字节，指针大概6字节，总共14字节，1k=1024字节，整页可以存放1170个（16 * 1024 / 14 = 1170）。

在3层的情况下，2层非数据节点，1层数据节点，可以存放大概21902400条数据。1170117016=21902400，已经到千万级别了，一个表里放千万条数据已经很大了，再大就要考虑分库分表了。

结构简述

HashMap和ConcurrentHashMap的结构都是一样的，jdk1.8之后都是 数组+链表+红黑树，链表长度超过8之后转红黑树。

计算

节点为6个的时候，链表的平均查询时间：(1+2+3+4+5+6)/ 6 = 3.5，红黑树的平均查询时间 (1+22+33)/6=2.3

节点为7个的时候，链表的平均查询时间：(1+2+3+4+5+6+7)/ 7 = 4，红黑树的平均查询时间 (1+22+34)/7=2.4

节点为8个的时候，链表的平均查询时间：(1+2+3+4+5+6+7+8)/ 8 = 4.5，红黑树的平均查询时间 (1+22+34+1*4)/8=2.6

链表的时间复杂度为O(n)，而树的时间复杂度为O(ln n)，上面计算有明显的效率变化，至于为啥选8这个阈值，应该是基于大量数据收集之后比较而定的。

结构图

HashMap

流程图

代码详解

ConcurrentHashMap

流程图

代码详解

虽然网上已经有很多了，但是我还是尝试总结一下，添加一点自己的心得。

总体来说，数组和链表是两种数据结构，所有的异同都是这两种数据结构的特点导致的。这两种数宝结构是计算机的基本数据结构，基态所有都是基于这两种数据结构实现的，只不过在细节上有区别。

简述

数组：多用于读多写少的情况，读取O(1)，写入O(n)，修改O(1)，删除O(n)；需要连续内存。

链表：多用于读少写多的情况，读取O(n)，写入O(1)，修改O(n)，删除O(1)；不需要连续内存。

数据结构差异

​ 从下图很明显就能看出两者的差别。数组需要连续，即连在一起，而链表不需要，只需要有个指针指向下一个。但是这个指向下一个的指针，也需要占用内存，导致链表中的单个元素比数组中的一个元素的内存大。

增删改查的效率差异

上面的数据结构差异，不可避免的导致了读写性能的差异。

数组

就像把人都聚集在一起，排好大小个顺序放在一个房间(连续内存)里。

查：一般我们查，都是按下标去查数组里的元素，也就相当于知道按大小顺序排的第多少个，直接找到就行。O(1)

改：既然我们能查到某个元素，改的话就是换掉这个元素。就相当于找到某个位置的人，把这个人换掉，一个位置换个人而已。O(1)

增：这时候你需要增加一个人（元素）进来，找到位置，这时候这位置上原本是有人（元素）的，那现在插入的人（元素）来了，这位置和后面位置的人都要向后移一位。   O(n)

删：这刚好和上面的增操作是相反操作。找到合适位置后，踢出这个人（元素），后面位置上的人（元素）都要前进一位。O(n)

链表

就像我们把一个一个人分开，他们每个人只知道排在自己后面的人在什么位置(也可以知道前一个人)，类似于手拉手排队一样。

查：这时候没有具体位置给我们，因为我们也不知道每个人（元素）的具体位置。只是因为大家手拉手（指针）的原因，前一个人能找到排在他后面位置的人。那我们找一个人的时候，就需要每个人都问一边，问一下是不是我们要找的人，不是的话再找下一个，直至找到或者找完。O(n)

改：和上面相同，既然能找到，就能换掉，只不过这次换有点特殊。每个人都是手拉手（指针），我们换掉之后要保证他们还是手拉手（指针）。O(n)

增：这时候你需要增加一个人（元素）进来，找到位置，这时候这位置上原本是有人（元素）的，后面的位置也可能是有人（元素）的，此时我们不要移动后面的人，只需要前后位置人的手牵到的是新增人员（元素）的手行，这样就减少了移动的操作。O(1)

删：这刚好和上面的增操作是相反操作。找到合适位置后，踢出这个人（元素），这位置前后面位置上的人（元素）手拉手就行。O(1)

空间差异

数组

上面也说到了，数组就像把人都聚集在一起，排好大小个顺序放在一个房间(连续内存)里，那对房子的要求就比较高，需要有足够大的房子。如果新增一人，房间（连续内存）不够大了，那所有的人都要换一个大一点的房子进去按顺序排着。这样就不利于扩展，大家都知道大房子（连续内存）是稀缺资源。

链表

而链表就比较友好了，有块空地(内存)就行，因为不需要房子(连续内存)，这样对于空间(内存)利用率就比较高，能把所有没有房子(非连续内存)的地方都用上，这样就比较适合添加人。

扩展

其实计算机的所有底层内存逻辑基本都按这个连续和不连续的模式来的。比如二叉树这种数据结构，说白了也就是链表的一种变种，由链表的指向下一个变成指向下两个。

除此之外，在jvm底层的垃圾回收，基本也是按照这种套路，新老代的垃圾回收，各种回收算法。比如标记清理、标记整理。

标记清理: 只是把内存中无效的对象删掉，可以想象，一块内存中，其中有的对象被删了有的没删，这就导致这部分内存可用性就低，因为内存被没删的内存分隔成一小段一小段的，不是连续的。虽然空间利用率不高，但是这种办法简单，只要删掉无效的对象就行。

标记整理: 算法的前部分和标记-清理算法一样，将无效对象删掉，但是资格算法还有后续，将剩余的对象整理一起，放在内存的一端，这样空出的内存就又连续上了。这种算法对空间的利用率就比较好，但是比较麻烦，毕竟要整理嘛。

约瑟夫斯问题

有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。
人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。
问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

问题

有n个人编号，站成一圈：
1 2 3 4 … … n-1 n

现在从1开始进行报数，报到k的出列自杀，然后剩下的人继续从1报数（当到达编号为n的人时，下一个报数的从编号为1的人开始进行）：
1 2 3 4… k(出列自杀) 1 2 …

直到圈内只剩余m人，求胜利者的编号。
例如：当n=6, k=5, m=1时，5,4,6,2,3将会被依次处决，而1将会幸免。

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

import java.util.ArrayList;
import java.util.List;

public class JosephProblem {

    /**
     * 返回活着的人的位置
     *
     * @param total 总人数
     * @param magicNum 报数到该数字的人自杀
     * @param remain 笑着活下去的人
     * @return
     */
    private List getJosephNumbers(int total, int magicNum, int remain) {

        List<Integer> peopleList = new ArrayList<>();
        for (int i = 1; i <= total; i++) {
            peopleList.add(i);
        }
        List<Integer> diedList = new ArrayList<>();


        int index = -1;  //当前应该删除的位置
        while (true) {
            index = (index + magicNum) % peopleList.size();

            diedList.add(peopleList.get(index));
            peopleList.remove(index);

            //从上一个位置开始计数
            index--;

            //判断是否剩余m个，如果是的话结束
            if (peopleList.size() == remain) {
                System.out.println("共" + total + "人，依次报数，当报到" + magicNum + "的人自杀，" + remain + "个人笑着活下去.");
                System.out.println("死掉的序号顺序为：" + diedList);
                System.out.println("笑着活下去序号为：" + peopleList);
                System.out.println("----------------------------------");
                return peopleList;
            }
        }
    }

    public static void main(String[] args) {
        JosephProblem test = new JosephProblem();

        test.getJosephNumbers(10, 4, 1);
        test.getJosephNumbers(10, 2, 1);
        test.getJosephNumbers(10, 3, 1);
        test.getJosephNumbers(20, 10, 3);
        test.getJosephNumbers(20, 4, 6);
    }
}

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

共10人，依次报数，当报到4的人自杀，1个人笑着活下去.
死掉的序号顺序为：[4, 8, 2, 7, 3, 10, 9, 1, 6]
笑着活下去序号为：[5]
----------------------------------
共10人，依次报数，当报到2的人自杀，1个人笑着活下去.
死掉的序号顺序为：[2, 4, 6, 8, 10, 3, 7, 1, 9]
笑着活下去序号为：[5]
----------------------------------
共10人，依次报数，当报到3的人自杀，1个人笑着活下去.
死掉的序号顺序为：[3, 6, 9, 2, 7, 1, 8, 5, 10]
笑着活下去序号为：[4]
----------------------------------
共20人，依次报数，当报到10的人自杀，3个人笑着活下去.
死掉的序号顺序为：[10, 20, 11, 2, 14, 6, 19, 15, 9, 7, 5, 8, 13, 18, 12, 4, 17]
笑着活下去序号为：[1, 3, 16]
----------------------------------
共20人，依次报数，当报到4的人自杀，6个人笑着活下去.
死掉的序号顺序为：[4, 8, 12, 16, 20, 5, 10, 15, 1, 7, 14, 2, 11, 19]
笑着活下去序号为：[3, 6, 9, 13, 17, 18]
----------------------------------