前言

相比于前面三種垃圾收集算法，引用計數(shù)算法算是實現(xiàn)最簡單的了，它只需要一個簡單的遞歸即可實現(xiàn)?，F(xiàn)代編程語言比如Lisp，Python，Ruby等的垃圾收集算法采用的就是引用計數(shù)算法?，F(xiàn)在就讓我們來看下引用計數(shù)算法(reference counting)是如何工作的。

算法原理

引用計數(shù)算法很簡單，它實際上是通過在對象頭中分配一個空間來保存該對象被引用的次數(shù)。如果該對象被其它對象引用，則它的引用計數(shù)加一，如果刪除對該對象的引用，那么它的引用計數(shù)就減一，當該對象的引用計數(shù)為0時，那么該對象就會被回收。

比如說，當我們編寫以下代碼時，

String p = new String("abc")

abc這個字符串對象的引用計數(shù)值為1.

而當我們?nèi)コ齛bc字符串對象的引用時，則abc字符串對象的引用計數(shù)減1

p = null

由此可見，當對象的引用計數(shù)為0時，垃圾回收就發(fā)生了。這跟前面三種垃圾收集算法不同，前面三種垃圾收集都是在為新對象分配內(nèi)存空間時由于內(nèi)存空間不足而觸發(fā)的，而且垃圾收集是針對整個堆中的所有對象進行的。而引用計數(shù)垃圾收集機制不一樣，它只是在引用計數(shù)變化為0時即刻發(fā)生，而且只針對某一個對象以及它所依賴的其它對象。所以，我們一般也稱呼引用計數(shù)垃圾收集為直接的垃圾收集機制，而前面三種都屬于間接的垃圾收集機制。

而采用引用計數(shù)的垃圾收集機制跟前面三種垃圾收集機制最大的不同在于，垃圾收集的開銷被分攤到整個應用程序的運行當中了，而不是在進行垃圾收集時，要掛起整個應用的運行，直到對堆中所有對象的處理都結(jié)束。因此，采用引用計數(shù)的垃圾收集不屬于嚴格意義上的"Stop-The-World"的垃圾收集機制。這個也可以從它的偽代碼實現(xiàn)中看出：

New(): //分配內(nèi)存
    ref <- allocate()
    if ref == null
        error "Out of memory"
    rc(ref) <- 0  //將ref的引用計數(shù)(reference counting)設(shè)置為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的引用計數(shù)為0，則表明其將要被回收
            for each fld in Pointers(ref)
                deleteReference(*fld)
            free(ref) //釋放ref指向的內(nèi)存空間

對于上面的偽代碼，重點在于理解兩點，第一個是當對象的引用發(fā)生變化時，比如說將對象重新賦值給新的變量等，對象的引用計數(shù)如何變化。假設(shè)我們有兩個變量p和q，它們分別指向不同的對象，當我們將他們指向同一個對象時，下面的圖展示了p和q變量指向的兩個對象的引用計數(shù)的變化。

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

當我們執(zhí)行代碼p=q時，實際上相當于調(diào)用了偽代碼中的Write(p,q)， 即對p原先指向的對象要進行deleteReference()操作 - 引用計數(shù)減一，因為p變量不再指向該對象了，而對q原先指向的對象要進行addReference()操作 - 引用計數(shù)加一。

第二點需要理解的是，當某個對象的引用計數(shù)減為0時，collector需要遞歸遍歷它所指向的所有域，將它所有域所指向的對象的引用計數(shù)都減一，然后才能回收當前對象。在遞歸過程中，引用計數(shù)為0的對象也都將被回收，比如說下圖中的phone和address指向的對象。

環(huán)形數(shù)據(jù)問題

但是這種引用計數(shù)算法有一個比較大的問題，那就是它不能處理環(huán)形數(shù)據(jù) - 即如果有兩個對象相互引用，那么這兩個對象就不能被回收，因為它們的引用計數(shù)始終為1。這也就是我們常說的“內(nèi)存泄漏”問題。比如下圖展示的將p變量賦值為null值后所出現(xiàn)的內(nèi)存泄漏。

后記

到今天為止，四種基本的垃圾收集算法就都介紹完了。每種算法都有它自己的優(yōu)點和缺點。同時每種基本算法還有它自己的優(yōu)化算法，但是在這里我只專注于介紹基本的原理，讓大家知道它們是怎么工作的，對于它們的優(yōu)化算法，大家可以自己查閱資料進行學習。后面我們會來看下這幾種基本垃圾收集算法怎么組合成更加高級的垃圾收集算法，比如說分代垃圾收集算法等。