java - 是否应该允许在 Java 中将 HashSet 添加到自身？

Question

根据 Java 中的 Set 约定，“集合不允许将自身包含为元素”(source)。然而，这在对象的 HashSet 的情况下是可能的，如下所示:

Set<Object> mySet = new HashSet<>();
mySet.add(mySet);
assertThat(mySet.size(), equalTo(1));

这个断言通过了，但我希望行为是结果集为 0 或抛出异常。我意识到 HashSet 的底层实现是 HashMap，但似乎在添加元素之前应该进行相等性检查以避免违反该契约(Contract)，不是吗？

Answer 1

其他人已经通过引用 Russell's paradox 指出了为什么从数学角度来看这是有问题的。 .

不过，这并不能在 技术 层面回答您的问题。

让我们来剖析一下:

首先，再次介绍 JavaDoc of the Set interface: 中的相关部分。

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.

有趣的是，JavaDoc of the List interface做了一个类似的，虽然有点弱，但同时更技术性的声明:

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.

最后，关键在于 JavaDoc of the Collection interface ，它是 Set 和 List 接口(interface)的共同祖先:

Some collection operations which perform recursive traversal of the collection may fail with an exception for self-referential instances where the collection directly or indirectly contains itself. This includes the clone(), equals(), hashCode() and toString() methods. Implementations may optionally handle the self-referential scenario, however most current implementations do not do so.

^(我强调)

粗体部分暗示了为什么您在问题中提出的方法还不够:

it seems like there should be an equality check before adding an element to avoid violating that contract, no?

这对你没有帮助。关键是当集合直接或间接包含自身时，您总会遇到问题。想象一下这种情况:

Set<Object> setA = new HashSet<Object>();
Set<Object> setB = new HashSet<Object>();
setA.add(setB);
setB.add(setA);

显然，这两个集合都直接包含自身。但它们中的每一个都包含另一个 - 因此，它们本身间接。这无法通过简单的引用相等检查(在 add 方法中使用 ==)来避免。

---

避免这种“不一致的状态”在实践中基本上是不可能的。当然理论上是可以的，引用 Reachability计算。事实上，垃圾收集器基本上必须这样做!

但是当涉及到自定义类时，在实践中就变得不可能了。想象这样一个类:

class Container {

    Set<Object> set;

    @Override 
    int hashCode() {
        return set.hashCode(); 
    }
}

搞砸这个和它的set:

Set<Object> set = new HashSet<Object>();
Container container = new Container();
container.set = set;
set.add(container);

Set的add方法基本上没有办法检测到那里添加的对象是否有some(间接)引用集合本身。

长话短说:

你不能阻止程序员把事情搞砸。