Auflistungen und Datenstrukturen

Ä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:

• Die Fähigkeit zum Enumerieren der Auflistung

  .NET-Auflistungen implementieren entweder System.Collections.IEnumerable oder System.Collections.Generic.IEnumerable<T>, damit die Auflistung durchlaufen werden kann. Ein Enumerator kann als beweglicher Zeiger auf ein Element in der Auflistung betrachtet werden. Die Anweisungen foreach, in und For Each...Next verwenden den Enumerator, der mit der GetEnumerator-Methode verfügbar gemacht wird, und verbergen die Komplexität der Bearbeitung des Enumerators. Darüber hinaus gilt jede Auflistung, die System.Collections.Generic.IEnumerable<T> implementiert, als abfragbarer Typ und kann mit LINQ abgefragt werden. LINQ-Abfragen bieten ein allgemeines Muster für den Datenzugriff. Sie sind normalerweise präziser und besser lesbar als standardmäßige foreach-Schleifen und bieten Filter-, Sortier- und Gruppierungsfunktionen. LINQ-Abfragen können auch die Leistung verbessern. Weitere Informationen finden Sie unter LINQ to Objects (C#), LINQ to Objects (Visual Basic), Parallel LINQ (PLINQ), Einführung in LINQ-Abfragen (C#) und Basic Query Operations (Visual Basic) (Grundlegende Abfragevorgänge (Visual Basic)).

• Die Möglichkeit, den Inhalt der Auflistung in ein Array zu kopieren

  Alle Auflistungen können mit der CopyTo-Methode in ein Array kopiert werden. Die Reihenfolge der Elemente im neuen Array basiert jedoch auf der Reihenfolge, in der sie vom Enumerator zurückgegeben werden. Das resultierende Array ist stets eindimensional mit einer unteren Grenze von 0 (Null).

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.

Verwandte Themen

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