Ich denke darüber nach, eine Sammlung mit einer großen Anzahl einzigartiger Objekte zu füllen. Wie hoch sind die Kosten einer Einfügung in einem Set (zB HashSet) im Vergleich zu einer List (zB ArrayList)?
Mein Gefühl ist, dass die doppelte Eliminierung in Mengen einen leichten Overhead verursachen kann.
Es gibt keine "doppelte Eliminierung" wie zum Beispiel einen Vergleich mit allen existierenden Elementen. Wenn Sie in einen Hash-Satz einfügen, handelt es sich wirklich um ein Dictionary mit Hash-Code. Es gibt keine doppelte Überprüfung, es sei denn, es gibt bereits Elemente mit demselben Hash-Code. Angesichts einer vernünftigen (gut verteilten) Hash-Funktion ist es nicht so schlimm.
Wie Will bemerkt hat, ist HashSet wegen der Dictionary-Struktur wahrscheinlich etwas langsamer als ein ArrayList (es sei denn, Sie wollen "zwischen" vorhandene Elemente einfügen). Es ist auch ein bisschen größer. Ich bin mir nicht sicher, ob das ein wesentlicher Unterschied ist.
Wenn Sie sicher sind werden Ihre Daten eindeutig sein, verwenden Sie eine Liste. Sie können ein Set verwenden, um diese Regel durchzusetzen .
Sets sind schneller als Listen wenn Sie einen großen Datensatz haben, während der inverse ist true für kleinere Datensätze. Ich habe diese Behauptung nicht persönlich getestet.
Welche Art von Liste?
Überlegen Sie auch, welche Liste Sie verwenden möchten. VerknüpfteListen können Elemente schneller hinzufügen oder entfernen.
ArrayLists sind schneller bei wahlfreiem Zugriff ( for loops, usw.), aber dies kann mit dem Iterator einer LinkedList umgangen werden. ArrayLists sind viel schneller bei: list.toArray() .
Sie haben Recht: Mengenstrukturen sind von Natur aus komplexer, um Duplikate zu erkennen und zu eliminieren. Ob dieser Overhead für Ihren Fall signifikant ist, sollte mit einem Benchmark getestet werden.
Ein weiterer Faktor ist die Speichernutzung. Wenn Ihre Objekte sehr klein sind, kann der Speicherbedarf, der durch die Mengenstruktur eingeführt wird, erheblich sein. Im extremsten Fall ( TreeSet<Integer> vs. ArrayList<Integer> ) kann die Mengenstruktur mehr als 10 mal so viel Speicher benötigen.
Wenn das Ziel die Eindeutigkeit der Elemente ist, sollten Sie eine Implementierung von java.util.Set Schnittstelle. Die Klasse java.util.HashSet und java.util.LinkedHashSet haben O ( alpha ) (nahe bei O (1) im besten Fall) Komplexität für einfügen, löschen und enthält überprüfen.
ArrayList haben O ( n ) für Objekt (nicht Index) enthält überprüfen (Sie müssen durch die gesamte Liste scrollen) und Einfügen (wenn die Einfügung nicht im Ende der Liste ist, Sie müssen das gesamte Unterstreichungsfeld verschieben).
Sie können LinkedHashSet verwenden, die die Reihenfolge der Einfügung beibehalten und die gleiche Potenz von HashSet haben (belegt nur ein bisschen mehr Speicher).
Sie müssen konkrete Implementierungen vergleichen (zum Beispiel HashSet mit ArrayList ), weil die abstrakten Schnittstellen Set / List nicht wirklich etwas über die Leistung aussagen.
Das Einfügen in HashSet ist eine ziemlich billige Operation, solange die hashCode() des einzufügenden Objekts gesund ist. Es ist immer noch etwas langsamer als ArrayList , da es sich bei der Einfügung um eine einfache Einfügung in ein Array handelt (vorausgesetzt, Sie fügen am Ende ein und es gibt noch freien Platz; ich berücksichtige nicht die Größe des internen Arrays, da die gleichen Kosten anfallen auch zu HashSet ).
Ich glaube nicht, dass Sie dieses Urteil einfach über die Kosten des Baus der Sammlung fällen können. Andere Dinge, die Sie berücksichtigen müssen, sind:
Diese können alle Ihre Wahl der Datenstruktur beeinflussen.
Java-Liste:
Wenn Sie eine solche Anforderung nicht haben, müssen Sie doppelt halten oder nicht. Dann können Sie List statt Set verwenden.
List ist eine Schnittstelle im Collection-Framework. Was die Collection-Schnittstelle erweitert. und ArrayList, LinkedList ist die Implementierung der List-Schnittstelle.
Wann wird ArrayList oder LinkedList
verwendet?ArrayList: Wenn Sie eine solche Anforderung haben, die in Ihrer Anwendung am meisten funktioniert, ist der Zugriff auf die Daten. Dann sollten Sie sich für ArrayList entscheiden. weil ArrayList RtandomAccess-Schnittstelle implementiert, die Marker-Schnittstelle ist. Aufgrund der Marker-Schnittstelle haben ArrayList die Möglichkeit, auf die Daten in O (1) -Zeit zuzugreifen. und Sie können ArrayList über LinkedList verwenden, wo Sie Daten entsprechend der Reihenfolge erhalten möchten.
LinkedList: Wenn Sie eine solche Anforderung haben, ist Ihre Arbeit meistens das Einfügen oder Löschen. Dann sollten Sie LinkedList über die ArrayList verwenden. Weil in InsertedList Insertion und Deletion in O (1) Zeit passieren, während in ArrayList es O (n) Zeit ist.
Java-Set:
Wenn Sie in Ihrer Anwendung Anforderungen haben, dass Sie keine Duplikate wünschen. Dann sollten Sie Set statt List wählen. Weil Set keine Duplikate speichert. Weil Set nach dem Hashing-Prinzip arbeitet. Wenn wir ein Objekt in Set hinzufügen, prüft es zunächst den Hash-Code des Objekts im Bucket, wenn ein Hash-Code gefunden wird, der in seinem Block vorhanden ist. Dann wird das Objekt nicht hinzugefügt.
Tags und Links java list set insert collections