树哈希常用的方式

树哈希，顾名思义，对树进行哈希，经常判断两个树是否同构。一下均为对有根树的算法，而无根树只需要找重心。

我们有时需要判断一些树是否同构。这时，选择恰当的哈希方式来将树映射成一个便于储存的哈希值（一般是 32 位或 64 位整数）是一个优秀的方案。

树哈希有很多种哈希方式，下面将选出几种较为常用的方式来加以介绍。

方法一

公式

注意：

其中为以节点 x 为根的子树对应的哈希值。特殊地，我们令叶子节点的哈希值为 1。

表示以节点 x 为根的子树大小。

表示 x 所有子节点以 f 作为关键字排序后排名第 i 的儿子。

为选定的一个合适的种子（最好是质数，对字符串 hash 有了解的人一定不陌生）

上述哈希过程中，可以适当取模避免溢出或加快运行速度。

Hack

上图中，可以计算出两棵树的哈希值均为。

方法二

公式

注意：

其中为以节点 x 为根的子树对应的哈希值。特殊地，我们令叶子节点的哈希值为 1。

表示以节点 x 为根的子树大小。

表示 x 所有子节点之一（不用排序）。

为选定的一个合适的质数。

表示异或和。

Hack

由于异或的性质，如果一个节点下有多棵本质相同的子树，这种哈希值将无法分辨该种子树出现1,3,5,…次的情况。

方法三

公式

注意：

其中为以节点 x 为根的子树对应的哈希值。

表示以节点 x 为根的子树大小。

表示 x 所有子节点之一（不用排序）。

表示第 i 个质数。

事实上，树哈希是可以很灵活的，可以有各种各样奇怪的姿势来进行 hash，只需保证充分性与必要性，选手完全可以设计出与上述方式不同的 hash 方式。