Возможно ли, что TreeSet равно HashSet, но не HashSet равно TreeSet - PullRequest
62 голосов
/ 19 июня 2020

Сегодня у меня было интервью, и человек, проводивший мое интервью, озадачил меня своим заявлением, спрашивая, возможно ли, что TreeSet равно HashSet, но не HashSet равно TreeSet. Я сказал «нет», но, по его словам, ответ - «да».

Как такое вообще возможно?

Ответы [ 5 ]

67 голосов
/ 19 июня 2020

Ваш интервьюер прав, они не проводят отношения эквивалентности для некоторых конкретных c случаев. Возможно, что TreeSet может быть равно HashSet, а не наоборот. Вот пример:

TreeSet<String> treeSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
HashSet<String> hashSet = new HashSet<>();
treeSet.addAll(List.of("A", "b"));
hashSet.addAll(List.of("A", "B"));
System.out.println(hashSet.equals(treeSet)); // false
System.out.println(treeSet.equals(hashSet)); // true

Причина в том, что TreeSet использует компаратор для определения дублирования элемента, а HashSet использует equals.

Цитирование TreeSet:

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

19 голосов
/ 19 июня 2020

Невозможно без нарушения договора равных или Set . Определение равенства в Java требует симметрии, т.е. a.equals(b) должно быть таким же, как b.equals(a).

Фактически, сама документация Set говорит

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

7 голосов
/ 24 июля 2020

NO , это невозможно без нарушения общего контракта метода equals класса Object, который требует симметрии , т.е. x.equals(y) if и только если y.equals(x).

НО , классы TreeSet и HashSet по-разному реализуют контракт равно интерфейса Set. Этот контракт требует, среди прочего, чтобы каждый член указанного набора содержался в этом наборе. Чтобы определить, входит ли элемент в набор, вызывается метод contains, который для TreeSet использует Comparator, а для HashSet использует hashCode.

И напоследок:

ДА , в некоторых случаях это возможно.

2 голосов
/ 22 августа 2020

Это цитата из книги Java Generics and Collections:

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

Итак, ответ: да, это может произойти, но только когда вы не соблюдаете свою сторону контракта с Java. Здесь вы можете сказать, что Java нарушил свойство равенства симметрии c, но если это произойдет, убедитесь, что именно вы нарушили сначала договор некоторых других интерфейсов. Java уже задокументировал это поведение.

Обычно вам следует прочитать документацию по интерфейсам Comparator и Comparable, чтобы правильно использовать их в отсортированных коллекциях.

На этот вопрос так или иначе ответят в Эффективном Java Третье издание, пункт 14 на страницах 66-68.

Это цитата из книги при определении контракта на реализацию интерфейса Comparable (обратите внимание, что это только часть всего контракта):

• Настоятельно рекомендуется, но не обязательно, чтобы (x.compareTo (y) == 0) == (x.equals (y)). Вообще говоря, любой класс, реализующий интерфейс Comparable и нарушающий это условие, должен четко указывать на этот факт. Рекомендуемый язык - «Примечание: этот класс имеет естественный порядок, несовместимый с равным».

Здесь написано Настоятельно рекомендуется, но не обязательно , это означает, что вы разрешено иметь классы, для которых x.compareTo(y)==0 не означает x.equal(y)==true. (Но если это реализовано таким образом, вы не можете использовать их как элемент в отсортированных коллекциях, это как раз тот случай с BigDecimal)

Стоит упомянуть параграф книги, описывающий эту часть контракта интерфейса Comparable:

Это сильное предложение, а не истинное требование, просто говорится, что проверка равенства Метод compareTo обычно должен возвращать те же результаты, что и метод equals. Если это положение соблюдается, порядок, установленный методом compareTo, считается совместимым с equals. Если он нарушается, порядок считается несовместимым с равенством. Класс, чей метод compareTo устанавливает порядок, несовместимый с equals, по-прежнему будет работать, но отсортированные коллекции, содержащие элементы класса, могут не подчиняться общему соглашению соответствующих интерфейсов коллекций (Collection, Set или Map). Это связано с тем, что общие контракты для этих интерфейсов определены в терминах метода equals, но в отсортированных коллекциях c используется проверка равенства, наложенная compareTo вместо equals. Если это произойдет, это не катастрофа, но об этом следует помнить.

На самом деле у нас есть некоторые классы в самом Java, которые не следовали этой рекомендации. BigDecimal - один из них, и он упоминается в книге.

Например, рассмотрим класс BigDecimal, чей метод compareTo несовместим с equals. Если вы создаете пустой экземпляр HashSet, а затем добавляете новые BigDecimal («1.0») и новые BigDecimal («1.00»), набор будет содержать два элемента, потому что два экземпляра BigDecimal, добавленные в набор, не равны при сравнении с использованием метода equals. Однако, если вы выполняете ту же процедуру с использованием TreeSet вместо HashSet, набор будет содержать только один элемент, поскольку два экземпляра BigDecimal равны при сравнении с использованием метода compareTo. (Подробности см. В документации BigDecimal.)

Однако такое поведение задокументировано в BigDecimal Документации. Давайте посмотрим на эту часть документации:

Примечание: следует проявлять осторожность, если объекты BigDecimal используются в качестве ключей в SortedMap или элементы в SortedSet, поскольку естественный порядок BigDecimal несовместим с равными. См. Comparable, SortedMap или SortedSet для получения дополнительной информации.

Итак, хотя вы можете писать код, как показано ниже, вы не должны этого делать, потому что класс BigDecimal запретил такое использование:

Set<BigDecimal> treeSet = new TreeSet<>();
Set<BigDecimal> hashSet = new HashSet<>();
treeSet.add(new BigDecimal("1.00"));
treeSet.add(new BigDecimal("2.0"));
hashSet.add(new BigDecimal("1.00"));
hashSet.add(new BigDecimal("2.00"));
System.out.println(hashSet.equals(treeSet)); // false
System.out.println(treeSet.equals(hashSet)); // true

Обратите внимание, что Comparable будет использоваться как естественный порядок элементов когда вы не передаете какой-либо компаратор в TreeSet или TreeMap, то же самое может произойти, когда вы передадите Comparator этому конструктору класса. Это упоминается в документации Comparator:

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

Следует проявлять осторожность при использовании компаратора, способного наложить порядок, несовместимый с равенством заказать отсортированный набор (или отсортированную карту). Предположим, что отсортированный набор (или отсортированная карта) с явным компаратором c используется с элементами (или ключами), взятыми из набора S. Если порядок, наложенный c на S, несовместим с равенством, отсортированный набор (или отсортированная карта) будет вести себя "странно". В частности, отсортированный набор (или отсортированная карта) будет нарушать общий договор для набора (или карты), который определяется с точки зрения равенства.

Итак, учитывая этот документ Comparator, следующий пример предоставленный @Aniket Sahrawat не поддерживается для работы:

TreeSet<String> treeSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
HashSet<String> hashSet = new HashSet<>();
treeSet.addAll(List.of("A", "b"));
hashSet.addAll(List.of("A", "B"));
System.out.println(hashSet.equals(treeSet)); // false
System.out.println(treeSet.equals(hashSet)); // true

В двух словах ответ таков: да, это может произойти, но только если вы нарушите документированный контракт одного из вышеупомянутых интерфейсов (SortedSet, Comparable, Comparator).

1 голос
/ 22 августа 2020

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

В математике, Logi c и, соответственно, в компьютерных науках, " равно « - это Симметрия c Двоичное отношение , что означает, что если A is equal to B, то B is equal to A.

Итак, если TreeSet X равно HashSet Y, тогда HashSet Y должно быть равно TreeSet X, и это должно быть верно всегда .

Если, однако, симметрия c свойство Equality нарушено (т.е. Equality реализовано неправильно), тогда x.equals(y) может не означать y.equals(x).

В документации метода Object # equals в Java явно указывается, что:

Метод equals реализует отношение эквивалентности для ненулевого объекта ссылки.

следовательно, он реализует свойство symri c , а если нет, то нарушает равенство, в общем, и нарушает метод Object # equals, особенно в Java.

...