引用計數(shù)算法
很多教科書判斷對象是否存活的算法是這樣的:給對象中添加一個引用計數(shù)器,每當有一個地方引用它時,計數(shù)器值就加1;當引用失效時,計數(shù)器值就減1;任何時刻計數(shù)器為0的對象就是不可能再被使用的义图。作者面試過很多的應屆生和一些有多年工作經(jīng)驗的開發(fā)人員,他們對于這個問題給予的都是這個答案摇展。
客觀地說,引用計數(shù)算法(ReferenceCounting)的實現(xiàn)簡單,判定效率也很高,在大部分情況下它都是一個不錯的算法,也有一些比較著名的應用案例,例如微軟公司的COM(Component Object Model)技術(shù)尤慰、使用ActionScript 3的FlashPlayer种樱、Python語言和在游戲腳本領域被廣泛應用的Squirrel中都使用了引用計數(shù)算法進行內(nèi)存管理舍咖。但是,至少主流的Java虛擬機里面沒有選用引用計數(shù)算法來管理內(nèi)存,其中最主要的原因是它很難解決對象之間相互循環(huán)引用的問題蚓庭。
可達性分析算法
在主流的商用程序語言(Java娇跟、C#,甚至包括前面提到的古老的Lisp)的主流實現(xiàn)中,都是稱通過可達性分析(Reachability Analysis)來判定對象是否存活的僻爽。這個算法的基本思路就是通過一系列的稱“GC Roots”的對象作為起始點,從這些節(jié)點開始向下搜索,搜索所走過的路徑稱為引用鏈(Reference hain),當一個對象到GCRoots沒有任何引用鏈相連(用圖論的話來說,就是從GC Roots到這個對象不可達)時,則證明此對象是不可用的。
