HashSet Fehlerhaft

[javimka]

Hallo zusammen,

ich habe ein seltsames Verhalten der Klasse HashSet festgestellt. Ich habe ein Objekt, welches ich in das HashSet einfüge, dann etwas verändere und nochmals einfüge. Das genau gleiche Objekt ist dann zwei mal im Set.

Gemäss Dokumentation dürfte das aber nicht passieren:

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2))

Ich habe ein kleines Beispiel, um dies zu veranschaulichen:

import java.util.HashSet;

public class HashSetTest {

	public static void main(String[] args) {

		HashSet<Element> set = new HashSet<Element>();
		Element element = new Element();
		set.add(element); // füge einmal ein
		element.value = 7;
		set.add(element); // füge das gleiche Objekt nochmals ein

		System.out.println("Anzahl elemente: "+set.size());
		for (Element e:set) {
			System.out.println("Element mit value "+e.value);
		}
		
		Object[] os = set.toArray();
		System.out.println("hash stimmt überein:   "+(os[0]==os[1]));
		System.out.println("equals ergibt:   "+os[0].equals(os[1]));
		System.out.println("(e==null ? e2==null : e.equals(e2)) egibt:   "+(os[0]==null ? os[1]==null : os[0].equals(os[1])));
	}
	
	static class Element extends Object {
		
		public int value = 5;
		
		@Override
		public boolean equals(Object o) {
			if (o == this) return true;
			if (!(o instanceof Element))
				return false;
			return ((Element) o).value == value;
		}
		
		@Override
		public int hashCode() {
			return value;
		}
	}
}

Die Ausgabe meines Programms zeigt klar, dass die beiden Objekte im Set, die ja genau das gleiche Objekt sind, logischerweise sowohl gleiche Hashwerte haben, als auch equals true ergibt und auch der Term aus der Dokumentation true ergibt, obwohl versprochen wird, dass das Element genau dann nicht eingefügt wird. Eine fehlerhafte Implementation wie ich finde.

Das Problem entsteht offenbar, weil sich der hashCode des Objekts zwischen den Einfügungen verändert hat. Meiner Meinung nach, müsste HashSet (insbesondere gemäss Dokumentation) dies bemerken.

Sehe ich das richtig, dass die Implementierung hier der Dokumentation nicht entspricht, könnte man dies gar einen Bug nennen? Gibt es eine kluge Alternative oder muss ich mein HashSet selber implementieren?

Dankre für alle Ideen
Gruss
Martin

 

[XHelp]

Sehe ich das richtig, dass die Implementierung hier der Dokumentation nicht entspricht, könnte man dies gar einen Bug nennen? Gibt es eine kluge Alternative oder muss ich mein HashSet selber implementieren?

Nö. Ich verstehe nicht so ganz das Problem. In der equals-Methode vergleichst du (u.A.) den value-Wert. Zuerst ist es 5, dann ist es 7. Warum sollen diese Objekte plötzlich gleich sein? ???:L

 

[Marco13]

Solange ein Objekt in einer HashSet liegt, darf NICHTS an dem Objekt verändert werden, was bewirken würde, dass sein hashCode sich ändert. Wenn man das doch macht, kommt eben solcher Unfug raus. Aber zugegeben: Ich wüßte jetzt nicht auswendig, wo das explizit dokumentiert ist... kann man wohl nur "wissen", wenn man eine ungefähre Vorstellung davon hat, wie eine HashSet funktioniert....

 

[Marco13]

Ah, doch, so halb, in der Doku oben von Set (Java Platform SE 6) :

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set.

Und hashCode spielt da eben entsprechend der Doku Object (Java Platform SE 6) mit rein

 

[nrg]

naja. ich verstehe das Verhalten ehrlich gesagt auf den ersten Blick auch nicht ganz. Ändert man den Code z.B. wie folgt:

(plus der Implementierung von Element (s. Code TO))

        HashSet<Element> set = new HashSet<Element>();
        Element element = new Element();
        set.add(element); // füge einmal ein
        element.value = 7;
        Object[] o = set.toArray();
        System.out.println(o[0] == element);
        System.out.println(o[0].equals(element));
        System.out.println(set.contains(element));

ist die Ausgabe

true
true
false

warum ist das einzige Element des Sets inhaltlich und referenziell identisch mit [c]element[/c] aber contains liefert trotzdem false?

 

[Marco13]

Weil auf basis des (geänderten) hashCodes das Bin gesucht wird, wo das Objekt reingehasht sein müßte - da ist es aber nicht drin, weil es vorher (mit dem alten hashCode) in ein anderes Bin reingehasht wurde.

 

[javimka]

Vielen Dank Marco, dann ist das etwas versteckt wohl doch dokumentiert. Wenn das Verhalten für mutable Objekte nicht definiert ist, muss man sich wohl damit abfinden.

Nun, falls wieder mal jemand diesem Problem begegnet und eine simple Lösung sucht, die zwar vergleichsweise viel langsamer dafür aber funktionstüchtig ist, kann man das z.B. so implementieren:

public class SimpleSet<E> extends LinkedList<E> implements Set<E> {

	@Override
	public boolean add(E e) {
		boolean doit = !contains(e);
		if (doit)
			super.add(e);
		return doit;
	}
}

//edit:
@XHelp
Das Objekt ist trozdem dasselbe, auch wenn sich der gespeicherte int Wert darin verändert hat. Dem HashSet fällt dies nicht auf, weil beim zweiten Einfügen wegen dem geänderten Hashwert nicht an dem "Ort" im HashSet nach einem gleichen Objekt gesucht wird, wo es zuvor mit dem alten Hashwert eingefügt wurde.

 

[tagedieb]

Wenn du Objekte in einem Set mutiertst kannst dies zu ungueltigen Zustaenden fuehren. Wenn du 2 verschiedene Instanzen in einer Set hast und setzt den Wert der 2. Instanz gleich dem der 1. Instanz erhaelst du dadurch doppelte Eintraege in einer Set --> Illegal

Set: A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

Am sichersten waere das Objekt aus der Set rausnehmen, mutieren und wieder reinstellen.
1. set.remove(object);
2. object.setValue(value);
3. set.add(onject);

 

[cyau]

es wurde schon erwähnt, aber nochmal zur verdeutlichung: aus der doku zu hashCode() in Object:

The general contract of hashCode is:
•Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
...

das ist einzuhalten, sonst macht man crap code 😉

 

[tagedieb]

das ist einzuhalten, sonst macht man crap code

Damit bin ich einverstanden. Aber fuer mutierbare Klassen funktioniert es nicht so einfach wie es da steht.
Wenn sich alle Werte aendern koennen kann man auch keinen Hashcode berechnen. Das Einzige was uebrig bleibt ist denselben Hashcode fuer jede Instanz zu verwenden. Soweit funktioniert dies auch, sind aber zum speichern in einem HashSet definitiv ungeeignet, da alle Instanzen im selben Bucket gespeichert werden.

        public int hashCode() {
            return 735917;
        }

 

[Marco13]

@cyau: Das hatte ich auch gefunden, es hat aber mit dem Problem nichts zu tun 😉 (Oder nur indirekt). Es ist durchaus erlaubt, dass sich der HashCode eines Objektes ändert. Sofern sich das Verhalten von "equals" dazu passend ändert, ist das alles OK. Equals darf sich aber nicht ändern, wenn das Objekt in einem Set liegt. Es gilt
(1) a.equals(b) -> a.hashCode() == b.hashCode();
das kann man umformen zu
(2) !(a.hashCode() == b.hashCode()) -> !a.equals(b)
Und zusammen mit der Information aus der Set-Doku
(3) equalsChanges -> setContainsCrap
kann man daraus ableiten
hashCodeChanges --(2)--> equalsChanges --(3)--> setContainsCrap
Oder kurz: Der hashCode darf sich nicht ändern, wenn das Objekt in einer Set liegt.

Die vermutlich sinnvollste Abhilfe ist, wie tagdieb schon geschrieben hat, ein Entfernen-Ändern-NeuEinfügen. Das ist aber u.U. schwer (bis umnöglich) "global" anzuwenden, da man ja nie weiß, wer wo in einer (ggf. privaten) HashMap das Objekt gespeichert hat...