Set<Object> mySet = new HashSet<>();
mySet.add(mySet);
assertThat(mySet.size(), equalTo(1));
这个断言通过了,但我期望的行为应该是要么得到的集合为空,要么抛出异常。我知道 HashSet 的底层实现是 HashMap,但在添加元素之前似乎应该有一个相等性检查来避免违反契约,不是吗?
Set<Object> mySet = new HashSet<>();
mySet.add(mySet);
assertThat(mySet.size(), equalTo(1));
这个断言通过了,但我期望的行为应该是要么得到的集合为空,要么抛出异常。我知道 HashSet 的底层实现是 HashMap,但在添加元素之前似乎应该有一个相等性检查来避免违反契约,不是吗?
其他人已经指出了从数学角度来看这是可疑的,他们提到了罗素悖论。
但这并没有回答你在技术层面上的问题。
让我们仔细研究一下:
首先,再次引用 Set
接口的 JavaDoc:
注意:如果使用可变对象作为集合元素,则必须非常小心。如果更改对象的值以影响等于比较,同时该对象是集合中的元素,则不会指定集合的行为。此禁止的一个特殊情况是,集合不能包含自身作为元素。
有趣的是,List
接口的 JavaDoc也做出了类似的、虽然略微弱化,但同时更具技术性的陈述:
允许列表将自身作为元素包含在内,但应极度小心:在这样的列表上,
equals
和hashCode
方法不再定义明确。
最后,在 Collection
接口 中的关键在于,它是 Set
和 List
接口的共同祖先:
对于递归遍历集合的某些集合操作,如果集合直接或间接包含自身,则可能因递归失败而导致异常。这包括
clone()
、equals()
、hashCode()
和toString()
方法。实现可以选择处理自引用的情况,但大多数当前的实现都不会这样做。
(我加粗了)
粗体部分提示了为什么你在问题中提出的方法不能足够有效:
看起来应该在添加元素之前进行相等性检查,以避免违反该协定,不是吗?
这在这里无济于事。关键点是当集合直接或间接地包含自身时,总会遇到问题。想象一下以下场景:
Set<Object> setA = new HashSet<Object>();
Set<Object> setB = new HashSet<Object>();
setA.add(setB);
setB.add(setA);
显然,这两个集合都不会直接包含它们自己。但是它们各自包含对方 - 因此,它们间接地包含了自己。这不能通过简单的引用相等性检查(在add
方法中使用==
)来避免。
在实践中基本上不可能避免这种“不一致状态”。当然,在理论上使用可达性计算是可能的,参考可达性计算。事实上,垃圾回收器就必须要做到这一点!
但是当涉及到自定义类时,这变得在实践中是不可能的。想象一个像这样的类:
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
方法基本上无法检测添加的对象是否具有对集合本身的 一些(间接)引用。
简而言之:
您无法防止程序员搞砸事情。
将集合加入自身一次会使测试通过。而将其添加两次会导致你所寻求的StackOverflowError
。
从个人开发者的角度来看,强制在基础代码中进行检查以防止这种情况没有任何意义。如果尝试做太多次这样的操作,或计算hashCode
-这将导致立即溢出-在您的代码中会得到StackOverflowError
,这足以确保任何理智的开发者不会在他们的代码库中保留此类代码。
java.util.Set
不是数学中的集合,例如,它可能会随时间改变,必须是有限的等。在数学中,根据ZFC公理系统的良基要求,一个集合不能是其自身的成员,但是还有其他的公理系统可以允许这种情况。详见https://en.wikipedia.org/wiki/Non-well-founded_set_theory。 - Reinstate Monicajava.util.Set
不允许一个集合包含自身,完全是出于实际原因(例如,你如何计算这样一个集合的哈希码?),而不是由于某个晦涩的数学理论。 - Reinstate Monicacontains
方法的潜在有用近似。但这不是java.util.Set
的目的! - ruakh你需要阅读完整的文档并完全引用:
如果在对象作为集合元素时以影响等式比较的方式更改对象的值,则不指定集合的行为。该禁止的一个特殊情况是不允许将集合本身作为元素包含在内。
实际上,限制在第一句话中。如果集合的元素被修改,则其行为是未指定的。
由于将一个集合添加到它自身会导致其变化,而再次添加会再次导致变化,因此结果是未指定的。
请注意,限制是行为未指定,而该限制的特殊情况是将集合添加到自身。
因此,换句话说,文档表示将集合添加到自身会导致未指定的行为,这就是您所看到的。具体实现要处理(或不处理)这个问题。
我同意你的观点,从数学角度来看,这种行为确实没有意义。
这里有两个有趣的问题:首先,Set
接口的设计者在多大程度上试图实现数学集合?其次,即使他们没有这样做,那么它是否可以豁免他们遵守集合理论的规则?
对于第一个问题,我将指向 Set文档:
包含不重复元素的集合。更正式地说,集合不包含任何一对元素e1和e2,使得e1.equals(e2),并且最多一个空元素。正如其名称所暗示的,该接口对数学集合抽象进行建模。
值得注意的是,当前的集合理论不允许集合成为其自身的成员。(请参见正则公理) 这部分归因于Russell's Paradox(罗素悖论),该悖论揭示了在朴素集合论(允许集合是任何对象的集合-没有禁止集合包含自身的规定)中的矛盾。这常常被理发师悖论所说明:假设在一个特定的城镇中,理发师剃光所有男人——只有不为自己剃须的男人。问题:理发师剃自己吗?如果他剃了,那么违反第二个约束;如果他没有剃,那么违反第一个约束。这显然是逻辑上不可能的,但实际上,在朴素的集合论规则下是完全允许的(这就是为什么更新的“标准”集合论明确禁止集合包含它们自己的原因)。
这个问题在Math.SE上的这个问题中有更多讨论,关于为什么集合不能是它们自己的元素。
话虽如此,这引出了第二个问题:即使设计者没有明确尝试建模数学集合,这是否完全免于与朴素集合论相关的问题?我认为不是 - 我认为许多困扰朴素集合论的问题将困扰任何一种收集方式,只要它在类似于朴素集合论的方式下受到不足够约束。事实上,我可能读多了一些东西,但文档中对Set
的第一部分定义听起来非常像朴素集合论中集合直觉概念的定义:
包含无重复元素的集合。
诚然(并且值得称赞),他们稍后至少会对此加以一些限制(包括声明您真的不应该尝试让Set包含自身),但是您可能会质疑它是否真正“足够”避免与朴素集合论相关的问题。例如,在尝试计算包含自身的HashSet的哈希代码时,您会遇到“无底龟”的问题。这不仅仅是实际问题 - 它也说明了这种形式的根本理论问题。
顺便说一句,我确实意识到,当然任何集合类都有一些限制,不能完全建模数学集合。例如,Java文档警告不要在集合中包含可变对象的危险。一些其他语言(例如Python)至少试图完全禁止许多种可变对象:
集合类使用字典实现。因此,集合元素的要求与字典键的要求相同;即元素必须同时定义
__eq__()
和__hash__()
。 因此,集合不能包含可变元素,例如列表或字典。但是,它们可以包含不可变集合,例如元组或ImmutableSet的实例。为了方便实现集合的集合,内部集合会自动转换为不可变形式,例如Set([Set(['dog'])])
转换为Set([ImmutableSet(['dog'])])
。其他人指出的另外两个主要区别是:
简而言之, 不应该允许集合成为其自身成员(或者至少不应该这样做),因为集合不能包含自身。
==
相等性只能处理少部分不允许的情况。 - Turing85