Java: Warum akzeptieren Sammlungen einen Komparator, aber keinen (hypothetischen) Hasher und Äquator?

25

Dieses Problem tritt am deutlichsten auf, wenn Sie unterschiedliche Implementierungen einer Schnittstelle haben und sich für die Zwecke einer bestimmten Sammlung nur um die Ansicht der Objekte auf Schnittstellenebene kümmern. Angenommen, Sie hatten eine Schnittstelle wie diese:

public interface Person {
    int getId();
}

Die übliche Art hashcode()und Weise, equals()Klassen zu implementieren und zu implementieren, würde in der equalsMethode folgenden Code enthalten :

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

Dies verursacht Probleme, wenn Sie Implementierungen von Personin a mischen HashMap. Wenn HashMapsich der Benutzer nur um die Ansicht auf Schnittstellenebene kümmert Person, kann dies zu Duplikaten führen, die sich nur in den implementierenden Klassen unterscheiden.

Sie könnten diesen Fall unter Verwendung der gleichen liberalen equals()Methode für alle Implementierungen zum Laufen bringen, aber dann laufen Sie Gefahr equals(), in einem anderen Kontext das Falsche zu tun (z. B. zwei Persons zu vergleichen, die durch Datenbankdatensätze mit Versionsnummern unterstützt werden).

Meine Intuition sagt mir, dass Gleichheit pro Sammlung anstatt pro Klasse definiert werden sollte. Wenn Sie Sammlungen verwenden, die auf der Bestellung basieren, können Sie mithilfe einer benutzerdefinierten ComparatorReihenfolge die richtige Reihenfolge für jeden Kontext auswählen. Es gibt kein Analogon für Hash-basierte Sammlungen. Warum ist das?

Zur Verdeutlichung unterscheidet sich diese Frage von " Warum befindet sich .compareTo () in einer Schnittstelle, während .equals () in einer Klasse in Java enthalten ist? ", Da sie sich mit der Implementierung von Auflistungen befasst. compareTo()und equals()/ oder hashcode()beide haben das Problem der Universalität bei der Verwendung von Sammlungen: Sie können nicht verschiedene Vergleichsfunktionen für verschiedene Sammlungen auswählen. Für die Zwecke dieser Frage spielt die Vererbungshierarchie eines Objekts also keine Rolle. Alles, was zählt, ist, ob die Vergleichsfunktion pro Objekt oder pro Sammlung definiert ist.

Sam
quelle
5
Sie können immer Wrapper - Objekte einführen für Persondas die erwartete Umsetzung equalsund hashCodeVerhalten. Sie hätten dann eine HashMap<PersonWrapper, V>. Dies ist ein Beispiel, in dem ein Pure-OOP-Ansatz nicht elegant ist: Nicht jede Operation an einem Objekt ist als Methode dieses Objekts sinnvoll. Java ganze ObjectArt ist eine Mischung aus unterschiedlichen Zuständigkeiten - nur die getClass, finalizeund toStringMethoden scheinen fern gerechtfertigt durch die heutigen Best Practices.
amon
1
1) In C # können Sie eine IEqualityComparer<T>an eine Hash-basierte Sammlung übergeben. Wenn Sie keine angeben, wird eine Standardimplementierung verwendet, die auf Object.Equalsund basiert Object.GetHashCode(). 2) Das Überschreiben Equalseines veränderlichen Referenztyps durch IMO ist selten eine gute Idee. Auf diese Weise ist die Standardgleichheit ziemlich streng, aber Sie können eine lockerere Gleichheitsregel verwenden, wenn Sie sie über eine benutzerdefinierte benötigen IEqualityComparer<T>.
CodesInChaos
2
Verwandte Meta-Frage: Sind diese Fragen doppelt vorhanden?

Antworten:

23

Dieses Design wird manchmal als "Universal Equality" bezeichnet. Man glaubt, dass es eine universelle Eigenschaft ist, ob zwei Dinge gleich sind oder nicht.

Darüber hinaus ist Gleichheit eine Eigenschaft von zwei Objekten, aber in OO rufen Sie immer eine Methode für ein einzelnes Objekt auf , und dieses Objekt entscheidet allein, wie dieser Methodenaufruf behandelt wird. In einem Entwurf wie dem von Java, in dem Gleichheit eine Eigenschaft eines der beiden zu vergleichenden Objekte ist, können einige grundlegende Eigenschaften der Gleichheit wie Symmetrie nicht einmal garantiert werden ( a == bb == a ) , da im ersten Fall die Methode wird angerufen aund im zweiten Fall wird es angerufen bund aufgrund der Grundprinzipien von OO ist es allein adie Entscheidung (im ersten Fall) oderbEntscheidung (im zweiten Fall), ob es sich dem anderen gleich sieht oder nicht. Die einzige Möglichkeit, Symmetrie zu erlangen, besteht darin, die beiden Objekte zusammenarbeiten zu lassen, aber wenn sie nicht ... Pech haben.

Eine Lösung wäre, die Gleichheit nicht zu einer Eigenschaft eines Objekts zu machen, sondern entweder zu einer Eigenschaft zweier Objekte oder zu einer Eigenschaft eines dritten Objekts. Diese letztere Option löst auch das Problem der universellen Gleichheit, denn wenn Sie Gleichheit zu einer Eigenschaft eines dritten "Kontext" -Objekts machen, können Sie sich vorstellen, unterschiedliche EqualityComparerObjekte für unterschiedliche Kontexte zu haben.

Dies ist das Design, das für Haskell zum Beispiel für die EqTypenklasse gewählt wurde. Es ist auch das Design, das von einigen Scala-Bibliotheken von Drittanbietern (z. B. ScalaZ) gewählt wurde, nicht jedoch von der Scala-Kern- oder Standardbibliothek, die universelle Gleichheit für die Kompatibilität mit der zugrunde liegenden Hostplattform verwendet.

Interessanterweise ist es auch das Design, das mit Javas Comparable/ ComparatorInterfaces gewählt wurde. Die Entwickler von Java waren sich des Problems klar bewusst, lösten es jedoch aus irgendeinem Grund nur zur Bestellung, nicht aber zur Gleichheit (oder zum Hashing).

Also, was die Frage betrifft

warum gibt es eine Comparatorschnittstelle aber nein Hasherund Equator?

Die Antwort lautet "Ich weiß nicht". Die Entwickler von Java waren sich des Problems Comparatordurchaus bewusst, wie die Existenz von beweist , aber sie hielten es offensichtlich nicht für ein Problem für Gleichheit und Hasching. Andere Sprachen und Bibliotheken treffen andere Entscheidungen.

Jörg W. Mittag
quelle
7
+1, aber beachten Sie, dass es OO-Sprachen gibt, in denen mehrere Sendungen existieren (Smalltalk, Common Lisp). Deshalb ist im folgenden Satz immer zu stark: "In OO rufen Sie immer eine Methode für ein einzelnes Objekt auf".
Coredump
Ich habe das gesuchte Zitat gefunden. Laut JLS 1.0, The methods equals and hashCode are declared for the benefit of hashtables such as java.util.Hashtabledh beides, equalsund hashCodewurden Objectvon Java-Entwicklern ausschließlich zum Zweck der Einführung als Methoden eingeführt Hashtable- es gibt keine Vorstellung von UE oder etwas Silimarem in der Spezifikation, und das Zitat ist für mich klar genug. wenn nicht für die Hashtable, equalswäre das wohl in einer schnittstelle gefallen Comparable. Während ich Ihre Antwort früher für richtig hielt, halte ich sie jetzt für unbegründet.
Vaxquis
@ JörgWMittag es war ein Tippfehler, IFTFY. Apropos clone- es war ursprünglich ein Operator , keine Methode (siehe Oak Language Specification), Zitat: 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)- die drei keyword-ähnlichen Operatoren waren instanceof new clone(Abschnitt 8.1, Operatoren). Ich nehme an, das ist der wahre (historische) Grund für das clone/ Cloneablechaos - es Cloneablewar einfach eine spätere Erfindung und der vorhandene cloneCode wurde damit nachgerüstet.
Vaxquis
2
"Dies ist das Design, das für Haskell gewählt wurde, zum Beispiel mit der Eq-Typenklasse." Dies ist in gewisser Weise wahr, aber es ist erwähnenswert, dass Haskell im Vorfeld ausdrücklich feststellt, dass zwei Objekte unterschiedlicher Typen niemals gleich sind, während Javas Ansatz dies nicht tut. Die Gleichheitsoperation ist somit Teil des Typs (daher "Typenklasse") und nicht Teil eines dritten Kontextwerts.
Jack
19

Die wahre Antwort auf

warum gibt es eine Comparatorschnittstelle aber nein Hasherund Equator?

ist, Zitat mit freundlicher Genehmigung von Josh Bloch :

Die ursprünglichen Java-APIs wurden innerhalb kürzester Zeit erstellt, um ein schließendes Marktfenster zu erreichen. Das ursprüngliche Java-Team hat einen unglaublichen Job gemacht, aber nicht alle APIs sind perfekt.

Das Problem liegt nur in Java Geschichte, wie bei anderen ähnlichen Angelegenheiten, zB .clone()vs Cloneable.

tl; dr

es ist hauptsächlich aus historischen Gründen; Das aktuelle Verhalten / die aktuelle Abstraktion wurde in JDK 1.0 eingeführt und später nicht behoben, da dies bei Aufrechterhaltung der Abwärtscodekompatibilität praktisch unmöglich war.


Fassen wir zunächst einige bekannte Java-Fakten zusammen:

  1. Java war von Anfang an bis heute mit Stolz abwärtskompatibel und erforderte, dass ältere APIs in neueren Versionen weiterhin unterstützt werden.
  2. als solches hat fast jedes mit JDK 1.0 eingeführte Sprachkonstrukt bis heute gelebt,
  3. Hashtable, .hashCode()& .equals()wurden in JDK 1.0 implementiert ( Hashtable )
  4. Comparable/ Comparatorwurde in JDK 1.2 ( Vergleichbar ) eingeführt,

Nun folgt es:

  1. Es war praktisch unmöglich und sinnlos, verschiedene Schnittstellen nachzurüsten .hashCode()und .equals()dabei die Abwärtskompatibilität beizubehalten, nachdem die Leute erkannt hatten, dass es bessere Abstraktionen gibt, als sie in Superobjekten zu platzieren, weil z. B. jeder einzelne Java-Programmierer von 1.2 wusste, dass jeder Objectsie hat und sie hat Dort physisch zu bleiben, um auch Kompatibilität mit kompiliertem Code (JVM) zu gewährleisten - und eine explizite Schnittstelle zu jeder ObjectUnterklasse hinzuzufügen , die sie tatsächlich implementiert hat, würde dieses Durcheinander gleich Clonableeins machen (sic!) ( Bloch erläutert, warum klonbar ist , siehe auch EJ 2nd) und viele andere Orte, einschließlich SO),
  2. Sie ließen sie einfach dort, damit die zukünftige Generation eine konstante Quelle von WTFs hat.

Nun fragen Sie sich vielleicht: "Was hat Hashtabledas mit all dem zu tun?"

Die Antwort lautet: hashCode()/ equals()Vertrag und weniger gute Sprachdesign-Kenntnisse der Java-Kernentwickler 1995/1996.

Zitat aus der Java 1.0-Sprachspezifikation vom 1996 - 4.3.2 Die Klasse Object, S.41:

Die Methoden equalsund hashCodewerden zum Nutzen von Hashtabellen wie java.util.Hashtable(§21.7) deklariert. Die Methode equals definiert einen Begriff der Objektgleichheit, der auf dem Vergleich von Werten und nicht von Referenzen basiert.

(beachten Sie diese genaue Aussage wurde geändert in späteren Versionen, zu sagen, Zitat: The method hashCode is very useful, together with the method equals, in hashtables such as java.util.HashMap., was es unmöglich macht , die direkt zu machen Hashtable- hashCode- equalsVerbindung ohne historische JLS zu lesen!)

Das Java-Team entschied sich für eine Sammlung im Stil eines guten Wörterbuchs und erstellte diese Hashtable(bisher gute Idee), wollte aber, dass der Programmierer sie mit möglichst wenig Code- / Lernaufwand verwenden kann (Hoppla! Probleme beim Empfang!). und da es noch keine generika gab [es ist ja doch JDK 1.0], würde das bedeuten, dass entweder jeder Object put in Hashtableexplizit eine schnittstelle implementieren müsste (und die schnittstellen waren damals noch in den Anfängen ... Comparablenoch nicht einmal!) Dies zu einer Abschreckung für viele zu machen - oder implizit eine Hash-Methode Objectzu implementieren.

Offensichtlich haben sie sich aus den oben genannten Gründen für Lösung 2 entschieden. Ja, jetzt wissen wir, dass sie falsch lagen. ... es ist einfach, im Nachhinein schlau zu sein. Kichern

hashCode() Erfordertequals() nun, dass jedes Objekt, das es hat, eine eigene Methode haben muss - daher war es ziemlich offensichtlich, dass equals()dies auch eingegeben werden musste Object.

Da die Standardimplementierungen dieser Methoden auf valid a& b Objects im Wesentlichen durch Redundanz nutzlos sind ( a.equals(b) Gleichstellung mit a==bund a.hashCode() == b.hashCode() ungefähr Gleichstellung mit a==b, es sei denn hashCodeund / oder sie equalswerden überschrieben, oder Sie GC Hunderttausende von Objects während des Lebenszyklus Ihrer Anwendung 1 ). Es ist sicher zu sagen, dass sie hauptsächlich als Sicherungsmaßnahme und aus Gründen der Benutzerfreundlichkeit bereitgestellt wurden. Genau so kommen wir zu der bekannten Tatsache, dass immer beides außer Kraft gesetzt wird .equals()und .hashCode()wenn Sie beabsichtigen, die Objekte tatsächlich zu vergleichen oder sie mit Hash zu speichern. Das Überschreiben von nur einem Code ohne den anderen ist eine gute Möglichkeit, Ihren Code zu verfälschen (durch schlechte Vergleichsergebnisse oder wahnsinnig hohe Bucket-Kollisionswerte) - und für Anfänger ist es eine Quelle ständiger Verwirrung und Fehler (suchen Sie nach SO, um zu sehen) es für sich selbst) und ständige Belästigung für erfahrene.

Beachten Sie auch, dass C # zwar besser mit Equals & Hashcode umgeht, aber Eric Lippert selbst angibt, dass er mit C # fast den gleichen Fehler begangen hat , den Sun mit Java vor C # gemacht hat :

Aber warum sollte es der Fall sein, dass jedes Objekt in der Lage sein sollte, sich selbst für das Einfügen in eine Hash-Tabelle zu hashen? Scheint eine seltsame Sache zu sein, die von jedem Gegenstand verlangt, dass er es kann. Ich denke, wenn wir das Typensystem heute von Grund auf neu entwerfen würden, könnte das anders aussehen, vielleicht mit einer IHashableSchnittstelle. Als das CLR-Typsystem entworfen wurde, gab es keine generischen Typen, und daher musste eine universelle Hash-Tabelle in der Lage sein, jedes Objekt zu speichern.

1 natürlich Object#hashCodekann immer noch kollidieren, aber es ein wenig Mühe nimmt , das zu tun, siehe: http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6809470 und verknüpften Fehlerberichte für Details; https://stackoverflow.com/questions/1381060/hashcode-uniqueness/1381114#1381114 behandelt dieses Thema ausführlicher.

vaxquis
quelle
Es ist jedoch nicht nur Java. Viele seiner Zeitgenossen (Ruby, Python, ...) und Vorgänger (Smalltalk, ...) und einige seiner Nachfolger haben auch Universal Equality und Universal Hashability (ist das ein Wort?).
Jörg W Mittag
@ JörgWMittag siehe programmers.stackexchange.com/questions/283194/… - Ich bin nicht einverstanden mit "UE" in Java; UE war historisch gesehen nie ein wirkliches Anliegen in Objectder Gestaltung; Hashbarkeit war.
Vaxquis
@vaxquis Ich möchte nicht darauf eingehen, aber mein vorheriger Kommentar zeigt, dass zwei gleichzeitig erreichbare Objekte denselben (Standard-) Hash-Code haben können.
Setzen Sie Monica
1
@vaxquis OK. Ich kaufe das. Ich mache mir Sorgen, dass jemand, der lernt, dies sieht und denkt, er sei schlau, indem er den System-Hashcode anstelle von Gleichgestellten verwendet Keine Möglichkeit, das Problem zuverlässig zu reproduzieren.
JimmyJames
1
Dies sollte die akzeptierte Antwort sein, da die Schlussfolgerung der akzeptierten Antwort "Ich weiß nicht" lautet
Phoenix,