c - 复杂结构的哈希

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 3 年前。

Improve this question

我想知道一种相对简单的方法来生成复杂 C 结构的哈希(在我的例子中形成一个图)。我所说的“简单”是指，如果可能的话，无需遍历它形成的所有节点。之后，我的目标是检查两个结构是否相同(由于它们的哈希值)，而且还要以有序的方式对它们进行排序。

例如，有用于数字或字符串的函数和算法，但我不知道对结构执行此操作的好方法。你会推荐什么？

Answer 1

Git 版本控制系统有一个像您所描述的哈希系统。 Git 存储库是 directed acyclic graph 。每次提交都是一个节点。

每个提交都有一个 ID。 ID 是一个哈希值。它对节点的内容及其所有连接的哈希进行哈希处理。

例如，如果您进行提交，它将有一个 ID，该 ID 是其内容的哈希值(sha256 校验和)。我们将该提交称为 A。如果您在 A 之上进行另一个提交，则其 ID 将是该提交内容的哈希值加上 A 的哈希值。等等。

A hash(A's content)
^
|
B hash(hash(B's content) + A's hash)
^
|
C hash(hash(C's content) + B's hash)

如果您有一个合并，其中单个合并提交有两个连接，它将使用两个节点的哈希值。

 C
 ^
 |\
 D E
 ^ ^
 |/
 F hash(hash(F's contents) + D's hash + E's hash)

最后，Git 还将节点存储在以其提交 ID 为关键字的哈希中，以便通过 ID 进行 O(1) 节点查找。

F 的哈希值取决于 D 和 E 的哈希值，而 D 和 E 的哈希值又取决于 C 的哈希值，而 C 的哈希值又取决于 B 的哈希值，而 B 的哈希值又取决于 A 的哈希值。 F 的哈希取决于整个存储库的内容。如果过去的任何提交发生更改，无论是内容还是连接，F 的哈希值都将无效。

这就是 Git 能够如此快速地比较存储库的更改的方式。它只需要比较每个分支尖端的提交 ID 来知道是否存在差异，然后向后工作，直到找到共同的提交 ID。它使用图表向后遍历提交历史记录，并使用哈希来查找是否存在共同的提交 ID。

<小时/>

此技术之所以有效，是因为 Git 的图是 DAG。连接仅指向一种方向(有向)，并且不存在环路(非循环)。也许这适用于您的情况，或者您可能会调整该技术。