sha1 - 如何在对象树上创建 SHA1 摘要？

Question

假设我有一棵对象树，其中每个对象都有一个字符串表示。我想在整个树上创建一个 SHA1 摘要。

最简单的方法是递归遍历树的每个节点。对于每个节点，我将连接（作为简单字符串）所有子节点的 SHA1 摘要，将给定节点的字符串表示形式添加到这个连接的字符串，然后对其执行 SHA1。这将是给定节点的 SHA1 摘要。

问题是这个摘要是否会像我连接子节点的字符串表示而不是子节点的摘要一样“好”？

谢谢

Answer 1

这会比散列孩子的串联更好。考虑以下树：

• 一种
  • AA
  • AB

连接时，它变成“AAAB”。与以下树对比：

• 一种
  • AAA
  • 乙

不同，但连接的哈希值是相同的。

Answer 2

假设您可以选择节点标签中永远不允许出现的 Unicode 字符。

然后，您可以使用流 API（如 Java MessageDigest）类以树顺序提供所有标签，并在其间插入保留的分隔符。

最后，您有一个相对紧凑的摘要，无需支付额外级别的 SHA 计算。

编辑

上面的方案不太正确，但是，再一次，原始问题也不是，因为它没有对树的结构进行编码。代码需要为每个节点构造某种比遍历顺序更强的 ID，并将其包含在节点的哈希输入中，以便具有不同形状但相同标签的树不会进行相同的哈希处理。

如果树顺序很重要但精确结构不重要，则答案中的原始方案有效。