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

Question

根据Java in Set的合同,"不允许集合将自己包含为元素"(来源).但是,对于HashSet of Objects,这是可能的,如下所示:

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

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

Answer 1

其他人已经通过提及罗素的悖论从数学的角度指出了为什么它是值得怀疑的.

但是,这不能在技术层面上回答您的问题.

那么让我们剖析一下:

首先,再次从界面的JavaDoc相关部分:Set

注意:如果将可变对象用作set元素,则必须非常小心.如果在对象是集合中的元素的同时以影响等于比较的方式更改对象的值,则不指定集合的​​行为.这种禁令的一个特例是,不允许集合将自身作为一个要素包含在内.

有趣的是,界面的JavaDocList做了类似的,虽然有些弱,但同时更多的技术声明:

虽然列表允许将自己包含为元素,但建议极其谨慎:在这样的列表中不再明确定义equals和hashCode方法.

最后,关键是接口的JavaDocCollection,它是接口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);

该add方法Set基本上无法检测添加的对象是否对该集合本身有一些(间接)引用.

长话短说:

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

Answer 2

添加到收藏本身曾经导致测试通过.添加两次会导致StackOverflowError您所寻求的.

从个人开发人员的角度来看,强制检查底层代码以防止这种情况是没有任何意义的.StackOverflowError如果您尝试执行此操作太多次,或计算hashCode- 这将导致即时溢出 - 您获得代码的事实应该足以确保没有理智的开发人员将这种代码保留在他们的代码库中.

Answer 3

您需要阅读完整的文档并完整引用它:

如果在对象是集合中的元素的同时以影响等于比较的方式更改对象的值,则不指定集合的行为.这种禁令的一个特例是,不允许集合将自身作为一个要素包含在内.

实际限制在第一句中.如果集合的元素发生变异,则行为未指定.

由于将一个集合添加到自身会使其发生变异,并再次添加它会再次变异,结果是未指定的.

请注意,限制是行为未指定,并且该限制的特殊情况是将集合添加到自身.

因此,文档说,换句话说,为自己添加一个集合会导致未指定的行为,这就是您所看到的.由具体的实现来处理(或不处理).

Answer 4

我同意你的观点,从数学的角度来看,这种行为确实没有意义.

这里有两个有趣的问题:首先,Set界面的设计者在多大程度上试图实现数学集？其次,即使它们不是,它在多大程度上豁免了它们的集合论规则？

对于第一个问题,我将向您指出Set 的文档:

不包含重复元素的集合.更正式地说,集合不包含元素对e1和e2,使得e1.equals(e2)和至多一个null元素.正如其名称所暗示的,该界面模拟数学集抽象.

值得一提的是,目前的集理论公式不允许集合成为它们自己的成员.(参见规则公理).这部分是由于罗素的悖论,它暴露了天真集理论中的矛盾(允许集合成为任何对象的集合 - 没有禁止集合包括他们自己).理发师悖论经常说明这一点:假设在一个特定的城镇,理发师会刮掉所有不刮胡子的男人 - 只有男人.问题:理发师自己刮胡子吗？如果他这样做,那就违反了第二个限制; 如果他不这样做,则违反了第一个约束.这显然在逻辑上是不可能的,但实际上在朴素集合理论的规则下是完全允许的(这就是为什么集合论的新"标准"公式明确禁止集合自身​​).

在这个关于Math.SE的问题中,有关为什么集合不能成为自身元素的讨论.

话虽如此,这提出了第二个问题:即使设计师没有明确地试图建模数学集,这是否完全"免除"与天真集理论相关的问题？我认为不是 - 我认为困扰幼稚集理论的许多问题都会困扰任何类型的集合,这些集合在类似于天真集理论的方式上受到了不充分的约束.实际上,我可能会对此进行过多的阅读,但Set文档中a的定义的第一部分听起来像天真集合理论中的直觉概念:

不包含重复元素的集合.

诚然(和他们的信用),他们这样做的地方,至少一些在此限制以后(包括说明你真的不应该尝试有一组包含本身),但你可能会问,它是否是真正的"足够",以避免问题用朴素集理论.这就是为什么,例如,当您尝试计算包含自身的HashSet的哈希码时,您有一个"乌龟一直向下"的问题.正如其他人所暗示的那样,这不仅仅是一个实际问题 - 它说明了这类公式的基本理论问题.

作为一个简短的题外话,我确实认识到,当然,对于任何集合类对数学集的真实建模的接近程度有一些限制.例如,Java的文档警告在集合中包含可变对象的危险.其他一些语言,比如Python,至少试图完全禁止多种可变对象:

使用字典实现集合类.因此,对集合元素的要求与字典键的要求相同; 即,该元素定义了__eq__()和__hash__().因此,集合不能包含可变元素,例如列表或字典.但是,它们可以包含不可变集合,例如元组或ImmutableSet实例.为了方便实现集合集,内部集合自动转换为不可变形式,例如,Set([Set(['dog'])])转换为Set([ImmutableSet(['dog'])]).

其他人指出的另外两个主要差异是

• Java集是可变的
• Java集是有限的.显然,任何集合类都是如此:除了对实际无穷大的担忧之外,计算机只有有限的内存量.(有些语言,比如Haskell,有懒惰的无限数据结构;但是,在我看来,一个类似法律的选择序列似乎比经典集合理论更自然地模拟这些,但这只是我的意见).

TL; DR不,它确实不应该被允许(或者,至少,你永远不应该这样做),因为集合不能成为他们自己的成员.