散列树结构

一尘不染

散列树结构

algorithm

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

以下面的树为例：

        Ø
       / \
      / \
     面向对象
    / | \ |
   / | \ |
  OOOO
          / \
         / \
        面向对象

其中每个O代表树的节点，是一个任意对象，具有关联的哈希函数。因此问题减少到：给定树结构的节点的哈希码和已知的结构，一种用于计算整个树的（相对）无冲突哈希码的不错的算法是什么？

有关哈希函数属性的一些说明：

哈希函数应取决于树中每个节点的哈希码及其位置。
对节点的子节点重新排序应该明显改变生成的哈希码。
反映树的任何部分都应该明显改变生成的哈希码

如果有帮助，尽管我主要是在寻找理论上的解决方案，但我在我的项目中正在使用C＃4.0，因此伪代码，描述或另一种命令性语言的代码都可以。

更新

好吧，这是我自己提出的解决方案。这里的几个答案对它有很大帮助。

每个节点（子树/叶节点）具有以下哈希函数：

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指出了这一点）。

无论如何，如果有人可以在这里对我建议的解决方案发表评论，我将不胜感激-如果它做得很好，那就很好，否则任何可能的改进都将受到欢迎。

阅读 354

2020-07-28

共1个答案

一尘不染

如果要执行此操作，则可能会执行以下操作：

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

对于每个内部节点，请从左到右计算1的串联和任何本地数据的哈希（NB：可能不适用）以及子代的哈希。

每当您进行任何更改时，这都会导致树的级联，但这可能不足以使开销值得。如果与更改量相比更改相对不频繁，则使用加密安全的哈希甚至更有意义。

Edit1：
还可以在每个节点上向每个节点添加“哈希有效”标志，并在树上沿树传播“假”（或“哈希无效”并向树传播“真”）。这样，有可能在需要树哈希时避免完全重新计算，并且有可能避免未使用的多个哈希计算，而在需要时可能会有更少的可预测时间获得哈希。

Edit3：
如果GetHashCode的结果可以为0，则Noldorin在问题中建议的哈希码看起来很可能会发生冲突。本质上，没有办法用“符号”来区分由单个节点组成的树。哈希”
30和“值哈希”
25，以及两节点树，其中根的“符号哈希”为0，“值哈希”为30，子节点的总哈希为25。示例完全是是发明的，我不知道预期的哈希范围是多少，所以我只能对在所提供的代码中看到的内容进行评论。

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

但是，如果散列在预期数据上表现良好，则看起来好像可以完成工作。它肯定比使用加密哈希（在下面的示例代码中完成）要快。

Edit2： 对于特定的算法和所需的最小数据结构，类似于以下内容（Python，翻译成任何其他语言应该相对容易）。

＃！/ usr / bin / env python

导入Crypto.Hash.SHA

类节点：
    def __init__（self，parent = None，contents =“”，children = []）：
        self.valid =假
        self.hash =假
        self.contents =内容
        self.children =孩子


    def append_child（自己，孩子）：
        self.children.append（child）

        self.invalidate（）

    def invalidate（个体）：
        self.valid =假
        如果为self.parent：
            self.parent.invalidate（）

    def gethash（个体经营）：
        如果self.valid：
            返回self.hash

        消化器= crypto.hash.SHA.new（）

        摘要更新（self.contents）

        如果是self.children：
            对于self.children中的孩子：
                summaryer.update（child.gethash（））
            self.hash =“ 1” + digester.hexdigest（）
        其他：
            self.hash =“ 0” + digester.hexdigest（）

        返回self.hash

    def setcontents（个体）：
        self.valid =假
        返回self.contents

2020-07-28