带有长度比较器错误的 Java TreeSet？

Question

我有下面的代码，它使用基于字符串长度的比较器创建一个 TreeSet。

public class TreeSetComparator {
    public static void main(String[] args) {
        SortedSet<String> sortedSet = new TreeSet<>(Comparator.comparing(String::length));
        sortedSet.addAll(Arrays.asList("aa", "bb", "aa"));
        System.out.println(sortedSet);
    }
}

令我惊讶的是，上面的输出是

[aa]

虽然我期待

[aa, bb]

或者

[bb, aa]

“bb”部分消失了，这似乎与 SortedSet 合约相反。比较器应该只对元素进行排序，而不是确定它们的唯一性，这通常由 equals 确定。

另一方面，如果我增强比较器以始终为如下所示的不等项返回非零值，那么只有这样我才能得到正确的结果。

    SortedSet<String> sortedSet = new TreeSet<>(Comparator.comparing(String::length).reversed().thenComparing(String::toString));
    sortedSet.addAll(Arrays.asList("aa", "bb", "aa"));
    System.out.println(sortedSet);

现在的输出是 [aa, bb]正如我所料。

以上是 TreeSet 实现中的错误吗？

我的环境如下:

mvn --version                                                                                                                                            21:40:22
Apache Maven 3.5.4 (1edded0938998edf8bf061f1ceb3cfdeccf443fe; 2018-06-17T19:33:14+01:00)
Maven home: /home/aaaa/.sdkman/candidates/maven/current
Java version: 10.0.2, vendor: Oracle Corporation, runtime: /usr/lib/jvm/java-10-jdk
Default locale: en_GB, platform encoding: UTF-8
OS name: "linux", version: "4.14.60-1-manjaro", arch: "amd64", family: "unix"

更新

这是一篇相关的帖子以及有关如何在 future 版本的 Java 中解决此问题的建议:https://yesday.github.io/blog/2018/java-gotchas-sorted-set-ignores-the-equals-method.html

Answer 1

这不是一个错误。至少不是在 TreeSet .

从javadoc，我强调:

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance 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 set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

所以因为“aa”和“bb”的长度都是2，所以compareTo认为它们相等。因此由 TreeSet .

By definition , 与 equals 一致意味着:

The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S.