1.3.3　标记清除

从根集合出发，遍历对象，把活跃对象入栈，并依次处理。处理方式可以是广度优先搜索也可以是深度优先搜索（通常使用深度优先搜索，节约内存）。标记出活跃对象之后，就可以把不活跃对象清除。下面演示一个简单的例子，从根集合出发查找堆空间的活跃对象，如图1-3所示。

图1-3　标记清除算法

这里仅仅演示了如何找到对象，没有进一步介绍找到对象后如何处理。对于标记清除算法其实还需要额外的数据结构（比如一个链表）来记录可用空间，在对象分配的时候从这个链表中寻找能够容纳对象的空间。当然这里还有很多细节都未涉及，比如在分配时如何找到最合适的内存空间，有First Fit、Best Fit和Worst Fit等方法，这里不再赘述。标记清除算法最大的缺点就是使内存碎片化。