在使用MAT分析项目的内存泄漏问题时,其中有一个支配树(Dominator)视图。如果我们把Java对象之间的引用关系看做一张有向图(可以存在环)的话,对象的支配树体现了对象之间的支配关系。如果所有指向对象B的路径都要经过对象A,则认为对象A支配对象B。如果对象A是离对象B最近的支配对象,则认为对象A是对象B的直接支配者。
除起始节点外都有每个点都有唯一的idom(直接支配者),且不成环,故所有的 (idom(w),w) 边形成一棵树,v支配w当且仅当v是树中w的祖先,这棵树叫做支配树。
可以用来求深堆的大小。这里解释一下浅堆和深堆:
从支配树的性质可以看出,如果释放对象A,则对象A对应的支配树上的子树都将被释放,因为子树上的对象都不可达了,应该被GC回收。所以支配树上某个对象节点的子树上所有对象的大小就是该对象的深堆大小。
使用 “迭代+DFS”方法实现。时间复杂度是O(mn)。
Lengauer-Tarjan算法可以在更优的时间复杂度下求解有向图的支配树。