hashCode

[max_07]

Ich wollte ein paar Punkt-Objekte in ein HashSet einfügen und war davon überzeugt, die Punkt-Objekte, die ich mehrfach eingefügt habe, nur einmal zu sehen. Leider haben sich meine Erwartungen nicht bewahrheitet. Hier die Klasse Punkt:

class Punkt
{
    private int x, y;

    public Punkt(int x, int y)
    {
        this.x = x; this.y = y;
    }

    public String toString()
    {
        return "x = " + x + ", y = " + y;     
    }

    public boolean equals(Object o)
    {
        if (o == this) return true; 
        else if (!(o instanceof Punkt)) return false; 
        else
        {
            Punkt p = (Punkt)o;
            return x == p.x && y == p.y;
        }
    }
}

Und hier noch der Testcode:

HashSet<Punkt> hSet = new HashSet<Punkt>();
hSet.add(new Punkt(10, 20)); 
hSet.add(new Punkt(30, 300)); 
hSet.add(new Punkt(10, 20)); 

Iterator it = hSet.iterator(); 

while(it.hasNext())
{
    System.out.println(it.next().toString()); 
}

Ich habe erwartet, dass die Instanz (10, 20) nur einmal angezeigt wird. Was mach ich falsch? Ich hätte gedacht, dass vor dem Einfügen in das HashSet ein Vergleich angestellt wird, wobei die Methoden 'equals' einbezogen wird.

Danke.

 

[The_S]

HASHSet => du solltest noch die hashCode - Methode überschreiben.

 

[tfa]

Wenn deine Klasse equals() überschreibt, muss hashCode() auch entsprechend überschrieben werden. Lies dir am besten mal die API-Docs zu diesen Methoden durch (in java.lang.Object).

 

[max_07]

Ich habe die API schon gelesen. Wenn equals true liefert, müsste auch der HashCode gleich sein. Nun, wie macht man so was (sinnvolle Implementierung der Methode hashCode) im Falle einer solchen Klasse wie Punkt? Soll ich die Koordinaten addieren? Oder den Abstand vom Ursprung berechnen? Denn, ein Punkt (10, 5) ist nicht gleich wie Punkt (5, 10), obwohl die beiden den gleichen Abstand vom Ursprung haben? Wie könnte man die Methode hashCode sinnvoll implementieren?

 

[The_S]

Ein hashCode muss auch nicht eindeutig sein, er sollte nur so eindeutig wie möglich sein .

 

[Beni]

Wenn equals "true" ergibt, müssen die hashcodes gleich sein.
Dass gleiche hashcodes zu equals=true führt, wird niergends vorgeschrieben.

Die Summe der Koordinaten wird schon ganz gut sein. Du kannst auch noch ein bisschen mit Multiplikationen und Bit-Shifting rumspielen, damit die hashcodes etwas besser verteilt werden.

Aber eigentlich würde schon eine Methode "hashCode" die immer 0 zurückgibt korrekt funktionieren (abgesehen von enormen Performanceverlusten bei HashSet/HashMap...).

 

[Ark]

Mir ist spontan folgende Funktion eingefallen:

public int hashCode(){
    return (x<<16 | x>>>16) ^ y;
}

 

[tfa]

Manche IDEs generieren diese Methoden auch auf Wunsch automatisch, z.B.:

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + x;
		result = prime * result + y;
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof Punkt))
			return false;
		final Punkt other = (Punkt) obj;
		if (x != other.x)
			return false;
		if (y != other.y)
			return false;
		return true;
	}

Ob man das schön finden soll, bleibt jedem selbst überlassen. Funktioniert jedenfalls.

 

[ice-breaker]

Ich empfehle da sehr stark FNV, denn der ist weit effektiver als diese Spielereien, dass man da selbst irgendwie nen bissel mathematisch rumrechnet, und er ist sau simpel und schnell, wird zB von MySQL genutzt

 

[byte]

Das Eclipse Refactoring zum automatischen Überschreiben von equals und hashcode (siehe tfa) benutzt iirc den Algorithmus von J. Bloch aus Effective Java und der ist ziemlich gut. Man muss nur bei komplexen Typen aufpassen, dass man keine Zyklen erzeugt, die zu nur Endlosschleife führen würden.