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

Question

Мне бы хотелось иметь SortedSet of Collections (сами в этом случае, но не обязательно в общем), которые сортируют по размеру Collection. Кажется, это нарушает запрет на то, чтобы Comparator соответствовал equals () - то есть две коллекции могут быть неравными (из-за наличия разных элементов), но сравниваться с одним и тем же значением (потому что они имеют одинаковое количество элементов).

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

РЕДАКТИРОВАТЬ: Вот полный абзац из Javadoc для SortedSet.

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

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

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

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

Answer 3

Как пишет 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 4

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

Answer 5

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

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