前言

相比于前面三种垃圾收集算法，引用计数算法算是实现最简单的了，它只需要一个简单的递归即可实现。现代编程语言比如Lisp，Python，Ruby等的垃圾收集算法采用的就是引用计数算法。现在就让我们来看下引用计数算法(reference counting)是如何工作的。

算法原理

引用计数算法很简单，它实际上是通过在对象头中分配一个空间来保存该对象被引用的次数。如果该对象被其它对象引用，则它的引用计数加一，如果删除对该对象的引用，那么它的引用计数就减一，当该对象的引用计数为0时，那么该对象就会被回收。

比如说，当我们编写以下代码时，

String p = new String("abc")


abc这个字符串对象的引用计数值为1.

 



 

而当我们去除abc字符串对象的引用时，则abc字符串对象的引用计数减1

p = null




由此可见，当对象的引用计数为0时，垃圾回收就发生了。这跟前面三种垃圾收集算法不同，前面三种垃圾收集都是在为新对象分配内存空间时由于内存空间不足而触发的，而且垃圾收集是针对整个堆中的所有对象进行的。而引用计数垃圾收集机制不一样，它只是在引用计数变化为0时即刻发生，而且只针对某一个对象以及它所依赖的其它对象。所以，我们一般也称呼引用计数垃圾收集为直接的垃圾收集机制，而前面三种都属于间接的垃圾收集机制。

而采用引用计数的垃圾收集机制跟前面三种垃圾收集机制最大的不同在于，垃圾收集的开销被分摊到整个应用程序的运行当中了，而不是在进行垃圾收集时，要挂起整个应用的运行，直到对堆中所有对象的处理都结束。因此，采用引用计数的垃圾收集不属于严格意义上的"Stop-The-World"的垃圾收集机制。这个也可以从它的伪代码实现中看出：

New(): //分配内存
    ref <- allocate()
    if ref == null
        error "Out of memory"
    rc(ref) <- 0  //将ref的引用计数(reference counting)设置为0
    return ref

atomic Write(dest, ref) //更新对象的引用
    addReference(ref)
    deleteReference(dest)
    dest <- ref

addReference(ref):
    if ref != null
        rc(ref) <- rc(ref)+1
        
deleteReference(ref):
    if ref != null
        rc(ref) <- rc(ref) -1
        if rc(ref) == 0 //如果当前ref的引用计数为0，则表明其将要被回收
            for each fld in Pointers(ref)
                deleteReference(*fld)
            free(ref) //释放ref指向的内存空间


对于上面的伪代码，重点在于理解两点，第一个是当对象的引用发生变化时，比如说将对象重新赋值给新的变量等，对象的引用计数如何变化。假设我们有两个变量p和q，它们分别指向不同的对象，当我们将他们指向同一个对象时，下面的图展示了p和q变量指向的两个对象的引用计数的变化。

String p = new String("abc")
String q = new String("def")
p = q


当我们执行代码p=q时，实际上相当于调用了伪代码中的Write(p,q)， 即对p原先指向的对象要进行deleteReference()操作 - 引用计数减一，因为p变量不再指向该对象了，而对q原先指向的对象要进行addReference()操作 - 引用计数加一。



第二点需要理解的是，当某个对象的引用计数减为0时，collector需要递归遍历它所指向的所有域，将它所有域所指向的对象的引用计数都减一，然后才能回收当前对象。在递归过程中，引用计数为0的对象也都将被回收，比如说下图中的phone和address指向的对象。



环形数据问题

但是这种引用计数算法有一个比较大的问题，那就是它不能处理环形数据 - 即如果有两个对象相互引用，那么这两个对象就不能被回收，因为它们的引用计数始终为1。这也就是我们常说的“内存泄漏”问题。比如下图展示的将p变量赋值为null值后所出现的内存泄漏。



后记

到今天为止，四种基本的垃圾收集算法就都介绍完了。每种算法都有它自己的优点和缺点。同时每种基本算法还有它自己的优化算法，但是在这里我只专注于介绍基本的原理，让大家知道它们是怎么工作的，对于它们的优化算法，大家可以自己查阅资料进行学习。后面我们会来看下这几种基本垃圾收集算法怎么组合成更加高级的垃圾收集算法，比如说分代垃圾收集算法等。

 

如何判断对象是否存活
引用计数法
概念
引用计数法就是如果一个对象没有被任何引用指向，则可视之为垃圾。这种方法的缺点就是不能检测到环的存在。
首先需要声明，至少主流的Java虚拟机里面都没有选用引用计数算法来管理内存。
什么是引用计数算法：
给对象中添加一个引用计数器，每当有一个地方引用它时，计数器值加１；
当引用失效时，计数器值减１.任何时刻计数器值为０的对象就是不可能再被使用的。
那为什么主流的Java虚拟机里面都没有选用这种算法呢？
其中最主要的原因是它很难解决对象之间相互循环引用的问题。
根搜索算法
概念
这个算法的基本思想是通过一系列称为“GC Roots”的对象作为起始点，从这些节点向下搜索，搜索所走过的路径称为引用链，当一个对象到GC Roots没有任何引用链(即GC Roots到对象不可达)时，则证明此对象是不可用的。
那么问题又来了，如何选取GCRoots对象呢？
在Java语言中，可以作为GCRoots的对象包括下面几种：
(1). 虚拟机栈(栈帧中的局部变量区，也叫做局部变量表)中引用的对象。
(2). 方法区中的类静态属性引用的对象。
(3). 方法区中常量引用的对象。
(4). 本地方法栈中JNI(Native方法)引用的对象。
下面给出一个GCRoots的例子，如下图，为GCRoots的引用链。
举例分析，看下面的图：
根搜索算法的基本思路就是通过一系列名为”GC Roots”的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链(Reference Chain)，当一个对象到GC Roots没有任何引用链相连时，则证明此对象是不可用的。
从上图，reference1、reference2、reference3都是GC Roots，可以看出：
reference1-> 对象实例1；
reference2-> 对象实例2；
reference3-> 对象实例4；
reference3-> 对象实例4 -> 对象实例6；
可以得出对象实例1、2、4、6都具有GC Roots可达性，也就是存活对象，不能被GC回收的对象。
而对于对象实例3、5直接虽然连通，但并没有任何一个GC Roots与之相连，这便是GC Roots不可达的对象，这就是GC需要回收的垃圾对象。
引用计数法 已经被淘汰了!因为循环依赖问题!
A a = new A()    每个对象有个年龄 大于了一定年龄(15) 存放老年代 否则 新生代
GC线程不定时进行回收，如果对象被应用的话，年龄就+1，如果没有被继续回收则-1
如果年龄为0的话，被回收
循环依赖问题：
A a = new A()
B b = new B()
a.x=b
b.x=a
a=null
b=null
很难判断 然后 怎么去标记为0  去回收
根搜索算法  GCRoots 没有和GCRoots  需要和根节点有依赖关系 如果没有和GCRoots有任何引用关系情况，GC认为不可达对象。
遍历一遍看看 与GCRoots有引用没
只有 user3和user5 不可达 。

引用计数算法
导语
什么是引用计数算法
两种实现方式
算法优点
算法劣势

导语
引用计数算法作为垃圾收集器最早的算法，只需要一个简单的递归就可以实现，有一定优势，也有一定的劣势。JVM不再采用引用计数算法进行垃圾回收，但是这种算法并未被淘汰，在著名的Redis中依然使用。
什么是引用计数算法
对于创建的每一个对象都有一个相关联的计数器，这个计数器记录着该对象被引用的次数，垃圾收集器进行垃圾回收时，对扫描到的每个对象都要判断下该对象计数器是否为0，若为0就会释放该对象的内存空间。这里要注意：遍历该对象属性引用相应的计数都要减一。
伪代码实现
new():分配内存
	ref <- allocate()
	if ref == null
		error "out of memory"
	rc(ref) <- 0 //将ref的引用计数（reference counting） 设置为0
	return ref

atomic write(dest,ref) //更新对象的引用
	addReference(ref)
	deleteReference(dest)
	dest <- ref

addReference(ref):
	if ref != null 
		rc(ref) <- rc(ref)+1
		
deleteReference(ref):
	if ref != null
		rc(ref) <- rc(ref)-1
		if rc(ref) == 0 //如果当前ref的应用计数为0，则表明其将被回收
			for each fld in Pointers(ref)
				deleteReference(*fld)
			free(ref) //释放ref的内存空间

Java代码示例
String p = new String("abc")
String q = new String("def")
p = q

当我们执行代码p=q时，实际上相当于调用了伪代码中的write(p,q)方法，即对p原先指向的对象要进行deleteReference()操作-引用计数减一，原因是p变量不在指向该对象。对于q引用的对象要进行addReference()操作-引用计数加一。
两种实现方式
侵入式与非侵入式，引用计数算法的垃圾收集一般分为侵入式和非侵入式。侵入式的实现方式是将引用计数器直接根植在对象内部，用C++的思想进行解释是，在对象的构造或者拷贝构造中进行加一操作，在对象的析构中进行减一操作，非侵入式思想就是有一块单独的内存空间用于对象的引用计数器。
算法优点
使用引用计数器，内存回收可以穿插在程序中运行，在程序运行中，但发现某一对象的引用计数器为0时，可以立即对该对象所占的内存空间进行回收，这种方式可以避免FULL GC带来的程序暂停。
算法劣势
采用引用计数算法进行垃圾回收，最大的缺点是不能解决循环引用的问题。例如一个父对象持有一个子对象的引用，子对象也持有父对象的引用，这种情况下父子对象将会一直存储在JVM堆中，无法进行回收。

参考资料一

参考资料二

主流的Java虚拟机里面没有选用引用计数算法来管理内存的，最主要的原因是它很难解决对象之间循环引用的问题。
/**
* testGC()方法执行后，objA和objB会不会被GC呢？
*/
public class ReferenceCountingGC {
public Object instance = null;
private static final int _1MB = 1024 * 1024;
/**
* 这个成员属性的唯一意义就是占点内存，以便在能在GC日志中看清楚是否有回收过
*/
private byte[] bigSize = new byte[2 * _1MB];
public static void testGC() {
ReferenceCountingGC objA = new ReferenceCountingGC();
ReferenceCountingGC objB = new ReferenceCountingGC();
objA.instance = objB;
objB.instance = objA;
objA = null;
objB = null;
// 假设在这行发生GC，objA和objB是否能被回收？
System.gc();
}
}
以上代码运行后GC日志中包含“4603k->210k”,说明虚拟机并没有因为这两个对象互相引用就不回收它们，侧面说明并不是通过引用计数算法来判断对象是否存活的。
Java中把对象的引用状态分为四种：
1.强引用
只要强引用在，垃圾收集器永远不会回收掉被引用的对象。
2.软引用
在系统将要发生内存溢出之前，回收这些对象，如果回收掉之后还没有足够的内存，才会抛出内存溢出异常。
3.弱引用
被弱引用关联的对象只能生存到下一次垃圾收集发生之前。
4.虚引用
无法通过虚引用来获取一个对象实例。为一个对象设置一个虚引用关联的唯一目的就是能在这个对象被收集器回收时收到一个系统通知。