为什么许多编程语言中的集合不是真正的集合

本文关键字:集合 许多 为什么 编程语言 | 更新日期: 2023-09-27 18:29:50

在几种编程语言中,有Set集合,它们被认为是有限集数学概念的实现。

然而,这不一定是真的,例如在C#Java中,HashSet<T>的两个实现都允许您将任何HashSet<T>集合添加为其自身的成员。根据数学集合的现代定义,这是不允许的。

背景:

根据天真集合论,集合的定义是:

集合是不同对象的集合。

然而,这个定义导致了著名的罗素悖论以及其他悖论。为了方便起见,罗素的悖论是:

设R是不是其自身成员的所有集合的集合。如果R不是其自身的成员,则其定义规定它必须包含自身,如果包含自身,则与自身矛盾定义为不是其自身成员的所有集合的集合。

所以根据现代集合论(参见:ZFC),集合的定义是:

集合是不同对象的集合,没有一个是集合它本身

具体来说,这是正则性公理的结果。

那又怎样?这意味着什么?为什么这个问题出现在StackOverflow上

罗素悖论的含义之一是并非所有集合都是集合。此外,在这一点上,数学家们放弃了集合的定义,认为它是通常的英语定义。所以我相信这个问题在一般的编程语言设计中有很大的分量。

问题:

那么,为什么在某种形式上在设计中使用这些原则的编程语言在其语言库中实现Set时会忽略这些原则呢?

其次,这在数学概念的其他实现中是否常见?

也许我有点挑剔,但如果这些是Set的真正实现,那么为什么要忽略定义的一部分呢?

更新

添加C#和Java代码片段示例行为:

Java代码段:

Set<Object> hashSet = new HashSet<Object>();
hashSet.add(1);
hashSet.add("Tiger");
hashSet.add(hashSet);
hashSet.add('f');
Object[] array = hashSet.toArray();
HashSet<Object> hash = (HashSet<Object>)array[3];
System.out.println("HashSet in HashSet:");       
for (Object obj : hash)
    System.out.println(obj);
System.out.println("'nPrinciple HashSet:");
for (Object obj : hashSet)
    System.out.println(obj);

哪个打印出来:

HashSet in HashSet:
f
1
Tiger
[f, 1, Tiger, (this Collection)]
Principle HashSet:
f
1
Tiger
[f, 1, Tiger, (this Collection)]

C#代码段:

HashSet<object> hashSet = new HashSet<object>();
hashSet.Add(1);
hashSet.Add("Tiger");
hashSet.Add(hashSet);
hashSet.Add('f');
object[] array = hashSet.ToArray();
var hash = (HashSet<object>)array[2];
Console.WriteLine("HashSet in HashSet:");
foreach (object obj in hash)
     Console.WriteLine(obj);
Console.WriteLine("'nPrinciple HashSet:");
foreach (object obj in hashSet)
     Console.WriteLine(obj);

哪个打印出来:

HashSet in HashSet:
1
Tiger
System.Collections.Generic.HashSet`1[System.Object]
f
Principle HashSet:
1
Tiger
System.Collections.Generic.HashSet`1[System.Object]
f

更新2

关于Martijn Courteaux的第二点,即可以以计算效率的名义进行:

我用C#做了两个测试集合。它们是相同的,只是在其中一个的Add方法中——我添加了以下检查:if (this != obj),其中obj是要添加到集合中的项。

我分别对它们进行了计时,它们将添加100000个随机整数:

带检查:~28毫秒

无检查:~21毫秒

这是一个相当显著的性能提升。

为什么许多编程语言中的集合不是真正的集合

编程语言集实际上与ZFC集不同,但原因与您想象的完全不同:

  1. 你不能通过理解来形成一个集合(即所有对象的集合,这样…)。注意,这已经阻止了所有(我相信)天真的集合论悖论,所以它们是无关的。

  2. 它们通常不可能是无限的。

  3. 存在不是集合的对象(在ZFC中只有集合)。

  4. 它们通常是可变的(即,您可以向集合添加元素/从集合中删除元素)。

  5. 它们包含的对象可以是可变的。

的答案

那么,为什么在某种形式上在设计中使用这些原则的编程语言在其语言库中实现Set时会忽略这些原则呢?

语言不使用这些原则。

我不能代表C#说话,但就Java而言,集合就是集合。如果您查看Set接口的javadoc,您将看到(emphasis mine):

注意:如果可变对象用作集合元素,则必须非常小心。当对象是集合中的元素时,如果对象的值以影响相等比较的方式更改,则不指定集合的行为这种禁止的一个特殊情况是,不允许集合将自身包含为元素

禁令是否得到了积极执行尚不清楚(例如,向其本身添加哈希集不会引发任何例外),但至少有明确的文件表明,你不应该尝试,因为这样会导致行为未明确。

嗯,我认为这是因为一些原因:

  1. 出于非常特定的编程目的,您可能希望创建一个包含其自身的集合。当你这样做的时候,你并不真正关心集合在数学上意味着什么,你只想享受Set提供的功能:在不创建重复条目的情况下向集合"添加"元素。(老实说,我想不出你想在什么情况下这样做。)

  2. 出于性能目的。你想要使用集合并让它包含自己的机会是非常非常罕见的。因此,每次尝试添加元素时都要检查它是否是集合本身,这将是对计算能力、能量、时间、性能和环境健康的浪费。

在java中,集合是数学集合。可以插入对象,但集合中只能有一个对象。来自javadoc的关于集合的信息:

一个不包含重复元素的集合。更正式地说,集合不包含一对元素e1和e2,使得e1.equals(e2),最多包含一个null元素。正如其名称所暗示的,这个接口为数学集合抽象建模。

来源:http://docs.oracle.com/javase/7/docs/api/