树哈希

· · 算法·理论

一种好写且卡不掉的树哈希

定义子树的 hash 值为：h_x=\sum\limits_{y\in son(x)} gf(h_y)

其中 gf(x) 是一个随机函数。

“可以证明：如果 gf(x) 为随机函数，这样的哈希在自然溢出下的期望冲突数不超过 O(n^2/2^w)。”

“上述哈希最大的优势是好写。如果需要换根，第二次 dp 时只需把子树哈希减掉即可。”

inline ull H_value(ull x) {
    return x*x*x*1237123+1000010101;
}

inline ull gf(ull x) {
    return H_value(x&((1ull<<31)-1))+H_value(x>>31);
}

1000010101 是质数耶。