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

问题描述

我有这个简单的 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.

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

标签： javatreeset

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

根据TreeSet文档，它

add... 为基本操作（remove和）提供有保证的 log(n) 时间成本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'svalue从更改为1到4（因此它应该是集合中的最后一个元素），第二个contains(fooOne)将返回false，因为TreeSet不再排序。但是，将转换TreeSet为 anArrayList并在中搜索ArrayList会产生预期的结果，因为ArrayList没有对元素顺序做出任何假设。

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

编辑：

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

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

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

问题描述

解决方案

推荐阅读