compareTo & equals

[RalleII]

Hallo,
ich habe eine Frage zu einem Hinweis den man in der Compareable-API findet (bzw. hier aus dem Java ist auch eine Insel Buch):
"Wichtig ist neben einer Implementierung von compareTo() auch die passende Realisierung in equals(). Sie ist erst dann konsistent, wenn e1.compareTo(e2) == 0 das gleiche Ergebnis wie e1.equals(e2) liefert, wobei e1 und e2 den gleichen Typ besitzen. Ein Verstoß gegen diese Regel kann bei sortierten Mengen schnell Probleme bereiten"


Hm, was kann passieren wenn man das nicht befolgt?

Was ich habe:
Ich habe eine Hilfsstruktur in der ich paar Dinge speicher. Unter anderem ein long-Wert, in dem der Zeitpunkt der letzten Änderung steht.
Nun habe ich bewusst dieser Hilfsstruktur das Compareable-Interface spendiert, dass die Reihenfolge bezüglich des Änderungszeitpunkt zurückgibt.
Das habe ich so gemacht, damit mein TreeSet nach dem Änderungszeitpunkt sortiert ist.

Aber die equals-Methode hat bei mir nichts damit zu tun. Sollten 2 Objekte in der gleichen Millisekunde verändert werden (was aber unwahrscheinlich ist) würde compareTo 0 zurück geben aber da sie nicht gleich sind würde equals false zurückgeben.

Bis jetzt habe ich keine Probleme damit (wahrscheinlich weil es so gut wie nie vorkommt, dass es zwei Objekte mit dem gleichen Änderungszeitpunkt gibt) aber mit welchen Problemen muss ich rechnen?
Wie kann ich das Problem eleganter lösen?

Danke

 

[mjustin]

Hm, was kann passieren wenn man das nicht befolgt?
...
Sollten 2 Objekte in der gleichen Millisekunde verändert werden (was aber unwahrscheinlich ist) würde compareTo 0 zurück geben aber da sie nicht gleich sind würde equals false zurückgeben.

Den Fehler kann man dann leicht reproduzieren, indem man Objekte mit gleichen Millisekundenwerten konstruiert und dem TreeSet hinzufügt.

Wenn man dann auf das TreeSet zugreift, in dem e1 und e2 und ein bestimmtes Objekt sucht, wird anhand compareTo gesucht.

Wenn e1 und e2 den gleichen Millisekundenwert enthalten (und damit compareTo implementiert wird), wird das zum Beispiel dazu führen, dass bei treeSet.add(e1); und treeSet.add(e2) das zuerst gespeicherte Objekt e1 durch e2 ersetzt wird.

 

[Marco13]

Ja, man muss damit rechnen, dass das eine Element das andere (laut compareTo ja "gleiche") Element überschreibt (AFAIK wird bei der TreeSet nicht nochmal mit equals geprüft). Abhilfe... hm... An welchen Stellen brauchst du die Eigenschaft, dass die Objekte sortiert sind? Im Zweifelsfall muss man wohl mit einer Liste rumhantieren, wo man sortiert löscht und einfügt, aber das in bezug auf die Laufzeit in die Nähe einer TreeSet zu bringen wäre frickelig...

 

[mjustin]

Eine Lösung wird hier beschrieben: Problem when adding elements to a TreeSet<Comparator> – some elements are not added

 

[nillehammer]

Anfangs habe ich auch immer fleißig Comparable implementiert. Mach ich heute garnicht mehr. Man kann für fast alles einen Comparator benutzen. Wenn dieser konsistent zu equals() ist, gut, falls nicht, auch egal.

 

[RalleII]

Hallo,
danke für eure Antworten.

Dass 2 gleiche Elemente sich überschreiben hab ich gar nicht bedacht. Habe vor kurzen einen eigenen AVL-Baum gebaut, der gleiche Elemente trotzdem aufnehmen kann, weshalb ich diese Problematik wohl nicht bemerkt habe. Aber ok, eigentlich klar, Sets sind ja soweit ich weiß definiert, dass es keine doppelten Einträge geben kann.

Den Satz von oben
"Wichtig ist neben einer Implementierung von compareTo() auch die passende Realisierung in equals(). Sie ist erst dann konsistent, wenn e1.compareTo(e2) == 0 das gleiche Ergebnis wie e1.equals(e2) liefert, wobei e1 und e2 den gleichen Typ besitzen. Ein Verstoß gegen diese Regel kann bei sortierten Mengen schnell Probleme bereiten"

finde ich dann trotzdem irreführend. Da hört es sich so an, als müsste equals auch true zurück geben, wenn compareTo 0 zurück gibt, sonst würde etwas nicht funktionieren.
Wenn ich es nun richtig verstanden habe wollen sie nur darauf hinweisen, dass bei einem compareTo der Tree von einem equals true ausgeht aber man equals trotzdem anders implementieren kann.

Ich habs nun so gelöst, dass ich nicht die Zeit speicher, zu der das Element verändert wurde, sondern einen "Veränderungscounter" habe. Es gibt einen static changeCounter. Dieser wird bei einer Veränderung in einem Element mit lastChange = changeCounter++ zugeteilt.
Ein Überlauf wird auch behandelt.
Somit geh ich dieser Problematik aus dem Weg.


Danke für eure Antworten.

 

[Marco13]

Den Satz von oben
"Wichtig ist neben einer Implementierung von compareTo() auch die passende Realisierung in equals(). Sie ist erst dann konsistent, wenn e1.compareTo(e2) == 0 das gleiche Ergebnis wie e1.equals(e2) liefert, wobei e1 und e2 den gleichen Typ besitzen. Ein Verstoß gegen diese Regel kann bei sortierten Mengen schnell Probleme bereiten"

finde ich dann trotzdem irreführend. Da hört es sich so an, als müsste equals auch true zurück geben, wenn compareTo 0 zurück gibt, sonst würde etwas nicht funktionieren.

Das ist auch so!

Wenn ich es nun richtig verstanden habe wollen sie nur darauf hinweisen, dass bei einem compareTo der Tree von einem equals true ausgeht aber man equals trotzdem anders implementieren kann.

"Können" tut man viel, aber es ist trotzdem wichtig, dass das Verhalten der Spezifikation entspricht. Angenommen, in der nächsten Java-Version (oder auch nur in einer anderen Implementierung von SortedSet!) wird (aus welchem Grund auch immer) zusätzlich zu a.compareTo(b)==0 noch überprüft, ob a.equals(b) gilt: Wenn man sich an die Vorgaben gehalten hat, funktioniert alles weiterhin. Wenn nicht: Viel Spaß bei der Fehlersuche...

 

[ThreadPool]

Das ist auch so!

Und das steht wo? Ich lese nur Folgendes aus der Beschreibung von Comparable: "[...]It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y)).[...]"

 

[Marco13]

Inferenzmechanismen 😉

Comparable:

The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C.

AND

TreeSet:

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface.

IMPLIES so in etwa

If a tree set is to correctly implement the Set interface, e1.compareTo(e2)==0 must have the same boolean value as e1.equals(e2) for all its elements

 

[ThreadPool]

Inferenzmechanismen..., die funktionieren aber nur zuverlässig solange man von gültigen Voraussetzungen ausgeht.

Du beziehst dich mit deinem Zitat - "Das ist auch so!" auf die Aussage - "Da hört es sich so an, als müsste equals auch true zurück geben, wenn compareTo 0 zurück gibt, sonst würde etwas nicht funktionieren." Die sich wiederrum auf eine Aussage über die grundsätzliche Implementierung von compareTo.

Deine Aussage ist dann einfach irrelevant, weil du von einer falschen Voraussetzung ausgegangen bist von der ich nicht sprach nämlich compareTo im Kontext von Java-Set-Implementierungen.

Grundsätzlich darf die compareTo-Methode sehr wohl != 0 sein wenn equals == true ist, was auch eindeutig im Dokumentationstext zu lesen ist inkl. zusätzlicher Bemerkungen wie eine derartige Abweichung zu dokumentieren ist. Und genau damit wollte ich den OT bestätigen der feststellte das der Buchtext irreführend sei.

Deine Anmerkung im Kontext von Java-Set-Implementierungen ist jedoch richtig, wie du auch schlüssig mithilfe der Dokumentation gezeigt hast. Auf diese Problematik der nicht konsistenten Ordnungen wird zusätzlich im Dokumentationstext von Comparable hingewiesen.

 

[Marco13]

Ich weiß nicht worauf du raus willst, aber die ursprüngliche Frage bezog sich auf sortierte Mengen. Ist wohl nicht so wichtig.