如何在Java中检测列表是否包含自身

Question

来自Java文档：

注意：虽然允许列表包含自身作为元素，但极其谨慎：在这样的列表上，equals和hashCode方法不再定义良好。

问题在于List对象的哈希码是递归计算的。

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

问题是如何使我的代码傻瓜化并检测List对象（或其某些项甚至更深层次的对象）是否包含List对象本身。

在遍历List对象时如何保持List对象的列表并能够调用类似contains（）的方法？保留System.identityHashCode（object）并测试它是否足够好？

- user1608790

---

你可以定义自己的列表类型吗？当另一个equals或hashCode调用开始时，您可以检测列表是否已经处于中间状态，但在多线程环境中使其正常工作可能会变得棘手。如果您需要使用ArrayList之类的东西，那么这是否可行取决于您需要处理什么类型的元素。如果列表元素具有包含您的列表的私有字段，则您可能永远不会知道。 - user2357112

Answer 1

System.identityHashCode可以帮助，但使用内置工具之一来跟踪对象标识（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;
}

需要注意的是，您不能依赖于System.identityHashCode不会发生冲突。首先，在JVM中可以分配超过2^32个对象，而可能的identityHashCode只有2^32个...

如果不仅仅是Iterable中的成员，而是任何循环引用，这就更难了，但是可以通过反射实现。话虽如此，存在这种循环引用并不一定意味着equals和hashCode无法正常工作；只要equals和hashCode方法中的引用是非循环的，循环引用就完全没问题，也没有通用的方法来检测这一点。

- Louis Wasserman