java - 关于 TreeSet 的调试挑战

Question

所以这将是我的问题，但我在写它的时候实际上已经解决了这个问题。也许这对其他人有用(如果它是重复的或被认为不适合本网站，我将删除该问题)。我知道我的问题有两种可能的解决方案，但也许有人会想出比我想象的更好的解决方案。

我不明白为什么 TreeSet 并没有删除这里的第一个元素。我的尺寸TreeSet应该保持有界，但似乎无限增长。

这是我认为相关的代码:

此代码驻留在双 for 循环内。 NUM_GROUPs是 static final int设置为 100 。 newGroups是 TreeSet<TeamGroup>在双 for 循环之前初始化的对象(没有元素)(变量 group 和 team 来自两个 for-each 循环)。

final TeamGroup newGroup = new TeamGroup(group, team);
newGroups.add(newGroup);
System.err.println("size of newGroups: " + newGroups.size());
if (newGroups.size() > NUM_GROUPS) {
    System.err.println("removing first from newGroups");
    newGroups.remove(newGroups.first());
    System.err.println("new size of newGroups: "
        + newGroups.size());
}

我添加了调试语句以表明问题确实发生了。我得到以下类型的输出:

size of newGroups: 44011
removing first from newGroups
new size of newGroups: 44011

您会看到，虽然 if显然正在输入语句，TreeSet<TeamGroup> teamGroups的大小并没有被减少。在我看来，发生这种情况的唯一方法是 remove call 不会删除任何内容 - 但它怎么能不从对 first() 的调用中删除某些内容呢？这应该肯定是 TreeSet 中的一个元素？

这是 compareTo我的方法TeamGroup类( score 是一个 int ，对于许多不同的 TeamGroup 对象来说，它可能非常合理地相同，因此我使用 R_ID 字段作为决胜局):

public int compareTo(TeamGroup o) {
    // sorts low to high so that when you pop off of the TreeSet object, the
    // lowest value gets popped off (and keeps the highest values).
    if (o.score == this.score)
        return this.R_ID - o.R_ID;
    return this.score - o.score;
}

这是 equals我的方法TeamGroup类:

@Override
public boolean equals(final Object o) {
    return this.R_ID == ((TeamGroup) o).R_ID;
}

...我不担心 ClassCastException在这里，因为这与我的上述问题特别相关，我从不尝试比较 TeamGroup对象与任何东西，但另一个TeamGroup对象 - 这绝对不是问题(至少不是 ClassCastException 问题)。

R_ID应该是唯一的，我通过以下方式保证这一点:

private static final double WIDTH = (double) Integer.MAX_VALUE
        - (double) Integer.MIN_VALUE;
private static final Map<Integer, Integer> MAPPED_IDS = 
    new HashMap<Integer, Integer>(50000);
...
public final int R_ID = TeamGroup.getNewID();
...
private static int getNewID() {
    int randID = randID();
    while (MAPPED_IDS.get(randID) != null) {
        randID = randID();
    }

    MAPPED_IDS.put(randID, randID);

    return randID;
}

private static int randID() {
    return (int) (Integer.MIN_VALUE + Math.random() * WIDTH);
}

Answer 1

问题出在这里:

        return this.R_ID - o.R_ID;

应该是:

        return Integer.compare(this.R_ID, o.R_ID);

取两个之差int或Integer如果两个值都保证为非负值，则值有效。但是，在您的示例中，您使用的是 int 整个范围内的 ID 值。/Integer这意味着减法可能会导致溢出......以及 compareTo 的错误结果.

不正确的实现会导致 compareTo 的情况方法不是自反的；即整数I1 , I2和I3其中compareTo方法说 I1 < I2和I2 < I3 ，还有 I3 < I1 。当您将其插入TreeSet时，元素被插入到树中的错误位置，并且会发生奇怪的行为。到底发生了什么很难预测 - 这将取决于插入的对象以及它们插入的顺序。

TreeSet.first() should definitely return an object which belongs to the set, right?

可能...

So then why can it not remove this object?

可能是因为它找不到它......因为compareTo损坏了。

要了解到底发生了什么，您需要单步执行 TreeSet 代码等。