Probleme mit Sets

[Se7enDays]

Hallo,

ich verstehe nicht warum folgender Code nicht funktioniert:

public class Pair implements Comparable<Pair> {
    int x;
    int y;
    
    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public int getX() {
        return x;
    }
    
    public int getY() {
        return y;
    }
    
    public boolean equals(Object o) {
        if(o instanceof Pair) {
            Pair p = (Pair)o;
            if(this.x == p.x && this.y == p.y) return true;
            if(this.x == p.y && this.y == p.x) return true;            
        }
        return false;
    }
    
    public int compareTo(Pair p) {
        if(this.x == p.x && this.y == p.y) return 0;
        if(this.x == p.y && this.y == p.x) return 0;          
        if(this.x - p.x == 0) return this.y - p.y;
        return this.x - p.x;
    }
    
    public static void main(String[] args) {
        int[] test = new int[]{1, 2, 3, 4};
        SortedSet<Pair> set = new TreeSet<Pair>();
        
        for(int x : test) {
            for(int y : test) {
                if(x != y) set.add(new Pair(x, y));
            }
        }
        
        for(Pair p : set) {
            System.out.println(p.getX() + " " + p.getY());
        }
        System.out.println(set.size());
    }
}

Ich benutze ein Set um Duplikate zu verhindern. Für mich sind (1,2) und (2,1) auch Duplikate. Aber zum Schluss befinden sich trotzdem mehr Elemente drin als gewollt. Andere Set-Klassen funktionieren auch nicht.

Und nicht sagen, man kann das mit zwei geschachtelten for-Schleifen lösen. Habe ein einfaches Beispiel genommen als Abstraktion.[/code]

 

[Wildcard]

Wer equals überschreibt. muss auch hashcode überschreiben. Das ist der Kontrakt der Methoden.

 

[Se7enDays]

Ok, habe hashcode überschrieben. Aber Problem bleibt dasselbe.

 

[Murray]

Wie hast Du hashcode() denn überschrieben?

 

[Se7enDays]

erstmal provisorisch mit:

public int hashCode() {
        return x * y;
    }

 

[Marco13]

HashCode sollte unbedingt überschrieben werden - bei einer TreeSet hat das aber nichts mit dem Problem zu tun. Das Problem liegt beim compareTo. Du hast dort eine "lexikographische" Sortierung implementiert. Durch deine Forderung an die Gleichheit geht aber die Ordnung kaputt. Es gilt
(1,4) < (2,3) < (4,1)
aber gleichzeitig (1,4)==(4,1). Damit ist (2,3) sowohl größer als auch kleiner als (4,1)==(1,4), und wo welches Pair in der soriterten Menge landet ist "Zufall" (d.h. hängt davon ab, wie sortiert wird). Wenn du mal die Reihenfolge der Zahlen in deinem Array umdrehst (zu {4,3,2,1}) wirst du sehen, dass andere Pairs das Einfügen "überleben".

Durch die Verwendung einer HashSet (und überschriebener hashCode-Methode) kann man das Problem zwar umgehen, aber das ändert nichts daran, dass die Mischung aus compareTo und equals, die du implementiert hast, "inkonsistent" ist.

 

[Marco13]

Noch als Ergänzung, das letzte war vielleicht nicht ganz klar: Wenn du die Pairs ERST in eine HashSet einfügst, und daraus dann mit
SortedSet<Pair> sortedSet = new TreeSet<Pair>(hashSet);
eine Sortiere Menge erstellst, sollte alles in Ordnung sein, aber das potentielle Fehler durch die inkonsistente Implementiertung bleibt.

 

[Murray]

Wenn in Deinem Kontext Pair(x,y) wirklich äquivalent ist zu Pair(y,x), dann ändere doch den Konstruktor:

    public Pairs(int x, int y) {
        this.x = Math.max( x, y);
        this.y = Math.min( x, y);
    }