Java: почему коллекции принимают компаратор, а не (гипотетический) хэшер и экватор?

25

Эта проблема наиболее очевидна, когда у вас есть разные реализации интерфейса, и для целей конкретной коллекции вы заботитесь только о представлении объектов на уровне интерфейса. Например, предположим, что у вас был такой интерфейс:

public interface Person {
    int getId();
}

Обычный способ реализации hashcode()и equals()реализации классов должен иметь такой код в equalsметоде:

if (getClass() != other.getClass()) {
    return false;
}

Это вызывает проблемы, когда вы смешиваете реализации Personв HashMap. Если HashMapтолько заботится о представлении на уровне интерфейса Person, то это может привести к дубликатам, которые отличаются только своими классами реализации.

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

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

Просто чтобы прояснить, этот вопрос отличается от « Почему .compareTo () в интерфейсе, а .equals () в классе в Java? », Потому что он касается реализации коллекций. compareTo()и equals()/ hashcode()оба страдают от проблемы универсальности при использовании коллекций: вы не можете выбирать разные функции сравнения для разных коллекций. Таким образом, для целей этого вопроса иерархия наследования объекта не имеет значения вообще; имеет значение только то, определена ли функция сравнения для каждого объекта или для каждой коллекции.

Сэм
источник
5
Вы всегда можете ввести объекты-оболочки для Personреализации ожидаемого equalsи hashCodeповедения. Вы бы тогда имели HashMap<PersonWrapper, V>. Это один пример, когда подход чистого ООП не элегантен: не каждая операция над объектом имеет смысл как метод этого объекта. Вся Явы Objectтипа представляет собой совокупность различных обязанностей - только getClass, finalizeи toStringметоды кажутся оправданными удаленно с помощью современных передовых методов.
Амон
1
1) В C # вы можете передать IEqualityComparer<T>коллекцию на основе хеша. Если вы не укажете один, он использует реализацию по умолчанию на основе Object.Equalsи Object.GetHashCode(). 2) Переопределение IMO Equalsдля изменяемого ссылочного типа редко является хорошей идеей. Таким образом, равенство по умолчанию является довольно строгим, но вы можете использовать более мягкое правило равенства, когда вам это нужно с помощью обычая IEqualityComparer<T>.
CodesInChaos

Ответы:

23

Этот дизайн иногда называют «универсальным равенством», это убеждение, что две вещи равны или нет, является универсальным свойством.

Более того, равенство является свойством двух объектов, но в ОО вы всегда вызываете метод для одного отдельного объекта , и этот объект получает единоличное решение о том, как обрабатывать этот вызов метода. Таким образом, в проекте, подобном Java, где равенство является свойством одного из двух сравниваемых объектов, даже невозможно гарантировать некоторые базовые свойства равенства, такие как симметрия ( a == bb == a), поскольку в первом случае метод вызывается, aа во втором случае вызывается, bи в силу основных принципов ОО, это исключительно aрешение (в первом случае) илиbРешение (во втором случае), считает ли он себя равным другому. Единственный способ получить симметрию - это заставить два объекта взаимодействовать, но если они этого не сделают ... не повезло.

Одним из решений было бы сделать равенство не свойством одного объекта, а либо свойством двух объектов, либо свойством третьего объекта. Этот последний вариант также решает проблему универсального равенства, потому что, если вы сделаете равенство свойством третьего объекта «контекста», тогда вы можете представить себе разные EqualityComparerобъекты для разных контекстов.

Это является конструкция выбрана для Haskell, например, с Eqклассом типов. Это также дизайн, выбранный некоторыми сторонними библиотеками Scala (например, ScalaZ), но не ядро ​​Scala или стандартная библиотека, которая использует универсальное равенство для совместимости с базовой платформой хоста.

Это интересно, и дизайн выбран с Явой Comparable/ Comparatorинтерфейсами. Разработчики Java ясно знали о проблеме, но по какой-то причине решили ее только для упорядочивания, но не для равенства (или хеширования).

Итак, что касается вопроса

почему есть Comparatorинтерфейс, а нет Hasherи Equator?

ответ "я не знаю". Очевидно, что разработчики Java знали об этой проблеме, о чем свидетельствует существование Comparator, но они явно не считали ее проблемой равенства и хеширования. Другие языки и библиотеки делают другой выбор.

Йорг Миттаг
источник
7
+1, но учтите, что в ОО-языках существует многократная диспетчеризация (Smalltalk, Common Lisp). Так что всегда слишком сильно в следующем предложении: «в ОО вы всегда вызываете метод для одного объекта».
coredump
Я нашел цитату, которую искал; в соответствии с JLS 1.0, The methods equals and hashCode are declared for the benefit of hashtables such as java.util.Hashtableт. е. оба equalsи hashCodeбыли введены ObjectJava-разработчиками в качестве методов исключительно ради Hashtable- в спецификации нет никакого понятия UE или чего-либо другого, и цитата для меня достаточно ясна; если бы не Hashtable, equalsвероятно, был бы в интерфейсе, как Comparable. Таким образом, если раньше я считал ваш ответ правильным, то теперь считаю его необоснованным.
vaxquis
@ JörgWMittag, это была опечатка, IFTFY. Кстати, говоря о том, что clone- изначально это был оператор , а не метод (см. Спецификацию языка Oak), цитата: The unary operator clone is applied to an object. (...) The clone operator is normally used inside new to clone the prototype of some class, before applying the initializers (constructors)- три ключевых словоподобных оператора были instanceof new clone(раздел 8.1, операторы). Я предполагаю, что это реальная (историческая) причина clone/ Cloneablemess - Cloneableбыло просто более поздним изобретением, и существующий cloneкод был модифицирован с ним.
vaxquis
2
«Это дизайн, выбранный для Haskell, например, с классом типов Eq». Это своего рода правда, но стоит отметить, что Haskell прямо заявляет, что два объекта разных типов никогда не равны, в отличие от подхода Java. Операция равенства, таким образом, является частью типа (следовательно, «класс типов»), а не частью третьего значения контекста.
Джек,
19

Реальный ответ на

почему есть Comparatorинтерфейс, а нет Hasherи Equator?

цитата любезно предоставлена ​​Джошем Блохом :

Оригинальные API Java были сделаны очень быстро в сжатые сроки, чтобы соответствовать закрывающемуся окну рынка. Оригинальная команда Java проделала невероятную работу, но не все API идеальны.

Проблема заключается исключительно в истории Java, как и в других подобных вопросах, например, .clone()против Cloneable.

ТЛ; др

в основном по историческим причинам; текущее поведение / абстракция была введена в JDK 1.0 и не была исправлена ​​позже, потому что это было практически невозможно сделать с поддержанием обратной совместимости кода.


Во-первых, давайте подведем итог нескольким известным фактам Java:

  1. Java с самого начала и до наших дней гордо поддерживала обратную совместимость, что требовало поддержки устаревших API в новых версиях,
  2. Таким образом, почти каждая языковая конструкция, представленная в JDK 1.0, дожила до наших дней,
  3. Hashtable, .hashCode()& .equals()Были реализованы в JDK 1.0, ( Hashtable )
  4. Comparable/ Comparatorбыл введен в JDK 1.2 ( сопоставимый ),

Теперь следует:

  1. было практически невозможно и бессмысленно модернизировать .hashCode()и использовать .equals()различные интерфейсы, сохраняя при этом обратную совместимость после того, как люди поняли, что есть абстракции лучше, чем помещать их в суперобъект, потому что, например, каждый Java-программист в 1.2 знал, что у каждого Objectесть они, и у них оставаться там физически для обеспечения совместимости скомпилированного кода (JVM) - и добавление явного интерфейса к каждому Objectреально реализованному им подклассу сделает этот беспорядок равным (sic!) Clonableодному ( Блох обсуждает, почему Cloneable отстой , также обсуждался, например, в EJ 2nd и многие другие места, в том числе SO),
  2. они просто оставили их там, чтобы у будущего поколения был постоянный источник WTF.

Теперь вы можете спросить: «Что Hashtableсо всем этим?»

Ответ таков: hashCode()/ equals()контракт и не очень хорошие навыки языкового проектирования основных разработчиков Java в 1995/1996 гг.

Цитата из Java 1.0 Language Spec от 1996 - 4.3.2 The Class Object, с.41:

Методы equalsи hashCodeобъявлены в пользу хеш- java.util.Hashtableтаблиц, таких как (§21.7). Метод equals определяет понятие равенства объектов, основанное на сравнении, а не на ссылке.

(обратите внимание , это точное утверждение было изменено в более поздних версиях, чтобы сказать, цитату: The method hashCode is very useful, together with the method equals, in hashtables such as java.util.HashMap., что делает его невозможно сделать прямое Hashtable- hashCode- equalsсоединение без чтения исторических JLS!)

Команда Java решила, что им нужна хорошая коллекция в стиле словаря, и они создали Hashtable(пока хорошая идея), но они хотели, чтобы программист мог использовать ее с как можно меньшим количеством кода / кривой обучения (упс! Неприятности поступают!) - и, так как не было ни одного дженерики пока [это JDK 1.0 в конце концов], это будет означать, что либо каждый Object положить в Hashtableбы явно реализовать некоторый интерфейс (и интерфейсы были еще только в их начала тогда ... нет Comparableпока еще!) делая это сдерживающим фактором, чтобы использовать его для многих - или Objectпришлось бы неявно реализовать какой-то метод хеширования.

Очевидно, они пошли с решением 2 по причинам, изложенным выше. Да, теперь мы знаем, что они были неправы. ... в ретроспективе легко быть умным. посмеиваться

Теперь hashCode() требует, чтобы у каждого объекта, имеющего его, был свой equals()метод - так что было совершенно очевидно, что equals()его также нужно вставить Object.

Поскольку по умолчанию реализаций этих методов по действительным aи b Objectс, по существу бесполезна, будучи избыточными (делает a.equals(b) равными для a==bи a.hashCode() == b.hashCode() примерно равны по a==bтакже, если hashCodeи / или equalsне перекрываться, или GC сотни тысяч Objectс в течение всего жизненного цикла приложения 1 ) Можно с уверенностью сказать, что они были предоставлены в основном в качестве резервной меры и для удобства использования. Именно так мы добираемся до общеизвестного факта, который всегда переопределяет оба, .equals()и .hashCode()если вы намереваетесь фактически сравнивать объекты или хранить их в хеш-памяти, Переопределение только одного из них без другого - это хороший способ испортить ваш код (путем злых результатов сравнения или безумно высоких значений столкновений сегментов) - и обдумывание этого является источником постоянной путаницы и ошибок для начинающих (ищите ТАК, чтобы увидеть это для себя) и постоянная неприятность для более опытных.

Также обратите внимание, что хотя C # работает с equals & hashcode немного лучше, сам Эрик Липперт утверждает, что они допустили почти ту же ошибку с C #, что и Sun с Java за годы до появления C # :

Но почему так должно быть, что каждый объект должен иметь возможность хэшировать себя для вставки в хеш-таблицу? Кажется странной вещью требовать, чтобы каждый объект был в состоянии сделать. Я думаю, что если бы мы сегодня проектировали систему типов с нуля, хеширование могло бы быть сделано иначе, возможно, с помощью IHashableинтерфейса. Но когда была разработана система типов CLR, не было общих типов, и поэтому хэш-таблица общего назначения должна была хранить любой объект.

1, конечно, Object#hashCodeвсе еще может конфликтовать, но для этого требуется немного усилий, см. Подробности в http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6809470 и связанных отчетах об ошибках; /programming/1381060/hashcode-uniqueness/1381114#1381114 охватывает эту тему более подробно.

vaxquis
источник
Это не просто Java, хотя. Многие из его современников (Ruby, Python, ...) и предшественники (Smalltalk, ...) и некоторые из его преемников также имеют Универсальное Равенство и Универсальную Хашируемость (это слово?).
Йорг Миттаг
@ JörgWMittag, см. Programmers.stackexchange.com/questions/283194/… - Я не согласен с «UE» в Java; UE исторически никогда не было реальной проблемой в Objectдизайне России; hashability был.
vaxquis
@vaxquis Я не хочу об этом говорить, но мой предыдущий комментарий показывает, что два одновременно достижимых объекта могут иметь одинаковый (по умолчанию) хэш-код.
Восстановить Монику
1
@vaxquis ОК. Я покупаю это. Меня беспокоит то, что кто-то, кто учится, увидит это и подумает, что он умен, используя хеш-код системы вместо равных и т. Д. Если он это сделает, он, скорее всего, будет работать достаточно хорошо, за исключением редких случаев, когда это не так и будет нет способа воспроизвести проблему надежно.
JimmyJames
1
Это должен быть принятый ответ, так как принятый ответ «я не знаю»
Феникс,