3.3 垃圾收集算法
此书并不过多讨论算法实现，只对理论和思想进行讲述，若有兴趣的话推荐阅读Richard Jones撰写的《垃圾回收算法手册》。
（3.1）分代收集理论
- 弱分代假说（Weak Generational Hypothesis） ： 绝大多数对象都是朝生夕灭的。
- 强分代假说（Strong Generational Hypothesis） ： 熬过越多次垃圾收集过程的对象就越难以消亡。
- 跨代引用假说（ Intergenerational Reference Hypothesis） ： 跨代引用相对于同代引用来说仅占极少数。
根据如上两种假说，我们可以简单的将弱分代的认为是新生代，强分代认为是老年代和方法区，让垃圾收集器根据不同的区域去实行不同的收集算法，从而达到效率的最大化。
由此演变出来如“标记-复制算法”“标记-清除算法”“标记-整理算法”等针对性的垃圾收集算法。
由于跨代引用导致不得不在固定的GC Roots之外， 再额外遍历整个老年代（新生代）中所有对象来确保新生代（老年代）可达性分析结果的正确性，这样无疑是灾难性的，于是虚拟机就在新生代上建立了一个全局的数据结构（ 该结构被称为“记忆集”， Remembered Set） ， 以此来标记老年代的部分内存区域，当再次发生新生代GC的时候只额外遍历标记内存立的对象即可，即采用空间换时间。
此处出现分代的理论，作者为避免读者产生混淆， 在这里统一定义：
- 部分收集（ Partial GC） ： 指目标不是完整收集整个Java堆的垃圾收集， 其中又分为：
- 新生代收集（ Minor GC/Young GC） ： 指目标只是新生代的垃圾收集。
- 老年代收集（ Major GC/Old GC） ： 指目标只是老年代的垃圾收集。 目前只有CMS收集器会有单独收集老年代的行为。 另外请注意“Major GC”这个说法现在有点混淆， 在不同资料上常有不同所指，读者需按上下文区分到底是指老年代的收集还是整堆收集。
- 混合收集（ Mixed GC） ： 指目标是收集整个新生代以及部分老年代的垃圾收集。 目前只有G1收集器会有这种行为。
- 整堆收集（ Full GC） ： 收集整个Java堆和方法区的垃圾收集。
（3.2）标记 - 清除算法（Mark - Sweep）
算法分为“标记”和“清除”两个阶段： 首先标记出所有需要回收的对象， 在标记完成后， 统一回收掉所有被标记的对象， 也可以反过来， 标记存活的对象， 统一回收所有未被标记的对象。
★ 缺点
(1). 执行效率不稳定， 如果Java堆中包含大量对象， 而且其中大部分是需要被回收的， 这时必须进行大量标记和清除的动作， 导致标记和清除两个过程的执行效率都随对象数量增长而降低；
(2). 内存空间的碎片化， 标记、 清除之后会产生大量不连续的内存碎片， 空间碎片太多可能会导致当以后在程序运行过程中需要分配较大对象时无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。
（3.2）标记 - 复制算法（Mark - Copy）
算法将可用内存按容量划分为大小相等的两块， 每次只使用其中的一块。 当这一块的内存用完了， 就将还存活着的对象复制到另外一块上面， 然后再把已使用过的内存空间一次清理掉。
★ 优点
在分配内存时可以进行指针碰撞，大大提高分配效率。
★ 缺点
(1). 若存活的对象的数据较大，将会产生大量的内存间复制的开销。
(2). 空间浪费太大。
（3.3）标记-整理算法（Mark-Compact）
标记整理算法的标记与“标记-清除算法”的相同，但是后续步骤不是直接对可回收对象进行清理， 而是让所有存活的对象都向内存空间一端移动， 然后直接清理掉边界以外的内存。
此算法在移动存活对象并更新所有引用这些对象的地方将会是一种极为负重的操作， 而且这种对象移动操作必须全程暂停用户应用程序才能进行。
至此我们可以知道，进行整理和不整理都会有各自的弊端，移动则内存回收时会更复杂， 不移动则内存分配时会更复杂。
此时我们引入一个新的概念吞吐量=赋值器效率+收集器效率。根据吞吐量来看，进行对象移动的情况下总体的吞吐量效果是大于不进行移动的情况的。HotSpot虚拟机里面关注吞吐量的ParallelScavenge收集器是基于标记-整理算法的， 而关注延迟的CMS收集器则是基于标记-清除算法的。
另外， 还有一种“和稀泥式”解决方案可以不在内存分配和访问上增加太大额外负担， 做法是让虚拟机平时多数时间都采用标记-清除算法， 暂时容忍内存碎片的存在， 直到内存空间的碎片化程度已经大到影响对象分配时， 再采用标记-整理算法收集一次， 以获得规整的内存空间。 前面提到的基于标
记-清除算法的CMS收集器面临空间碎片过多时采用的就是这种处理办法。