内存回收的艺术 加权quick-union算法

在java虚拟机内存回收的时候采用的是可达性分析算法，就是设置一个GCRoot的对象作为起始点，从这个节点开始向下搜索，搜索所走过的路径叫做引用链，当一个对象到GCRoot没有任何引用链链接时，证明此对象是不可达的。这时这个对象就可以被回收了。

下面介绍一下这个可达性分析算法：加权quick-union算法

public class WeightedQuickUnionUF{
    private int[] id;  //节点链接数组
    private int[] sz;  //每个根节点上所对应的分量的大小
    private int count; //连通分量的数量
    
    public WeightedQuickUnionUF(int n){
        count = n;
        id = new int[n];
        for(int i = 0 ; i < n ; i++) id[i] = i;
        sz = new int[n];
        for(int i = 0 ; i < n ; i++) sz[i] = 1;
    }
    
    //树的数量
    public int count(){
        return count;
    }
    
    //判断两个节点是否连通，一般来说直接判断根节点是否与目标节点连通即可
    public boolean connected(int p, int q){
        return find(p) == find(q);
    }
    
    //找到树根节点
    private int find(int p){
        //如果当前的数字不是自身原始位置则说明还没到根节点
        while(p != id[p]){
           p = id[p];
        }
        return p;
    }
    
    //使两个对应的节点连通
    public void union(int p, int q){
        int i = find(p);
        int j = find(q);
        if(i == j)return;
        //将小树的根节点和大树根节点连通
        if(sz[i] < sz[j]){
            id[i] = j;
            sz[j] =+ sz[i];
        }else{
            id[j] = i;
            sz[i] =+ sz[j];
        }
        //集合数量减小
        count--;
    }
    
    //断开某个节点
    public void breakOff(int p){
        //找到上一跳节点
        int root = id(id[p]);
        //修改根节点数量
        sz[root] =- sz[p];
        //断开节点,节点数字还原
        id[p] = p;
        //集合数量增加
        count++;
    }
}```
这是一个树型结构
union方法用于与根节点建立连接
breakOff方法用于断开与跟节点的连接
union() 方法时间复杂度为 lgN
find() 方法时间复杂度为 lgN