可以更改 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

}

在 TreeSet 中更改 Pojo 的 value 可以吗？我不介意这是否会破坏 TreeSet.

中的排序

我很好奇，因为在实例处于 HashMap 时更改 hashCode() 或 equas() 中使用的 value 不是一个好主意。

Answer 1

如果我们更改影响元素顺序的属性，我们将违反 TreeSet 的约定。

根据TreeSet's documentation，它

... provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

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 的 value 从 1 更改为 4（因此它应该是集合中的最后一个元素），第二个 contains(fooOne) 将 return false 因为 TreeSet 不再排序。然而，将 TreeSet 转换为 ArrayList 并在 ArrayList 中搜索会产生预期的结果，因为 ArrayList 没有对元素顺序做出任何假设。

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

编辑：

与一样，我们甚至可以在更基本的层面上打破 TreeSet，方法是添加（经过修改，但仍然与 == 相同）fooOne到 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.size());
        fooOne.setValue(4);
        set.add(fooOne);
        System.out.println(set.size());
    }
}

Ideone demo

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

Is it ok to change a value that is used in compareTo in a TreeSet?

java

treeset