1.3.3　標(biāo)記清除

從根集合出發(fā)，遍歷對象，把活躍對象入棧，并依次處理。處理方式可以是廣度優(yōu)先搜索也可以是深度優(yōu)先搜索（通常使用深度優(yōu)先搜索，節(jié)約內(nèi)存）。標(biāo)記出活躍對象之后，就可以把不活躍對象清除。下面演示一個簡單的例子，從根集合出發(fā)查找堆空間的活躍對象，如圖1-3所示。

圖1-3　標(biāo)記清除算法

這里僅僅演示了如何找到對象，沒有進(jìn)一步介紹找到對象后如何處理。對于標(biāo)記清除算法其實還需要額外的數(shù)據(jù)結(jié)構(gòu)（比如一個鏈表）來記錄可用空間，在對象分配的時候從這個鏈表中尋找能夠容納對象的空間。當(dāng)然這里還有很多細(xì)節(jié)都未涉及，比如在分配時如何找到最合適的內(nèi)存空間，有First Fit、Best Fit和Worst Fit等方法，這里不再贅述。標(biāo)記清除算法最大的缺點就是使內(nèi)存碎片化。