hash - 如何散列和检查具有循环引用的对象的相等性

Question

我有一个 循环 由 Node 对象表示的类似图的结构。
一个节点要么是一个标量值(叶)，要么是一个 n>=1 节点(内部节点)的列表。

由于可能存在循环引用，我不能简单地使用递归 HashCode() 函数，该函数结合了所有子节点的 HashCode():它将以无限递归结束。

虽然 HashCode() 部分似乎至少可以通过标记和忽略已经访问过的节点来实现，但我在考虑 Equals() 的有效算法时遇到了一些麻烦。

令我惊讶的是，我没有找到任何关于此的有用信息，但我相信许多聪明人已经想到了解决这些问题的好方法......对吗？

示例( python ):

A = [ 1, 2, None ]; A[2] = A  
B = [ 1, 2, None ]; B[2] = B

A 等于 B，因为它表示完全相同的图。

顺便提一句。这个问题不针对任何特定语言，但在 Java 中为所描述的 Node 对象实现 hashCode() 和 equals() 将是一个很好的实际示例。

Answer 1

如果你把它想象成图，叶节点是一个只有一个连接的节点，一个复杂节点是一个至少有 2 个连接的节点。所以你得到了它，实现一个简单的 BFS 算法，将哈希函数应用于每个节点它通过然后丢弃结果。通过这种方式，您可以确保自己不会陷入圈套或多次通过任何节点。

实现可能非常简单。阅读它 here .