如何使用循环引用来散列和检查对象的相等性

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,因为它代表完全相同的图形.

BTW.这个问题并不针对任何特定的语言,但是在Java中为所描述的Node对象实现hashCode()和equals()将是一个很好的实际例子.

Answer 1

如果您将其视为图，则叶节点是仅具有 1 个连接的节点，而复杂节点是至少具有 2 个连接的节点。因此，您可以通过这种方式实现一种简单的 BFS 算法，该算法将哈希函数应用于每个节点它经过的节点然后丢弃结果。通过这种方式，您可以确保自己不会陷入循环或多次经过任何节点。

实施可能非常简单。在这里阅读相关内容。