TreeSet没有添加所有元素？

Question

我一直在研究不同Java集合类型的速度,并遇到了一些奇怪的东西.我将1,000,000个对象从静态数组添加到不同的集合类型并返回所需的时间.这部分代码工作正常.

在进一步的调查中,我注意到它TreeSet没有收到所有1,000,000个对象,并且每次都收到不同的金额.下面是将对象从数组传输到的方法TreeSet:

    public int treeSet(int num)
    {
       Date before = new Date();

       for(int i=0; i<num; i++) 
       {
           treeSet.add(personsArray[i]);
       }

       Date after = new Date();
       return (int) (after.getTime() - before.getTime());
    }

下面是调用treeSet()方法并测试其大小的代码.

    System.out.println("\tTree set with 1,000,000 objects--" + t.treeSet(1000000));
    System.out.println("Tree set contains " + t.treeSet.size() + " elements");

这个输出是:

    Tree set with 1,000,000 objects--1192
    Tree set contains 975741 elements

我希望有人可以向我解释为什么TreeSet没有收到所有的对象以及它为什么收到不一致的金额.

Answer 1

您几乎肯定会生成重复的Person对象.

在你的评论中,你说每个人都是从包含"数百个"名字和年龄的文本文件中的性别,名字和姓氏中随机生成的.假设性爱有两种可能性,每个名字和姓氏有300种可能性,还有100种可能的年龄值.这可能是18,000,000个独特的人.

让我们进一步假设equals()在这个对象上正确实现,即它正确地检查所有这些字段.

您在18,000,000种可能性的空间中使用随机特征生成1,000,000个独特的人.

直观地说,你可能会认为复制的可能性"微不足道",但重复的可能性实际上是1.0减去epsilon.这被称为生日问题或有时生日悖论.

如该页面所示,任何两个选择之间发生碰撞的概率大约是

1 - ((d-1)/ d)^ n(n-1)/ 2

其中d是域中值的数量,n是所做选择的数量.我不完全确定,但是d = 18,000,000和n = 1,000,000的值我认为这是有用的1.0 - 1E-323.(编辑:正确的值是关于1.0 - 2.84E-12294.这是非常接近一个.)

这种选择中预期的碰撞次数由以下公式给出:

n - d + d*((d-1)/ d)^ n

如果d = 18,000,000且n = 1,000,000,那么这大约为27,000.也就是说,平均而言,你会遇到27,000次碰撞.这非常接近TreeSet中"缺失"元素的数量,这就是碰撞会表现出来的方式.我承认我选择的数字非常接近您所看到的数字,但我的假设和结果完全合情合理.

您需要重新考虑生成存储到集合中的数据的方式.