Auflistungen und Datenstrukturen

  • Artikel

Ähnliche Daten können häufig effizienter verarbeitet werden, wenn sie als eine Auflistung gespeichert und bearbeitet werden. Verwenden Sie die Klasse System.Array oder die Klassen in den Namespaces System.Collections, System.Collections.Generic, System.Collections.Concurrent, System.Collections.Immutable, um einzelne Elemente oder einen Bereich von Elementen zu einer Sammlung hinzuzufügen, aus dieser zu entfernen und zu ändern.

Es gibt zwei Grundarten von Auflistungen: generische Auflistungen und nicht generische Auflistungen. Generische Auflistungen sind beim Kompilieren typsicher. Aus diesem Grund bieten generische Auflistungen in der Regel eine bessere Leistung. Generische Auflistungen akzeptieren beim Erstellen einen Typparameter und erfordern nicht, dass Sie eine Umwandlung in den und aus dem Object-Typ durchführen, wenn Sie Elemente aus der Auflistung hinzufügen oder entfernen. Darüber hinaus werden die meisten generischen Auflistungen in Windows Store-Apps unterstützt. Nicht generische Auflistungen speichern Elemente als Object, erfordern eine Umwandlung, und die meisten werden für die Windows Store-App-Entwicklung nicht unterstützt. Allerdings finden Sie möglicherweise in älterem Code auch nicht generische Auflistungen.

Ab .NET Framework 4 stellen die Auflistungen im System.Collections.Concurrent-Namespace effiziente threadsichere Vorgänge für den Zugriff auf Auflistungselemente aus mehreren Threads bereit. Die unveränderlichen Sammlungsklassen im Namespace System.Collections.Immutable (NuGet-Paket) sind grundsätzlich threadsicher, da Vorgänge mit einer Kopie der ursprünglichen Sammlung ausgeführt werden und die ursprüngliche Sammlung nicht geändert werden kann.

Allgemeine Auflistungsfunktionen

Alle Sammlungen bieten Methoden zum Hinzufügen, Entfernen oder Suchen von Elementen in der Sammlung. Darüber hinaus teilen sich alle Auflistungen, die die ICollection-Schnittstelle oder die ICollection<T>-Schnittstelle direkt oder indirekt implementieren, diese Funktionen:

Viele Auflistungsklassen enthalten außerdem die folgenden Funktionen:

  • Kapazität und Zähleigenschaften

    Die Kapazität einer Auflistung ist die Anzahl der Elemente, die sie enthalten kann. Die Anzahl einer Auflistung ist die Anzahl der tatsächlich enthaltenen Elemente. Einige Auflistungen blenden die Kapazität oder die Anzahl oder beides aus.

    Die meisten Auflistungen erweitern ihre Kapazität automatisch, wenn die aktuelle Kapazität erreicht ist. Der Speicher wird neu zugewiesen, und die Elemente werden aus der alten Auflistung in die neue kopiert. Dies reduziert den Code, der für die Verwendung der Auflistung erforderlich ist. Die Leistung der Auflistung kann dadurch allerdings beeinträchtigt werden. Beispiel: Für List<T> ist das Hinzufügen eines Elements ein O(1)-Vorgang, wenn Count kleiner als Capacity ist. Wenn die Kapazität für das neue Element erhöht werden muss, ist das Hinzufügen eines Elements ein O(n)-Vorgang, wobei nCount ist. Am besten vermeiden Sie Leistungsverluste aufgrund mehrerer Neuzuweisungen, indem Sie die anfängliche Kapazität als geschätzte Größe der Auflistung festlegen.

    Ein BitArray ist ein Sonderfall; die Kapazität ist identisch mit der Länge, die wiederum mit der Anzahl übereinstimmt.

  • Eine konsistente Untergrenze

    Die untere Grenze einer Auflistung ist der Index des ersten darin enthaltenen Elements. Alle indizierten Auflistungen in den System.Collections-Namespaces haben eine untere Grenze von 0 (Null), d. h. sie sind 0-indiziert. Array hat standardmäßig eine untere Grenze von 0; es kann jedoch eine andere Untergrenze definiert werden, wenn Sie eine Instanz der Array-Klasse mit Array.CreateInstance erstellen.

  • Synchronisierung für den Zugriff von mehreren Threads (nur System.Collections-Klassen).

    Nicht generische Auflistungstypen im System.Collections-Namespace bieten durch die Synchronisierung ein gewisses Maß an Thread-Sicherheit; in der Regel werden sie durch die SyncRoot- und IsSynchronized-Members verfügbar gemacht. Diese Auflistungen sind nicht standardmäßig Thread-sicher. Wenn Sie skalierbaren und effizienten Multithreadzugriff auf eine Auflistung benötigen, verwenden Sie eine der Klassen im System.Collections.Concurrent-Namespace oder ziehen Sie den Einsatz einer unveränderlichen Auflistung in Erwägung. Weitere Informationen finden Sie unter Threadsichere Auflistungen.

Auswählen einer Sammlung

Im Allgemeinen sollten Sie generische Auflistungen verwenden. Die folgende Tabelle beschreibt einige häufig auftretende Auflistungsszenarios sowie die Auflistungsklassen, die Sie für diese Szenarien verwenden können. Wenn Sie sich mit der Arbeit mit generischen Auflistungen noch nicht auskennen, hilft Ihnen diese Tabelle bei der Auswahl der generischen Auflistung, die am besten für Ihre Aufgabe geeignet ist.

Ziel Optionen für generische Auflistungen Optionen für nicht generische Auflistungen Optionen für threadsichere oder unveränderliche Auflistungen
Speichern von Elementen als Schlüssel-Wert-Paare für die schnelle Suche nach Schlüssel Dictionary<TKey,TValue> Hashtable

(Eine Sammlung von Schlüssel-Wert-Paaren, die auf Grundlage des Hashcodes des Schlüssels geordnet sind.)		 ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Zugriff auf die Elemente nach Index List<T> Array

ArrayList		 ImmutableList<T>

ImmutableArray
Verwenden von Elementen nach First-in-First-Out (FIFO)-Prinzip Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Verwenden von Daten nach Last-In-First-Out (LIFO)-Prinzip Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Zugriff auf Elemente in Reihenfolge LinkedList<T> Keine Empfehlung Keine Empfehlung
Empfang von Benachrichtigungen, wenn Elemente der Auflistung hinzugefügt oder aus ihr entfernt werden. (Implementiert INotifyPropertyChanged und INotifyCollectionChanged) ObservableCollection<T> Keine Empfehlung Keine Empfehlung
Sortierte Auflistung SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Ein Satz für mathematische Funktionen HashSet<T>

SortedSet<T>		 Keine Empfehlung ImmutableHashSet<T>

ImmutableSortedSet<T>

Algorithmische Komplexität von Sammlungen

Bei der Auswahl einer Sammlungsklasse ist es sinnvoll, potenzielle Leistungseinbußen zu berücksichtigen. Verwenden Sie die folgende Tabelle als Referenz für den Vergleich zwischen verschiedenen veränderlichen Sammlungstypen und ihren unveränderlichen Gegenstücken in Bezug auf algorithmische Komplexität. Häufig sind unveränderliche Sammlungstypen weniger leistungsfähig, bieten aber aufgrund ihrer Unveränderlichkeit einen Vergleichsvorteil.

Veränderlich Amortisiert Ungünstigster Fall Unveränderlich Komplexität
Stack<T>.Push O(1) O(n) ImmutableStack<T>.Push O(1)
Queue<T>.Enqueue O(1) O(n) ImmutableQueue<T>.Enqueue O(1)
List<T>.Add O(1) O(n) ImmutableList<T>.Add O(log n)
List<T>.Item[Int32] O(1) O(1) ImmutableList<T>.Item[Int32] O(log n)
List<T>.Enumerator O(n) O(n) ImmutableList<T>.Enumerator O(n)
HashSet<T>.Add, lookup O(1) O(n) ImmutableHashSet<T>.Add O(log n)
SortedSet<T>.Add O(log n) O(n) ImmutableSortedSet<T>.Add O(log n)
Dictionary<T>.Add O(1) O(n) ImmutableDictionary<T>.Add O(log n)
Dictionary<T> lookup O(1) O(1) – oder strikt O(n) ImmutableDictionary<T> lookup O(log n)
SortedDictionary<T>.Add O(log n) O(n log n) ImmutableSortedDictionary<T>.Add O(log n)

Eine List<T>-Klasse kann effizient mithilfe einer for-Schleife oder einer foreach-Schleife erstellt werden. Eine ImmutableList<T>-Klasse führt jedoch aufgrund der O(log n)-Zeit für ihren Indexer in einer for-Schleife zu schlechten Ergebnissen. Das Enumerieren einer ImmutableList<T>-Klasse mithilfe einer foreach-Schleife ist effizient, da ImmutableList<T> anstelle eines einfachen Arrays wie List<T> eine binäre Struktur verwendet, um die Daten zu speichern. Ein Array kann sehr schnell indiziert werden, wohingegen eine binäre Struktur durchlaufen werden muss, bis der Knoten mit dem gewünschten Index gefunden wird.

Außerdem ist SortedSet<T> genauso komplex wie ImmutableSortedSet<T>. Das liegt daran, dass beide binäre Strukturen verwenden. Der wesentliche Unterschied besteht darin, dass ImmutableSortedSet<T> eine unveränderliche binäre Struktur verwendet. Da ImmutableSortedSet<T> auch eine System.Collections.Immutable.ImmutableSortedSet<T>.Builder-Klasse bietet, die Mutation zulässt, können Sie sowohl von Unveränderlichkeit als auch von guten Leistungen profitieren.

Titel Beschreibung
Auswählen einer Auflistungsklasse Beschreibt die verschiedenen Auflistungen und hilft Ihnen bei der Auswahl für Ihr Szenario.
Häufig verwendete Auflistungstypen Beschreibt häufig verwendete generische und nicht generische Auflistungstypen, z. B. System.Array, System.Collections.Generic.List<T> und System.Collections.Generic.Dictionary<TKey,TValue>.
Verwenden von generischen Auflistungen Erörtert die Verwendung generischer Auflistungstypen.
Vergleiche und Sortierungen innerhalb von Auflistungen Erläutert die Verwendung von Übereinstimmungs- und Sortiervergleichen in Auflistungen.
Sortierte Auflistungstypen Beschreibt die Leistung und die Merkmale von sortierten Auflistungen.
Hashtable-Auflistungstyp und Dictionary-Auflistungstyp Beschreibt die Funktionen von generischen und nicht generischen hashbasierten Wörterbuchtypen.
Threadsichere Sammlungen Beschreibt Auflistungstypen wie System.Collections.Concurrent.BlockingCollection<T> und System.Collections.Concurrent.ConcurrentBag<T>, die den sicheren und effizienten gleichzeitigen Zugriff von mehreren Threads unterstützen.
System.Collections.Immutable Enthält einführende Informationen zu unveränderlichen Auflistungen und Links zu den Auflistungstypen.

Referenz

System.Array System.Collections System.Collections.Concurrent System.Collections.Generic System.Collections.Specialized System.Linq System.Collections.Immutable