计算 Tree 的哈希值的最佳方法是什么? ?
我需要在O(1)中比较几棵树之间的相似度。现在,我想预先计算哈希值并在需要时比较它们。但后来我意识到,散列树与散列序列不同。我无法想出一个好的哈希函数。
计算树的哈希值的最佳方法是什么?
注意:我将用 c/c++ 实现该函数
最佳答案
拥有一棵树意味着以独特的方式表示它,这样我们就可以使用简单的表示或数字将其他树与这棵树区分开来。在普通多项式哈希上,我们使用数基转换,将字符串或序列转换为特定素数基数,并使用也是大素数的 mod 值。现在使用相同的技术我们可以对树进行哈希处理。
现在将树的根固定在任意顶点。设 root = 1 并且,
B = 我们要转换的基数。
P[i] = B 的 i 次方 (B^i)。
level[i] = 第 i 个顶点的深度(距根的距离)。
child[i] = 第 i 个顶点的子树中包含 i 的顶点总数。
Degree[i] = 顶点 i 的相邻节点数。
现在第 i 个顶点对哈希值的贡献是 -
hash[i] = ( (P[level[i]]+ Degree[i]) * child[i] ) % modVal
而整棵树的哈希值就是所有顶点哈希值的总和 -
(哈希[1]+哈希[2]+....+哈希[n]) % modVal
关于algorithm - 如何计算树的哈希值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18418004/