垃圾回收算法与思想

引用计数法（Reference Counting）：

引用计数法是最经典也是最古老的的一种垃圾收集算法，大致思想是：为每一个对象配备计数器，如果有引用就+1，如果引用失效就-1，如果某个对象的计数器为0，说明没有引用，则可以被回收。

但是引用计数法有一个显著的缺点就是无法回收循环引用的对象，例如有A和B两个对象，两者相互调用，但是这两个对象除了相互调用外，没有被其他任何一个对象调用，但是因为相互调用，计数器不为0，所以不会被回收，这就可能会导致内存泄漏。

标记-清除算法(Mark-Sweep):

标记-清除算法是现代垃圾回收算法的基础思想，标记-清除算法将垃圾回收分为两个阶段，一个是标记阶段，另外一个是清楚阶段，

标记阶段：从根节点开始，标记所有从跟节点到可达到的对象，未标记的对象就是没有别引用的对象。

清除阶段：清除所有未被标记的对象。

标记-清除算法最大的问题就是空间碎片，垃圾回收之后，空间是不连续的，在对象的堆空间分配过程中，尤其是大对象，不连续的内存空间的工作效率低于连续的。

复制算法（Copying）

复制算法是一种相对比较高效的算法，主要思想是：将内存空间分为大小相等的两部分，每次只是用一块，在垃圾回收的时候，将正在是用的那一块空间中的引用对象复制到另外一块中，然后清除正在使用的那一块空间的所有对象，交换两个内存的角色，完成垃圾回收。

优点是回收过后的内存空间没有碎片。

缺点是内存折半，复制大量的对象。

Java的新生代串行垃圾回收器用的就是这个算法。新生代分为eden,from space, to space三个部分，from space 和 to space是大小相等，地位相等，可进行角色互换的空间块。

在垃圾回收时，eden中的存活对象会被复制到未使用的survivor中（假设是to space）,正在使用的存活对象也会从from space复制到to space中，eden 和 from space留下来的是未被使用的对象，被直接清空，to space存放复制过后的存活对象。

标记-压缩算法（Mark-Compact）

复制算法的高效性是建立在存活对象少，垃圾对象多的情况，如新生代。但是如果是老年代的话，复制成本过高，则就不适用了。

标记-压缩算法是一种老年代的回收算法，它是在标记-清除算法的基础上做了一些优化，如标记-清除一样，首先也是从根节点开始，对所有可达对象进行标记，但是不同的是，标记-压缩会将存活对象压缩到内存的一端，然后清理边界外的所有空间，这样的好处是不用两块内存相同的空间和避免了空间碎片。

增量算法(Incremental Collecting)

对大部分垃圾回收算法而言，在进行垃圾回收期间，我们的应用程序是处于挂起的状态，也称之为Stop the World状态，但是如果垃圾回收的时间过长的话，则应用程序挂起时间会很久，这样会严重影响用户体验和系统的稳定性。

增量算法的基本思想是，如果一次性将所有的垃圾进行回收，需要造成系统长时间的停顿，那么就可以想到一个折中的办法，让垃圾回收线程和应用程序线程交替运行，垃圾回收线程只回收一小部分内存，然后就切换到应用程序线程，如此反复，直到执行完垃圾回收。在垃圾回收过程中，还执行了应用程序的代码，这样减少了系统停顿的时间，但是因为垃圾回收线程和上下文线程的切换的消耗，造成了垃圾回收成本的增加，从而导致了系统吞吐量的下降。

分代算法(Generational Collecting)

标记-清除，复制，标记-压缩等算法，在这些算法中，并没有一种算法完全代替其他算法，它们都就有各自的优势和特点。

因此，根据回收对象的特点，选择合适的回收算法，才是明智的选择。

分代就是基于这样的思想，它将内存区间根据对象的特点进行划分，然后根据各个内存区间的特点，使用不同的垃圾回收算法，提高垃圾回收效率。

以Hot Spot为例，它将所有新建的对象都放入称为新生代的内存区域，新生代的特点是对象朝生夕灭，大约90%对象都会被回收，因此新生代就适用用高效的复制算法；经过几次垃圾回收依然存活的对象，就会保存在老年代中，老年代中几乎所有的对象都是经过几次垃圾回收依然幸存的，在一段时间内，甚至应用程序整个生命周期，都是内存常驻的。对于老年代，因为大部分对象是存活的，所以采用复制算法的话，是不可取的，采用标记-压缩算法才是高效的。