Objekte in TreeSet einfügen + compareTo

[MarkusLe]

Hallo zusammen.

Ich versuche Objekte (NavigationNodes) in ein TreeSet zu speichern.
Jedes Objekt hat einen Primärschlüssel (aus einer DB), dessen Eindeutigkeit kann also festgestellt werden.
Die NavigationNodes haben eine CompareTo Methode, die Anhand des Primärschlüssels Werte zurückgibt. Das TreeSet sollte ja jetzt mit Hilfe der CompareTo Methode Duplikate feststellen und diese dann nicht ins TreeSet hinzufügen, was aber leider nicht der Fall ist.

Nachfolgend meine Debugausgaben und entsprechende Kommentare:

Füge das Erste Objekt / NavigationNode in das TreeSet ein (Es existieren aber schon 5 andere Objekte (auch NavigationNodes) im TreeSet

MSG: Versuche folgenden Knoten in Treeset zu adden (durch User): Knoten [1]: Knowledgebase ;Vorgaenger: 0 ;Ref: ]

Auflistung der bereits existierenden Objekte im TreeSet:

MSG: Folgende Knoten sind schon in Treeset enthalten: 
MSG:  ... Knoten [7]: KLB Administration ;Vorgaenger: 1 ;Ref: ]
MSG:  ... Knoten [11]: User Administration ;Vorgaenger: 7 ;Ref: Adminformular.jsp]
MSG:  ... Knoten [12]: Beitrags- Administration ;Vorgaenger: 7 ;Ref: Statistikformular.jsp]
MSG:  ... Knoten [61]: AdminNavigation ;Vorgaenger: 7 ;Ref: AdminNavigation.jsp]
MSG:  ... Knoten [92]: Logfile ;Vorgaenger: 7 ;Ref: AdminLogfile.jsp]

Da ja schon 5 Objekte im TreeSet existieren würde ich ja jetzt erwarten, daß
5 mal die Compare Methode aufgerufen wird, aber:

MSG: [NavigationNode.compareTo] ...
  -->11 :: 1
MSG: [NavigationNode.compareTo] ...
  -->7 :: 1

... sie wird nur 2 mal aufgerufen ... Der neue Knoten wird nur mit Knoten 11 und 7 verglichen. Die Knoten 12, 61 und 92 werden nicht verglichen.

Gleiches Spiel setzt sich fort wenn ich weitere Knoten hinzufüge:

MSG: Knoten Knoten [1]: Knowledgebase ;Vorgaenger: 0 ;Ref: ] wird in Treeset geschrieben (über User) ...
MSG: Versuche folgenden Knoten in Treeset zu adden (durch User): Knoten [5]: PDM (CDB) ;Vorgaenger: 0 ;Ref: ]
MSG: Folgende Knoten sind schon in Treeset enthalten: 
MSG:  ... Knoten [1]: Knowledgebase ;Vorgaenger: 0 ;Ref: ]
MSG:  ... Knoten [7]: KLB Administration ;Vorgaenger: 1 ;Ref: ]
MSG:  ... Knoten [11]: User Administration ;Vorgaenger: 7 ;Ref: Adminformular.jsp]
MSG:  ... Knoten [12]: Beitrags- Administration ;Vorgaenger: 7 ;Ref: Statistikformular.jsp]
MSG:  ... Knoten [61]: AdminNavigation ;Vorgaenger: 7 ;Ref: AdminNavigation.jsp]
MSG:  ... Knoten [92]: Logfile ;Vorgaenger: 7 ;Ref: AdminLogfile.jsp]
MSG: [NavigationNode.compareTo] ...
  -->11 :: 5
MSG: [NavigationNode.compareTo] ...
  -->7 :: 5
MSG: [NavigationNode.compareTo] ...
  -->1 :: 5

Interessanter Weise (für micht) habe ich das gleiche Bsp schon mit Strings nachprogrammiert (um Konzeptfehler zu finden), da hat dann aber alles sauber funktioniert.

[Alwin Ibba]

Ist equals und hashCode korrekt implementiert? TreeSet stellt Duplikate nicht mit Hilfe von compareTo sicher sondern mit equals. compareTo dient der Sortierung der Elemente. equals (und damit auch hashCode) muß implementiert werden und muß true zurückgeben wenn compareTo 0 liefert und false andernfalls.

[MarkusLe]

Ich habe mal ein System.out.println in meine equals und hashcode Methoden geschrieben. Interessanter Weise werden diese nicht aufgerufen!

    @Override
    /** Die Gleichheit eines Knoten wird anhand der Knotenid festgestellt. Die Knotenid ist DB Primärschlüssel und somit eindeutig. */
    public boolean equals(Object obj)
    {
        System.out.println("!! equals ...");
        NavigationNode otherNode = (NavigationNode) obj;

        if (otherNode.nodeId == this.nodeId) 
        {
            if (debug) System.out.println("Ist gleich: " + otherNode + " and " + this.toString());
            return true;
        }
        else 
        {    
            if (debug) System.out.println("Ist NICHT gleich: " + otherNode + " and " + this.toString());
            return false;
        }
    }

    @Override
    public int hashCode()
    {
        System.out.println("!! HashCode");
        return this.nodeId;
    }

[Alwin Ibba]

Sorry stand auf dem Schlauch. Das ist ein TreeSet und dieses ruft tatsächlich nur compareTo auf um eine ev. Gleichheit festzustellen. Da die Semantik des Set interfaces auf equals basiert ist es lediglich dringend empfohlen equals zu implementieren so das es mit compareTo übereinstimmt. Funktionieren sollte es mit dem TreeSet (nur mit diesem!) aber trotzdem. Es muß aber nicht zwangsläufig x-mal compareTo aufgerufen werden. Wenn das TreeSet feststellt
das das neue Element a < Element b und Element b < Element c, so kann der Vergleich a mit c entfallen weil a garantiert kleiner ist als c. Dafür ist es ja als tree implementert. Voraussetzung ist natürlich, das compareTo korrekt implementiert ist.

[MarkusLe]

Gelöst

Sorry stand auf dem Schlauch. Das ist ein TreeSet und dieses ruft tatsächlich nur compareTo auf um eine ev. Gleichheit festzustellen. Da die Semantik des Set interfaces auf equals basiert ist es lediglich dringend empfohlen equals zu implementieren so das es mit compareTo übereinstimmt. Funktionieren sollte es mit dem TreeSet (nur mit diesem!) aber trotzdem. Es muß aber nicht zwangsläufig x-mal compareTo aufgerufen werden. Wenn das TreeSet feststellt
das das neue Element a < Element b und Element b < Element c, so kann der Vergleich a mit c entfallen weil a garantiert kleiner ist als c. Dafür ist es ja als tree implementert. Voraussetzung ist natürlich, das compareTo korrekt implementiert ist.

Du hast natürlich absolut recht. Nach deiner Antwort habe ich noch ca 30 Sekunden gebraucht um den Fehler zu finden:
Es war wirklich die CompareTo Methode (auskommentiert ist der alte Code)

        if (otherObject.getNodeId() == this.getNodeId()) 
        {
            return 0;
        }
        else // Beide Objekte sind unterschiedlich
        {
            //if (this.isFile()) return 1;
            //else return -1;
            if (otherObject.getNodeId() > this.getNodeId()) return -1;
            else return 1;

        }

Ich wollte damit eigentlich eine spezielle Sortierung erreichen, nur war die Logik leider falsch
Nach deiner Antwort sind mir aber spontan wieder ein paar Studieninhalte eingefallen

Vielen Dank dass du mich auf die Lösung "gelupft" hast