1

计算Tree的哈希值的最佳方法是什么？

我需要比较O(1)中几棵树之间的相似性。现在，我想预先计算哈希值并在需要时进行比较。但后来我意识到，散列一棵树与散列一个序列是不同的。我无法想出一个好的散列函数。

计算树的哈希值的最佳方法是什么？

注意：我将在 c/c++ 中实现该功能

4

4 回答 4

2

拥有一棵树意味着以独特的方式表示它，以便我们可以使用简单的表示或数字将其他树与这棵树区分开来。在普通多项式哈希中，我们使用数基转换，我们将字符串或序列转换为特定的素数基数，并使用也是一个大素数的 mod 值。现在使用同样的技术，我们可以散列一棵树。

现在将树的根固定在任何顶点。让 root = 1 并且，

B = 我们要转换的基数。

P[i] = B 的 i 次方 (B^i)。

level[i] = 第 i 个顶点的深度，其中（到根的距离）。

child[i] = 包含 i 的第 i 个顶点的子树中的顶点总数。

degree[i] = 顶点 i 的相邻节点数。

现在第 i 个顶点在哈希值中的贡献是 -

哈希[i] = ( (P[level[i]]+degree[i]) * child[i] ) % modVal

而整棵树的哈希值就是所有顶点哈希值的总和——

(hash[1]+hash[2]+....+hash[n]) % modVal

于 2019-10-22T10:38:39.037 回答
1

如果我们使用树等价的这个定义：

T1 等价于 T2 如果所有到 T1 的叶子的路径在 T2 中只存在一次，并且所有到 T2 的叶子的路径在 T2 中只存在一次

散列序列（路径）很简单。如果h_tree(T)是 T 的所有路径到叶子的哈希，其中路径的顺序不会改变结果，那么它是整个 T 的良好哈希，在某种意义上，等效树将产生相等的哈希，根据对上述等价的定义。所以我提议：

h_path(path) = an order-dependent hash of all elements in the path. 
            Requires O(|path|) time to calculate, 
            but child nodes can reuse the calculation of their 
            parent node's h_path in their own calculations.     
h_tree(T) = an order-independent hashing of all its paths-to-leaves. 
            Can be calculated in O(|L|), where L is the number of leaves

在伪 C++ 中：

struct node {
    int path_hash;  // path-to-root hash; only use for building tree_hash
    int tree_hash;  // takes children into account; use to compare trees
    int content;
    vector<node> children;
    int update_hash(int parent_path_hash = 1) {
       path_hash = parent_path_hash * PRIME1 + content;     // order-dependent
       tree_hash = path_hash;
       for (node n : children) {
            tree_hash += n.update_hash(path_hash) * PRIME2; // order-independent
       }
       return tree_hash;
    }
};

构建两棵树后，更新它们的哈希值并进行比较。等效的树应该具有相同的哈希，不同的树没有那么多。请注意，我使用的路径和树哈希相当简单，并且选择它是为了便于编程而不是为了更好的抗碰撞性......

于 2019-10-22T11:28:30.610 回答
0

我建议将树转换为规范序列并对序列进行哈希处理。（转换的细节取决于你对等价的定义。例如，如果树是二叉搜索树并且等价关系是结构的，那么转换可以是按顺序枚举树，因为二叉搜索树的结构可以从前序枚举中恢复。）

乍一看，托马斯的答案归结为将多变量多项式与每棵树相关联并在特定位置评估多项式。目前，有两个步骤必须基于信念进行；第一个是地图不会将不等价的树发送到相同的多项式，第二个是评估方案不会引入太多的冲突。我目前无法评估第一步，尽管有合理的等价定义允许从二变量多项式重建。第二个在理论上并不可靠，但可以通过 Schwartz-Zippel 实现。

于 2013-08-24T14:46:53.080 回答
0

子哈希应该连续乘以素数并相加。节点本身的哈希应该乘以不同的素数并相加。

整体缓存树的哈希——如果我有一个包含 AST 的包装器对象，我更喜欢将它缓存在 AST 节点之外。

public class RequirementsExpr {
    protected RequirementsAST ast;
    protected int hash = -1;

    public int hashCode() {
        if (hash == -1)
            this.hash = ast.hashCode();
        return hash;
    }
}

public class RequirementsAST {
    protected int    nodeType;
    protected Object data;
    // -
    protected RequirementsAST down;
    protected RequirementsAST across;

    public int hashCode() {
        int nodeHash = nodeType;
        nodeHash = (nodeHash * 17) + (data != null ? data.hashCode() : 0);
        nodeHash *= 23;            // prime A.

        int childrenHash = 0;
        for (RequirementsAST child = down; child != null; child = child.getAcross()) {
            childrenHash *= 41;    // prime B.
            childrenHash += child.hashCode();
        }
        int result = nodeHash + childrenHash;
        return result;
    }
}

这样做的结果是，不同位置的子/后代节点总是乘以不同的因子；并且节点本身总是乘以与任何可能的子/后代节点不同的因子。

请注意，其他素数也应用于构建nodeHash节点数据本身。这有助于避免例如。不同的值nodeType与 的不同值发生冲突data。

在 32 位散列的限制内，该方案总体上为树结构（例如，转置两个兄弟）或值的任何差异提供了非常高的唯一性机会。

一旦计算（在整个 AST 上），哈希值就会非常高效。

于 2013-08-24T11:26:00.423 回答