如何散列并检查具有循环引用的对象的相等性
我有一个由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() 将是一个很好的实际示例。
I have a cyclic graph-like structure that is represented by Node objects.
A Node is either a scalar value (leaf) or a list of n>=1 Nodes (inner node).
Because of the possible circular references, I cannot simply use a recursive HashCode() function, that combines the HashCode() of all child nodes: It would end up in an infinite recursion.
While the HashCode() part seems at least to be doable by flagging and ignoring already visited nodes, I'm having some troubles to think of a working and efficient algorithm for Equals().
To my surprise I did not find any useful information about this, but I'm sure many smart people have thought about good ways to solve these problems...right?
Example (python):
A = [ 1, 2, None ]; A[2] = A
B = [ 1, 2, None ]; B[2] = B
A is equal to B, because it represents exactly the same graph.
BTW. This question is not targeted to any specific language, but implementing hashCode() and equals() for the described Node object in Java would be a good practical example.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我也想知道一个好的答案。到目前为止，我使用基于访问集的解决方案。
当计算哈希时，我遍历图结构并保留一组访问过的节点。我不会两次进入同一个节点。当我点击已经访问过的节点时，哈希会返回一个没有递归的数字。
这甚至适用于平等比较。我比较节点数据并递归调用子节点。当我点击一个已经访问过的节点时，比较返回 true 而无需递归。
I would like to know a good answer as well. So far I use a solution based on the visited set.
When computing hash, I traverse the graph structure and I keep a set of visited nodes. I do not enter the same node twice. When I hit an already visited node, the hash returns a number without recursion.
This work even for the equality comparison. I compare node data and recursively invoke on the children. When I hit an already visited node, the comparison returns true without recursion.
如果您将其视为图，则叶节点是仅具有 1 个连接的节点，而复杂节点是至少具有 2 个连接的节点。因此，您可以通过这种方式实现一种简单的 BFS 算法，该算法将哈希函数应用于每个节点它经过的节点然后丢弃结果。通过这种方式，您可以确保自己不会陷入循环或多次经过任何节点。
实施可能非常简单。请此处阅读相关内容。
If you think about this as graph, a leaf node is a node that has only one connection and a complex node is one with at least 2. So one you got it that way, implement a simple BFS algorithm witch applies the hash function to each node it passes and then drops the result. This way you ensure yourself that you wont fall in cicles or go through any node more than once.
The implementation could be very straihgtforward. Read about it here.
您需要遍历图表。
这里有一个问题：这些图相等吗？
如果是这样，您需要一组 (Node, Node) 元组。使用此设置来捕获循环，并在捕获循环时返回“true”。
如果没有，您可以提高效率，并使用从节点到节点的映射。然后，在遍历图表时，建立一组对应关系。 （在上面的情况下，A 将对应于 B，A[2] 将对应于 B[2]，&c。）然后，当您访问节点对时，请确保确切的对在地图中；如果不是，则图表不匹配。
You need to walk the graphs.
Here's a question: are these graphs equal?
If so, you need a set of (Node, Node) tuples. Use this set to catch loops, and return 'true' when you catch a loop.
If not, you can be a bit more efficient, and use a map from Node to Node. Then, when walking the graphs, build up a set of correspondances. (In the case above, A would correspond to B, A[2] would correspond to B[2], &c.) Then when you visit a node pair you make sure the exact pair is in the map; if it isn't the graph doesn't match.