algorithm - 散列树结构

Question

我刚刚在我的项目中遇到一个场景，我需要比较不同的树对象与已知实例的相等性，并且认为在任意树上运行的某种哈希算法会非常有用。

以下面的树为例:

        O       / \      /   \     O     O    /|\    |   / | \   |  O  O  O  O          / \         /   \        O     O

Where each O represents a node of the tree, is an arbitrary object, has has an associated hash function. So the problem reduces to: given the hash code of the nodes of tree structure, and a known structure, what is a decent algorithm for computing a (relatively) collision-free hash code for the entire tree?

A few notes on the properties of the hash function:

• The hash function should depend on the hash code of every node within the tree as well as its position.
• Reordering the children of a node should distinctly change the resulting hash code.
• Reflecting any part of the tree should distinctly change the resulting hash code

If it helps, I'm using C# 4.0 here in my project, though I'm primarily looking for a theoretical solution, so pseudo-code, a description, or code in another imperative language would be fine.

---

UPDATE

Well, here's my own proposed solution. It has been helped much by several of the answers here.

Each node (sub-tree/leaf node) has the following hash function:

public override int GetHashCode()
{
    int hashCode = unchecked((this.Symbol.GetHashCode() * 31 +
        this.Value.GetHashCode()));
    for (int i = 0; i < this.Children.Count; i++)
        hashCode = unchecked(hashCode * 31 + this.Children[i].GetHashCode());
    return hashCode;
}

在我看来，这种方法的优点在于可以缓存哈希码，并且仅在节点或其后代之一发生更改时才重新计算。 (感谢 vatine 和 Jason Orendorff 指出这一点)。

无论如何，如果人们可以在这里对我建议的解决方案发表评论，我将不胜感激 - 如果它能很好地完成工作，那就太好了，否则欢迎任何可能的改进。

Answer 1

如果我要这样做，我可能会做如下事情:

对于每个叶节点，计算 0 和节点数据的散列的串联。

对于每个内部节点，计算 1 和任何本地数据的哈希值(注意:可能不适用)以及从左到右的子节点的哈希值的串联。

每次您更改任何内容时，这都会导致树向上级联，但这可能足够低的开销是值得的。如果与更改量相比更改相对不频繁，则采用加密安全散列甚至可能有意义。

Edit1: 还有可能向每个节点添加“哈希有效”标志并简单地将“假”传播到树中(或“哈希无效”并传播“真”)在节点更改上向上树。这样，就可以在需要树哈希时避免完全重新计算，并可能避免未使用的多个哈希计算，但风险是在需要时获得哈希的可预测时间略有减少。

Edit3: Noldorin 在问题中建议的哈希码看起来有可能发生冲突，如果 GetHashCode 的结果永远为 0。本质上，没有办法区分一个由单个节点组成的树，“符号散列”为 30，“值散列”为 25，还有一个双节点树，其中根的“符号散列”为 0，“值散列”为 30，子节点有总哈希值为 25。这些示例完全是虚构的，我不知道预期的哈希范围是多少，所以我只能评论我在提供的代码中看到的内容。

使用 31 作为乘法常数是好的，因为它会导致在非位边界上发生任何溢出，尽管我认为，如果树中有足够的 child 和可能的对抗性内容，项目的哈希贡献早期散列的可能由后来散列的项目支配。

但是，如果哈希对预期数据的表现不错，看起来它就可以完成这项工作。它肯定比使用加密散列更快(如下面列出的示例代码中所做的那样)。

Edit2:至于具体的算法和所需的最小数据结构，类似下面(Python，翻译成任何其他语言应该相对容易)。

#! /usr/bin/env  pythonimport Crypto.Hash.SHAclass Node:    def __init__ (self, parent=None, contents="", children=[]):        self.valid = False        self.hash = False        self.contents = contents        self.children = children    def append_child (self, child):        self.children.append(child)        self.invalidate()    def invalidate (self):        self.valid = False        if self.parent:            self.parent.invalidate()    def gethash (self):        if self.valid:            return self.hash        digester = crypto.hash.SHA.new()        digester.update(self.contents)        if self.children:            for child in self.children:                digester.update(child.gethash())            self.hash = "1"+digester.hexdigest()        else:            self.hash = "0"+digester.hexdigest()        return self.hash    def setcontents (self):        self.valid = False        return self.contents