Faustregel für die Auswahl einer Implementierung einer Java Collection?

Question

Hat jemand eine gute Faustregel für die Wahl zwischen verschiedenen Implementierungen von Java Collection-Schnittstellen wie List, Map oder Set?

Warum oder in welchen Fällen würde ich beispielsweise im Allgemeinen lieber einen Vector oder eine ArrayList, eine Hashtable oder eine HashMap verwenden?

Answer 1

Ich habe diese Entscheidungen immer von Fall zu Fall getroffen, je nach Anwendungsfall, wie zum Beispiel:

• Muss die Bestellung bestehen bleiben?
• Werde ich null Schlüssel/Werte haben?Dups?
• Wird von mehreren Threads darauf zugegriffen?
• Benötige ich ein Schlüssel/Wert-Paar?
• Benötige ich Direktzugriff?

Und dann hole ich meine handliche 5. Auflage hervor Java auf den Punkt gebracht und vergleichen Sie die ca. 20 Optionen.In Kapitel fünf gibt es nette kleine Tabellen, die einem dabei helfen, herauszufinden, was angemessen ist.

Ok, wenn ich aus dem Stegreif weiß, dass ein einfaches ArrayList oder HashSet ausreicht, werde ich vielleicht nicht alles nachschlagen.;) aber wenn an meiner beabsichtigten Verwendung irgendetwas auch nur annähernd komplex ist, bin ich sicher, dass ich es weiß.Übrigens dachte ich, dass Vector ein „alter Hut“ sein soll – ich habe ihn seit Jahren nicht mehr verwendet.

Answer 2

Dieser Spickzettel von Sergiy Kovalchuk gefällt mir wirklich gut Blog-Eintrag:

Ausführlicher war das Flussdiagramm von Alexander Zagniotov, aber leider ist es offline.

Answer 3

Ich gehe davon aus, dass Sie den Unterschied zwischen einer Liste, einem Satz und einer Karte aus den obigen Antworten kennen.Warum Sie zwischen ihren Implementierungsklassen wählen würden, ist eine andere Sache.Zum Beispiel:

Aufführen:

1. Anordnungsliste ist schnell beim Abrufen, aber langsam beim Einsetzen.Es ist gut für eine Implementierung, die viel liest, aber nicht viel einfügt/entfernt.Die Daten werden in einem fortlaufenden Speicherblock gespeichert, sodass jedes Mal, wenn eine Erweiterung erforderlich ist, das gesamte Array kopiert wird.
2. LinkedList ist langsam beim Abrufen, aber schnell beim Einfügen.Es ist gut für eine Implementierung, die viel einfügt/entfernt, aber nicht viel liest.Es wird nicht das gesamte Array in einem zusammenhängenden Speicherblock gespeichert.

Satz:

1. HashSet garantiert nicht die Reihenfolge der Iteration und ist daher die schnellste der Mengen.Es verursacht einen hohen Overhead und ist langsamer als ArrayList. Daher sollten Sie es nicht verwenden, außer bei großen Datenmengen, wenn die Hashing-Geschwindigkeit eine Rolle spielt.
2. TreeSet Hält die Daten geordnet und ist daher langsamer als HashSet.

Karte: Die Leistung und das Verhalten von HashMap und TreeMap sind parallel zu den Set-Implementierungen.

Vector und Hashtable sollten nicht verwendet werden.Es handelt sich um synchronisierte Implementierungen vor der Veröffentlichung der neuen Sammlungshierarchie, daher langsam.Wenn eine Synchronisierung erforderlich ist, verwenden Sie Collections.synchronizedCollection().

Answer 4

Theoretisch gibt es nützliche Big-Oh Kompromisse, aber in der Praxis spielen diese fast keine Rolle.

In realen Benchmarks ArrayList übertrifft LinkedList Auch bei großen Listen und bei Operationen wie "viele Einschübe in der Nähe der Front". Akademiker ignorieren die Tatsache, dass reale Algorithmen konstante Faktoren haben, die die asymptotische Kurve überwältigen können.Beispielsweise erfordern verknüpfte Listen eine zusätzliche Objektzuweisung für jeden Knoten, was eine langsamere Erstellung eines Knotens und erheblich schlechtere Speicherzugriffseigenschaften bedeutet.

Meine Regel ist:

1. Beginnen Sie immer mit ArrayList und HashSet und HashMap (d. h.nicht LinkedList oder TreeMap).
2. Typdeklarationen sollten immer eine Schnittstelle sein (d. h.Wenn ein Profiler oder eine Codeüberprüfung das Gegenteil beweist, können Sie die Implementierung ändern, ohne dass etwas kaputt geht.

Answer 5

Zu deiner ersten Frage...

List, Map und Set dienen unterschiedlichen Zwecken.Ich schlage vor, mehr über das Java Collections Framework zu lesen unter http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html.

Um es etwas konkreter zu sagen:

• Verwenden Sie List, wenn Sie eine Array-ähnliche Datenstruktur benötigen und über die Elemente iterieren müssen
• Verwenden Sie Map, wenn Sie so etwas wie ein Wörterbuch benötigen
• Verwenden Sie ein Set, wenn Sie nur entscheiden müssen, ob etwas zum Set gehört oder nicht.

Zu deiner zweiten Frage...

Der Hauptunterschied zwischen Vector und ArrayList besteht darin, dass ersteres synchronisiert ist und letzteres nicht synchronisiert ist.Weitere Informationen zur Synchronisierung finden Sie unter Java-Parallelität in der Praxis.

Der Unterschied zwischen Hashtable (beachten Sie, dass das T kein Großbuchstabe ist) und HashMap ist ähnlich: Ersteres ist synchronisiert, letzteres ist nicht synchronisiert.

Ich würde sagen, dass es keine Faustregel für die Bevorzugung der einen oder anderen Implementierung gibt, es hängt wirklich von Ihren Bedürfnissen ab.

Answer 6

Für nicht sortiert ist die beste Wahl in mehr als neun von zehn Fällen:ArrayList, HashMap, HashSet.

Vector und Hashtable sind synchronisiert und daher möglicherweise etwas langsamer.Es kommt selten vor, dass Sie synchronisierte Implementierungen wünschen, und wenn Sie dies tun, sind deren Schnittstellen nicht umfangreich genug, als dass die Synchronisierung nützlich wäre.Im Fall von Map fügt ConcurrentMap zusätzliche Operationen hinzu, um die Schnittstelle nützlich zu machen.ConcurrentHashMap ist eine gute Implementierung von ConcurrentMap.

LinkedList ist fast nie eine gute Idee.Selbst wenn Sie viele Einfügungen und Entfernungen durchführen und einen Index zur Angabe der Position verwenden, müssen Sie die Liste durchlaufen, um den richtigen Knoten zu finden.ArrayList ist fast immer schneller.

Bei Map und Set sind die Hash-Varianten schneller als bei Tree/Sorted.Hash-Algorithmen neigen dazu, eine Leistung von O(1) zu haben, wohingegen Bäume eine Leistung von O(log n) haben.

Answer 7

Listen erlauben doppelte Elemente, während Sets nur eine Instanz zulassen.

Ich verwende eine Karte, wann immer ich eine Suche durchführen muss.

Für die spezifischen Implementierungen gibt es reihenfolgeerhaltende Varianten von Maps und Sets, aber es kommt vor allem auf die Geschwindigkeit an.Ich tendiere dazu, ArrayList für relativ kleine Listen und HashSet für relativ kleine Mengen zu verwenden, aber es gibt viele Implementierungen (einschließlich solcher, die Sie selbst schreiben).HashMap ist für Maps ziemlich verbreitet.Alles, was mehr als „ziemlich klein“ ist, und Sie müssen sich Gedanken über den Speicher machen, damit dieser algorithmisch viel spezifischer ist.

Diese Seite hat viele von animierten Bildern zusammen mit Beispielcode zum Testen von LinkedList vs.ArrayList, wenn Sie an harten Zahlen interessiert sind.

BEARBEITEN: Ich hoffe, die folgenden Links zeigen, dass es sich bei diesen Dingen eigentlich nur um Gegenstände in einem Werkzeugkasten handelt. Sie müssen nur darüber nachdenken, was Ihre Bedürfnisse sind:Siehe Commons-Collections-Versionen von Karte, Aufführen Und Satz.

Answer 8

Wie in anderen Antworten vorgeschlagen, gibt es je nach Anwendungsfall unterschiedliche Szenarien für die Verwendung der richtigen Sammlung.Ich liste einige Punkte auf,

Anordnungsliste:

• In den meisten Fällen müssen Sie lediglich eine Reihe von Dingen speichern oder durchlaufen und diese später durchlaufen.Das Iterieren ist schneller, da es indexbasiert ist.
• Immer wenn Sie eine ArrayList erstellen, wird ihr eine feste Speichermenge zugewiesen, und sobald diese überschritten wird, wird das gesamte Array kopiert

Verlinkte Liste:

• Es verwendet eine doppelt verknüpfte Liste, sodass der Einfüge- und Löschvorgang schnell erfolgt, da nur ein Knoten hinzugefügt oder entfernt wird.
• Das Abrufen ist langsam, da die Knoten durchlaufen werden müssen.

HashSet:

• Andere Ja-Nein-Entscheidungen zu einem Gegenstand treffen, z."Ist der Artikel ein englisches Wort?", "Ist der Artikel in der Datenbank?", "Ist der Artikel in dieser Kategorie?" usw.

• Merken, „welche Elemente Sie bereits bearbeitet haben“, z.B.beim Durchführen eines Webcrawls;

HashMap:

• Wird in Fällen verwendet, in denen Sie sagen müssen: „Was ist für ein gegebenes X das Y?“?Es ist oft nützlich für die Implementierung von In-Memory-Caches oder Indizes, d. h. Schlüssel-Wert-Paaren. Zum Beispiel:Wie lautet für eine bestimmte Benutzer-ID der zwischengespeicherte Name/Benutzerobjekt?
• Verwenden Sie immer HashMap, um eine Suche durchzuführen.

Vector und Hashtable sind synchronisiert und daher etwas langsamer. Wenn eine Synchronisierung erforderlich ist, verwenden Sie Collections.synchronizedCollection().Überprüfen Das für sortierte Sammlungen.Ich hoffe, das hat geholfen.

Answer 9

Ich fand Bruce Eckels Thinking in Java sehr hilfreich.Er vergleicht die verschiedenen Kollektionen sehr gut.Als schnelle Referenz hatte ich immer ein von ihm veröffentlichtes Diagramm, das die Vererbung zeigt, an der Wand meines Würfels hängen.Ich empfehle Ihnen, die Thread-Sicherheit im Auge zu behalten.Leistung bedeutet normalerweise nicht Thread-sicher.

Answer 10

Nun, es kommt darauf an, was Sie brauchen.Die allgemeinen Richtlinien sind:

Aufführen ist eine Sammlung, in der die Daten in der Reihenfolge ihrer Einfügung aufbewahrt werden und jedes Element einen Index erhält.

Satz ist ein Beutel mit Elementen ohne Duplizierung (wenn Sie dasselbe Element erneut einfügen, wird es nicht hinzugefügt).Daten haben keinen Ordnungsbegriff.

Karte Sie greifen auf Ihre Datenelemente zu und schreiben sie über ihren Schlüssel, der jedes mögliche Objekt sein kann.

Namensnennung: https://stackoverflow.com/a/21974362/2811258

Weitere Informationen zu Java-Sammlungen finden Sie unter Schauen Sie sich diesen Artikel an.