How to hash and check for equality of objects with circular references
- by mfya
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.
