Collections Datenstruktur gesucht

[Ratzer]

Hallo!
Ich suche eine Datenstruktur, die Objekte von einem selbst erstellten Typ aufnimmt und dabei die Reihenfolge des Einfügens beibehält sowie doppelte Einträge vermeidet.
Das schreit jetzt erstmal nach einer LinkedHashSet, das Ding ist nur, dass ich die Objekte auch ändern muss. In einer LinkedHashSet könnte ich jetzt zwar durch die ganze Menge iterieren bis ich das gesuchte Objekt habe, allerdings müsste ich es ja dann löschen und neu einfügen, jedoch soll die alte Reihenfolge beibehalten bleiben, denn durch das neue Einfügen landet das veränderte Objekte ja ganz am Ende. Gibt es überhaupt solche Datenstrukturen? Wenn nicht, müsste ich wohl eine eigene Klasse - von z.B. ArrayList abgeleitet - erstellen und dort die einfüge-Operation so überschreiben, dass keine doppelten Einträge in die Liste kommen.

 

[XHelp]

Wie sieht denn die Hashfunktion aus? Vlt bauchst du einfach eine, wo die zu veränderten Werte nicht reinfließen.

 

[nillehammer]

Was Du suchst, ist ein IndexedSet oder eine UniqueList. Sowas gibt es in Java leider nicht. Das hängt ein bischen damit zusammen, dass sich die Interfaces etwas widersprechen und mit der Art und Weise, wie die Daten intern gepspeichert werden. Eine gute Annäherung einer solchen Datenstruktur stellt Apache Commons Collections zur Verfügung (SetUniqueList oder ListOrderedSet). Prüfe, ob diese Deinen Anforderungen genügen. Selbst implementieren geht natürlich auch.

 

[Ratzer]

Die beiden Datenstrukturen schauen ja ganz gut aus. Hab mir mal so ein bisschen den Quellcode angesehen und die scheinen ja zu basieren auf einer Set im Zusammenspiel mit einer ArrayList.

Was haltet ihr eigentlich davon, es so zu machen?

HashSet set = new HashSet();
ArrayList list = new ArrayList(Arrays.asList(set.toArray()));

Oder wäre das wohl von der Performance zu schlecht? Zu beachten ist, dass man wohl nur einmal in die Set etwas einfügt und dann nie wieder.

 

[XHelp]

Hast du nicht gesagt, dass die die Reihenfolge wichtig ist?

 

[Ratzer]

Dass ich ein Index habe ist wichtig und dass die Reihenfolge nach dem Erstellen der Liste immer gleich bleibt, ist wichtig. Aber das ist auch egal. Die Set wird ja sowieso nur zum einmaligen Einfügen benutzt, d.h. ich kann das auch gleich so machen:

inserted = set.add(object);
if (inserted)
      list.add(object);

Und für was anderes wird die Set eben nicht gebraucht.
Wenn man sich mal das hier anguckt, sieht man, dass fertige Java IndexSets genauso funktionieren.

 

[Gassst]

In einer LinkedHashSet könnte ich jetzt zwar durch die ganze Menge iterieren bis ich das gesuchte Objekt habe, allerdings müsste ich es ja dann löschen und neu einfügen

Warum musst du das Objekt aus der liste löschen und wieder einfügen zum ändern?

 

[XHelp]

und dabei die Reihenfolge des Einfügens beibehält

Reihenfolge nach dem Erstellen der Liste immer gleich bleibt

Aber das ist auch egal.

Ja was denn nun? :bahnhof:

 

[Ark]

Ich vermute mal, es ist so gemeint: Die Liste wird benutzt, um die Reihenfolge des Einfügens festzuhalten, und das Set wird benutzt, um vor dem Einfügen schnell/performant feststellen zu können, ob das Element schon eingefügt wurde.

Theoretisch könnte man sich das Set sparen, aber um halt den Test auf "schon eingefügt" mit O(1) oder O(log n) durchführen zu können, wird ein Element sowohl in das Set als auch in die Liste eingefügt (wenn es denn eingefügt wird). Würde man nicht zusätzlich noch das Vorhandensein von Elementen in einem Set mitführen, wäre dieser Test auf "schon eingefügt" mit O(n) durchzuführen (ergo: man müsste die Liste abklappern), und das will man verhindern.

Ark

 

[Ratzer]

Warum musst du das Objekt aus der liste löschen und wieder einfügen zum ändern?

Weil sich der Hashcode ändert.

Ark hat das richtig erklärt, genauso läuft das bei mir jetzt.

 

[Michael...]

Weil sich der Hashcode ändert.

Definierst Du den Hashcode selbst?

Mir ist auch nicht ganz klar warum man das Objekt löschen und neu einfügen muss? Man kann doch das Objekt ändern, wenn sich der Hashcode ändert ist doch egal, das Objekt bleibt an der selben Stelle der Liste.

 

[Ark]

Mir ist auch nicht ganz klar warum man das Objekt löschen und neu einfügen muss? Man kann doch das Objekt ändern, wenn sich der Hashcode ändert ist doch egal, das Objekt bleibt an der selben Stelle der Liste.

In der Liste bleibt das Objekt da, wo es ist, ja. Aber das mit dem Set ist dann ein echtes Problem, wie der TO schon richtig angemerkt hat: Durch die Änderung am Objekt, die auch eine Änderung der Werte von [c]equals()[/c] bzw. [c]hashCode()[/c] hervorruft, findet das HashSet das Objekt nicht mehr wieder, da es jetzt (quasi falsch einsortiert) irgendwo in der Hashtabelle "verschwunden" ist. Das Set merkt ja nicht, dass sich etwas am Objekt geändert hat und deswegen das Objekt neu einsortiert werden müsste.

Dass solche Konstellationen schwierig sind, steht schon in der Dokumentation: [c]hashCode()[/c] schiebt einen Großteil der Verantwortung auf [c]equals()[/c] ab, und [c]equals()[/c] muss laut Dokumentation nicht nur reflexiv, transitiv und symmetrisch sein (wie jede Äquivalenzrelation), sondern auch noch konsistent:

It is consistent: for any non-null reference values [c]x[/c] and [c]y[/c], multiple invocations of [c]x.equals(y)[/c] consistently return [c]true[/c] or consistently return [c]false[/c], provided no information used in [c]equals[/c] comparisons on the objects is modified.

Ergo: [c]equals()[/c] und [c]hashCode()[/c] sollten idealerweise nur von Werten abhängen, die sich nicht im Laufe der Zeit ändern. Wenn dem doch so ist, muss man dafür sorgen, dass die Objekte, wenn sie von HashSets referenziert werden, wieder neu einsortiert werden. Das kann man am einfachsten mit: rausnehmen, ändern, einfügen.

Ark

 

[nillehammer]

Die beiden Datenstrukturen schauen ja ganz gut aus. Hab mir mal so ein bisschen den Quellcode angesehen und die scheinen ja zu basieren auf einer Set im Zusammenspiel mit einer ArrayList.

Dann benutz sie doch. Die scheinen doch genau das zu machen, was Du willst. Warum dann selber implementieren? Und nun sag nicht: "Zu Übungszwecken". Der Lerneffekt davon, eine add-Methode zu schreiben, die erst in ein Set und dann ggf. in eine List added ist marginal. Auch, wenn Du am Ende etwas hinbekommst, wird es in der ein oder anderen Situation fehlerhaft sein, weil Du etwas nicht beachtet hast. Wenn Du dann doch alles beachtet und alle Bugs beseitigt hast, sieht dein Quelltext wahrscheinlich mehr oder weniger genau so aus wie der von Commons Collections. Also wieso nicht gleich das benutzen? Lernen kann man auch, indem man den Quelltext nachvollzieht (hast Du ja sogar schon mit angefangen).