Java SortedSet + компаратор, согласованность с equals() вопрос

Question

Я бы хотел иметь SortedSet коллекций (в данном случае самих наборов, но не обязательно в целом), которые сортируются по размеру коллекции.Это, по-видимому, нарушает предписание согласовывать компаратор с equals() - т. е. две коллекции могут быть неравными (из-за наличия разных элементов), но сравниваться с одним и тем же значением (потому что они имеют одинаковое количество элементов).

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

Кажется ли этот случай несоответствия проблемой?

Answer 1

Как написал ChssPly76 в комментарии, вы можете использовать hashCode для решения вызова CompareTo в случае, когда две коллекции имеют одинаковый размер, но не равны.Это работает нормально, за исключением того редкого случая, когда у вас есть две коллекции одинакового размера, которые не равны, но имеют одинаковый хеш-код.Правда, шансы на это довольно малы, но вполне возможны.Если вы хотите быть очень осторожными, вместо hashCode используйте System.identityHashCode.Это должно дать вам уникальный номер для каждой коллекции, и у вас не должно возникнуть коллизий.

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

псевдокод:

if (a.equals(b)) {
    return 0;
} else if (a.size() > b.size()) {
    return 1;
} else if (b.size() > a.size()) {
    return -1;
} else {
    return System.identityHashCode(a) > System.identityHashCode(b) ? 1 : -1;
}

Answer 2

SortedSet интерфейс расширяет ядро Set и, таким образом, должно соответствовать контракту, изложенному в Set Спецификация.

Единственный возможный способ добиться этого – сделать так, чтобы ваш элемент equal() поведение метода должно соответствовать вашему Comparator - причина в том, что ядро Set действует на основе равенства, тогда как SortedSet работает на основе сравнения.

Например, add() метод, определенный в базовом интерфейсе Set, указывает, что вы не можете добавить элемент в набор, если уже существует элемент, чей equal() метод вернет true с этим новым элементом в качестве аргумента.Хорошо, SortedSet не использует equal(), оно использует compareTo().Так что если ваш compareTo() возвращает false ваш элемент БУДЕТ добавлен, даже если equals() должны были вернуться true, тем самым нарушая Set договор.

Ничто из этого не является практичный проблема сама по себе, однако. SortedSet поведение всегда последовательно, даже если compare() против equals() не.

Answer 3

Это, по-видимому, нарушает предписание согласовывать компаратор с equals() - т.Е. две коллекции могут быть неравными (из-за наличия разных элементов), но сравниваться с одинаковыми значение (потому что они имеют одинаковое количество элементов).

Нет требования, ни заявленного (в Javadoc), ни подразумеваемого, что Comparator быть согласованным с реализацией объекта boolean equals(Object).

Обратите внимание , что Comparable и Comparator являются различные интерфейсы с разными целями. Comparable используется для определения "естественного" порядка для класса.В этом контексте это было бы плохой идеей для equals и compateTo быть непоследовательным.Напротив, a Comparator используется, когда вы хотите использовать порядок, отличный от естественного порядка класса.

Редактировать:Вот полный абзац из Javadoc для SortedSet.

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

Я выделил последнее предложение.Дело в том, что такой SortedSet будет работать так, как вы, скорее всего, ожидаете, но поведение некоторых операций не будет точно соответствовать Set спецификация ...поскольку спецификация определяет их поведение в терминах equals способ.

Так что на самом деле там является заявленное требование согласованности (моя ошибка), но последствия его игнорирования не так плохи, как вы могли бы подумать.Конечно, вам решать, стоит ли это делать.По моей оценке, все должно быть в порядке, при условии, что вы тщательно прокомментируете код и убедитесь, что SortedSet не "протекает".

Однако мне не ясно, будет ли работать компаратор для коллекций, который смотрит только на "размер" коллекций...с семантической точки зрения.Я имею в виду, вы действительно хотите сказать, что все коллекции, содержащие (скажем) 2 элемента, равны?Это будет означать , что ваш набор может содержать только одну коллекцию любого заданного размера ...

Answer 4

Нет причин, по которым Comparator должен возвращать те же результаты, что и equals().Фактически, Comparator API был введен, потому что equals() просто недостаточно:Если вы хотите отсортировать коллекцию, вы должны знать, являются ли два элемента меньшими или большими.

Answer 5

Немного странно, что SortedSet как часть стандартного API нарушает контракт, определенный в интерфейсе Set, и использует компаратор для определения равенства вместо метода равенства, но это так.

Если ваша реальная проблема состоит в том, чтобы отсортировать коллекцию коллекций в соответствии с размером содержащихся коллекций, вам лучше использовать список, который вы можете сортировать с помощью Collections.sort(List, Comparator>);