垃圾回收算法（核心）

GC 算法的分类

JVM 中使用的垃圾回收算法可以分为几大类，它们各有特点和适用场景：

GC 算法分类
  │
  ├── 引用计数算法（Reference Counting）
  │     └── 早期使用，无法处理循环引用，JVM 不使用
  │
  ├── 追踪式算法（Tracing GC）
  │     ├── 标记-清除（Mark-Sweep）
  │     ├── 复制算法（Copying）
  │     └── 标记-压缩（Mark-Compact）
  │
  └── 分代算法（Generational GC）
        └── 结合上述算法，按分代策略使用

追踪式 GC 的基本思路

「追踪」的意思是：从 GC Roots 出发，顺着引用链「顺藤摸瓜」，找出所有可达的对象。没有被 GC Roots 引用到的对象，就是垃圾。

GC Roots（根节点集合）
      │
      ├─→ 对象A ──→ 对象B
      │
      ├─→ 对象C
      │
      └─→ 对象D（不可达 → 垃圾）

三种基本算法

1. 标记-清除（Mark-Sweep）

最基础的 GC 算法，分两步：标记存活对象 → 清除垃圾对象。

标记阶段：
  ┌─────────────────────────────┐
  │ [A]  [B]  [C]  [D]  [E]   │  ← GC Roots 出发，标记可达对象
  │  ✓     ✓     ✓           │  ← A、C、E 被标记（存活）
  │      [D]  [B]            │  ← B、D 未被标记（垃圾）
  └─────────────────────────────┘

清除阶段：
  ┌─────────────────────────────┐
  │ [A]  [C]  [E]  [____]  [____] │
  │  ✓     ✓     ✓      ← 删除     │
  │                             ← 删除  │
  └─────────────────────────────┘

2. 复制算法（Copying）

把内存分成两半，每次只使用一半。回收时，把存活对象复制到另一半，然后直接清空当前半。

复制前：
┌──────────────────┐  ┌──────────────────┐
│     使用中        │  │      空白        │
│  [A]  [B]  [C]  │  │                  │
│  [D]  [E]  [F]  │
│  [G]             │
└──────────────────┘  └──────────────────┘
        From                    To

复制后：
┌──────────────────┐  ┌──────────────────┐
│                  │  │    存活对象      │
│  (全部清空)       │  │  [A]  [C]  [E]  [G] │
└──────────────────┘  └──────────────────┘
        From                    To

3. 标记-压缩（Mark-Compact）

在标记-清除的基础上，增加了一步压缩：把存活对象移到一起，消除内存碎片。

压缩前：                         压缩后：
┌──────────────────────┐    ┌──────────────────────┐
│ [A]  [___] [B]  [C] │    │ [A]  [B]  [C]  [___] │
│ [D]  [E]  [___] [F] │    │ [D]  [E]  [F]  [___] │
│ [___] [G]  [___]    │    │ [G]  [___] [___]     │
└──────────────────────┘    └──────────────────────┘
      内存碎片                    规整紧凑

三种算法的对比

维度	标记-清除	复制算法	标记-压缩
速度	中等	最快（只扫描存活对象）	最慢（需要移动对象）
内存利用率	100%（不清除不移动）	50%（每次只用一半）	100%
碎片	有碎片（内存不连续）	无碎片（总是整齐）	无碎片（压缩后规整）
对象移动	不移动	全部复制到另一半	移动存活对象
适用场景	老年代	年轻代（存活对象少）	老年代

复制算法的缺陷

复制算法的最大问题是内存利用率只有 50%。为了解决这个问题，JVM 的实际做法是把年轻代分成 Eden + Survivor：

年轻代的复制算法：
┌──────────────────────────────────────────┐
│                    年轻代                    │
│  ┌─────────┐  ┌────────┐  ┌────────┐   │
│  │  Eden   │  │   S0   │  │   S1   │   │
│  │  (8/10) │  │ (1/10) │  │ (1/10) │   │
│  └─────────┘  └────────┘  └────────┘   │
│                                             │
│  Survivor 只有一个在使用                       │
│  Eden + S0 → S1 → S0 → S1 ...               │
└──────────────────────────────────────────┘

分代收集：算法的组合

JVM 采用分代收集策略，针对不同区域的特性使用不同算法：

区域	对象特点	算法	原因
年轻代（Eden）	大量新对象，绝大多数立即死亡	复制算法	存活对象少，复制开销小
Survivor（S0/S1）	经历过一次 MinorGC 的存活对象	复制算法	同上
老年代	长期存活的对象	标记-清除 / 标记-压缩	存活对象多，复制开销大
G1 Region	按 Region 灵活选择	复制 / 标记-清除	混合策略

算法与 GC 收集器的对应关系

Serial GC
  ├── 年轻代：Serial（复制）
  └── 老年代：Serial Old（标记-压缩）

Throughput GC（Parallel GC）
  ├── 年轻代：Parallel Scavenge（复制）
  └── 老年代：Parallel Old（标记-压缩）

CMS GC
  ├── 年轻代：ParNew（复制）
  └── 老年代：CMS（标记-清除）── 最终触发 Serial Old（标记-压缩）

G1 GC
  ├── 年轻代：Eden → Survivor（复制）
  └── 老年代：Mixed GC（标记-清除 + 复制）

本节小结

GC 三大基本算法：

算法	核心思想	优点	缺点
标记-清除	标记存活对象，清除垃圾	实现简单	产生内存碎片
复制	把存活对象复制到另一半	无碎片，速度快	内存利用率低（50%）
标记-压缩	标记后压缩存活对象	无碎片，利用率高	速度最慢，需要移动对象

分代算法是现代 JVM 的标准做法：年轻代用复制（高效），老年代用标记-清除/压缩（利用率高）。

理解这三种基本算法，是理解所有 GC 收集器的底层基础。

下一节，我们来看 引用计数法（原理/优缺点）。