java - 为什么对此 Treeset 的删除调用不能有效删除元素？

Question

我之前尝试编写 Dijkstra 算法，但在实现中遇到了问题。我终于找到了解决方案，但仍然对代码的行为感到困惑。

我在这里尝试做的是迭代地标记树集的元素。每次标记一个元素时，我都会将其从集合中删除并重新插入，因此集合将其放置在集合的末尾(正如 compareTo 方法告诉它的那样)。 这样做，我可以在 while 循环中获取集合的第一个元素，并在第一个元素被标记时停止。

以下示例是一个最小示例:

public static void main(final String[] args) {
    Set<Element> elements = new TreeSet<>();
    elements.add(new Element(1));
    elements.add(new Element(2));
    elements.add(new Element(3));
    elements.add(new Element(5));
    elements.add(new Element(4));
    System.err.println(elements.size());
    while(!elements.iterator().next().mark){
        Element element = elements.iterator().next();
        element.mark();
        elements.remove(element);
        elements.add(element);
    }
    System.err.println(elements.size());
}

private static class Element implements Comparable<Element>{

    private boolean mark = false;
    private final int id;

    public Element(int id){
        this.id = id;
    }

    public void mark(){
        this.mark = true;
    }

    @Override
    public boolean equals(Object o){
        Element other = (Element) o;
        if(this.mark == other.mark){
            return this.id == other.id;
        } else {
            return false;
        }
    }

    @Override
    public int compareTo(Element other){
        if(this.mark == other.mark){
            return this.id - other.id;
        } else if(this.mark && !other.mark){
            return 1;
        } else {
            return -1;
        }
    }
}

这里的问题是这一行:

elements.remove(element);

不删除该元素。但是，在调试器中运行它，我可以看到该元素与集合中的元素具有完全相同的引用，并且就 equals 方法而言等于它。因此，运行该行时:

elements.add(element);

相同的元素被添加两次；因为我认为树集中的插入使用二分搜索，并且不测试集合的第一个元素和新插入的元素之间的相等性。

我明白交换两行:

element.mark();
elements.remove(element);

确实解决了问题。

我的问题是:为什么在通过迭代器修改时，树集的修改元素没有被有效删除？

Answer 1

TreeSet 使用 compareTo 来定位树结构中的元素(并确定相等性)。如果您将一个元素放入 TreeSet 中，然后修改 compareTo 方法中使用的属性(即您案例中的标记)，remove 无法找到该元素，因为它在与插入原始元素的位置不同的位置中查找该元素。

如果在更改元素之前删除该元素，则可以解决问题，因为在插入元素时会找到原始元素。