散列树结构
我刚刚在我的项目中遇到了一个场景，我需要将不同的树对象与已知实例进行比较，并且认为某种在任意树上运行的哈希algorithm将非常有用。
以下面的树为例：
Ø
/ \
/ \
OO
/ | \ |
/ | \ |
OOOO
/ \
/ \
OO
其中每个O表示树的一个节点，是一个任意的对象，有一个关联的散列函数。 所以问题简化为：给定树结构节点的散列码和已知的结构，计算整个树的（相对）无碰撞散列码的体面algorithm是什么？
有关散列函数属性的一些说明：
- 散列函数应该取决于树中每个节点的散列码以及它的位置。
- 重新sorting节点的子节点应该明显改变生成的散列码。
- 反映树的任何部分应明显改变生成的哈希码
如果有帮助的话，我在我的项目中使用C＃4.0，虽然我主要是在寻找一个理论上的解决scheme，所以在另一个命令式语言中使用伪代码，描述或者代码就没有问题。
UPDATE
那么，这是我自己提出的解决scheme。 这里得到了很多答案。
每个节点（子树/叶节点）具有以下散列函数：
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; }
正如我所看到的那样，这个方法的好处是散列码可以被caching，并且只有在节点或其下一个节点发生变化时才能重新计算。 （感谢vatine和Jason Orendorff指出了这一点）。
无论如何，如果人们可以在这里评论我的build议解决scheme，我将不胜感激，如果它做得好，那么很好，否则任何可能的改进都会受到欢迎。
如果我这样做，我可能会做如下的事情：
对于每个叶节点，计算0和节点数据的散列的连接。
对于每个内部节点，计算1和所有本地数据的散列（NB：可能不适用）的连接以及从左到右的子节点的散列。
这会导致每当你改变任何东西时，树会逐级上升，但是这可能是一个低的开销，是值得的。 如果变化相对于变化的数量相对较less，那么为了encryption安全的散列可能更有意义。
编辑1：也有可能为每个节点添加一个“散列有效”标记，并简单地在树上传播一个“假”（或“散列无效”并传播“真”）在节点变化上的树。 这样，当需要树散列时可以避免完整的重新计算，并且可能避免多次散列计算不被使用，在需要时可能会有less得多的可预测时间来获得散列。
Edit3：如果GetHashCode的结果可以是0，那么Noldorin在这个问题中提出的哈希代码看起来会有碰撞的机会。实际上，没有办法区分由单个节点组成的树，散列“30和”值散列“25以及双节点树，其中根具有”符号散列“0和”值散列“30并且子节点具有总散列25。发明，我不知道预期的散列范围是什么，所以我只能评论我所看到的代码。
使用31作为乘法常数是好的，因为它会导致任何溢出发生在一个非位边界，虽然我认为，有足够的儿童和可能的敌对内容在树中，散列贡献的项目散列早MAY被后来的散列项目所主宰。
但是，如果散列在预期的数据上performance不错，它看起来好像能完成这项工作。 这肯定比使用encryption散列更快（如下面列出的示例代码所做的那样）。
编辑2：至于具体的algorithm和所需的最小数据结构，像下面的东西（Python，翻译成任何其他语言应该是相对容易的）。
＃！ / usr / bin / env python
导入Crypto.Hash.SHA
类节点：
def __init__（self，parent = None，contents =“”，children = []）：
self.valid = False
self.hash = False
self.contents =内容
self.children =孩子
def append_child（self，child）：
self.children.append（子）
self.invalidate（）
def invalidate（self）：
self.valid = False
如果self.parent：
self.parent.invalidate（）
def gethash（self）：
如果self.valid：
返回self.hash
digester = crypto.hash.SHA.new（）
digester.update（self.contents）
如果self.children：
为孩子在self.children：
digester.update（child.gethash（））
self.hash =“1”+ digester.hexdigest（）
其他：
self.hash =“0”+ digester.hexdigest（）
返回self.hash
def setcontents（self）：
self.valid = False
返回self.contents
好的，在你编辑之后，你已经介绍了一个要求，即对于不同的树布局，哈希结果应该是不同的，你只剩下select遍历整个树并将其结构写入单个数组。
这是这样做的：你遍历树并转储你做的操作。 对于可能是（对于左孩子右兄弟姐妹结构）的原始树：
[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]
然后你可以用你喜欢的方式散列这个列表（也就是一个string）。 作为另一种select，你甚至可以通过散列函数返回这个列表，所以它变成了无冲突的树表示。
但是添加关于整个结构的精确信息并不是散列函数通常所做的。 所提出的方法应该计算每个节点的哈希函数以及遍历整个树。 所以你可以考虑其他散列方式，如下所述。
如果你不想遍历整棵树：
我立即想到的一个algorithm就是这样。 select一个大的素数H （这大于孩子的最大数量）。 散列一个树，散列它的根，select一个子数字H mod n ，其中n是根子树的数目，recursion地散列这个子树的子树。
如果树木在树叶附近深度不同，这似乎是一个不好的select。 但至less它应该跑得快，不是很高的树木。
如果你想散列较less的元素，但通过整个树 ：
而不是散列子树，你可能想散列层次。 也就是说，散列根，而不是哈希作为子节点的子节点之一，然后是孩子的子节点之一等。因此，你覆盖整个树，而不是一个特定的path。 当然，这使得哈希程序更慢。
--- 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规则选取来自图层的节点。
这个版本和以前版本的区别在于一棵树应该经历一个非常不合逻辑的转换来保留散列函数。
散列任何序列的通常技术是以某种math方式结合其元素的值（或其散列）。 我不认为在这方面树会有什么不同。
例如，下面是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; }
这是一个相对复杂的组合，通过实验select常量来获得典型长度元组的最佳结果。 我试图用这个代码片断展示的是，这个问题非常复杂，非常具有启发性，结果的质量可能取决于数据的更具体的方面，即领域知识可能会帮助您达到更好的结果。 但是，为了获得足够好的结果，你不应该看得太远。 我猜想，采取这个algorithm，结合树的所有节点，而不是所有的元组元素，再加上他们的位置发挥将给你一个很好的algorithm。
考虑位置的一种select是节点在树的无序行走中的位置。
任何时候你正在使用树的recursion应该浮现在脑海：
public override int GetHashCode() { int hash = 5381; foreach(var node in this.BreadthFirstTraversal()) { hash = 33 * hash + node.GetHashCode(); } }
散列函数应该取决于树中每个节点的散列码以及它的位置。
检查。 我们明确使用node.GetHashCode()来计算树的哈希码。 此外，由于algorithm的性质，节点的位置在树的最终哈希码中起作用。
重新sorting节点的子节点应该明显改变生成的散列码。
检查。 在顺序遍历中将以不同的顺序访问它们，导致不同的哈希码。 （请注意，如果有两个具有相同散列码的孩子，则在交换这些孩子的顺序时，最终将得到相同的散列码。）
反映树的任何部分应明显改变生成的哈希码
检查。 再次以不同的顺序访问节点，导致不同的哈希码。 （请注意，如果每个节点都反映到具有相同散列码的节点中，则reflection会导致相同的散列码。）
这种无冲突的性质将取决于节点数据使用的散列函数是如何无冲突的。
这听起来像你想要一个系统，其中特定节点的散列是子节点散列的组合，其中顺序很重要。
如果你打算对这棵树进行大量的操作，那么你可能需要在每个节点上存储哈希码的空间，以避免在树上执行操作时重新计算的代价。
由于子节点的顺序很重要，一种可能在这里工作的方法是将节点数据与孩子使用素数倍数相加，并加上模数。
去找类似于Java的String hashcode的东西：
假设你有n个子节点。
hash(node) = hash(nodedata) + hash(childnode[0]) * 31^(n-1) + hash(childnode[1]) * 31^(n-2) + <...> + hash(childnode[n])
关于上述scheme的更多细节可以在这里find： http : //computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
我可以看到，如果你有大量的树来比较，那么你可以使用散列函数来检索一组潜在的候选人，然后做一个直接的比较。
可以工作的子string就是使用lisp语法在树的周围放置括号，按照预定顺序写出每个节点的标识符。 但是这在计算上等同于树的预先比较，为什么不这样做呢？
我已经给出了两个解决scheme：一个是完成时（需要解决冲突）比较两棵树，另一个是计算哈希码。
树比较：
比较最有效的方法是按照固定的顺序简单recursion地遍历每一棵树（预序简单，和其他任何事物一样），比较每一步的节点。
-
所以，只需创build一个访问者模式，连续返回树中预订的下一个节点。 即它的构造函数可以取树的根。
-
然后，创buildVisitor的两个insces，作为preorder下一个节点的生成器。 即Vistor v1 =新访客（root1），访客v2 =新访客（root2）
-
写一个比较函数，可以比较自己到另一个节点。
-
然后访问树的每个节点，比较，如果比较失败，则返回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
结束模块
哈希代码生成：
如果要写出树的string表示forms，则可以对树使用lisp语法，然后对string进行采样以生成较短的哈希码。
模
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函数返回的string中进行子string比较，以确定树是否相等。 对于较短的哈希码，只需对TreeToString函数进行采样，即每5个字符一次。
结束模块
我认为你可以recursion地做到这一点：假设你有一个哈希函数h散列任意长度的string（例如SHA-1）。 现在，树的散列是一个string的散列，该string被创build为当前元素的散列（您有自己的函数）和该节点的所有子元素的散列（从recursion调用function）。
对于二叉树，您将拥有：
Hash( h(node->data) || Hash(node->left) || Hash(node->right) )
您可能需要仔细检查树几何是否适当考虑。 我认为，通过一些努力，你可以得到一个方法，为这样的树寻找冲突可能和find底层哈希函数中的冲突一样困难。
一个简单的枚举（以任何确定性的顺序）连同一个散列函数一起工作，该散列函数取决于何时访问该节点。
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(); }
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是一个函数，它结合了两个哈希码，所以顺序很重要。 我不知道这是什么，但你可以弄清楚。 有些转移，四舍五入，你知道…
这个想法是，你必须分析节点的一些环境，取决于你想要达到的质量。
我不得不说，你的要求有点违背了整个hashcodes的概念。
散列函数的计算复杂度应该非常有限。
它的计算复杂度不应线性取决于容器（树）的大小，否则它会完全打破基于哈希码的algorithm。
考虑到作为节点散列函数的主要属性的位置也有点违背了树的概念，但是可以实现的，如果你replace了需求，那么它必须依赖于位置。
我build议的总体原则是用SHOULD要求取代MUST的要求。 这样你可以拿出适当和高效的algorithm。
例如，考虑构build一个有限序列的整数散列码标记，并按照优先顺序添加你想要的序列。
这个序列中元素的顺序很重要，它会影响计算值。
例如，对于您要计算的每个节点：
- 添加底层对象的哈希码
- 如果可用，添加最近兄弟的基础对象的哈希码。 我想，即使是单身的左兄弟也足够了。
- 添加父代的基础对象的散列码，它与节点本身最近的兄弟节点相同，与2相同。
-
重复这与祖父母有限的深度。
//--------5------- ancestor depth 2 and it's left sibling; //-------/|------- ; //------4-3------- ancestor depth 1 and it's left sibling; //-------/|------- ; //------2-1------- this;事实上，你添加一个直接的兄弟的基础对象的散列码给散列函数的位置属性。
如果这还不够，请添加孩子：您应该添加每个孩子，只是一些给一个体面的哈希码。
-
添加第一个孩子，它是第一个孩子，它是第一个孩子..限制深度一些常数，不要recursion计算任何东西 – 只是底层节点的对象的哈希码。
//----- this; //-----/--; //----6---; //---/--; //--7---;
这样，复杂度与底层树的深度是线性的，而不是元素的总数。
现在你有一个序列，如果整数，把它们与一个已知的algorithm结合起来，就像上面提到的伊利。
1,2，… 7
这样，您将拥有一个轻量级的散列函数，具有一个位置属性，不依赖于树的总大小，甚至不依赖于树的深度，并且当您更改时不需要重新计算整个树的散列函数树结构。
我敢打赌，这7个数字将给予近乎完美的散列分数。
编写自己的散列函数几乎总是一个错误，因为你基本上需要math学位才能做好。 散列函数非常不直观，并且具有高度不可预测的碰撞特性。
不要尝试直接结合Child节点的哈希码 – 这将放大底层哈希函数中的任何问题。 相反，按顺序连接来自每个节点的原始字节，并将其作为字节stream提供给经过validation的真正的哈希函数。 所有的encryption散列函数都可以接受一个字节stream。 如果树很小，你可能只想创build一个字节数组，并在一个操作中对其进行散列。
