Collections Datenstruktur gesucht

Ratzer

Mitglied
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.
 
N

nillehammer

Gast
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

Mitglied
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?
Java:
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.
 

Ratzer

Mitglied
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:
Java:
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.
 

Ark

Top Contributor
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
 

Ark

Top Contributor
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
 
N

nillehammer

Gast
Ratzer hat gesagt.:
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).
 
Zuletzt bearbeitet von einem Moderator:
Ähnliche Java Themen
  Titel Forum Antworten Datum
N Datenstruktur für Netze gesucht Allgemeine Java-Themen 8
T Datenstruktur gesucht Allgemeine Java-Themen 18
G Datenstruktur gesucht: Allgemeine Java-Themen 3
M Eigene Datenstruktur um eine Menge zu speichern Allgemeine Java-Themen 3
Kirby.exe Union Find Datenstruktur Allgemeine Java-Themen 27
U Klassen Komplexe Datenstruktur in Java Allgemeine Java-Themen 4
J Datenstruktur für eine Map erstellen Allgemeine Java-Themen 2
B Suche geeignete Datenstruktur Allgemeine Java-Themen 5
ruutaiokwu datenstruktur welche sich "im kreis" dreht Allgemeine Java-Themen 26
P Große Datenstruktur im Speicher halten Allgemeine Java-Themen 13
B Suche passende Datenstruktur für 2 Einträge Allgemeine Java-Themen 19
G Welche Datenstruktur? Allgemeine Java-Themen 19
D Datenstruktur für Hierarchie/Baum mit Tiefe 3 Allgemeine Java-Themen 8
D Datenstruktur .. BlockingQueue (LIFO) Allgemeine Java-Themen 3
P Suche Datenstruktur Allgemeine Java-Themen 2
S Welche Datenstruktur für verschiedene Sprachen sinnvoll? Allgemeine Java-Themen 2
ruutaiokwu schnelle datenstruktur... Allgemeine Java-Themen 13
S Baumstruktur/Datenstruktur in Datei speichern Allgemeine Java-Themen 23
D Datenstruktur Allgemeine Java-Themen 2
B Datenstruktur: Liste Allgemeine Java-Themen 5
A Thread sichere Datenstruktur Allgemeine Java-Themen 5
J Arrayähnliche Datenstruktur Allgemeine Java-Themen 4
B Script Problem "Dynamische Datenstruktur" Allgemeine Java-Themen 13
S Frage zum Design der Datenstruktur Allgemeine Java-Themen 10
G Datenstruktur: LISTEN Allgemeine Java-Themen 7
D Suche nach passender Datenstruktur Allgemeine Java-Themen 4
G Daten von Excel kopieren - sinnvolle Datenstruktur? Allgemeine Java-Themen 3
U eigene Datenstruktur ArrayList<String> nach Object [][ Allgemeine Java-Themen 2
F welche Datenstruktur? Allgemeine Java-Themen 9
F Welche Datenstruktur Allgemeine Java-Themen 2
T Datenstruktur für großes Netz Allgemeine Java-Themen 2
Z Welche Datenstruktur verwende ich h_ier bloss ? Allgemeine Java-Themen 14
G NullPointer. in einer Datenstruktur Allgemeine Java-Themen 2
S Welche Datenstruktur passt bei mir? Allgemeine Java-Themen 6
H Speicheverbrauch einer Datenstruktur ermitteln Allgemeine Java-Themen 29
S Suche geeignete Datenstruktur Allgemeine Java-Themen 27
S Datenstruktur für einen Baum Allgemeine Java-Themen 5
D Welche Datenstruktur? Allgemeine Java-Themen 2
T Datenstruktur für Straße ! Allgemeine Java-Themen 5
B Datenstruktur elegant zerlegen Allgemeine Java-Themen 6
A Datenstruktur und Sortierung Allgemeine Java-Themen 12
Peterw73 Hilfe bei Java gesucht Allgemeine Java-Themen 3
N Java API für CardDav und CalDav gesucht Allgemeine Java-Themen 4
B OCR Library gesucht Allgemeine Java-Themen 6
V Javalehrer gesucht Allgemeine Java-Themen 2
K Java-Forum gesucht Allgemeine Java-Themen 12
O Best Practice Hilfe bei Algorithmus gesucht Allgemeine Java-Themen 10
A Hilfe gesucht Allgemeine Java-Themen 44
N Schulung zu Tomcat/JSP/Struts gesucht Allgemeine Java-Themen 0
E Gewollte Endlosschleife unterbrechen oder Alternative gesucht Allgemeine Java-Themen 2
S API gesucht Allgemeine Java-Themen 3
O Freies Tool zum Jar-File obfuscaten gesucht! Allgemeine Java-Themen 5
Londi DJ MP3 Lib gesucht Allgemeine Java-Themen 0
I Dringend nachhilfe in programmieren gesucht!!!!!!!! Allgemeine Java-Themen 1
I Dringend nachhilfe in programmieren in mannheim gesucht!!!!! Allgemeine Java-Themen 3
L Lib gesucht: Java-Objekte mit JSON Allgemeine Java-Themen 2
J Kalenderwecker gesucht Allgemeine Java-Themen 2
D Kuriose Geschichte -> Antwort gesucht Allgemeine Java-Themen 4
O Tag Cloud Algorithmus Idee gesucht Allgemeine Java-Themen 2
S Java XTools gesucht Allgemeine Java-Themen 2
N Boolsche Algebra via eval vereinfachen -> Ausmultiplizieren gesucht Allgemeine Java-Themen 15
E Nachhilfe in Java gesucht!!! Allgemeine Java-Themen 3
H Graph-Algorithmus gesucht Allgemeine Java-Themen 21
B Dringend Hilfe gesucht für Struktogramm Allgemeine Java-Themen 11
N Liste gesucht Allgemeine Java-Themen 2
Guybrush Threepwood Pattern gesucht: Punkt ohne Leerzeichen dahinter Allgemeine Java-Themen 3
B IRC-Library Gesucht Allgemeine Java-Themen 2
T Projektthema gesucht Allgemeine Java-Themen 2
c_sidi90 Aufgaben für Einstellungstest (Azubicasting) gesucht Allgemeine Java-Themen 10
M WebFramework für Userhandling gesucht Allgemeine Java-Themen 7
E Dezimalzahl -> Hexadezimalzahl [Lösungsweg gesucht] Allgemeine Java-Themen 2
M Funktion gesucht: Text vektorisieren Allgemeine Java-Themen 20
J Algorithmus gesucht (Stringtransformation) Allgemeine Java-Themen 4
P JFormattedTextField für durch Semikolon getrennte Integer-Werte gesucht / Regulärer Ausdruck Allgemeine Java-Themen 3
alex_fairytail IT-Kleinprojekt: Ideen gesucht! Allgemeine Java-Themen 18
B TypeOf oder ähnliches gesucht Allgemeine Java-Themen 3
A Bibliothek für NP-harte Zuordnung gesucht. Allgemeine Java-Themen 7
E Super erzwingen, konzept/pattern gesucht. Allgemeine Java-Themen 8
T Passende Listenstruktur gesucht Allgemeine Java-Themen 5
S Webstart: vollständige JNLP-Doku. gesucht Allgemeine Java-Themen 4
S Meinung zu Programmidee gesucht Allgemeine Java-Themen 9
Guybrush Threepwood Neuronale Netzwerke - Bibliothek gesucht Allgemeine Java-Themen 3
agentone Graphen-Lib gesucht Allgemeine Java-Themen 7
Ark Name für Funktion gesucht Allgemeine Java-Themen 5
F Spam-Mail-Programm gesucht Allgemeine Java-Themen 11
S JKL - Bibiliothek gesucht ? Allgemeine Java-Themen 9
hdi Beispiel für EDT Violations gesucht Allgemeine Java-Themen 4
J Open Source Projekt anbieten - Leitfaden gesucht Allgemeine Java-Themen 3
E Mehrfacher vererbungsersatz gesucht. Allgemeine Java-Themen 9
F Passende Struktur gesucht Allgemeine Java-Themen 6
A Regex gesucht Allgemeine Java-Themen 9
J Parser / Scanner / Tokenizer gesucht Allgemeine Java-Themen 3
V DecimalformatPattern gesucht Allgemeine Java-Themen 4
as182005 Bibliothek für Graph Visualisierung gesucht Allgemeine Java-Themen 3
H Framework empfehlung / gute Anfängerbeispiele gesucht Allgemeine Java-Themen 12
M Texteditor gesucht Allgemeine Java-Themen 3
B Effizienter Suchalgorithmus gesucht Allgemeine Java-Themen 10
D design gesucht - Angabe von zu ersetzenden substrings Allgemeine Java-Themen 2
P Java-Security-Aufgabe gesucht Allgemeine Java-Themen 2
J Listener für Ende eines Threads gesucht... Allgemeine Java-Themen 5

Ähnliche Java Themen

Neue Themen


Oben