木のハッシュ

目的

衝突しにくい木のハッシュを生成します。

計算量

頂点数を$n$として$O(n)$。

使い方

ArrayList[] g
ハッシュ値を計算したい木の隣接リストを代入してください。
int root
ハッシュ値を計算したい木の根の頂点番号を代入してください。
long hash()
木のハッシュ値をreturn。

参考文献

http://rng-58.blogspot.com/2017/02/hashing-and-probability-of-collision.html

ソースコード

class Tree {
    ArrayList<Integer>[] g;
    int root;
    int[] h;
    long[] rand;
    long p = Long.valueOf(BigInteger.valueOf(500_000_000).nextProbablePrime().toString());
 
    long hash() {
        h = new int[g.length];
        dfs(root, -1);
        int deg = h[root];
        rand = new long[deg + 1];
        rand[0] = 1;
        for (int i = 1; i < rand.length; ++i) {
            rand[i] = Long.valueOf(BigInteger.valueOf(rand[i - 1]).nextProbablePrime().toString());
        }
        long H = dfs2(root, -1);
        return H;
    }
 
    long dfs2(int cur, int par) {
        long ret = 1;
        for (int dst : g[cur]) {
            if (dst == par)
                continue;
            ret *= (rand[h[cur]] + dfs2(dst, cur));
            ret %= p;
        }
        return ret;
    }
 
    void dfs(int cur, int par) {
        for (int dst : g[cur]) {
            if (dst == par) {
                continue;
            }
            dfs(dst, cur);
            h[cur] = Math.max(h[cur], h[dst] + 1);
        }
    }
}