树形结构的哈希化

Question

树形结构的哈希化

algorithmdata-structurestreehash

51

我刚刚在项目中遇到一个场景，需要将不同的树对象与已知实例进行比较，并考虑到一些对任意树结构进行哈希的算法会非常有用。

以以下树为例：

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

每个 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指出这一点)。无论如何，如果我的建议解决方案做得不错，那就太好了，否则，欢迎任何可能的改进意见。

- Noldorin

@Eli Bendersky：确实如此。我修改了问题，以暗示“尽可能无碰撞”。 - Noldorin

2

这些答案都没有很好地解释它，但是一棵树只是一个元组（节点本地数据、子树0、子树1等）。元组是可散列的。完成。更多细节请参见vatine和pnm的答案。 - Jason Orendorff

@Eli Bendersky：就实际目的而言，无冲突是相当简单的。例如，SHA1已经有15年历史了，仅有160位，但即使使用我们最好的超级计算机，也没有人找到过两个具有相同SHA1哈希值的值（尽管我猜很快就会发生这种情况）。 - BlueRaja - Danny Pflughoeft

1

@BlueRaja 是的，但是尝试将SHA1的输出映射到一个可寻址空间，它是一个序列递增的、线性递增的，比如说，1,000个元素长。现在告诉我这不会出现碰撞。 - San Jacinto

会用到Merkle树吗？ - Vladimir Panteleev

显示剩余4条评论

11个回答

8

好的，在您引入了哈希结果应该针对不同的树布局而不同的修改后，您只剩下了遍历整个树并将其结构写入单个数组的选项。

这可以这样完成：遍历树并转储所执行的操作。对于原始树来说，可能是这样的（对于左子右兄弟结构）：

[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 是根节点的子节点数，并递归哈希此子树。

如果树只在叶子节点附近有深度差异，则这似乎是一个糟糕的选项。但至少对于不太高的树，它应该运行得很快。

如果您要哈希较少的元素但要遍历整个树：

与其哈希子树，您可能希望按层哈希。也就是先哈希根，然后哈希其中一个节点，该节点是其子节点之一，然后是其中一个孩子等等。这样您就覆盖了整个树而不是特定路径中的一个。当然，这会使哈希过程变慢。

    --- 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规则选择层中的一个节点。

这个版本与之前的版本的区别在于，为了保留哈希函数，树应该经历相当不合逻辑的转换。

- P Shved

有趣的建议。不确定它可能会成为多大的问题，但这些树可能潜在地非常深，并且没有真正的最大节点数（可能是10、100、1000甚至更大一些）。 - Noldorin

嗯，为什么每个人的答案都这么复杂？你只需要用5行代码就可以生成一个精确的哈希码，并对其进行采样以生成一个较短的哈希码（请参见我下面的答案）。 - Larry Watanabe

@Larry，更加巧妙的解决方案通常比直接的方案更加复杂。 - P Shved

提议的方法（遍历树来构建列表）过于复杂。这个问题有一个简单、直接的解决方案，由vatine和pnm提供。 - Jason Orendorff

@Jason Orenforff，（a）我提出了三种方法，（b）我认为这并不复杂。至于这是否是我的问题，我不确定。 - P Shved

7

通常哈希任何序列的技术是以某种数学方式组合其元素的值（或哈希值）。我认为树在这方面也不会有什么不同。

例如，以下是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;
}

这是一个相对复杂的组合，选取了实验结果最佳的常量来处理典型长度的元组。我试图通过这段代码片段展示这个问题非常复杂和启发式，并且结果的质量可能取决于数据的更具体方面 - 即领域知识可以帮助你获得更好的结果。然而，对于足够好的结果，您不需要走得太远。我猜测，将此算法与树的所有节点结合起来，而不是所有元组元素，并加入它们的位置，将会给您一个相当不错的算法。

考虑节点在树的中序遍历中的位置是一个选择。

- Eli Bendersky

总的来说，你提出了一个很好的观点。然而，树与序列略有不同，因为它们包含更大的结构 - 除非你特别知道它是二叉/三叉等树，否则不能简单地用序列表示树。但是，可能可以轻松地调整算法... - Noldorin

一棵树可以被表示为一个序列。我在我的答案中展示了如何表示的示例。 - P Shved

“位置”包含路径信息。例如，对于每个节点，为节点本身分配一个位置值为0，对于从左到右的每个n个子节点，分别分配1..n的位置值。在遍历时访问第i个子节点时，将i包含在哈希中。当访问节点本身时，包括0和节点的哈希内容。常数0、1、...、n的选择是任意的，应根据特定领域的知识进行选择，例如，“0-mississippi”、“1-mississippi”等可能效果更好。 - President James K. Polk

@Pavel Shved：确实可以，但序列仍然是一种模糊的表示。例如，请参见此处：http://pastebin.com/m44d5b6b6（深度优先遍历也适用） - Noldorin

@Noldorin，这就是为什么添加额外的符号到序列中很重要，这样它的长度将比原始树更大。 - P Shved

6

任何时候当你在处理树形结构时，递归都应该是一个考虑的方向：

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

哈希函数应该依赖于树中每个节点的哈希码以及其位置。

检查。我们在计算树的哈希码时明确使用了 node.GetHashCode()。此外，由于算法的性质，节点的位置对树的最终哈希码起到了作用。

重新排序节点的子节点应该明显地改变结果哈希码。

检查。它们将按不同顺序在中序遍历中访问，从而导致不同的哈希码。（请注意，如果有两个哈希码相同的子节点，则交换这些子节点的顺序将导致相同的哈希码。）

反射树的任何部分应该明显地改变结果哈希码。

检查。同样，节点将按不同的顺序访问，从而导致不同的哈希码。（请注意，在某些情况下，如果每个节点都反射到具有相同哈希码的节点中，则反射可能会导致相同的哈希码。）

- jason

@Jason：谢谢回复。这确实是一个简单而不错的解决方案 - 这是我首先想到的，但它未满足我在这里提出的条件：http://pastebin.com/m44d5b6b6（对于我最初的问题没有注明，很抱歉）。 - Noldorin

这里有一个bug。应该使用this.ChildNodes而不是this.InOrderTraversal()。否则每个节点将被访问2^(n-1)次，其中n是它的祖先数量... - Jason Orendorff

@Noldorin：你说得对，深度优先搜索也会有类似的问题。因此，我认为你需要将所采取的路径编码到过程中。 - jason

@Jason Orendorff：什么？在树遍历中，每个节点只被访问一次。 - jason

@Jason：是的，这个解决方案与我自己提出的建议相当相似。我在想，将hash初始化为非零（质数）值是否有任何真正的优势呢？ - Noldorin

4

这将取决于节点数据所使用的哈希函数有多少“无碰撞”属性。

听起来你想要一个系统，其中特定节点的哈希是子节点哈希的组合，其中顺序很重要。

如果您计划经常操作此树，则可能需要支付存储每个节点的哈希码的空间成本，以避免在执行树操作时重新计算的惩罚。

由于子节点的顺序很重要，因此在这里可能适用的一种方法是使用质数倍数和加法模某个大数将节点数据和子节点组合起来。

为了实现类似于Java字符串哈希码的效果：

假设您有n个子节点。

hash(node) = hash(nodedata) +
             hash(childnode[0]) * 31^(n-1) +
             hash(childnode[1]) * 31^(n-2) +
             <...> +
             hash(childnode[n])

以下是翻译的结果：

上面使用的方案的更多详细信息可以在这里找到：http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

该链接讲解了哈希函数为什么使用质数，并提供了相关细节。

- user242275

3

我看到如果你有一组大量的树需要比较，那么你可以使用哈希函数来检索一组潜在的候选项，然后进行直接比较。

一个可行的子串方案是使用lisp语法在树周围加上括号，按照先序写出每个节点的标识符。但这在计算上等价于对树进行先序比较，那为什么不直接这样做呢？

我提供了两种解决方案：一种用于在完成比较后比较两棵树（需要解决冲突），另一种用于计算哈希码。

树比较：

最有效的比较方法是简单地以固定顺序（先序很简单，与其他任何方法一样好）递归遍历每棵树，比较每一步的节点。

1. 因此，只需创建一个访问者模式，连续返回树中先序的下一个节点。即它的构造函数可以接受树的根节点。 2. 然后，只需创建两个Visitor实例，充当先序下一个节点的生成器。即Visitor v1 = new Visitor(root1), Visitor v2 = new Visitor(root2) 3. 编写一个比较函数，可以将自己与另一个节点进行比较。 4. 然后只需访问每个树的节点，进行比较，并在比较失败时返回false。即

模块

 Function Compare(Node root1, Node root2)
      Visitor v1 = new Visitor(root1)
      Visitor v2 = new Visitor(root2)

      loop
          Node n1 = v1.next
          Node n2 = v2.next
          if (n1 == null) and (n2 == null) then
                return true
          if (n1 == null) or (n2 == null) then
                return false
          if n1.compare(n2) != 0 then
                return false
      end loop
      // unreachable
 End Function

结束模块

哈希码生成:

如果您想要编写树的字符串表示形式，可以使用Lisp语法表示树，然后对字符串进行采样以生成较短的哈希码。

模块

 Function TreeToString(Node n1) : String
        if node == null
            return ""
        String s1 = "(" + n1.toString()
        for each child of n1
            s1 = TreeToString(child)

        return s1 + ")"
 End Function

node.toString()函数可以返回节点的唯一标识符/哈希码/其他内容。然后，您只需从TreeToString函数返回的字符串中进行子字符串比较，以确定树是否等效。要获得较短的哈希码，只需对TreeToString函数进行采样，即每5个字符取一个。

End Module

- Larry Watanabe

在我的情况下，我经常会多次将各种树与相同的其他树进行比较。在这种情况下，计算哈希肯定更有效率，因为您只需要递归一次即可遍历常见树的节点？ - Noldorin

我明白了 - 这就是为什么我修改了我的答案，包括哈希码生成器。你可以将树简单地写成一个字符串，然后对其进行采样。如果保留每个字符，则可以确保没有冲突，但效率较低。保留其他字符则更高效，但可能会出现冲突。你可以根据你的应用程序、数据等选择权衡。 - Larry Watanabe

@Larry：啊，这是一种新颖的方法。+1 这肯定是简单而有效的，我想...虽然可能不是最高效的。我会考虑一下的。 - Noldorin

你可以通过跳过字符而不是实际生成它们来轻松优化它。只要跳过函数是一致的，它仍将返回有效的哈希码。先把它做对，再进行优化 :) 这种简单的方法易于优化和扩展。如果你看看其他方法，你会发现它们只是使用了一种懒惰的哈希码生成方法，但它比这种方法更加临时，也不那么简单。从简单和正确开始，然后再进行优化。 - Larry Watanabe

1

一个简单的枚举（以任何确定性顺序）加上一个取决于节点访问时间的哈希函数应该可以解决问题。

int hash(Node root) {
  ArrayList<Node> worklist = new ArrayList<Node>();
  worklist.add(root);
  int h = 0;
  int n = 0;
  while (!worklist.isEmpty()) {
    Node x = worklist.remove(worklist.size() - 1);
    worklist.addAll(x.children());
    h ^= place_hash(x.hash(), n);
    n++;
  }
  return h;
}

int place_hash(int hash, int place) {
  return (Integer.toString(hash) + "_" + Integer.toString(place)).hash();
}

- Keith Randall

我认为这并不满足区分具有相同前序遍历但不同结构的树的要求。 - Jason Orendorff

我认为这不是列出的要求。如果您想要，可以将节点深度添加到哈希中。我猜先序索引加上节点深度将确定一个唯一的树。 - Keith Randall

@Keith：Jason是对的——遍历顺序不足以解决问题——还需要考虑结构。 - Noldorin

1

我认为你可以用递归来实现这个功能：假设你有一个哈希函数h，它可以哈希任意长度的字符串（例如SHA-1）。现在，树的哈希值是由当前元素的哈希值（你自己的函数）和该节点所有子节点的哈希值（从函数的递归调用中获得）连接而成的字符串的哈希值。

对于二叉树，你会有：

Hash( h(node->data) || Hash(node->left) || Hash(node->right) )

你可能需要仔细检查树的几何形状是否被正确考虑。我认为，通过一些努力，你可以得出一种方法，使得在这样的树中找到碰撞与在底层哈希函数中找到碰撞一样困难。

- Kris

0

class TreeNode
{
  public static QualityAgainstPerformance = 3; // tune this for your needs
  public static PositionMarkConstan = 23498735; // just anything
  public object TargetObject; // this is a subject of this TreeNode, which has to add it's hashcode;

  IEnumerable<TreeNode> GetChildParticipiants()
  {
   yield return this;

   foreach(var child in Children)
   {
    yield return child;

    foreach(var grandchild in child.GetParticipiants() )
     yield return grandchild;
  }
  IEnumerable<TreeNode> GetParentParticipiants()
  {
   TreeNode parent = Parent;
   do
    yield return parent;
   while( ( parent = parent.Parent ) != null );
  }
  public override int GetHashcode()
  {
   int computed = 0;
   var nodesToCombine =
    (Parent != null ? Parent : this).GetChildParticipiants()
     .Take(QualityAgainstPerformance/2)
    .Concat(GetParentParticipiants().Take(QualityAgainstPerformance/2));

   foreach(var node in nodesToCombine)
   {
    if ( node.ReferenceEquals(this) )
      computed = AddToMix(computed, PositionMarkConstant );
    computed = AddToMix(computed, node.GetPositionInParent());
    computed = AddToMix(computed, node.TargetObject.GetHashCode());
   }
   return computed;
  }
}

AddToTheMix是一个函数，它将两个哈希码组合起来，因此顺序很重要。我不知道具体是什么，但你可以自己想象一下。可能会涉及到一些位移、取整之类的操作。

这个函数的思路是，你需要分析节点周围的环境，根据你想要达到的质量水平来进行处理。

- George Polevoy

@George：能否详细解释一下那段代码？ - Noldorin

0

我不得不说，您的要求有些违背哈希码的整个概念。

哈希函数的计算复杂度应该非常有限。

它的计算复杂度不应该线性依赖于容器（树）的大小，否则它完全破坏了基于哈希码的算法。

考虑节点位置作为节点哈希函数的主要属性，也有些违背树的概念，但如果您替换它必须依赖位置的要求，这是可以实现的。

总的原则是用“应该”来替换“必须”的要求。这样，您就可以提出合适和高效的算法。

例如，考虑构建一个整数哈希码令牌的有限序列，并按优先顺序添加所需的内容。

这个序列中元素的顺序很重要，它会影响计算出的值。

例如，对于每个节点，您想计算：

添加基础对象的哈希码
如果可用，添加最近兄弟的基础对象的哈希码。我认为，即使是单个左兄弟也足够了。
添加父级和其最近兄弟的基础对象的哈希码，就像节点本身一样，同2。
将此重复到祖父母，但深度有限。
```
//--------5------- 祖先深度2及其左侧兄弟;
//-------/|------- ;
//------4-3------- 祖先深度1及其左侧兄弟;    
//-------/|------- ;
//------2-1------- 这个;
```
事实上，您正在添加直接兄弟的基础对象的哈希码，从而为哈希函数提供了位置属性。

如果这还不够，请添加子项：您应该添加每个子项，只需添加一些以获得体面的哈希码。
添加第一个子项及其第一个子项及其第一个子项..将深度限制为某个常量，并且不要递归计算任何内容 - 只需基础节点的对象的哈希码。
```
//----- 这个;
//-----/--;
//----6---;
//---/--;
//--7---;
```

这样，复杂度就与底层树的深度成线性关系，而不是元素总数。

现在你有一个整数序列，可以使用已知的算法将它们组合起来，就像Ely上面建议的那样。

1,2,...7

这样，您将拥有一个轻量级的哈希函数，具备位置特性，不依赖于树的总大小，甚至不依赖于树的深度，并且在更改树结构时不需要重新计算整个树的哈希函数。

我敢打赌，这7个数字会给出接近完美的哈希分布。

- George Polevoy

我所知道的所有哈希算法都使用了所有数据。哈希码只是被缓存以使得在实践中计算它们的时间是恒定的。 - Jason Orendorff

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vatine · Accepted Answer

如果我要做这件事，我可能会像下面这样做:

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

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

这将导致树上的级联，每次更改时都会发生，但这可能是足够低的开销，值得考虑。如果更改相对于更改量比较少，甚至可能有意义选择加密安全散列。

编辑1:还有一个可能性，即向每个节点添加“哈希有效”标志，并在节点更改时向树上传播“false”(或“哈希无效”并传播“true”)。这样，在需要树哈希时，可能可以避免完全重新计算，并可能避免多个未使用的哈希计算，风险是获得哈希所需的时间稍微不那么可预测。

编辑3:Noldorin在问题中建议的哈希代码似乎有碰撞的可能性，如果GetHashCode的结果可以为0。基本上，没有办法区别由单个节点组成的树，其“符号哈希”的值为30，而“值哈希”的值为25，以及一个两个节点的树，其中根具有“符号哈希”的总哈希值为0，一个“值哈希”的总哈希值为30的子节点。这些例子是完全编造的，我不知道期望的哈希范围，因此只能评论所呈现代码中看到的内容。

使用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

注：以上代码实现了一个节点类，用于表示Merkle树中的叶子节点和非叶子节点。在此基础上，可以进一步实现Merkle树的各种操作。