Java 中是否应该允许将 HashSet 添加到自身？
Should a HashSet be allowed to be added to itself in Java?
根据 Java、"it is not permissible for a set to contain itself as an element" (source) 的 Set 合同。然而，这在对象的 HashSet 的情况下是可能的，如下所示：
Set<Object> mySet = new HashSet<>();
mySet.add(mySet);
assertThat(mySet.size(), equalTo(1));
此断言通过，但我希望行为是将结果集设为 0 或抛出异常。我意识到 HashSet 的底层实现是 HashMap，但似乎在添加元素之前应该进行相等性检查以避免违反该契约，不是吗？
将集合添加到自身一次 会导致测试通过。添加它 两次 会导致您正在寻找的 WhosebugError。
从个人开发人员的角度来看，强制检查底层代码以防止这种情况没有任何意义。如果您尝试多次执行此操作或计算 hashCode（这会导致即时溢出），您的代码中会出现 WhosebugError，这一事实足以确保任何理智的开发人员都不会将这种代码保留在他们的代码库中。
我同意你的看法，从数学的角度来看，这种行为确实没有意义。
这里有两个有趣的问题：首先，Set 界面的设计者在多大程度上试图实现数学集？其次，即使他们不是，这在多大程度上使他们免于集合论的规则？
对于第一个问题，我将向您指出集合的documentation：
A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.
这里值得一提的是，当前的集合论公式不允许集合成为其自身的成员。 （请参阅 Axiom of regularity). This is due in part to Russell's Paradox, which exposed a contradiction in naive set theory (which permitted a set to be any collection of objects - there was no prohibition against sets including themselves). This is often illustrated by the Barber Paradox：假设在某个特定城镇，理发师为所有男性刮胡子 - 仅 不刮胡子的男性。问题： barber shave himself? 如果他这样做，就违反了第二个约束；如果他不这样做，就违反了第一个约束。这显然在逻辑上是不可能的，但实际上在朴素集合论的规则下是完全允许的（这就是为什么较新的"standard" 集合论的表述明确禁止集合包含自身）。
在 this question on Math.SE 中有更多关于为什么集合不能是它们自身的元素的讨论。
话虽如此，这引出了第二个问题：即使设计者没有明确地尝试对数学集合建模，这是否完全"exempt" 从与朴素集理论相关的问题？我不这么认为——我认为许多困扰朴素集合论的问题会困扰 任何 种集合，这些集合在类似于朴素集合论的方式上没有得到足够的约束。事实上，我可能对此读得太多了，但是文档中 Set 定义的第一部分听起来很像朴素集合论中集合的直观概念：
A collection that contains no duplicate elements.
不可否认（值得称赞的是），他们确实在稍后对此设置了至少 一些 限制（包括声明你真的不应该尝试让一个 Set 包含它自己） , 但你可能会质疑它是否真的 "enough" 避免了朴素集合论的问题。这就是为什么在尝试计算包含自身的 HashSet 的哈希码时出现 "turtles all the way down" 问题的原因。正如其他一些人所建议的那样，这不仅仅是一个实际问题 - 它说明了此类公式的基本理论问题。
作为一个简短的题外话，我确实认识到，对于任何集合 class 能够真正模拟数学集的程度，当然存在一些限制。例如，Java 的文档警告在集合中包含可变对象的危险。其他一些语言，例如 Python，至少尝试 ban many kinds of mutable objects entirely:
The set classes are implemented using dictionaries. Accordingly, the requirements for set elements are the same as those for dictionary keys; namely, that the element defines both __eq__() and __hash__(). As a result, sets cannot contain mutable elements such as lists or dictionaries. However, they can contain immutable collections such as tuples or instances of ImmutableSet. For convenience in implementing sets of sets, inner sets are automatically converted to immutable form, for example, Set([Set(['dog'])]) is transformed to Set([ImmutableSet(['dog'])]).
其他人指出的另外两个主要区别是
- Java 集是可变的
- Java 集合是有限的。显然，这对于 any 集合 class 是正确的：除了担心 actual infinity, computers only have a finite amount of memory. (Some languages, like Haskell, have lazy infinite data structures; however, in my opinion, a lawlike choice sequence 似乎是比 classical 集合更自然的模型理论，但这只是我的意见）。
TL;DR 不，它真的不应该被允许（或者，至少，你永远不应该这样做），因为集合不能是它们自己的成员。
您需要阅读完整文档并完整引用：
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.
真正的限制在第一句。如果集合中的元素发生变化，则行为是 未指定。
因为给它自己添加一个集合会变异它，再次添加它会再次变异它，所以结果是不确定的。
请注意，限制是行为未指定，并且该限制的特例是将集合添加到自身.
所以文档说，换句话说，向自身添加一个集合会导致未指定的行为，这就是您所看到的。具体处理（或不处理）由具体实现决定。
其他人已经从数学角度指出了为什么有问题，参考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 接口的共同祖先：
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 方法中使用 ==）来避免。
避免这样的"inconsistent state"在实践中基本上是不可能的。当然在理论上是可能的，使用参考 Reachability 计算。事实上，垃圾收集器基本上必须做到这一点！
但是当涉及自定义 classes 时，在实践中 变得不可能。想象一下这样的 class：
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（间接）引用自己设置。
长话短说：
你无法阻止程序员把事情搞砸。
根据 Java、"it is not permissible for a set to contain itself as an element" (source) 的 Set 合同。然而，这在对象的 HashSet 的情况下是可能的，如下所示：
Set<Object> mySet = new HashSet<>();
mySet.add(mySet);
assertThat(mySet.size(), equalTo(1));
此断言通过，但我希望行为是将结果集设为 0 或抛出异常。我意识到 HashSet 的底层实现是 HashMap，但似乎在添加元素之前应该进行相等性检查以避免违反该契约，不是吗？
将集合添加到自身一次 会导致测试通过。添加它 两次 会导致您正在寻找的 WhosebugError。
从个人开发人员的角度来看，强制检查底层代码以防止这种情况没有任何意义。如果您尝试多次执行此操作或计算 hashCode（这会导致即时溢出），您的代码中会出现 WhosebugError，这一事实足以确保任何理智的开发人员都不会将这种代码保留在他们的代码库中。
我同意你的看法，从数学的角度来看，这种行为确实没有意义。
这里有两个有趣的问题：首先，Set 界面的设计者在多大程度上试图实现数学集？其次，即使他们不是，这在多大程度上使他们免于集合论的规则？
对于第一个问题，我将向您指出集合的documentation：
A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.
这里值得一提的是，当前的集合论公式不允许集合成为其自身的成员。 （请参阅 Axiom of regularity). This is due in part to Russell's Paradox, which exposed a contradiction in naive set theory (which permitted a set to be any collection of objects - there was no prohibition against sets including themselves). This is often illustrated by the Barber Paradox：假设在某个特定城镇，理发师为所有男性刮胡子 - 仅 不刮胡子的男性。问题： barber shave himself? 如果他这样做，就违反了第二个约束；如果他不这样做，就违反了第一个约束。这显然在逻辑上是不可能的，但实际上在朴素集合论的规则下是完全允许的（这就是为什么较新的"standard" 集合论的表述明确禁止集合包含自身）。
在 this question on Math.SE 中有更多关于为什么集合不能是它们自身的元素的讨论。
话虽如此，这引出了第二个问题：即使设计者没有明确地尝试对数学集合建模，这是否完全"exempt" 从与朴素集理论相关的问题？我不这么认为——我认为许多困扰朴素集合论的问题会困扰 任何 种集合，这些集合在类似于朴素集合论的方式上没有得到足够的约束。事实上，我可能对此读得太多了，但是文档中 Set 定义的第一部分听起来很像朴素集合论中集合的直观概念：
A collection that contains no duplicate elements.
不可否认（值得称赞的是），他们确实在稍后对此设置了至少 一些 限制（包括声明你真的不应该尝试让一个 Set 包含它自己） , 但你可能会质疑它是否真的 "enough" 避免了朴素集合论的问题。这就是为什么在尝试计算包含自身的 HashSet 的哈希码时出现 "turtles all the way down" 问题的原因。正如其他一些人所建议的那样，这不仅仅是一个实际问题 - 它说明了此类公式的基本理论问题。
作为一个简短的题外话，我确实认识到，对于任何集合 class 能够真正模拟数学集的程度，当然存在一些限制。例如，Java 的文档警告在集合中包含可变对象的危险。其他一些语言，例如 Python，至少尝试 ban many kinds of mutable objects entirely:
The set classes are implemented using dictionaries. Accordingly, the requirements for set elements are the same as those for dictionary keys; namely, that the element defines both
__eq__()and__hash__(). As a result, sets cannot contain mutable elements such as lists or dictionaries. However, they can contain immutable collections such as tuples or instances of ImmutableSet. For convenience in implementing sets of sets, inner sets are automatically converted to immutable form, for example,Set([Set(['dog'])])is transformed toSet([ImmutableSet(['dog'])]).
其他人指出的另外两个主要区别是
- Java 集是可变的
- Java 集合是有限的。显然，这对于 any 集合 class 是正确的：除了担心 actual infinity, computers only have a finite amount of memory. (Some languages, like Haskell, have lazy infinite data structures; however, in my opinion, a lawlike choice sequence 似乎是比 classical 集合更自然的模型理论，但这只是我的意见）。
TL;DR 不，它真的不应该被允许（或者，至少，你永远不应该这样做），因为集合不能是它们自己的成员。
您需要阅读完整文档并完整引用：
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.
真正的限制在第一句。如果集合中的元素发生变化，则行为是 未指定。
因为给它自己添加一个集合会变异它，再次添加它会再次变异它，所以结果是不确定的。
请注意，限制是行为未指定，并且该限制的特例是将集合添加到自身.
所以文档说，换句话说，向自身添加一个集合会导致未指定的行为，这就是您所看到的。具体处理（或不处理）由具体实现决定。
其他人已经从数学角度指出了为什么有问题，参考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
equalsandhashCodemethods are no longer well defined on such a list.
最后，症结在 JavaDoc of the Collection interface，它是 Set 和 List 接口的共同祖先：
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()andtoString()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 方法中使用 ==）来避免。
避免这样的"inconsistent state"在实践中基本上是不可能的。当然在理论上是可能的，使用参考 Reachability 计算。事实上，垃圾收集器基本上必须做到这一点！
但是当涉及自定义 classes 时，在实践中 变得不可能。想象一下这样的 class：
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（间接）引用自己设置。
长话短说：
你无法阻止程序员把事情搞砸。