How to detect if the List contains itself in Java

Question

From Java documentation:

Note: While it is permissible for lists to contain themselves as elements, extreme caution is advised: the equals and hashCode methods are no longer well defined on such a list.

The problem is that the hash code of a List object is computed recursively.

 int hashCode = 1;
 for (E e : list)
     hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

The question is how to make my code idiot proof and detect whether a List object (or some of its items or even deeper) contains the List object itself.

How to keep a list of List objects while traversing the List object and be able to call contains()-like method? Is keeping System.identityHashCode(object) and testing against it good enough?

Answer 1

System.identityHashCode will help, but it'll almost certainly be simpler to use one of the built-in tools to track objects by identity -- IdentityHashMap.

boolean containsCircularReference(Iterable<?> iterable) {
  return containsCircularReference(
     iterable,
     Collections.newSetFromMap(new IdentityHashMap<Object, Boolean>()));
}

private boolean containsCircularReference(Object o, Set<Object> seen) {
  if (seen.contains(o)) {
    return true;
  }
  seen.add(o);
  if (o instanceof Iterable) {
    for (Object o2 : (Iterable<?>) o) {
      if (containsCircularReference(o2, seen)) {
        return true;
      }
    }
  }
  return false;
}

For reference, you cannot depend on System.identityHashCode being collision-free. For starters, you can allocate more than 2^32 objects in a JVM, and there are only 2^32 distinct identityHashCodes possible...

If it's not just membership in an Iterable, but any circular reference at all, that gets harder, albeit doable with reflection. That said, the existence of that sort of circular reference does not necessarily imply equals and hashCode won't work; circular references are perfectly okay as long as the references in equals and hashCode methods are acyclic, and there's no universal way to detect that.