可以更改 TreeSet 中 compareTo 中使用的值吗？

Question

我有这个简单的 Pojo：

public static class Pojo implements Comparable<Pojo> {

    Integer value;

    @Override
    public int compareTo(Pojo o) {
        return value.compareTo(o.value);
    }

    // getters and setter ommited

}

可以改变value一段Pojo时间TreeSet吗？我不介意这是否会破坏TreeSet.

我很好奇，因为更改valueused in ahashCode()或equas()while 实例在 aHashMap中并不是一个好主意。

Answer 1

如果我们改变影响元素顺序的属性，我们就违反了 的契约TreeSet。

根据TreeSet文档，它

... 为基本操作 ( add,remove和contains)提供有保证的 log(n) 时间成本。

该TreeSet可以通过保持有序的设定保证这些时间成本。然而，如果我们改变元素的属性，反过来又会改变集合中的顺序，我们就违反了这个契约。在TreeSet不断没有“监控”更改所有元素。此外，更改可能会触发重新排序，这将产生n * log(n)（以n的当前大小TreeSet）的成本。

我们可以使用以下代码使这种违反合同形式的影响可见：

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.TreeSet;

class Ideone {
    public static void main(String[] args) {
        Foo fooOne = Foo.of(1);
        Foo fooTwo = Foo.of(2);
        Foo fooThree = Foo.of(3);
        TreeSet<Foo> set = new TreeSet<>();
        set.addAll(List.of(fooOne, fooTwo, fooThree));
        System.out.println(set.contains(fooOne));
        fooOne.setValue(4);
        System.out.println(set.contains(fooOne));
        System.out.println(new ArrayList<>(set).contains(fooOne));
    }
}

class Foo implements Comparable<Foo> {
    private int value;

    private Foo(int value) {
        this.setValue(value);
    }

    public static Foo of(int value) {
        return new Foo(value);
    }

    public int getValue() {
        return value;
    }

    public Foo setValue(int value) {
        this.value = value;
        return this;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Foo foo = (Foo) o;
        return getValue() == foo.getValue();
    }

    @Override
    public int hashCode() {
        return Objects.hash(value);
    }

    @Override
    public int compareTo(Foo that) {
        return getValue() - that.getValue();
    }
}

Ideone demo

如果TreeSet对元素属性的重新排序发生更改，则所有三行都应显示true。但是，由于我们将fooOne'svalue从1改为4（因此它应该是集合中的最后一个元素），第二个contains(fooOne)将返回，false因为TreeSet不再排序。但是，将 转换TreeSet为 anArrayList并在 中搜索会ArrayList产生预期结果，因为ArrayList不对元素顺序做出任何假设。

如果基本操作的保证 log(n) 时间成本对用例来说不是必不可少的，我建议使用List不依赖于元素排序的不同数据结构（例如 a ）。但是请记住，对于（至少部分）基本操作而言，这会带来更高的时间成本。

编辑：

正如@Scratte 在评论中提到的那样，我们甚至可以TreeSet通过将（经过修改，但仍然相同的 wrt. ==）添加fooOne到TreeSet，将其大小增加 1来在更基本的层面上打破：

class Ideone {
    public static void main(String[] args) {
        Foo fooOne = Foo.of(1);
        Foo fooTwo = Foo.of(2);
        Foo fooThree = Foo.of(3);
        TreeSet<Foo> set = new TreeSet<>();
        set.addAll(List.of(fooOne, fooTwo, fooThree));
        System.out.println(set.size());
        fooOne.setValue(4);
        set.add(fooOne);
        System.out.println(set.size());
    }
}

Ideone demo