哈希树结构

Question

我刚刚在我的项目中遇到了一个场景,我需要比较不同的树对象与已知实例的相等性,并且考虑到在任意树上运行的某种散列算法将非常有用.

以下面的树为例:

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

其中每个O表示树的节点,是一个任意对象,具有相关的哈希函数.所以问题简化为:给定树结构节点的哈希码和已知结构,什么是计算整个树的(相对)无冲突哈希码的不错算法？

关于散列函数属性的一些注意事项:

• 散列函数应该取决于树中每个节点的哈希码及其位置.
• 重新排序节点的子节点应明显更改生成的哈希码.
• 反映树的任何部分应明显更改生成的哈希代码

如果它有帮助,我在我的项目中使用C#4.0,虽然我主要是寻找理论解决方案,所以伪代码,描述或其他命令式语言的代码都可以.

---

UPDATE

嗯,这是我自己提出的解决方案.这里的几个答案对它有很大帮助.

每个节点(子树/叶节点)具有以下散列函数:

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的串联和任何本地数据的散列(NB:可能不适用)以及从左到右的子节点的散列.

每当你改变任何东西时,这将导致树的级联,但这可能是足够低的开销是值得的.如果与变更量相比变化相对较少,那么获取加密安全散列甚至可能是有意义的.

编辑1:还有可能向每个节点添加"散列有效"标志,并且只是在节点更改时向树上传播"假"向上(或"散乱无效"并传播"真").这样,当需要树哈希时可以避免完全重新计算并且可能避免未使用的多个哈希计算,存在在需要时获得哈希的可预测时间稍微少的风险.

编辑3:如果GetHashCode的结果可能为0,Noldorin在问题中建议的哈希码看起来有可能发生冲突.实际上,没有办法区分由单个节点组成的树,用"符号" hash"30 and"value hash"25和一个双节点树,其中根的"符号散列"为0,"值散列"为30,子节点的总散列为25.示例完全是发明了,我不知道预期的哈希范围是什么,所以我只能评论我在所提出的代码中看到的内容.

使用31作为乘法常量是好的,因为它会导致在非位边界上发生任何溢出,尽管我认为,如果树中有足够的子节点和可能的对抗性内容,则项目的哈希贡献可能会在早期进行.被后来的哈希物品所统治.

但是,如果散列在预期数据上运行得体,那么它看起来就像是在完成这项工作.它肯定比使用加密哈希更快(如下面列出的示例代码中所做的那样).

Edit2:至于所需的特定算法和最小数据结构,如下所示(Python,翻译成任何其他语言应该相对容易).

#! /usr/bin/env  python

import Crypto.Hash.SHA

class 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

Answer 2

好的,在您编辑之后,您已经引入了对不同树布局的散列结果应该不同的要求,您只能选择遍历整个树并将其结构写入单个数组.

这是这样做的:你遍历树并转储你做的操作.对于可能的原始树(对于左子 - 右 - 兄弟结构):

[1, child, 2, child, 3, sibling, 4, sibling, 5, parent, parent, //we're at root again
 sibling, 6, child, 7, child, 8, sibling, 9, parent, parent]

然后,您可以按照自己喜欢的方式对列表进行哈希(即,实际上是一个字符串).作为另一种选择,您甚至可以作为哈希函数的结果返回此列表,因此它变为无冲突树表示.

但是添加关于整个结构的精确信息并不是哈希函数通常所做的.提出的方法应该计算每个节点的散列函数以及遍历整个树.因此,您可以考虑其他散列方法,如下所述.

如果你不想遍历整棵树:

我脑子里想到的一种算法是这样的.选择一个大的素数H(大于最大子项数).散列树,散列其根,选择一个子编号H mod n,其中n是root的子节点数,并递归地散列该子节点的子树.

如果树木仅在叶子附近深处不同,这似乎是一个不好的选择.但至少它应该快速运行不是很高的树木.

如果你想散列更少的元素但是要遍历整个树:

您可能希望以分层方式散列,而不是散列子树.首先是哈希根,而不是作为其子节点的哈希之一,然后是孩子的子节点之一等等.因此,您覆盖整个树而不是特定路径之一.当然,这使得散列过程变慢.

    --- O  ------- layer 0, n=1
       / \
      /   \
 --- O --- O ----- layer 1, n=2
    /|\    |
   / | \   |
  /  |  \  |
 O - O - O O------ layer 2, n=4
          / \
         /   \
 ------ O --- O -- layer 3, n=2

使用H mod n规则挑选层中的节点.

此版本与先前版本之间的区别在于树应该经历非常不合逻辑的转换以保留散列函数.

Answer 3

散列任何序列的常用技术是以某种数学方式组合其元素的值(或其散列).我不认为树在这方面会有任何不同.

例如,这里是Python中元组的哈希函数(取自Python 2.6源代码中的Objects/tupleobject.c):

static long
tuplehash(PyTupleObject *v)
{
    register long x, y;
    register Py_ssize_t len = Py_SIZE(v);
    register PyObject **p;
    long mult = 1000003L;
    x = 0x345678L;
    p = v->ob_item;
    while (--len >= 0) {
        y = PyObject_Hash(*p++);
        if (y == -1)
            return -1;
        x = (x ^ y) * mult;
        /* the cast might truncate len; that doesn't change hash stability */
        mult += (long)(82520L + len + len);
    }
    x += 97531L;
    if (x == -1)
        x = -2;
    return x;
}

这是一个相对复杂的组合,通过实验选择常数,以获得典型长度元组的最佳结果.我试图用这个代码片段展示的是问题非常复杂且非常具有启发性,结果的质量可能取决于数据的更具体方面 - 即领域知识可以帮助您获得更好的结果.但是,为了获得足够好的结果,你不应该看得太远.我猜想采用这种算法并结合树的所有节点而不是所有的元组元素,加上将它们的位置加入到游戏中会给你一个非常好的算法.

将位置考虑在内的一个选择是节点在树的顺序行走中的位置.

Answer 4

任何时候你正在使用树木递归应该想到:

public override int GetHashCode() {
    int hash = 5381;
    foreach(var node in this.BreadthFirstTraversal()) {
        hash = 33 * hash + node.GetHashCode();
    }
}

散列函数应该取决于树中每个节点的哈希码及其位置.

校验.我们明确地node.GetHashCode()在计算树的哈希码时使用.此外,由于算法的性质,节点的位置在树的最终哈希码中起作用.

重新排序节点的子节点应明显更改生成的哈希码.

校验.它们将在有序遍历中以不同的顺序被访问,从而导致不同的哈希码.(请注意,如果有两个具有相同哈希码的子代码,则在交换这些子代码的顺序时,最终会得到相同的哈希代码.)

反映树的任何部分应明显更改生成的哈希代码

校验.同样,将以不同的顺序访问节点,从而导致不同的哈希码.(请注意,如果每个节点都反映到具有相同哈希码的节点中,则存在反射可能导致相同哈希码的情况.)