メモリ回収の芸術的重み付け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