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

确保 People class 上的 compareTo() 方法得到正确实施。 Comparable javadoc 声明如下：

It is strongly recommended (though not required) that natural orderings be consistent with equals. This is so because sorted sets (and sorted maps) without explicit comparators behave "strangely" when they are used with elements (or keys) whose natural ordering is inconsistent with equals. In particular, such a sorted set (or sorted map) violates the general contract for set (or map), which is defined in terms of the equals method.

For example, if one adds two keys a and b such that (!a.equals(b) && a.compareTo(b) == 0) to a sorted set that does not use an explicit comparator, the second add operation returns false (and the size of the sorted set does not increase) because a and b are equivalent from the sorted set's perspective.

Answer 2

我可以非常自信地说您正在向您的 TreeSet 添加重复项。如果您不相信我，只需在 treeSet 中添加数字，确保数字在 1 到 1000000 之间，然后您会发现您得到的正是您所期望的。

一旦你清除了你的疑虑，那么让我们尝试对你的人进行排序class。

将以下内容添加到您的人脉 Class：

int id;    //ensure that every people object you create has different id. e.g. 1 to 10m;

@override
public boolean equals(Object o){
  if(this.getClass()!=o.getClass()) return false;
  else return (People (o)).id==this.id;
}

@override
public int hashCode(){
 return id;
}

现在开始向您的集合中添加内容。 :)

注意此代码只是创建不同人物的简单方法的示例 Class。用 treeSet 等做一些测试是一个很好的方法，但不推荐用于实际问题

Answer 3

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

在您的中，您说每个人都是根据包含 "hundreds" 姓名和年龄的文本文件中的性别、名字和姓氏随机生成的。假设性别有两种可能性，名字和姓氏各有 300 种可能性，年龄有 100 种可能值。总共有 18,000,000 个可能的独特人物。

让我们进一步假设 equals() 在此对象上正确实现，也就是说，它正确检查了所有这些字段。

您正在从 space 18,000,000 种可能性中使用随机特征生成 1,000,000 个独特的人。

直觉上，您可能认为存在 "minuscule" 重复的可能性，但实际上存在重复的概率约为 1.0 减去 epsilon。这被称为 Birthday Problem 或有时是生日悖论。

如该页面所示，任意两个选择之间发生冲突的概率约为

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。这非常接近 1。）

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

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

如果 d = 18,000,000 且 n = 1,000,000，则计算结果约为 27,000。也就是说，您平均会遇到 27,000 次碰撞。这非常接近 TreeSet 中的 "missing" 元素的数量，这就是碰撞的表现方式。我承认我选择的数字非常接近您所看到的，但我的假设和结果是完全合理的。

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

TreeSet 没有添加所有元素？

TreeSet not adding all elements?

java

collections

tree

set

treeset