聊聊垃圾回收算法 _算法

其实，对于写代码来说，也有垃圾回收这个问题，这里所说的垃圾，指的是程序中不再需要的内存空间，垃圾回收指的是回收这些不再需要的内存空间，让程序可以重新利用这些释放的内存空间。

那么垃圾回收是怎么，是不采用算法来实现呢？本次课时，我们就一起来探讨 JAVA 的垃圾回收算法。

标记-清除算法（Mark-Sweep）
标记-清除，顾名思义，先标记垃圾，再清除。它是垃圾回收最基础的算法，后续很多算法都是基于它上面去改进的。标记-清除算法主要分成两个阶段：

标记阶段：需要回收的对象。那么这个过程其实就是使用可达性分析去判断一个对象是不是垃圾的过程。

清除阶段：标记完成之后，就会统一清理掉要回收的对象。

用图表示出来大致如下图所示：

文章插图

先去标记哪些对象是存活的，哪些对象是可以回收的。标记完成之后把它回收的对象直接删掉。从这张图可以看出来。标记清除它存在一定的缺点，标记清除后会产生大量不连续的内存碎片，空间碎片太多可能会导致程序在运行过程中需要分配较大对象时，无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。比如现在假设我们想在内存里面分配一段连续三个单位的内存空间，要分配一个超大的字节数组，在这样的内存结构下就没有办法做到了。

标记-整理算法（Mark-compact）
下面来看一下做标记-整理算法，也有一些文章会把它翻译成标记-压缩，本课程里面统一称作是标记-整理算法，那么标记-整理算法是怎玩的。

首先也是标记要回收的对象，这个过程和标记清除是一样的，但是在标记完成之后并不是直接清除掉要回收的对象，而是把所有的存活对象都压缩到内存的一端，最后在清理掉边界之外的所有空间，所以不会产生内存碎片，提高了内存的利用率，这种算法适用于老年代。用图表示出来大概如下图所示：

文章插图
先去标记哪些对象是存活的，哪些对象可以回收，然后把存活的对象往内存的一端压缩，最后再把可以回收的对象除清除。这样就可以避免内存碎片的问题，但是这种方式在标记和整理移动的过程中也是耗时的。

复制算法（Copy）【聊聊垃圾回收算法】
复制算法大致上是这样玩的，把内存分成两块，每次只使用其中的一块，然后把正在使用的这块内存里面的存活对象复制到不使用的内存里面去，然后再清理掉正在使用的这块内存里面的所有对象，接着交换两块内存的角色，等待下一次回收。用图表示大概如下图所示：

文章插图

把一块内存分成了两块，每次只使用其中的一块，在做垃圾回收的时候，把存活的对象移动到另外一端内存里面去，然后清除掉这块内存里面的所有对象。那么在下一次回收的时候也是一样，把存活的对象移动回来，然后清除掉这一块内存里面的所有对象。

三种算法对比
以上是三种比较基础的垃圾回收算法，下面来对比一下这三种算法。

标记-清除算法的优点：实现起来比较简单。

缺点：存在内存碎片。另外使用标记清除算法的时候，分配内存的速度也会受到影响，这是为什么呢？你想，假设现在有一个比较大的对象，因为现在有很多碎片化的内存空间。那么想找到一块连续空间的话，就需要去便利空闲链表，从而值查找哪一块内存可以存放这样的对象。那么在极端场景下，需要把整个链表全部遍历完，才能知道这个对象该分配到哪里去，又或者根本没有办法分配。那么遍历空闲链表是需要时间的，所以分配内存的速度会受到影响。

标记-整理算法的优点：没有碎片。

缺点：整理存在开销。因为标记整理需要把对象集中起来，放到内存的一端，这个过程需要计算以及时间，并且对象越多，占的内存越大，整理的开销也会越大。

复制算法的优点是性能好，没有碎片。一般来讲复制算法比标记-清除算法以及标记-整理算法性能要好一些，因为它不像标记-清除算法或者标记-整理算法那样，需要标记哪些对象是存活的，哪些对象可以回收，而只需要找到存活的对象。然后移动这个存活的对象。所以性能上会有一些优势。