树哈希

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

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

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

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

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

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

1
2
3
4
5
6
7
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;
}