树哈希 | 爱飞鱼的blog

title: 树哈希
categories:

树哈希

考虑这样一种哈希方式。对于一棵以 𝑎为根的子树，假设儿子是$ v_1, v_2, \cdots, v_k$，定义子树的哈希 $h(a)=1+\sum_{1\le i\le k} f(h(v_i))$ 。其中 $h(v_i)$ 是 $v_i$ 对应子树的哈希， $f$ 为一个待定函数。

可以证明：如果 $f$ 为随机函数，这样的哈希在自然溢出下的期望冲突数不超过 $O(n^2/2^w)$ 。只需考虑最深的一对冲突点即可。

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

实践中，我们并不能取一个真正的随机函数当 $f$ 。但事实上，没有特殊性质的 $f$ 几乎都卡不掉；因为随便找个 $f$ 大概率很随机。

有一些反例：如果 $f$ 取多项式，可能因为一直保持 $2^k$ 同余关系而白给。但是经过我的实验，似乎只要扰动一下改掉这个性质即可。例如下述函数：

ll h(ll x) {
    return x * x * x * 1237123 + 19260817;
}
ll f(ll x) {
    ll cur = h(x & ((1 << 31) - 1)) + h(x >> 31);
    return cur;
}