.NET-Datenstrukturen: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary - Geschwindigkeit, Speicher und wann jeweils verwendet?

213

.NET hat viele komplexe Datenstrukturen. Leider sind einige von ihnen ziemlich ähnlich, und ich bin mir nicht immer sicher, wann ich eines verwenden soll und wann ich ein anderes verwenden soll. Die meisten meiner C # - und Visual Basic-Bücher sprechen bis zu einem gewissen Grad darüber, aber sie gehen nie wirklich ins Detail.

Was ist der Unterschied zwischen Array, ArrayList, List, Hashtable, Dictionary, SortedList und SortedDictionary?

Welche sind aufzählbar (IList - kann 'foreach'-Schleifen ausführen)? Welche verwenden Schlüssel / Wert-Paare (IDict)?

Was ist mit dem Speicherbedarf? Einfügegeschwindigkeit? Abrufgeschwindigkeit?

Gibt es noch andere erwähnenswerte Datenstrukturen?

Ich suche immer noch nach weiteren Details zur Speichernutzung und -geschwindigkeit (Big-O-Notation).

Brezel
quelle
12
Sie sollten diese Frage auseinander brechen. Sie fragen zwanzig verschiedene Dinge, von denen die Hälfte mit einer einfachen Google-Suche beantwortet werden kann. Bitte sei spezifischer; Es ist schwer zu helfen, wenn Ihre Frage so verstreut ist.
33
Ich dachte darüber nach, es aufzubrechen, erkannte aber, dass wahrscheinlich jemand in der Lage sein würde, all diese Antworten an einem Ort zusammenzufassen. Wenn jemand eine Tabelle erstellen kann, in der alles profiliert ist, kann dies zu einer wunderbaren Ressource auf dieser Website werden.
Brezel
9
Kann diese Frage in ein Wiki verwandelt werden?
BozoJoe
1
Dieser MSDN-Artikel behandelt viele dieser Fragen, einschließlich Bäume, Grafiken und Mengen. Eine umfassende Untersuchung der Datenstrukturen
Ryan Fisher
1
Ryan, die Artikel unter diesem Link sind 14 Jahre alt (12 zum Zeitpunkt der Veröffentlichung). Randnotiz Ich habe sie die letzte Woche selbst gelesen. Sie enthalten jedoch auch keine neuere Technologie und müssen dringend aktualisiert werden. Und mehr Leistungsmetriken und Beispiele.
htm11h

Antworten:

156

Aus dem Kopf:

  • Array* - stellt ein Speicherarray der alten Schule dar - ähnlich einem Alias ​​für ein normales type[]Array. Kann aufzählen. Kann nicht automatisch wachsen. Ich würde eine sehr schnelle Einführ- und Wiederholungsgeschwindigkeit annehmen.

  • ArrayList- automatisch wachsendes Array. Fügt mehr Overhead hinzu. Kann aufzählen, wahrscheinlich langsamer als ein normales Array, aber immer noch ziemlich schnell. Diese werden häufig in .NET verwendet

  • List- einer meiner Favoriten - kann mit Generika verwendet werden, sodass Sie ein stark typisiertes Array haben können, z List<string>. Davon abgesehen verhält sich sehr ähnlichArrayList

  • Hashtable- einfache alte Hashtabelle. O (1) bis O (n) schlechtester Fall. Kann die Werte- und Schlüsseleigenschaften auflisten und Schlüssel / Wert-Paare ausführen

  • Dictionary - wie oben nur stark über Generika typisiert, wie z Dictionary<string, string>

  • SortedList- eine sortierte generische Liste. Beim Einfügen verlangsamt, da herausgefunden werden muss, wo die Dinge abgelegt werden sollen. Kann enum., Wahrscheinlich das gleiche beim Abrufen, da es nicht neu greifen muss, aber das Löschen wird langsamer sein als eine einfache alte Liste.

Ich neige dazu, Listund die Dictionaryganze Zeit zu verwenden - sobald Sie anfangen, sie stark mit Generika typisiert zu verwenden, ist es wirklich schwierig, zu den nicht generischen Standard-Generika zurückzukehren.

Es gibt auch viele andere Datenstrukturen - es gibt KeyValuePaireinige, mit denen Sie einige interessante Dinge tun können, und eine, SortedDictionarydie ebenfalls nützlich sein kann.

Sam Schutte
quelle
3
Hash-Tabelle ist O (1), der schlimmste Fall (mit Kollisionen) kann O (n) sein
Justin Bozonier
7
Es gibt viele andere Datenstrukturen, die Sie hier hinzufügen müssen. wie LinkedList, Skip List, Stack, Queue, Heap, Trees, Graphs. Dies sind ebenfalls sehr wichtige Datenstrukturen.
DarthVader
2
ConcurrentDictionary in .Net 4.0 hinzugefügt bietet ein generisches Wörterbuch mit Thread Safety
Harindaka
2
Auch BlockingCollection <T> bietet eine thread-sichere Hersteller / Verbraucher-Implementierung
Harindaka
7
ArrayListverwendet virtuelle Methoden, aber List<T>nicht. ArrayListwurde weitgehend durch List<T>Standardkollektionen und Collection<T>als Basisklasse für benutzerdefinierte Sammlungen ersetzt. Hashtablewurde weitgehend ersetzt durch Dictionary<TKey, TValue>. Ich würde empfehlen, ArrayListund Hashtablefür neuen Code zu vermeiden .
Sam Harwell
29

Verwenden Sie nach Möglichkeit Generika. Das beinhaltet:

  • Liste anstelle von ArrayList
  • Wörterbuch statt HashTable
Adam Tegen
quelle
24

Zunächst implementieren alle Sammlungen in .NET IEnumerable.

Zweitens sind viele der Sammlungen Duplikate, da in Version 2.0 des Frameworks Generika hinzugefügt wurden.

Obwohl die generischen Sammlungen wahrscheinlich Funktionen hinzufügen, zum größten Teil:

  • List ist eine generische Implementierung von ArrayList.
  • Dictionary ist eine generische Implementierung von Hashtable

Arrays sind eine Sammlung mit fester Größe, mit der Sie den an einem bestimmten Index gespeicherten Wert ändern können.

SortedDictionary ist ein IDictionary, das nach den Schlüsseln sortiert ist. SortedList ist ein IDictionary, das nach einem erforderlichen IComparer sortiert ist.

Die IDictionary-Implementierungen (die KeyValuePairs unterstützen) sind also: * Hashtable * Dictionary * SortedList * SortedDictionary

Eine weitere Sammlung, die in .NET 3.5 hinzugefügt wurde, ist das Hashset. Es ist eine Sammlung, die Set-Operationen unterstützt.

Außerdem ist die LinkedList eine Standardimplementierung für verknüpfte Listen (die Liste ist eine Array-Liste zum schnelleren Abrufen).

Abe Heidebrecht
quelle
20

Hier einige allgemeine Tipps für Sie:

  • Sie können foreachfür implementierte Typen verwenden IEnumerable. IListist im Wesentlichen eine IEnumberablewith- Countund Item(Zugriff auf Elemente mithilfe eines auf Null basierenden Index) Eigenschaften. IDictionaryAuf der anderen Seite bedeutet dies, dass Sie über einen beliebigen Hash-Index auf Elemente zugreifen können.

  • Array, ArrayListUnd Listalle implementieren IList. Dictionary,, SortedDictionaryund Hashtableimplementieren IDictionary.

  • Wenn Sie .NET 2.0 oder höher verwenden, wird empfohlen, generische Gegenstücke der genannten Typen zu verwenden.

  • Informationen zur zeitlichen und räumlichen Komplexität verschiedener Vorgänge für diese Typen finden Sie in deren Dokumentation.

  • .NET-Datenstrukturen befinden sich im System.CollectionsNamespace. Es gibt Typbibliotheken wie PowerCollections, die zusätzliche Datenstrukturen bieten.

  • Konsultieren Sie Ressourcen wie CLRS, um ein umfassendes Verständnis der Datenstrukturen zu erhalten .

schwarzer Flügel
quelle
1
von msdn , es scheint wie sortiertListe implementieren IDictionnary - nicht IList
Haim Bendanan
Fest. danke für den Kommentar. Scheint, als würde SortedList eine Liste von Schlüsseln / Werten führen, sodass sie im Grunde genommen die Daten eines Wörterbuchs darstellen. Ich erinnere mich nicht, wie diese Klasse funktioniert hat, als ich die Antwort zum ersten Mal schrieb ...
blackwing
9

.NET-Datenstrukturen:

Mehr zum Gespräch darüber, warum ArrayList und List tatsächlich unterschiedlich sind

Arrays

Wie ein Benutzer angibt, sind Arrays die "Old School" -Sammlung (ja, Arrays werden als Sammlung betrachtet, obwohl sie nicht Teil davon sind System.Collections). Aber was ist "alte Schule" an Arrays im Vergleich zu anderen Sammlungen, dh denen, die Sie in Ihrem Titel aufgeführt haben (hier ArrayList und List (Of T))? Beginnen wir mit den Grundlagen, indem wir uns Arrays ansehen.

Zu Beginn sind Arrays in Microsoft .NET "Mechanismen, mit denen Sie mehrere [logisch verwandte] Elemente als eine einzige Sammlung behandeln können" (siehe verknüpften Artikel). Was bedeutet das? Arrays speichern einzelne Elemente (Elemente) nacheinander im Speicher mit einer Startadresse. Mit dem Array können wir leicht auf die sequentiell gespeicherten Elemente zugreifen, die an dieser Adresse beginnen.

Darüber hinaus können Arrays im Gegensatz zur Programmierung von 101 gängigen Konzepten sehr komplex sein:

Arrays können eindimensional, mehrdimensional oder jaddiert sein (gezackte Arrays sind lesenswert). Arrays selbst sind nicht dynamisch: Nach der Initialisierung reserviert ein Array mit einer Größe von n genügend Speicherplatz für n Objekte. Die Anzahl der Elemente im Array kann nicht wachsen oder schrumpfen. Dim _array As Int32() = New Int32(100)reserviert genügend Speicherplatz auf dem Speicherblock, damit das Array 100 Objekte vom Typ Int32 primitiv enthält (in diesem Fall wird das Array so initialisiert, dass es Nullen enthält). Die Adresse dieses Blocks wird an zurückgegeben _array.

Gemäß dem Artikel erfordert die Common Language Specification (CLS), dass alle Arrays auf Null basieren. Arrays in .NET unterstützen Arrays, die nicht auf Null basieren. Dies ist jedoch weniger häufig. Aufgrund der "Gemeinsamkeit" von Null-basierten Arrays hat Microsoft viel Zeit damit verbracht, ihre Leistung zu optimieren . Daher sind eindimensionale, nullbasierte (SZs) Arrays "speziell" - und wirklich die beste Implementierung eines Arrays (im Gegensatz zu mehrdimensionalen usw.) -, da SZs spezifische Anweisungen für die Zwischensprache haben, um sie zu manipulieren.

Arrays werden immer als Referenz übergeben (als Speicheradresse) - ein wichtiger Teil des Array-Puzzles, den Sie kennen sollten. Während sie die Grenzen überprüfen (wird einen Fehler auslösen), kann die Grenzprüfung auch für Arrays deaktiviert werden.

Das größte Hindernis für Arrays ist wiederum, dass sie nicht in der Größe veränderbar sind. Sie haben eine "feste" Kapazität. Einführung in ArrayList und List (Of T) in unsere Geschichte:

ArrayList - nicht generische Liste

Die ArrayList (zusammen mit List(Of T)- obwohl es hier einige kritische Unterschiede gibt, die später erläutert werden) - wird vielleicht am besten als nächste Ergänzung zu Sammlungen angesehen (im weiteren Sinne). ArrayList erbt von der IList-Schnittstelle (ein Nachkomme von 'ICollection'). ArrayLists selbst sind umfangreicher und erfordern mehr Overhead als Lists.

IListermöglicht es der Implementierung, ArrayLists als Listen mit fester Größe (wie Arrays) zu behandeln; Abgesehen von der zusätzlichen Funktionalität, die durch ArrayLists hinzugefügt wird, bietet die Verwendung von ArrayLists mit fester Größe keine wirklichen Vorteile, da ArrayLists (gegenüber Arrays) in diesem Fall deutlich langsamer sind.

Nach meiner Lektüre können ArrayLists nicht gezackt werden: "Die Verwendung mehrdimensionaler Arrays als Elemente ... wird nicht unterstützt". Wieder ein weiterer Nagel im Sarg von ArrayLists. ArrayLists werden auch nicht "getippt" - was bedeutet, dass eine ArrayList unter allem einfach ein dynamisches Array von Objekten ist : Object[]. Dies erfordert viel Boxen (implizit) und Unboxing (explizit) bei der Implementierung von ArrayLists, was wiederum den Overhead erhöht.

Unbegründeter Gedanke: Ich denke, ich erinnere mich, dass ich von einem meiner Professoren gelesen oder gehört habe, dass ArrayLists eine Art Bastard-Konzeptkind für den Versuch sind, von Arrays zu Sammlungen vom Typ Liste zu wechseln, dh einmal eine große Verbesserung für Arrays gewesen zu sein. Sie sind nicht mehr die beste Option, da die Sammlungen weiterentwickelt wurden

Liste (von T): Was ArrayList wurde (und hoffte zu sein)

Der Unterschied in der Speichernutzung ist signifikant genug, um zu erreichen, dass eine Liste (von Int32) 56% weniger Speicher verbraucht als eine ArrayList, die denselben primitiven Typ enthält (8 MB gegenüber 19 MB in der verknüpften Demonstration des oben genannten Gentlemans: wieder hier verknüpft ) Dies ist ein Ergebnis, das von der 64-Bit-Maschine zusammengesetzt wird. Dieser Unterschied zeigt wirklich zwei Dinge: Erstens (1) ist ein "Objekt" vom Typ Int32 (ArrayList) in einer Box viel größer als ein reiner primitiver Int32-Typ (Liste); Zweitens (2) ist der Unterschied aufgrund des Innenlebens einer 64-Bit-Maschine exponentiell.

Also, was ist der Unterschied und was ist eine Liste (von T) ? MSDN definiert a List(Of T)als "... eine stark typisierte Liste von Objekten, auf die über den Index zugegriffen werden kann." Die Wichtigkeit hierbei ist das "stark typisierte" Bit: Eine Liste (von T) "erkennt" Typen und speichert die Objekte als ihren Typ. Ein Int32wird also als Int32und nicht als ObjectTyp gespeichert . Dies beseitigt die Probleme, die durch das Ein- und Auspacken verursacht werden.

MSDN gibt an, dass dieser Unterschied nur beim Speichern primitiver Typen und nicht von Referenztypen zum Tragen kommt. Auch der Unterschied tritt wirklich im großen Maßstab auf: über 500 Elemente. Interessanter ist, dass die MSDN-Dokumentation lautet: "Es ist zu Ihrem Vorteil, die typspezifische Implementierung der List (Of T) -Klasse anstelle der ArrayList-Klasse zu verwenden."

Im Wesentlichen ist List (Of T) ArrayList, aber besser. Es ist das "generische Äquivalent" von ArrayList. Wie bei ArrayList kann die Sortierung erst nach dem Sortieren garantiert werden (siehe Abbildung). List (Of T) hat auch einige zusätzliche Funktionen.

Thomas
quelle
5

Ich sympathisiere mit der Frage - auch ich fand (finde?) Die Wahl verwirrend, also machte ich mich wissenschaftlich daran, herauszufinden, welche Datenstruktur am schnellsten ist (ich habe den Test mit VB durchgeführt, aber ich stelle mir vor, dass C # gleich wäre, da beide Sprachen gleich sind Machen Sie dasselbe auf CLR-Ebene. Hier können Sie einige von mir durchgeführte Benchmarking-Ergebnisse sehen (es wird auch diskutiert, welcher Datentyp unter welchen Umständen am besten verwendet werden kann).

Andy Brown
quelle
3

Sie sind in Intellisense ziemlich gut geschrieben. Geben Sie einfach System.Collections ein. oder System.Collections.Generics (bevorzugt) und Sie erhalten eine Liste und eine kurze Beschreibung der verfügbaren Funktionen.

Joel Coehoorn
quelle
3

Hashtabellen / Wörterbücher sind O (1) -Leistungen, was bedeutet, dass die Leistung keine Funktion der Größe ist. Das ist wichtig zu wissen.

BEARBEITEN: In der Praxis beträgt die durchschnittliche Zeitkomplexität für Hashtable / Dictionary <> Lookups O (1).

Chris
quelle
5
Es gibt keine "Leistung". Die Komplexität hängt vom Betrieb ab. Wenn Sie beispielsweise n Elemente in Dictionary <> einfügen, ist dies aufgrund des erneuten Aufwärmens nicht O (1).
Ilya Ryzhenkov
2
Zu Ihrer Information, auch beim Aufwärmen ist Dictionary immer noch O (1). Stellen Sie sich das Szenario kurz vor der Erweiterung des Wörterbuchs vor. Die Hälfte der Elemente - die seit der letzten Erweiterung hinzugefügt wurden - wurde einmal gehasht. Die Hälfte des Restes wurde zweimal gehasht. Die Hälfte des Restes davon, dreimal usw. Die durchschnittliche Anzahl von Hashing-Operationen, die an jedem Element ausgeführt werden, beträgt 1 + 1/2 + 1/4 + 1/4 ... = 2. Die Situation unmittelbar nach der Erweiterung ist im Wesentlichen dieselbe, jedoch wurde jedes Element ein weiteres Mal gehasht (die durchschnittliche Anzahl der Hashs beträgt also drei). Alle anderen Szenarien liegen dazwischen.
Supercat
3

Die generischen Sammlungen weisen eine bessere Leistung als ihre nicht generischen Gegenstücke auf, insbesondere wenn viele Elemente durchlaufen werden. Dies liegt daran, dass das Boxen und Entpacken nicht mehr erfolgt.

Russ Cam
quelle
2

Ein wichtiger Hinweis zu Hashtable vs Dictionary für die systematische Hochfrequenz-Handelstechnik: Thread-Sicherheitsproblem

Hashtable ist threadsicher für die Verwendung durch mehrere Threads. Öffentliche statische Dictionary-Mitglieder sind threadsicher, es wird jedoch nicht garantiert, dass Instanzmitglieder dies tun.

Daher bleibt Hashtable in dieser Hinsicht die "Standard" -Wahl.

rauben
quelle
Dies ist teilweise wahr. Das Hashtableist sicher mit nur einem Schreiber und mehreren Lesern gleichzeitig zu verwenden. Auf der anderen Seite ist es sicher, das Dictionarymit mehreren Lesegeräten zu verwenden, solange es nicht gleichzeitig geändert wird.
Bryan Menard
Bestimmt. Im Handelsbereich lesen wir jedoch gleichzeitig aus Live-Marktdaten und führen Analysen durch, die die angehängten Einträge enthalten. Es hängt auch davon ab, wie viele Händler das System nutzen - wenn es nur Sie sind, spielt es offensichtlich keine Rolle.
Rob
1
.NET 4.0 bietet ein ConcurrentDictionary <TKey, TValue>
Rob
1

Es gibt subtile und weniger subtile Unterschiede zwischen generischen und nicht generischen Sammlungen. Sie verwenden lediglich unterschiedliche zugrunde liegende Datenstrukturen. Zum Beispiel garantiert Hashtable One-Writer-Many-Reader ohne Synchronisierung. Wörterbuch nicht.

Ilya Ryzhenkov
quelle
1

Beliebteste C # -Datenstrukturen und -Sammlungen

  • Array
  • Anordnungsliste
  • Aufführen
  • LinkedList
  • Wörterbuch
  • HashSet
  • Stapel
  • Warteschlange
  • SortedList

C # .NET hat viele verschiedene Datenstrukturen, eine der häufigsten ist beispielsweise ein Array. C # enthält jedoch viel mehr grundlegende Datenstrukturen. Die Auswahl der richtigen Datenstruktur ist Teil des Schreibens eines gut strukturierten und effizienten Programms.

In diesem Artikel werde ich auf die integrierten C # -Datenstrukturen eingehen, einschließlich der neuen, die in C # .NET 3.5 eingeführt wurden. Beachten Sie, dass viele dieser Datenstrukturen für andere Programmiersprachen gelten.

Array

Die vielleicht einfachste und gebräuchlichste Datenstruktur ist das Array. Das AC # -Array ist im Grunde eine Liste von Objekten. Seine bestimmenden Merkmale sind, dass alle Objekte (in den meisten Fällen) vom gleichen Typ sind und es eine bestimmte Anzahl von ihnen gibt. Die Art eines Arrays ermöglicht einen sehr schnellen Zugriff auf Elemente basierend auf ihrer Position in der Liste (auch als Index bezeichnet). Das AC # -Array ist wie folgt definiert:

[object type][] myArray = new [object type][number of elements]

Einige Beispiele:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Wie Sie dem obigen Beispiel entnehmen können, kann ein Array ohne Elemente oder aus einer Reihe vorhandener Werte initialisiert werden. Das Einfügen von Werten in ein Array ist einfach, solange sie passen. Die Operation wird kostspielig, wenn mehr Elemente als die Größe des Arrays vorhanden sind. Zu diesem Zeitpunkt muss das Array erweitert werden. Dies dauert länger, da alle vorhandenen Elemente in das neue, größere Array kopiert werden müssen.

Anordnungsliste

Die C # -Datenstruktur ArrayList ist ein dynamisches Array. Das bedeutet, dass eine ArrayList eine beliebige Anzahl von Objekten und einen beliebigen Typ haben kann. Diese Datenstruktur wurde entwickelt, um das Hinzufügen neuer Elemente zu einem Array zu vereinfachen. Unter der Haube ist eine ArrayList ein Array, dessen Größe sich jedes Mal verdoppelt, wenn der Speicherplatz knapp wird. Das Verdoppeln der Größe des internen Arrays ist eine sehr effektive Strategie, die auf lange Sicht das Kopieren von Elementen reduziert. Wir werden hier nicht auf den Beweis eingehen. Die Datenstruktur ist sehr einfach zu bedienen:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

Der Nachteil der ArrayList-Datenstruktur besteht darin, dass die abgerufenen Werte wieder in ihren ursprünglichen Typ umgewandelt werden müssen:

int arrayListValue = (int)myArrayList[0]

Quellen und weitere Informationen finden Sie hier :

leonidaa
quelle