How to write the hashCode() function for a cyclic graph node?

Question

I have the following class that is used as part of a graph :

public class MyNode {

    private String name;

    private Set<MyNode> parents;

    private Set<MyNode> children;

    // getters and setters
}

When I use Eclipse's Source / Generate hashCode() and equals(), it generates this method:

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((children == null) ? 0 : children.hashCode());
    result = prime * result + ((name == null) ? 0 : name.hashCode());
    result = prime * result + ((parents == null) ? 0 : parents.hashCode());
    return result;
}

The problem is that this method goes from the current object to its children, then while computing the hashCode() of the first child, it gets back to the original node through the parents.hashCode() but don't know that the hashCode() has already been computed there. It then reenters the children of the original node, and it gives a beautiful infinite loop.

Question : how can I check that two instances of MyNode are the same object while, at the same time, avoid the infinite loop? Is this acceptable to add a visited boolean in the MyNode class, for the purpose of stopping the exploration? Or is there a better solution?

Thanks!

Answer 1

You should not use children or parents of node when implementing hashCode and equals. They are mutable properties. Calculation of hashCode will differ after changing edges and will result in broken Maps and Set collections.

Implement hashCode and equals using only immutable fields that makes a distinct natural key for an object. A name might be a good candidate, unless it can be changed.

If no immutable fields exists, either:

1. Don't override hashCode and equals methods, defaults will be fine. It will make each class instance unique.
2. Make some unique id field (by sequance) and use it as a seed in hashCode and comparison in equals.

Answer 2

You can check whether two objects are the same instance using the == opearator:

if(obj0 == obj1)

If you want to use a visited flag you should implement it using a lookup (a Map for example) since after your code runs you have to reset those flags.

I suggest ignoring parents/children and adding an unique id to each node instead.