Performancevergleich: HashSet <=> ArrayList

[Gast2007]

Hallo,
weiß jemand wie man am performantesten eine Liste von einmal vorkommen dürfenden Strings speichert?

Meines Wissens nach kann ich entweder ein HashSet nehmen, oder eine ArrayList, bei der ich folgenden Code benutzen muss:

if(!myList.contains(newElement))
    myList.add(newElement);

Kann es sein, dass man mit einem HashSet schneller ist, jedoch die ArrayList-Methode weniger Speicher frisst?

Vielen Dank.

[ja kann sein]

ja kann sein

[Gast]

Kommt darauf an, was du mit der Datenstruktur dann anfangen willst. Den contains()-Test kannst du dir beim Set jedenfalls schon mal sparen selber hinzuschreiben - das Set sorgt selbst dafür, dass jeder String nur einmal hinzugefügt wird. Der contains()-Test ist beim Set auch schneller als bei der ArrayList [O(1) im Vergleich zu O(n)].

Wenn du eine unsortierte Datenstruktur haben willst in der jeder String nur einmal abgelegt wird, ist das HashSet die richtige Wahl.

[Gast2007]

Vielen Dank für die schnelle Antwort. D. h., wenn ich die String in einer, z. B. alphabetisch sortierten Reihenfolge halten wollte, müsste ich die ArrayList nehmen, weil ich dort die Reihenfolge festlegen kann.
Wie sieht es denn mit dem Speicherverbrauch aus? Benötigt da das HashSet mehr oder weniger Speicher bei gleich vielen Elementen?

[xindon]

Kann man doch bestimmt ausprobieren?

Zwei simple mehr oder weniger gute Methoden:
1.) Task Manager / Speicherverbrauch des Programms
2.) Serialisierung und dann Dateigröße

Ist jetzt aber eigentlich nur geraten, wahrscheinlich sind beide Ideen Mist, oder?

[Javaner]

2.) ... ist kein Mist!

Ansonsten dürfte der Unterschied bei normalen
Anwendungen nicht ins Gewicht fallen.

[Gast]

Gast2007 schrieb:

Vielen Dank für die schnelle Antwort. D. h., wenn ich die String in einer, z. B. alphabetisch sortierten Reihenfolge halten wollte, müsste ich die ArrayList nehmen, weil ich dort die Reihenfolge festlegen kann.

Da gibt's aber auch was besseres für. Eine List nimmt man immer dann, wenn man die Reihenfolge beim Einfügen selber festlegt. Für eine automatische Sortierung wäre in deinem Fall wahrscheinlich das TreeSet ganz gut geeignet. Das ist einfach immer sortiert, nach jedem Einfügen und Entfernen und du musst dir darüber keine Gedanken machen. Amsonsten verhält es sich wie ein HashSet.

Wie sieht es denn mit dem Speicherverbrauch aus? Benötigt da das HashSet mehr oder weniger Speicher bei gleich vielen Elementen?

Nahezu gleich viel. Das HashSet ist wie die ArrayList intern mit einem Array implementiert und hat eine problemspezifische Hashfunktion (die von String in deinem Fall) und eine allgemeine, die den Hashcode auf den Index abbildet. Die Array-Elemente sind allerdings nicht die Strings selber sondern Buckets von Strings, das ist das, was einen minimalen Unterschied machen könnte.

Beim TreeSet brauchst du nochmal winzig mehr Speicher, weil jedes Element in seinen eigenen Node kommt. Aber in O-Notation unterscheidet sich der Speicherbedarf bei allen 3 Strukturen nicht. Nimm also ruhig das geeignetste her.

[grenouille_unreg]

Ich glaube es war um den Faktor 5, dass ein Element mehr Speicherplatz (auf die Referenz bezogen) im HashSet benötigt als i.d. ArrayList. Einfach die Entry Klasse in HashMap anschauen.(HashSet delegiert seine anfragen an HashMap).

Gruss
Marcel