java - 为什么我似乎能够将两个彼此相等的对象添加到 TreeSet

Question

将对象添加到 java.util.TreeSet 时，您希望两个相等的对象只存在一次，当两个对象都被添加时，并且以下测试按预期通过:

@Test
void canAddValueToTreeSetTwice_andSetWillContainOneValue() {
    SortedSet<String> sortedSet = new TreeSet<>(Comparator.naturalOrder());

    // String created in a silly way to hopefully create two equal Strings that aren't interned
    String firstInstance = new String(new char[] {'H', 'e', 'l', 'l', 'o'});
    String secondInstance = new String(new char[] {'H', 'e', 'l', 'l', 'o'});

    assertThat(firstInstance).isEqualTo(secondInstance);
    assertThat(sortedSet.add(firstInstance)).isTrue();
    assertThat(sortedSet.add(secondInstance)).isFalse();
    assertThat(sortedSet.size()).isEqualTo(1);
}

将这些字符串包装在包装类中，其中 equals() 和 hashCode() 仅基于包装类，但测试失败:

@Test
void canAddWrappedValueToTreeSetTwice_andSetWillContainTwoValues() {
    SortedSet<WrappedValue> sortedSet = new TreeSet<>(Comparator.comparing(WrappedValue::getValue).thenComparing(WrappedValue::getCreationTime));

    WrappedValue firstInstance = new WrappedValue("Hello");
    WrappedValue secondInstance = new WrappedValue("Hello");

    assertThat(firstInstance).isEqualTo(secondInstance); // Passes
    assertThat(sortedSet.add(firstInstance)).isTrue();   // Passes
    assertThat(sortedSet.add(secondInstance)).isFalse(); // Actual: True
    assertThat(sortedSet.size()).isEqualTo(1);           // Actual: 2
}

private class WrappedValue {
    private final String value;
    private final long creationTime;

    private WrappedValue(String value) {
        this.value = value;
        this.creationTime = System.nanoTime();
    }

    private String getValue() {
        return value;
    }

    private long getCreationTime() {
        return creationTime;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof WrappedValue)) return false;
        WrappedValue that = (WrappedValue) o;
        return Objects.equals(this.value, that.value);
    }

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

The JavaDoc for TreeSet.add()陈述我们的期望:

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if the set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.

鉴于我断言这两个对象是 equal()，我希望这会通过。我正在假设我遗漏了一些非常明显的东西，除非 TreeSet 不实际使用 Object.equals()，但在绝大多数情况下使用的东西几乎相同。

这是使用 JDK 1.8.0.60 观察到的 - 我还没有机会测试其他 JDK，但我假设某处存在一些“操作错误”......

Answer 1

问题是给定的用于对集合进行排序的比较器与WrappedValue 的equals 方法不兼容。您期望 SortedSet 表现得像 Set，但在这种情况下它不会这样做。

来自 SortedSet :

Note that the ordering maintained by a sorted set [...] must be consistent with equals if the sorted set is to correctly implement the Set interface. [...] This is so because the Set interface is defined in terms of the equals operation, but a sorted set performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the sorted set, equal. The behavior of a sorted set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

换句话说，SortedSet 仅使用您提供的比较器来确定两个元素是否相等。这种情况下的比较器是

Comparator.comparing(WrappedValue::getValue).thenComparing(WrappedValue::getCreationTime)

比较值然后比较创建时间。但是由于 WrappedValue 的构造函数使用 System.nanoTime() 初始化了一个(有效的)唯一创建时间，因此没有两个 WrappedValue 会被认为是相等的这个比较器。因此，就有序集而言

WrappedValue firstInstance = new WrappedValue("Hello");
WrappedValue secondInstance = new WrappedValue("Hello");

是两个不同的对象。事实上，如果您稍微修改构造函数以添加一个 long creationTime 参数，并为两个实例提供相同的时间，您会注意到“预期”结果(即排序集将只有一个添加两个实例后大小为 1)。

所以这里有3种解决方案:

1. 修复 equals 和 hashCode 方法，让它们比较值和时间。
2. 只给出比较值的比较器。
3. 接受这样一个事实，即 SortedSet 在这种特殊情况下的行为不像 Set。