垃圾回收算法

1. 引用计数(Reference Counting)
    我在面试过程中唯一说出的一种算法就是这个，当时冒出这个念头还是出于我知道Python中的垃圾回收机制是基于引用计数算法的
引用技术算法的原理:
    引用计数，顾名思义，就是每个对象上有个计数器，当添加了一个对它的引用时它的计数器就会加1，当不再使用这个引用时它的计数器就会递减1。当计数器为0的时候则认为该对象是垃圾，可以被回收了。
优点：
    该算法可以平滑的进行垃圾回收，"平滑"的意思是可以在程序运行的过程中不断的进行垃圾回收，而不用使程序挂起，然后再专门进行垃圾回收。后面有其它的算法就是必须使得程序挂起才能进行垃圾回收。
缺陷：
    之前谈到过，该算法的缺点就是要为每个生成的对象维护一个引用计数，不断的更新该计数，这样势必在成时间和空间上的部分开销。这也是我面试过程中回答的一点。不过该算法还有先天性的缺陷，也就是该算法不能解决”循环引用“的问题。所谓循环引用就是两个对象之间互相引用，那么这两个对象的引用计数就不可能为0，也就不能被回收。这跟进程/线程之间的死锁有点类似。可能举个例子更容易理解，下面的一段话是在网上摘抄的：
    比如现在A对象引用B对象，B对象的计数器加1，然后B引用C，C的计数加1，后来C又引用B，B的计数加1得到2。假如现在A不再引用B了，B的计数器成为1。而由于B、C互相引用，形成一个孤岛，但是计数器又没有变成0，又无法回收。（引用自：http://www.cnblogs.com/yuyijq/archive/2011/05/28/2060733.html）

下面的几种算法都属于跟踪算法，为什么叫跟踪算法，看下去就知道了

2.标记-清扫(Mark-Sweep)
    引用技术算法不能解决”循环引用“的问题，那么我们再来看看Mark-sweep算法
Mark-Sweep算法的原理：
    该算法分为两个阶段，第一阶段为标记，该算法遍历所有的对象，然后标记出活动的对象，也就是引用技术算法中的那些引用的计数大于0的对象。第二阶段为清除，既然标记出了活动的对象，那么就可以清除掉剩余的非活动对象的内存空间了。这是我的理解。下面一段话也是引用自上面的链接，觉得说得比较好：
    首先垃圾收集器会确定一些根（root）：比如线程当前正在执行的方法的局部变量，方法参数，以及所在类的实例变量及所有静态变量。然后垃圾收集器会从这些根对象出发查找他们所有的引用，然后在被引用的对象上作标记（mark），当垃圾收集器遇上一个已经被标记的对象后就不再往前走了（避免循环标记，造成死循环）。当标记阶段结束后，所有被标记的对象就称为可达对象（Reachable Object）或活对象（alive Object），而所有没有被标记的对象则被认为是垃圾，可以被回收。这个阶段进行完后就进入了清扫阶段（Sweep Phase）。在清扫阶段，垃圾收集器会从堆的底部开始扫描，然后将没有做标记的对象所占的内存全部回收，比如将这些垃圾添加到一个空闲空间链表。（http://www.cnblogs.com/yuyijq/archive/2011/05/28/2060733.html）
该算法的优点：
    解决了循环引用的问题，节省了引用计数带来的开销
缺陷：
    该算法带来了很大的内存碎片，为什么？试想一下，刚开始的内存很可能是连续分配的，即刚开始的时候，新创建的对象所占内存空间是连续的，但是随着程序的运行，其中的某些对象生命周期结束了，没有被标记为活动对象，那么就要被垃圾回收器回收。这样就造成了大量的内存碎片，在以后重新申请连续的内存时可能会失败。

3.拷贝节点
    该算法的原理很简单，不过简单的东西往往是最有效的，很佩服想出这种算法的大神，膜拜中.
    该算法的原理是将整个堆内存分为两个完全相等的两部分，是容量相等的两部分。为什么是堆内存？这个大家应该都很清楚，因为动态申请的内存都在堆中，栈里的对象不用我们操心，系统会帮我们释放的。首先我们假设整个堆内存分为第一部分和第二部分，程序的所有的动态分配的对象都在第一部分堆内存中，当第一部分内存空间占满时会触发垃圾回收机制，此时利用上面的标记-清除算法的第一步，标记出所有的活动对象，然后将这些活动对象转移到第二部分内存空间。此时第一部分堆内存里的都是非活动对象，可以回收这些对象了。等到第二部分堆内存满了，再将活动对象转移到第一部分堆内存，这样不断循环下去，直到整个程序结束，这就是该算法的核心思想，是不是觉得很奇妙，再次膜拜该算法的发明者。
优点：
    该算法实现简单而且很好的解决了Mark-Sweep算法中的内存碎片问题，因为整个堆内存就分为两部分，程序的所有活动对象就是在这两个完整的堆内存中不断转移。
缺点：
    没有最好，只有更好，该算法仍然存在缺陷，很多人认为这个缺陷还很大，既然程序将堆内存非为了两个相等的部分，程序只运行在其中一部分的堆内存中，那么总是存在着一部分堆内势必空闲，这样的代价就是减少了内存空间，而且对内存的利用率减少了一半，代价确实很大。

本文只是介绍了三种最基本最经典的几种垃圾回收算法，其它的垃圾回收算法笔者还没有了解，以后有时间再补充。