Java TreeSet с ошибкой компаратора длины?

У меня есть приведенный ниже код, который создает 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]

or

[bb, aa]

Часть «bb» исчезает, что, кажется, противоречит контракту SortedSet. Предполагается, что компаратор только сортирует элементы, а не определяет их уникальность, которая обычно определяется равными.

С другой стороны, если я улучшу компаратор, чтобы он всегда возвращал ненулевое значение для неравных элементов, как показано ниже, только тогда я получу правильные результаты.

    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"

ОБНОВЛЕНИЕ

Вот соответствующий пост вместе с предложениями о том, как исправить проблему в будущей версии Java: https://yesday.github.io/blog/2018/java-gotchas-sorted-set-ignores-the-equals-method.html


java comparator treeset
person Georgios F.    schedule 08.08.2018    source источник
comment
Компаратор должен только сортировать элементы, а не определять их уникальность... почему вы так думаете?   -  person shmosel    schedule 08.08.2018
comment
Это Set. Это гарантирует уникальность. Как вы думаете, почему это позволит дубликаты?!   -  person Boris the Spider    schedule 08.08.2018
comment
вам, вероятно, нужен компаратор с резервным сравнением, например, если они имеют одинаковую длину, сравните их лексикографически   -  person Walter Tross    schedule 08.08.2018
comment
@WalterTross OP уже понял это и предложил это в качестве решения позже в своем вопросе. Вопрос как раз в том, почему первый теряет один элемент.   -  person Zabuzard    schedule 08.08.2018
comment
ага, не заметил, извините   -  person Walter Tross    schedule 08.08.2018

Ответы (2)


arrow_upward
16
arrow_downward

Это не баг. По крайней мере, не в TreeSet.

Из javadoc, акцент сделан мной:

Обратите внимание, что порядок, поддерживаемый набором (независимо от того, предоставлен явный компаратор или нет), должен быть согласованным с равными, если он должен правильно реализовать интерфейс Set. (См. Comparable или Comparator для точного определения совместимости с равными.) Это так, потому что интерфейс Set определен в терминах операции equals, но экземпляр TreeSet выполняет все сравнения элементов, используя свой метод compareTo (или сравнение). , так что два элемента, которые считаются равными с помощью этого метода, с точки зрения множества равны. Поведение набора четко определено, даже если его порядок несовместим с равными; он просто не подчиняется общему контракту интерфейса Set.

Итак, поскольку «aa» и «bb» имеют длину 2, они считаются равными compareTo и, следовательно, TreeSet.

По определению, совместимо с равными означает:

Порядок, наложенный компаратором c на набор элементов S, называется совместимым с равенством тогда и только тогда, когда c.compare(e1, e2)==0 имеет то же логическое значение, что и e1. equals(e2) для каждого e1 и e2 в S.

person Marvin    schedule 08.08.2018

arrow_upward
0
arrow_downward

Похоже, они предполагают, что компаратор использует то же определение равенства, что и метод равенства. Из API SortedSet:

Обратите внимание, что порядок, поддерживаемый отсортированным набором (независимо от того, предоставлен явный компаратор или нет), должен соответствовать равенству, если отсортированный набор должен правильно реализовать интерфейс Set. (См. интерфейс Comparable или интерфейс Comparator для точного определения соответствия с равными.) Это так, потому что интерфейс Set определен в терминах операции равенства, но отсортированный набор выполняет все сравнения элементов, используя свой метод compareTo (или сравнение). , так что два элемента, которые считаются равными с помощью этого метода, равны с точки зрения отсортированного множества. Поведение отсортированного набора четко определено, даже если его порядок несовместим с равными; он просто не подчиняется общему контракту интерфейса Set.

person thorin4401    schedule 08.08.2018