双亲委派模型

双亲委派模型的作用

  1. 避免重复加载：父类加载器已加载的类，子类加载器无需重复加载，保证内存中类对象的唯一性。

  2. 保护核心类安全：核心类（如java.lang.String）由启动类加载器加载，开发者无法通过自定义同名类篡改其行为。例如： 由于双亲委派机制，JVM会优先加载核心类库中的String，自定义类不会被加载。

  3. 沙箱安全机制：JVM禁止在核心包（如java.lang）下创建自定义类，即使绕过双亲委派，也会因包名保护抛出安全异常。

如何打破双亲委派模型？

  • 自定义类加载器： 重写loadClass()方法，跳过父类委派逻辑（默认实现会调用parent.loadClass()）。例如 Tomcat为每个Web应用提供独立类加载器，实现类隔离。

  • 线程上下文类加载器： 将自定义类加载器绑定到线程上下文，用于加载SPI接口实现（如JDBC驱动）

JVM内存区域

  1. 堆内存：
    • 年轻代：Eden区：新对象首先分配在这里。 Survivor区（From和To）：经过Minor GC后存活的对象会移到Survivor区。
    • 老年代：长期存活的对象最终会晋升到这里。
    • 永久代或元空间：存储类信息、常量、静态变量等（Java 8之前是永久代，Java 8及之后是元空间）。
  2. 方法区：存储类信息、常量、静态变量等，Java 8及之后由元空间实现。
  3. 栈内存：存储局部变量和方法调用，不涉及GC。
  4. 本地方法栈：用于Native方法，不涉及GC。
  5. 程序计数器：每一个线程都必须有一个独立的程序计数器，用于记录下一条要运行的指令。不涉及GC。

GC类型

1. Minor GC（年轻代GC）

  • 定义：仅回收年轻代（Eden区 + Survivor区）。
  • 触发条件：Eden区满时触发。
  • 行为：
    • 存活对象从Eden区和From Survivor区复制到To Survivor区。
    • 对象年龄（Age）达到阈值（默认15）时晋升到老年代。
  • 适用范围：所有分代垃圾收集器（如Serial、Parallel、CMS、G1）。

2. Major GC（老年代GC）

  • 定义：传统分代收集器（如CMS、Serial Old、Parallel Old）中仅回收老年代的GC。
  • 触发条件：老年代空间不足时触发。
  • 行为：
    • CMS：并发标记清除，避免长时间STW，但存在内存碎片问题。
    • Serial Old/Parallel Old：标记-整理或标记-清除，伴随长时间STW。

3. Mixed GC（混合回收，G1特有）

  • 定义：G1收集器中同时回收年轻代和部分老年代Region的GC。
  • 触发条件：当老年代Region占用超过堆内存的阈值（默认45%）。
  • 行为：
    • 基于全局并发标记结果，选择高垃圾比例（Garbage-First策略）的Region进行回收。
    • 与年轻代GC合并执行，优先回收高价值Region，避免全量回收老年代。
  • 与Major GC的区别：
    • Major GC仅针对老年代，Mixed GC同时处理年轻代和部分老年代。
    • Major GC可能导致碎片化，Mixed GC通过复制算法避免碎片。

4. Full GC（整堆GC）

  • 定义：回收整个堆内存（年轻代+老年代）和方法区（元空间）。
  • 触发条件：
    • 老年代空间不足（Major GC失败后触发Full GC）。
    • 方法区（元空间）不足。
    • 显式调用System.gc()。
  • 行为：
    • 所有应用线程暂停（Stop-the-World，STW），耗时较长。
    • 在G1中，Full GC是单线程的Serial Old算法，性能极差，需尽量避免。

G1垃圾回收过程

G1（Garbage-First）是面向全堆的垃圾回收器，将堆划分为多个Region（区域），动态管理年轻代和老年代。其核心流程如下：

  1. 初始标记（Initial Marking）
  • 目标：标记GC Roots直接关联的对象。
  • 特点：短暂STW（Stop-The-World），通常与年轻代GC（Minor GC）并行完成。
  1. 并发标记（Concurrent Marking）
  • 目标：遍历堆中所有对象，标记存活对象。
  • 特点：与用户线程并发执行，耗时最长。使用三色标记算法追踪对象引用，并通过SATB处理并发期间对象状态变化。
  1. 最终标记（Final Marking）
  • 目标：修正并发标记期间因用户线程运行导致的引用变化（如漏标对象）。
  • 特点：短暂STW，使用Remembered Set记录跨Region引用，避免全堆扫描。
  1. 筛选回收（Evacuation）
  • 目标：根据Region的垃圾比例和用户设定的停顿时间，选择高价值的Region进行回收。
  • 过程：将存活对象复制到空闲Region，清理旧Region空间，避免内存碎片。
  1. 混合回收（Mixed GC）
  • 触发条件：当堆内存使用率超过阈值（默认45%）时触发。
  • 范围：同时回收年轻代和部分老年代Region，优先处理垃圾比例高的Region。
  1. Full GC（后备机制）
  • 触发条件：当Mixed GC无法满足内存需求（如大对象分配失败）时触发，退化为单线程的Serial Old收集器，导致长时间STW。

三色标记算法

所有对象标记为白色，GC Roots 直接引用的对象置为灰色。遍历灰色集合，将灰色对象的子引用置灰，自身置黑。直至灰色集合为空。剩余白色对象视为不可达垃圾，由GC线程回收。

在并发标记过程中，用户线程可能修改对象引用关系，导致以下两类问题：

  1. 漏标（对象消失）：
    • 条件：① 灰色对象断开对白色对象的引用；② 黑色对象新增对同一白色对象的引用。
    • 后果：白色对象被误判为垃圾，导致程序错误。
  2. SATB（Snapshot At The Beginning）机制：
    • 核心思想：在并发标记开始时保存对象图快照，确保所有在快照中存活的对象最终被标记，即使后续引用被删除。
    • 实现方式：
      • 写屏障：在用户线程修改对象引用时触发。例如，当删除灰色对象到白色对象的引用（如 B.d = null ），写屏障会记录被删除的引用关系，确保该白色对象在重新标记阶段仍被处理。
      • 处理队列：记录所有因引用删除可能被遗漏的对象，在重新标记阶段扫描这些对象，确保其存活状态。

三色标记算法通过颜色状态实现高效并发标记，SATB机制通过写屏障和快照技术解决了并发修改导致的漏标问题，是G1等现代收集器的关键技术。其核心是通过 记录初始快照和引用变更，在保证正确性的前提下最大化减少STW时间，平衡了GC效率与程序性能。

CMS与G1的区别

维度 CMS G1
应用范围 仅老年代 全堆（年轻代+老年代）
内存模型 物理分代（固定年轻代/老年代） 逻辑分代（动态Region划分）
回收算法 标记-清除（内存碎片问题） 标记-整理（复制存活对象）
停顿控制 无法预测停顿时间 支持设定最大停顿时间（可控延迟）
适用场景 低延迟、中小堆内存（<6GB） 大堆内存（>6GB）、高吞吐量

GC Root

  1. 虚拟机栈中的局部变量
  2. 方法区中的静态变量
  3. 方法区中的常量
  4. 本地方法栈中的 JNI 引用
  5. Java 虚拟机内部的引用
  6. 被同步锁（synchronized）持有的对象
  7. 活跃线程中的对象

GC算法

1、引用计数法：为每个对象维护引用计数器，计数为0时回收。

  • 应用场景：Java未使用。
  • 优点：即时回收，暂停时间短。
  • 缺点：无法解决循环引用，计数器开销大。

2、标记-清除：分两阶段：标记可达对象，清除未标记对象。

  • 应用场景：老年代GC（需结合其他算法优化）。
  • 优点：实现简单，兼容性好。
  • 缺点：内存碎片化，效率低。

3、复制算法：将内存分为两块，存活对象从From复制到To，清空From。

  • 应用场景：新生代GC（Eden和Survivor区）。
  • 优点：无碎片化，分配效率高。
  • 缺点：内存利用率低，复制成本高（存活率高时）。

4、标记-整理 ：标记可达对象后，将所有存活对象压缩到内存一端，消除碎片。

  • 应用场景：老年代GC（CMS、G1的标记阶段）。
  • 优点：无碎片化，内存利用率高。
  • 缺点：整理阶段开销大，移动对象成本高。

5、分代收集：根据对象生命周期分新生代（复制算法）和老年代（标记-整理/清除）。

  • 应用场景：JVM堆内存管理（默认策略）。
  • 优点：针对不同对象优化，提升吞吐量。
  • 缺点：需额外管理分代信息。

6、分区收集：将堆划分为多个独立区域，每次仅回收部分区域，控制停顿时间。

  • 应用场景：G1、ZGC等现代垃圾回收器。
  • 优点：减少单次GC影响范围，提升吞吐量。
  • 缺点：实现复杂，需额外区域管理。

强软弱虚引用

  • 强引用：最常见的引用类型，不会被 GC 回收。
  • 软引用：内存不足时回收，适合缓存。
  • 弱引用：发生 GC 时回收，适合临时缓存或监听器。
  • 虚引用：无法获取对象，需与引用队列（ReferenceQueue）配合使用，用于跟踪对象回收状态。
  • 引用队列（ReferenceQueue）：当引用对象被回收时，引用会被加入引用队列，方便后续处理。

ThreadLocal

每个线程内部都有一个 ThreadLocalMap： 键（Key）：ThreadLocal 实例（弱引用）。 值（Value）：用户设置的数据（强引用）。

内存泄漏的原因：ThreadLocalMap 中的键（ThreadLocal 实例）是弱引用，而值是强引用。如果 ThreadLocal 实例没有被外部强引用，垃圾回收会回收键，但值仍然保留在 ThreadLocalMap 中，导致无法被回收。

内存泄漏的触发条件：（1） 线程池环境：线程会复用 （2）未调用 remove() 方法：

如何避免内存泄漏：（1）显式调用 remove()（2）避免使用静态ThreadLocal（3） 使用弱引用或软引用的值

HashMap

数据结构：

  1. 数组（Node[] table）：数组的长度始终是 2 的幂次方（方便通过位运算计算索引）。
  2. 链表（链表节点：Node）：哈希冲突较少时，插入和删除操作的时间复杂度是 O(1) 。在哈希冲突严重的情况下，链表会变得很长，查找性能退化为 O(n)。
  3. 红黑树（TreeNode）：当链表的长度超过阈值（默认是 8）且数组长度大于等于 64 ，链表会转换为红黑树。自平衡二叉树，查找时间复杂度为 O(log n)。如果数组长度小于 64 ，优先扩容数组，而不是转换红黑树。当红黑树的节点数量减少到阈值以下（默认是 6）时，红黑树会退化为链表。

工作原理：

（1）插入键值对

  1. 计算哈希值：
    • 对键的 hashCode() 进行哈希运算，得到哈希值。
    • 通过 (n - 1) & hash 计算数组索引（n 是数组长度）。
  2. 插入到数组或链表：
    • 如果目标桶为空，直接插入节点。
    • 如果目标桶不为空，遍历链表或红黑树：
      • 如果找到相同的键（key.equals()），更新值。
      • 如果没有找到相同的键，插入新节点到链表或红黑树。

（2）扩容（Resize）

  1. 触发条件：
    • 当键值对的数量超过阈值（容量 * 负载因子，默认负载因子是 0.75(泊松分布下链表长度≥8的概率极低)）时，触发扩容。
  2. 扩容过程：
    • 创建一个新的数组，长度是原数组的 2 倍。
    • 将原数组中的键值对重新哈希到新数组中。
    • 如果桶中是红黑树，会根据节点数量决定是否将红黑树转换回链表。
  3. 扩容问题
    • JDK 7：使用链表头插法扩容，头插法会反转链表的顺序，多线程并发操作可能导致链表成环，进而引发死循环。
    • JDK 8：使用链表尾插法扩容，不会反转链表的顺序，避免链表成环。将链表拆分为高低位链表（低位是原索引，高位是原索引+旧容量），提高扩容效率。

ConcurrentHashMap

（1）分段锁（Java 7 及之前）：

  • 数据结构：将整个哈希表分成多个独立的段（Segment），每个段是一个独立的哈希表。
  • 锁机制：每个段有自己的锁（ReentrantLock），多个线程可以同时访问不同的段，从而减少锁竞争。
  • 并发度：通过设置并发度（concurrencyLevel）来控制段的数量，默认是 16。

优点：

  • 读操作不需要加锁，性能较高。
  • 写操作只锁住对应的段，不影响其他段的访问。

缺点：

  • 分段锁的实现较为复杂。
  • 并发度固定（默认最多16个线程同时访问），无法动态调整。

（2）CAS + synchronized（Java 8 及之后）：

  • 数据结构：使用数组 + 链表 + 红黑树的结构（与 HashMap 类似）。
  • 锁机制：
    • 对每个桶（Node）使用 synchronized 锁，粒度更细。
    • 使用 CAS 操作来保证原子性，例如在插入、扩容等操作中。
  • 插入操作：
    • 如果桶为空，使用 CAS 插入节点。
    • 如果桶不为空，使用 synchronized 锁住桶的头节点，然后插入或更新节点。
  • volatile 变量：ConcurrentHashMap 中的关键变量（如 table、sizeCtl）使用 volatile 修饰，保证可见性。
  • 原子操作：使用 Unsafe 类提供的 CAS 操作来保证原子性。

优点：

  • 锁粒度更细，性能更高。
  • 动态调整并发度（允许的并发线程数量与Node数量相同），适应不同的并发场景。

（3）与 Hashtable 和 Collections.synchronizedMap 的区别

  • Hashtable：使用全局锁，所有操作都需要加锁，性能较差。
  • Collections.synchronizedMap：使用一个全局锁来包装 HashMap，性能同样较差。

volatile

1、保证可见性：可见性是指当一个线程修改了共享变量的值，其他线程能够立即看到修改后的值。

  • MESI 协议：
    • volatile 变量的读写会直接操作主内存，而不是线程的工作内存（缓存）。
    • 通过 CPU 的 MESI 缓存一致性协议，确保多个线程对 volatile 变量的修改能够及时同步到主内存和其他线程的缓存中。
  • 内存屏障：
    • 在读取 volatile 变量时，会插入 Load 屏障，强制从主内存加载最新值。
    • 在写入 volatile 变量时，会插入 Store 屏障，强制将修改的值刷新到主内存。

2、禁止指令重排序：为了提高性能，编译器和处理器可能会对指令进行重排序，但这在多线程环境下可能导致问题。

  • 内存屏障：
    • 在 volatile 写操作之前插入 StoreStore 屏障，确保之前的普通写操作先完成。
    • 在 volatile 写操作之后插入 StoreLoad 屏障，确保 volatile 写操作先于后续的读操作。
    • 在 volatile 读操作之前插入 LoadLoad 屏障，确保 volatile 读操作先于后续的普通读操作。
    • 在 volatile 读操作之后插入 LoadStore 屏障，确保 volatile 读操作先于后续的写操作。
  • happens-before 规则：
    • volatile 变量的写操作 happens-before 于后续的读操作。

CAS（乐观锁）

无锁机制：通过 CPU 原子指令直接操作内存，无需加锁。

三步操作：比较内存值（V）与预期值（A），若相等则更新为新值（B）；否则重试（自旋）。

原子性保障：由硬件指令保证比较和交换的原子性。

缺点： 1）有ABA问题，需通过版本号解决（AtomicStampedReference）。 2）高竞争时自旋浪费。 3）仅支持单个变量的原子操作，多变量原子性需封装为对象（AtomicReference）。

synchronized悲观锁

底层通 对象头中的锁状态标志位 和 Monitor（监视器锁） 实现。

锁状态标志位：标识当前锁的级别（无锁、偏向锁、轻量级锁、重量级锁）（Mark Word -> Lock Flag）

Monitor：同步代码块通过 monitorenter 和 monitorexit 指令操作 Monitor，而同步方法通过方法标志 ACC_SYNCHRONIZED 实现.

synchronized锁升级

  • 流程：无锁 → 偏向锁 → 轻量级锁 → 重量级锁（单向升级）。
  • 触发条件：
    • 偏向锁：首次线程访问同步代码，无竞争时，通过对象头记录线程ID（适用于单线程场景）。
    • 轻量级锁：多个线程交替访问（低竞争），通过CAS自旋获取锁（避免线程阻塞）。
    • 重量级锁：高并发竞争，自旋失败后升级为OS互斥锁，线程进入阻塞队列。
  • 优点：减少锁竞争带来的性能损耗（如用户态与内核态切换）

偏向锁被废弃的原因（JDK15+）：

  • 适用场景局限：仅单线程访问时高效，多线程环境下撤销偏向锁开销大。
  • JVM优化方向：转向更普适的锁策略（如适应性自旋锁）

AQS

1. AQS的核心原理是什么？

  • 核心组件：
    • State变量：一个volatile int类型的状态值，用于表示同步状态（如锁的持有次数、信号量许可数等）。
    • CLH队列：一个基于双向链表的虚拟队列（FIFO），用于管理等待线程的排队与唤醒。
  • 工作模式：
    • 独占模式：同一时刻只有一个线程能获取资源（如ReentrantLock）。
    • 共享模式：多个线程可同时获取资源（如Semaphore、CountDownLatch）。

为什么AQS使用CLH队列而不是普通队列？

  • 答：CLH队列通过前驱节点的状态自旋减少竞争，优化多线程环境下的性能。

2. 公平锁与非公平锁在AQS中的区别？

  • 公平锁：
    • 先检查队列是否有等待线程，若有则放弃CAS抢锁，直接排队。
    • 优点：避免线程饥饿；
    • 缺点：上下文切换开销大。
  • 非公平锁：
    • 直接尝试CAS抢锁，不检查队列是否有等待线程。
    • 优点：减少线程切换，提升吞吐量；
    • 缺点：可能导致饥饿。

为什么默认使用非公平锁？

  • 答：非公平锁在多数场景下性能更高（减少线程挂起和唤醒的开销）。

Java线程池

核心参数：核心线程数、最大线程数、队列类型、存活时间、线程工厂、拒绝策略（Abort（抛异常）、Discard（静默丢弃）、DiscardOldest（丢弃下一个任务）CallerRuns（调用者执行）、自定义）

（1）线程池配置导致OOM的典型场景

  1. 无界任务队列导致堆内存溢出 （改为有界队列，增加拒绝策略）
  2. 线程数过多导致直接内存或元空间溢出 （单线程栈默认占用1MB，可动态调整线程池参数）
  3. 任务对象生命周期过长导致内存泄漏 （ThreadLocalMap）

（2）定位OOM类型与线程池参数

  • 使用jmap -dump:format=b,file=heap.bin <pid>导出堆快照，分析内存占用对象。
  • 通过jstack <pid>查看线程池状态，确认是否大量线程阻塞在任务队列。
  • 检查线程池配置参数：核心线程数、队列类型（有界/无界）、拒绝策略。

Spring循环依赖

三级缓存通过“先暴露引用，后属性赋值”解决Setter注入的循环依赖，但不支持构造器注入，且只支持单例Bean。

三级缓存 ：

  1. 三级缓存：存储生成 Bean 的工厂，用于延迟生成可能的代理对象。
  2. 二级缓存：存储提前暴露的半成品 Bean（仅实例化，未初始化）。
  3. 一级缓存：存储完整的单例 Bean（已实例化、属性注入、初始化）。

流程示例（A依赖B，B依赖A）：

  • 步骤 1：实例化 A，生成原始对象，将 对象工厂 存入三级缓存。
  • 步骤 2：A 注入属性 B，触发 B 的实例化；B 实例化后同样存入三级缓存。
  • 步骤 3：B 需要注入 A 时，从三级缓存获取 对象工厂，生成 A 的早期引用（可能是代理对象），存入二级缓存。
  • 步骤 4：B 完成初始化后存入一级缓存；A 继续注入 B 并完成初始化，最终存入一级缓存。

为什么二级缓存不够？

  • 若没有动态代理（如纯 POJO），二级缓存可以解决问题。
  • 当存在 AOP 时，Bean 的最终形态是代理对象，而非原始对象。仅用二级缓存：
    • 问题 1：代理对象需在初始化阶段生成，但依赖注入发生在属性填充阶段，此时代理对象尚未生成，导致注入的是原始对象。
    • 问题 2：若在实例化后立即生成代理对象存入二级缓存，会导致后续初始化流程中代理对象被重复处理（如 @PostConstruct 方法执行两次）。

Spring事务原理

核心原理：基于代理 + 拦截器，利用事务管理器、线程资源绑定及注解元数据，实现声明式事务管理。

  1. 动态代理机制 ：Spring 通过 AOP 动态代理（JDK 或 CGLIB）为 @Transactional 类生成代理对象，拦截方法调用，添加事务逻辑。
  2. 事务拦截器：TransactionInterceptor：在方法执行前后，通过 PlatformTransactionManager（如 DataSourceTransactionManager）控制事务。 开启事务 → 执行业务方法 → 成功则提交，失败则回滚（根据异常类型判断）
  3. 事务属性绑定
    • 事务定义（TransactionDefinition）：从 @Transactional 注解中解析传播行为、隔离级别、超时等属性。
    • 传播机制：例如 PROPAGATION_REQUIRED（默认）会加入当前事务，无事务则新建。

Spring事务失效

  1. 非public方法：注解仅对public方法生效。
  2. 自调用：同类内部方法调用（如A调用B，B有注解），不走代理。
  3. 异常处理不当：
    • 默认只回滚 RuntimeException/Error，未抛或捕获异常不触发回滚。
    • 检查异常需显式指定 @Transactional(rollbackFor=Exception.class)。
  4. 数据库不支持：如MyISAM引擎。
  5. 多数据源未指定：未用@Transactional("txManagerName")指定具体事务管理器。
  6. 传播配置错误：如PROPAGATION_NOT_SUPPORTED强制非事务执行。
  7. 未被Spring管理：类未加@Component/@Service等注解。

SpringBoot

1. 自动装配的实现原理？

Spring Boot 自动装配的核心机制包括 条件注解驱动、SPI（spring.factories）加载 和 属性绑定，其设计思想是“约定优于配置”。

  • 通过@EnableAutoConfiguration触发，加载META-INF/spring.factories中的配置类
  • 使用条件注解（如@ConditionalOnClass）判断依赖是否存在，动态配置Bean
  • 自动配置类通过 @ConfigurationProperties 将配置文件中的属性绑定到 Bean

2. Spring Boot Starter 机制

  • 依赖管理：在 Maven/Gradle 中定义 Starter 的依赖集合，标记非必需依赖为 optional
  • 自动配置类：创建 @Configuration 类，配合条件注解定义 Bean 加载逻辑（如 @ConditionalOnClass）
  • 注册配置类：在 META-INF/spring.factories 或 AutoConfiguration.imports 文件中声明自动配置类的全限定名

3. 如何解决自动装配中的循环依赖问题？

通过构造函数注入、@Lazy 注解延迟加载，或重构代码消除循环依赖。

4. Spring Boot 配置文件的加载顺序是怎样的？

命令行参数 > 系统环境变量 > application-{profile}.properties（外部）> application.properties（外部）> application-{profile}.properties（内部）> application.properties（内部）

注：外部配置文件指项目 Jar 包所在目录的 /config 子目录或同级目录

5. Spring Boot启动流程的关键步骤有哪些？

初始化：创建SpringApplication实例，加载ApplicationContextInitializer和ApplicationListener。

运行环境准备：解析命令行参数、加载配置文件（application.yml）。

创建上下文：根据应用类型（Web/非Web）创建AnnotationConfigServletWebServerApplicationContext。

刷新上下文：调用refresh()方法，加载Bean定义、初始化Bean、启动内嵌Tomcat。

后置处理：执行CommandLineRunner和ApplicationRunner。

6. 如何实现热部署？

引入 spring-boot-devtools，通过类加载器隔离和文件监控实现热加载。

7. 如何排除Spring Boot的自动配置？

方法一：@SpringBootApplication(exclude = {DataSourceAutoConfiguration.class})

方法二：配置 spring.autoconfigure.exclude=

MySQL索引类型

  1. 主键索引（B+Tree）InnoDB 的聚簇索引，叶子节点存储行数据。
  2. 普通索引（B+Tree）非聚簇索引，叶子节点存储主键值（需要回表查询）。
  3. 唯一索引（B+Tree）结构与普通 B+Tree 索引相同，但强制值唯一。
  4. 组合索引（B+Tree）多个字段的 B+Tree 联合索引，遵循最左前缀原则。
  5. 前缀索引（B+Tree）仅对字段的前缀部分构建 B+Tree 索引。
  6. 全文索引（倒排索引）通过分词和关键词映射实现全文搜索。
  7. 空间索引（R-Tree）用于地理空间数据的多维索引。

B+Tree优点

  1. 适合磁盘存储：B+Tree 的非叶子节点不存储数据，单节点可存储更多键值，树高更低，减少磁盘 I/O 次数。（B-Tree所有节点存储数据，范围查询时需要回溯到上层节点）
  2. 范围查询高效：叶子节点的有序链表结构，适合范围查询和排序操作。
  3. 数据一致性：InnoDB 的聚簇索引（B+Tree）将数据与索引绑定，保证事务和数据一致性。

MySQL索引失效

  • 左模糊查询（LIKE '%xx'）。
  • 函数操作。
  • 类型隐式转换。（当查询条件中的数据类型与索引字段类型不一致时，数据库会进行隐式类型转换，导致索引失效。）
  • 联合索引最左匹配失效。
  • 使用 OR 条件。（如果 OR 条件的某一侧没有索引，整个查询可能无法使用索引。）
  • NOT 或 != 操作。
  • 数据分布不均匀。（如果索引字段的值大部分是相同的，可能退化为全表扫描）

ACID 事务特性

  • 原子性：事务的所有操作要么全部成功，要么全部回滚。通过undo log实现，记录反向操作（如INSERT对应DELETE），事务失败时回滚到初始状态。
  • 持久性：事务提交后数据永久保存。依赖redo log的物理日志，先将修改写入redo log buffer ，再按策略刷盘（如每秒或每次事务提交），系统崩溃后通过redo log恢复未刷盘的数据。
  • 隔离性：事务间操作互不干扰。通过MVCC（解决读-写冲突）和锁机制（解决写-写冲突）实现。
    • 读未提交：直接读取最新数据，可能脏读，不可重复读和幻读。
    • 读已提交：通过MVCC每次快照读生成新 Read View，解决脏读，但存在不可重复读和幻读。
    • 可重复读：解决脏读和不可重复读。通过 MVCC 复用Read View 解决快照读的幻读，避免读到新插入的数据。通过 Next-Key Lock【记录锁+间隙锁】 解决当前读的幻读。但仍然没彻底解决（事务A先快照读->事务B插入并提交->事务A尝试更新）。
    • 串行化：所有操作加锁，完全串行执行。

  • 一致性：事务前后数据库的约束（如主键、外键）保持有效。由应用层逻辑和数据库约束（如唯一索引）共同保证。

  • 脏读：一个事务读取了另一个未提交事务修改的数据。
  • 不可重复读：同一事务中，多次读取同一数据，结果不一致（因其他事务提交了修改）。

  • 幻读：同一事务中，多次按相同条件查询，结果行数不一致（因其他事务提交了新增或删除）。

  • 快照读：普通 SELECT 查询。

  • 当前读：SELECT ... FOR UPDATE、UPDATE、DELETE、INSERT

  • 记录锁：锁定索引记录
  • 间隙锁：锁定索引记录之间的间隙，防止其他事务在间隙中插入新记录

MVCC 解决的问题

  • 读-写冲突：允许读操作不阻塞写操作，提升并发性能。
  • 隔离性实现：在已提交读和可重复读级别下，通过多版本数据避免脏读、不可重复读。

MVCC实现三要素

  • 隐藏字段：
    • DB_TRX_ID：记录最后一次修改该数据的事务ID。
    • DB_ROLL_PTR：指向undo log中旧版本数据的指针，形成版本链。
  • Undo Log版本链：每次数据修改生成新版本，旧版本存入undo log，通过指针链接成链，支持事务回滚和快照读。
  • Read View（读视图）：
    • 组成：活跃事务ID集合、最小活跃事务ID、预分配最大事务ID+1、当前事务ID。
    • 判断规则：
      1. 若数据版本的事务ID等于当前事务ID，可见（当前事务自身修改）。
      2. 若事务ID小于最小活跃事务ID，可见（事务已提交）。
      3. 若事务ID大于等于预分配最大事务ID，不可见（事务未开始）。
      4. 若事务ID在活跃事务ID集合中，不可见（事务未提交）；否则可见。

MVCC的优缺点

  • 优点：提高并发性能，减少锁竞争；支持非阻塞读操作。
  • 缺点：版本链过长可能影响查询效率；无法完全解决幻读（需间隙锁）。

为什么长事务会影响MVC？

  • Undo Log堆积：长事务未提交时，其生成的旧版本数据无法被清理，导致版本链过长，影响查询性能。

MVCC如何保证数据可见性？

  • 通过Read View规则匹配版本链中的合适版本，确保事务仅能看到已提交或自身修改的数据。

Redis分布式锁(AP)

  • 加锁：使用 SET 命令的 NX（不存在时设置）和 PX（设置过期时间）选项，保证原子性。
  • 释放锁：通过 Lua 脚本确保 判断锁归属 和 删除锁 的原子性。
  • 锁续期：Redisson WatchDog 线程，定期（默认每 10 秒）检查锁是否仍由当前线程持有。若锁存在且归属当前线程，则延长锁的过期时间（默认续期到 30 秒）。
  • 锁重入：Redisson 支持可重入锁
  • 集群脑裂：RedLock 算法通过多节点投票提高可靠性，在多个独立 Redis 节点（至少 5 个）上获取锁，确保大多数节点（N/2 + 1）加锁成功。

缓存击穿/穿透/雪崩

1、缓存穿透：请求查询 数据库中不存在的数据，导致请求绕过缓存直达数据库。

解决方案：1. 布隆过滤器拦截非法请求 2. 缓存空值（设置短TTL）3. 接口参数校验

2、缓存击穿：热点Key突然失效，大量并发请求直接冲击数据库。

解决方案：1. 互斥锁（DCL锁/分布式锁）保证单线程重建缓存。2. 逻辑永不过期（后台异步更新）

3、缓存雪崩：大量Key同时过期 或 缓存集群宕机，导致请求全部穿透到数据库。

解决方案：1. 随机过期时间分散失效节点 2. 多级缓存（本地+Redis） 3. 集群高可用

IO多路复用

Redis 在 Linux 系统下默认使用了 epoll 实现 I/O 多路复用。

  • select：1. 最大 fd 数限制（默认 1024）2. 全量轮询 O(n) 复杂度 3. 用户态数据拷贝到内核态
  • poll：相比 select 无 fd 数量限制。
  • epoll：事件驱动 O(1) 复杂度，内核通过红黑树管理 fd，仅返回就绪的 fd 列表，无需全量遍历。仅注册时数据拷贝，后续无。

ZooKeeper分布式锁

通过临时顺序节点+Watch机制实现强一致性，性能较低（百毫秒级）。

  • 无锁续期问题：临时节点在客户端断开时自动删除，无需额外机制。
  • 无脑裂问题：ZooKeeper 的选举机制确保集群一致性。

CAP理论

  • CAP定义：
    • Consistency（一致性）：所有节点访问同一份最新数据。
    • Availability（可用性）：每次请求都能获取非错误响应（不保证数据最新）。
    • Partition Tolerance（分区容忍性）：网络分区时系统仍能继续运行。
  • 矛盾点：网络分区（P）必须被容忍，实际中需在C和A之间权衡。
  • 高频追问：
    • “CP/AP系统”是否完全放弃另一特性？
      • 答：并非完全放弃，而是分区发生时优先保障C或A（如Redis集群脑裂时可能牺牲A）。

BASE理论

  • BASE核心：
    • Basically Available（基本可用）：允许降级（如返回缓存旧数据）。
    • Soft State（软状态）：允许中间状态（如订单支付中）。
    • Eventually Consistent（最终一致）：通过异步同步达成一致。
  • 与CAP关系：
    • BASE是AP系统的实践指导，通过牺牲强一致性换取可用性。

MQ 消息队列

  1. 为什么使用MQ？
    • 核心作用：解耦（系统间独立）、异步（非核心流程异步化）、削峰（缓冲高并发流量）。
    • 典型场景：电商订单处理（异步扣库存、发通知）、日志采集（大数据处理）、实时数据分析（Kafka流处理）。
  2. MQ的优缺点
    • 优点：提升系统扩展性、吞吐量和容错能力。
    • 缺点：系统复杂度增加（需处理消息丢失、重复消费等）、数据一致性挑战（异步导致部分失败不一致）。
  3. 主流MQ对比（RabbitMQ/Kafka/RocketMQ）
    • RabbitMQ：基于AMQP协议，适合中小型公司，支持复杂路由（如Topic、Fanout），但吞吐量较低（万级）。
    • Kafka：高吞吐（百万级）、日志处理首选，但延迟较高，适合大数据场景。
    • RocketMQ：阿里开源，支持事务消息、顺序消息，适用于金融级场景。
  4. 如何保证消息不丢失？
    • 生产者：使用确认机制（如RabbitMQ的Confirm模式）或事务消息（如RocketMQ）。
    • Broker：持久化消息到磁盘（同步刷盘）、副本机制（如Kafka的ISR）。
    • 消费者：手动提交偏移量（避免自动提交导致消息丢失）。
  5. 如何处理重复消费（幂等性）？
    • 唯一标识：通过业务ID（如订单号）去重，结合数据库唯一键或Redis缓存。
    • 版本控制：数据库乐观锁（版本号校验）或状态机（限制操作顺序）。
  6. 如何保证消息顺序性？
    • 全局有序：单队列单消费者（性能低，仅特殊场景使用）。
    • 局部有序：同一业务键（如订单ID）哈希到同一队列（Topic分区），消费者单线程处理。
  7. 消息堆积如何处理？
    • 定位原因：检查消费者性能（如代码瓶颈、资源不足）。
    • 扩容：增加消费者实例数（需同步增加队列数，如Kafka Partition）。
    • 批量处理：优化消费逻辑，批量拉取和处理消息（如Kafka的max.poll.records）。
  8. 如何实现延迟消息？
    • RabbitMQ：使用死信队列（TTL+DLX）。
    • RocketMQ：内置延迟队列（18个固定延迟级别）。
  9. RabbitMQ的交换机类型
    • Direct：精确匹配路由键（如订单路由到指定队列）。
    • Fanout：广播到所有绑定队列（如通知所有子系统）。
    • Topic：模式匹配路由键（如logs.*匹配logs.error）。
  10. RabbitMQ如何保证可靠性？
    • Confirm机制：生产者等待Broker确认消息持久化。
    • 持久化队列：队列和消息均标记为持久化（durable=true）。
  11. Kafka高性能的原因
    • PageCache缓存：利用操作系统缓存加速读写。
    • 顺序写磁盘：避免随机I/O，提升吞吐量。
    • 零拷贝技术：减少数据在内核态和用户态的拷贝次数。
  12. Kafka的Rebalance机制
    • 触发条件：消费者加入/退出、Topic分区数变化。
    • 问题：可能导致消费暂停，需优化分区分配策略（如StickyAssignor）。
  13. RocketMQ事务消息原理
    • 两阶段提交：发送半消息（Prepare）→ 执行本地事务 → Commit/Rollback。
    • 回查机制：Broker定时检查未确认的事务状态。
  14. RocketMQ负载均衡策略
    • Producer端：轮询/哈希选择队列。
    • Consumer端：平均分配队列（避免部分Consumer过载）。

短链生成系统

  • 短链生成算法：
    • 哈希算法（如MurmurHash） + 进制转换（62进制[a-zA-Z0-9]）。
    • 自增ID + 分布式唯一ID生成（如Snowflake）。
  • 存储设计：
    • 缓存层：Redis缓存短链→长链映射（设置过期时间）。
    • 数据库：持久化记录，字段包括短链码、长链、创建时间、访问次数。
  • 优化点：
    • 防止哈希冲突（布隆过滤器判断短链码是否存在）。
    • 高并发写入（分库分表 + 批量申请ID段）。

秒杀系统

目标：高并发：支持大量用户同时抢购。高性能：快速响应用户请求。

高可用：避免系统崩溃或数据不一致。防止超卖：确保库存准确，避免超卖。

技术设计：

  1. 流量削峰：通过消息队列和排队机制缓解高并发压力。
  2. 库存预扣：使用 Redis 原子操作（DECR）或分布式锁（Redis、MySQL乐观锁）避免超卖。
  3. 限流熔断：通过限流工具（Nginx）和熔断器（Sentinel）保护系统稳定性。
  4. 静态化页面：CDN分发，减少服务器压力，提升用户体验。
  5. 缓存预热：提前将库存数据加载到 Redis 中，避免缓存未命中。

限流/熔断/降级

限流：限流是通过限制单位时间内的请求数量，防止系统因流量过大而崩溃。

  • 固定窗口：在固定时间窗口内限制请求数量。（每秒最多处理 100 个请求）
  • 滑动窗口：在滑动时间窗口内限制请求数量，更精确地控制流量。（过去 1 秒内最多处理 100 个请求）
  • 令牌桶：以固定速率生成令牌，请求需要消耗令牌，令牌不足时拒绝请求。（每秒生成 100 个令牌，请求消耗令牌，令牌用完后拒绝请求。）
  • 漏桶：以固定速率处理请求，超出速率的请求排队或丢弃。（每秒处理 100 个请求，超出速率的请求排队或丢弃。）

熔断：熔断是一种故障保护机制，当系统检测到某个服务或资源出现故障时，主动断开对该服务的调用，避免故障扩散。

  • 依赖服务故障：当某个依赖服务（如数据库、第三方 API）出现故障时，避免雪崩效应。
  • 超时保护：当服务响应时间过长时，主动断开调用。
  • 故障恢复：在服务恢复后，逐步尝试重新调用。

降级：降级是一种容错机制，当系统检测到某个服务或资源不可用时，提供一种备选方案（如返回默认值、缓存数据等），保证系统的基本功能可用。

  • 熔断触发降级：当熔断器打开时，调用降级逻辑，返回备选结果。

CPU飙升排查

定位 CPU 飙升至 100% 的问题代码的步骤如下：

  1. 使用 top 命令找到高 CPU 进程和线程。 top -Hp <PID>
  2. 将线程 ID 转换为 16 进制。
  3. 使用 jstack 导出线程栈，查找高 CPU 线程的栈信息，定位执行的代码行。
  4. 分析问题代码，常见问题包括死循环、正则表达式回溯陷阱和频繁 GC（STW）。
  5. 使用工具（如 jstat 查看 JVM 各区内存和 GC 情况、jmap 堆内存快照、jvisualvm 图形化工具）进一步分析内存和 GC 情况。

Full GC频繁排查

  • 工具链：jstat -gcutil观察各区内存变化；jmap -dump导出堆快照，MAT分析大对象。
  • 常见原因：内存泄漏（如未关闭的数据库连接）、大对象未分片（如一次性加载全表数据）。

线程死锁排查

  • jstack <pid>查看线程栈，搜索“deadlock”关键词；或Arthas的thread -b命令。
  • 预防：避免嵌套锁、使用超时锁（如tryLock）。

分布式ID

  1. 高并发、分布式系统：优先选择 雪花算法，需解决时钟回拨问题（可能导致ID冲突）。
  2. 中小规模系统：选择 Redis 原子自增，简单易用，依赖网络。
  3. 中大规模系统：选择 数据库号段，如美团的 Leaf，支持多业务类型，需维护步长。
  4. 对顺序性无要求的场景：选择 UUID，简单高效。

TCP

1. TCP三次握手与四次挥手
问题：简述三次握手和四次挥手流程，为什么握手是三次而挥手是四次？
核心回答：

  • 三次握手：
    1. 客户端发送SYN（seq=x）→ 服务端（SYN_SENT）。
    2. 服务端返回SYN-ACK（seq=y，ack=x+1）→ 客户端（SYN_RCVD）。
    3. 客户端发送ACK（ack=y+1）→ 服务端（ESTABLISHED）。
      作用：验证双方收发能力，防止历史连接建立。
  • 四次挥手：
    1. 主动方发送FIN（seq=u）→ 被动方（FIN_WAIT_1）。
    2. 被动方返回ACK（ack=u+1）→ 主动方（CLOSE_WAIT）。
    3. 被动方发送FIN（seq=w）→ 主动方（LAST_ACK）。
    4. 主动方返回ACK（ack=w+1）→ 被动方（TIME_WAIT → CLOSED）。
      原因：TCP是全双工协议，需独立关闭两个方向，且被动方可能有剩余数据发送。

2. TCP与UDP的区别及适用场景
问题：TCP和UDP的核心区别是什么？各自适合哪些场景？
核心回答：

  • 区别：
    • TCP：面向连接、可靠传输（确认应答、重传）、流量控制、拥塞控制。
    • UDP：无连接、不可靠传输、低延迟、无控制机制。
  • 场景：
    • TCP：Web请求（HTTP）、文件传输（FTP）、邮件（SMTP）。
    • UDP：实时音视频（RTP）、DNS查询、游戏心跳包。

3. TCP如何保证可靠性
问题：TCP通过哪些机制保证数据传输的可靠性？
核心回答：

  1. 确认应答（ACK）：接收方对每个数据包发送ACK确认。
  2. 超时重传：未收到ACK时重发数据包。
  3. 滑动窗口：动态调整发送速率，避免接收方缓冲区溢出。
  4. 拥塞控制：慢启动、拥塞避免、快速重传/恢复算法（如Reno）。
  5. 序列号与校验和：保证数据有序且完整。

4. 拥塞控制的实现机制
问题：TCP的拥塞控制算法有哪些阶段？
核心回答：

  • 慢启动：初始cwnd=1，指数增长至阈值（ssthresh）。
  • 拥塞避免：cwnd线性增长，避免网络过载。
  • 快重传：收到3个重复ACK时立即重传丢失包。
  • 快恢复：cwnd减半后直接进入拥塞避免阶段，避免回到慢启动

5. TIME-WAIT状态的作用与2MSL等待
问题：四次挥手中的TIME-WAIT状态为什么要等待2MSL？
核心回答：

  • 作用：确保最后一个ACK送达被动方；防止旧连接的数据包干扰新连接。
  • 2MSL：MSL 是报文最大生存时间（通常30秒），等待2MSL确保网络中所有旧报文消失。
  • 1个 MSL 保证四次挥手中主动关闭方最后的 ACK 报文能最终到达对端，1个 MSL 保证对端没有收到 ACK 那么进行重传的 FIN 报文能够到达。

6. 粘包与拆包问题
问题：TCP粘包是什么？如何解决？
核心回答：

  • 原因：TCP是字节流协议，接收方无法区分消息边界。
  • 解决方案：
    1. 固定消息长度（如每个消息固定为100字节）。
    2. 分隔符（如\n）。
    3. 消息头+长度字段（如HTTP头部Content-Length）。

7. 滑动窗口与流量控制
问题：滑动窗口如何实现流量控制？
核心回答：

  • 机制：接收方通过TCP头部的窗口大小字段告知发送方剩余缓冲区容量。
  • 动态调整：发送方根据窗口大小调整发送速率，避免接收方缓冲区溢出。

8. 半连接队列与SYN Flood攻击
问题：什么是半连接队列？如何防御SYN Flood攻击？
核心回答：

  • 半连接队列：服务端在SYN_RCVD状态保存未完成三次握手的连接。
  • 防御：
    1. 启用SYN Cookie机制（不保存半连接状态）。
    2. 限制并发SYN请求数量。

9. TCP Keep-Alive机制
问题：TCP的Keep-Alive有什么用？默认参数是什么？
核心回答：

  • 作用：检测空闲连接是否存活，避免占用资源，维持长连接可靠性。
  • 默认参数：探测间隔7200秒（Linux），最多发送9次探测包。

10. 应用场景优化
问题：高并发场景下如何优化TCP性能？
核心回答：

  1. 调整内核参数：如增大net.ipv4.tcp_max_syn_backlog和somaxconn。
  2. 开启快速打开（TFO）：减少握手延迟。
  3. 多路复用：如HTTP/2通过单个连接并行传输多个请求。

HTTP与HTTPS

  • HTTP：明文传输，端口80；HTTPS：SSL/TLS加密，端口443。
  • 加密流程：
    1. 客户端请求证书，验证服务端身份（CA机构签名）。
    2. 协商对称加密密钥（如RSA交换密钥，AES加密数据）。
    3. 数据传输时使用对称加密。
  • HTTPS如何防止中间人攻击？
    • 答：证书链验证（防止伪造证书）+ 非对称加密保证密钥交换安全。

HTTP/2 优点

  • 二进制分帧：头部和主体数据转为二进制帧，提升解析效率。
  • 多路复用：单连接并行传输多个请求/响应，解决队头阻塞。
  • 头部压缩：HPACK算法压缩重复Header字段（如Cookie）。
  • 服务端推送：主动推送静态资源（如CSS/JS）。
  • 对比HTTP/1.1：减少连接数、降低延迟、节省带宽。

LRU缓存

FIFO（先进先出）、LRU（最近最少使用）和LFU（最不经常使用）

  • LinkedHashMap（accessOrder=true + removeEldestEntry）
  • 自定义双向链表 + HashMap实现（优化点：分段锁减少竞争、软/弱引用避免OOM、异步刷新过期数据）
public class LRUCache { // 时间复杂度都是 O(1)
    class Node {
        Node prev, next;
        Object key, value;
    }

    private int size;  // 最大容量
    private Map<Object, Node> cache;  // 存储数据
    private Node head, tail;  // 虚拟头尾节点

    public Object get(Object key) {
        Node node = cache.get(key);
        if (node != null) {
            moveToHead(node);
            return node.value;
        } else {
            return null;
        }
    }

    public void put(Object key, Object value) {
        Node node = cache.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            Node node1 = new Node(key, value);
            cache.put(key, node1);
            addToHead(node1);
            if (cache.size() > size) {
                Node tail = removeTail();
                cache.remove(tail.key);
            }
        }
    }

    private void moveToHead(Node node) {
        Queue<TreeNode> queue = new LinkedList<>();
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node prev = tail.prev;
        removeNode(prev);
        return prev;
    }

    // 先改自身指针，再改前后指针
    private void addToHead(Node node1) {
        node1.prev = head;
        node1.next = head.next;
        head.next.prev = node1;
        head.next = node1;
    }

    // 改前后指针即可
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

最小栈

题目：设计一个栈，支持push、pop、top操作，并能在常数时间内检索到最小元素。
考点：辅助栈与空间换时间。

    class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

最长递增子序列

答案要点（动态规划）：

public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int max = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

优化：二分查找法（时间复杂度O(nlogn)）。

快速排序

  • 时间复杂度：平均O(nlogn)，最坏O(n²)（如已有序数组）。
  • 空间复杂度：O(logn)（递归栈）。
public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pValue = arr[left]; // 选择第一个元素为基准
    int mark = left;
    for (int i = left + 1; i <= right; i++) {
        if (arr[i] < pValue) {
            mark++;
            swap(arr, i, mark);
        }
    }
    swap(arr, left, mark);
    return mark;
}

如何优化最坏情况？

  • 答：随机选择基准（如pivot = arr[random(low, high)]）。

最大的第K个数

思路：快速选择（分治减治）平均 O(n)，最坏 O(n²)

public int findKthLargest(int[] nums, int k) {
    int left = 0, right = nums.length - 1;
    while (true) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == nums.length - k) {
            return nums[pivotIndex];
        } else if (pivotIndex < nums.length - k) {
            left = pivotIndex + 1;
        } else {
            right = pivotIndex - 1;
        }
    }
}

private int partition(int[] nums, int low, int high) {
    int pivot = nums[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (nums[j] <= pivot) {
            swap(nums, i, j);
            i++;
        }
    }
    swap(nums, i, high);
    return i;
}

思路：堆排序 O(n log k) 大规模数据

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int num : nums) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    return heap.peek();
}

二维数组中的查找

思路：从左下角开始，若当前值小于目标则右移，否则上移，时间复杂度 O(m+n)

public boolean findNumberIn2DArray(int[][] matrix, int target) {
    int i = matrix.length - 1, j = 0;
    while (i >= 0 && j < matrix[0].length) {
        if (matrix[i][j] > target) {
            i--;
        } else if (matrix[i][j] < target) {
            j++;
        } else {
            return true;
        }
    }
    return false;
}

两数之和

题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
考点：哈希表优化查找时间（O(n)）。
变种：三数之和、四数之和。

   public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

最长无重复子串

题目：给定一个字符串，找出不含有重复字符的最长子串的长度。
考点：滑动窗口（双指针）与哈希集合。

   public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left++));
        }
        set.add(s.charAt(right));
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

连续子数组的最大和

题目：求整数数组中连续子数组的最大和。

思路：定义 dp[i] 表示以 nums[i] 结尾的子数组最大和，递推公式 dp[i] = max(nums[i], dp[i-1] + nums[i])

public int maxSubArray(int[] nums) {
    int max = nums[0], pre = 0;
    for (int num : nums) {
        pre = Math.max(pre + num, num);
        max = Math.max(max, pre);
    }
    return max;
}

回文子串

中心扩展法：回文子串的中心可能是一个字符（奇数长度）或两个相邻字符（偶数长度）。遍历每个可能的中心点，分别向左右扩展。 扩展过程：对于每个中心点，初始化左右指针，若左右字符相等，则继续扩展，直到不满足条件为止。 记录子串：每次扩展时，将当前满足条件的子串添加到结果列表中。

    List<String> allPalindromeSubstrings(String s) {
    List<String> result = new ArrayList<>();
    if (s == null || s.isEmpty()) {
        return result;
    }
    for (int i = 0; i < s.length(); i++) {
        expandAroundCenter(s, i, i, result); // 处理奇数长度的回文子串
        expandAroundCenter(s, i, i + 1, result); // 处理偶数长度的回文子串
    }
    return result;
}

void expandAroundCenter(String s, int left, int right, List<String> result) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        result.add(s.substring(left, right + 1)); // 截取当前回文子串并加入结果列表
        left--; // 向两侧扩展
        right++;
    }
}

合并区间

题目：给定一组区间，合并所有重叠的区间。
考点：排序与区间合并逻辑。

   public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> result = new ArrayList<>();
    int[] current = intervals[0];
    for (int[] interval : intervals) {
        if (interval[0] <= current[1]) {
            current[1] = Math.max(current[1], interval[1]);
        } else {
            result.add(current);
            current = interval;
        }
    }
    result.add(current);
    return result.toArray(new int[result.size()][]);
}

反转链表

题目：反转一个单链表。
考点：迭代与递归实现，指针操作。

   public ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

链表环检测

题目：判断链表中是否有环，并返回环的入口节点。
考点：1）哈希表+遍历。2）快慢指针（Floyd判圈算法）。

   public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

合并两个有序链表

题目：将两个升序链表合并为一个新的升序链表。
考点：递归与迭代实现。

   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = l1 != null ? l1 : l2;
    return dummy.next;
}

二叉树的中序遍历

递归实现

public void inorderRecur(TreeNode root, List<Integer> res) {
    if (root == null) return;
    inorderRecur(root.left, res);  // 递归左子树
    res.add(root.val);             // 访问根节点
    inorderRecur(root.right, res); // 递归右子树
}

非递归实现

public List<Integer> inorderNonRecur(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {       // 压入所有左子节点
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();          // 弹出并访问
        res.add(cur.val);
        cur = cur.right;            // 处理右子树
    }
    return res;
}

二叉树的层序遍历

题目：按层遍历二叉树，返回每层的节点值。 考点：队列实现，BFS逐层处理，记录每层节点数。

   // class TreeNode {int val;  TreeNode left, right;TreeNode(int x) { val = x; }}
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        result.add(level);
    }
    return result;
}

二叉树的最大深度

题目：给定一个二叉树，找出其最大深度。
考点：递归与DFS。

   public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

二叉树的最大路径和

题目：路径可以是任意节点到任意节点，不一定经过根节点。。
考点：递归与DFS。

   int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    dfs(root);
    return maxSum;
}

private int dfs(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = Math.max(dfs(root.left), 0); // 舍弃负数路径
    int right = Math.max(dfs(root.right), 0);
    maxSum = Math.max(maxSum, left + right + root.val);
    return Math.max(left, right) + root.val; // 返回单侧最大路径
}

二叉搜索树的第K大节点

题目：给定一棵二叉搜索树，找到其中第K大的节点。
考点：中序遍历与递归。

   private int count = 0, result = 0;

public int kthLargest(TreeNode root, int k) {
    reverseInorder(root, k);
    return result;
}

private void reverseInorder(TreeNode root, int k) {
    if (root == null) {
        return;
    }
    reverseInorder(root.right, k);
    if (++count == k) {
        result = root.val;
        return;
    }
    reverseInorder(root.left, k);
}

零钱兑换（凑硬币）

题目：给定不同面额的硬币和一个总金额，计算可以凑成总金额的最少硬币数。
考点：动态规划与状态转移方程。

    public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

编辑距离（单词转换）

题目：给定两个单词，计算将一个单词转换成另一个单词所需的最少操作数（插入、删除、替换）。
考点：二维动态规划。

    public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
    }
    return dp[m][n];
}

全排列（一维数组）

题目：给定一个不含重复数字的数组，返回其所有可能的全排列。
考点：回溯与剪枝。

    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] nums) {
    if (temp.size() == nums.length) {
        result.add(new ArrayList<>(temp));
        return;
    }
    for (int num : nums) {
        if (temp.contains(num)) {
            continue;
        }
        temp.add(num);
        backtrack(result, temp, nums);
        temp.remove(temp.size() - 1);
    }
}

题目：给定一个包含重复数字的数组，返回其所有可能的全排列。
考点：回溯与剪枝。

    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] nums, boolean[] used) {
    if (temp.size() == nums.length) {
        result.add(new ArrayList<>(temp));
        return;
    }
    for (int num : nums) {
        if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
            continue;
        }
        used[i] = true;
        temp.add(num);
        backtrack(result, temp, nums, used);
        used[i] = false;
        temp.remove(temp.size() - 1);
    }
}

数字和为目标数

题目：给定一个无重复元素的数组和一个目标数，找出所有可以使数字和为目标数的组合。
考点：回溯与剪枝。

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> temp, int[] candidates, int remain, int start) {
    if (remain < 0) {
        return;
    }
    if (remain == 0) {
        result.add(new ArrayList<>(temp));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        temp.add(candidates[i]);
        backtrack(result, temp, candidates, remain - candidates[i], i);
        temp.remove(temp.size() - 1);
    }
}

数组中出现次数超过一半

题目：找出数组中出现次数超过一半的元素。 思路：遍历数组，通过计数抵消不同元素，最终剩余元素为众数。

public int majorityElement(int[] nums) {
    int votes = 0, x = 0;
    for (int num : nums) {
        if (votes == 0) {
            x = num;
        }
        votes += (num == x) ? 1 : -1;
    }
    return x;
}

股票的最大利润

题目：给定一个数组表示股票每日价格，只能进行一次买卖操作，求最大利润。

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, maxProfit = 0;
    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price;
        } else {
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
    }
    return maxProfit;
}

题目：允许无限次买卖，求最大利润。

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}

N皇后问题

题目：在N×N的棋盘上放置N个皇后，使得它们互不攻击。
考点：回溯与位运算优化。

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

private void backtrack(List<List<String>> result, char[][] board, int row) {
    if (row == board.length) {
        result.add(construct(board));
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(result, board, row + 1);
            board[row][col] = '.';
        }
    }
}

private boolean isValid(char[][] board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

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

岛屿数量

题目：给定一个由’1’（陆地）和’0’（水）组成的二维网格，计算岛屿的数量。
考点：DFS/BFS与网格遍历。

    public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') return;
    grid[i][j] = '0';
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}

课程表

题目：给定课程总数与先修条件，判断是否能够完成所有课程。
考点：拓扑排序与环检测。

    public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    int[] inDegree = new int[numCourses];
    for (int[] edge : prerequisites) {
        graph.get(edge[1]).add(edge[0]);
        inDegree[edge[0]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int next : graph.get(course)) {
            if (--inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    return count == numCourses;
}

最短路径

题目：给定一个带权图，计算从起点到终点的最短路径。
考点：优先队列与贪心策略。

    public int[] dijkstra(int[][] graph, int start) {
    int n = graph.length;
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{start, 0});
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int node = curr[0], d = curr[1];
        if (d > dist[node]) {
            continue;
        }
        for (int neighbor = 0; neighbor < n; neighbor++) {
            if (graph[node][neighbor] != 0) {
                int newDist = dist[node] + graph[node][neighbor];
                if (newDist < dist[neighbor]) {
                    dist[neighbor] = newDist;
                    pq.offer(new int[]{neighbor, newDist});
                }
            }
        }
    }
    return dist;
}