Freigeben über

Sammlungen und Datenstrukturen

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

Es gibt zwei Haupttypen von Sammlungen; generische Auflistungen und nicht generische Auflistungen. Generische Auflistungen sind zur Kompilierungszeit typsicher. Daher bieten generische Sammlungen in der Regel eine bessere Leistung. Generische Auflistungen akzeptieren einen Typparameter, wenn sie erstellt werden. Sie müssen nicht in den Object Typ umwandeln, wenn Sie Elemente aus der Sammlung hinzufügen oder daraus entfernen. Darüber hinaus werden die meisten generischen Sammlungen in Windows Store-Apps unterstützt. Nicht generische Sammlungen speichern Elemente als Object, erfordern Umwandlungen und die meisten werden für die Entwicklung von Windows Store-Apps nicht unterstützt. Möglicherweise werden jedoch nicht generische Auflistungen im älteren Code angezeigt.

In .NET Framework 4 und höheren Versionen bieten die Auflistungen im System.Collections.Concurrent Namespace effiziente threadsichere Vorgänge für den Zugriff auf Sammlungselemente aus mehreren Threads. Die unveränderlichen Auflistungsklassen im System.Collections.Immutable Namespace (NuGet-Paket) sind inhärent threadsicher, da Vorgänge für eine Kopie der ursprünglichen Auflistung ausgeführt werden und die ursprüngliche Auflistung nicht geändert werden kann.

Allgemeine Sammlungsfeatures

Alle Auflistungen stellen Methoden zum Hinzufügen, Entfernen oder Suchen von Elementen in der Auflistung bereit. Darüber hinaus verwenden alle Auflistungen, die die ICollection Schnittstelle oder die ICollection<T> Schnittstelle direkt oder indirekt implementieren, diese Features:

Darüber hinaus enthalten viele Auflistungsklassen die folgenden Features:

  • Eigenschaften "Kapazität" und "Anzahl"

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

    Die meisten Sammlungen erweitern die Kapazität automatisch, wenn die aktuelle Kapazität erreicht ist. Der Speicher wird neu zugeordnet, und die Elemente werden aus der alten Sammlung in die neue kopiert. Dieser Entwurf reduziert den Code, der für die Verwendung der Auflistung erforderlich ist. Die Leistung der Sammlung kann jedoch negativ beeinflusst werden. Wenn beispielsweise List<T>Count kleiner als Capacity, ist das Hinzufügen eines Elements ein O(1)-Vorgang. Wenn die Kapazität erhöht werden muss, um das neue Element aufzunehmen, wird das Hinzufügen eines Elements zu einem O(n)-Vorgang, in dem n sich dies befindet Count. Die beste Methode, um eine schlechte Leistung zu vermeiden, die durch mehrere Reallocations verursacht wird, besteht darin, die anfängliche Kapazität auf die geschätzte Größe der Sammlung festzulegen.

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

  • Eine konsistente untere Grenze

    Die untere Grenze einer Auflistung ist der Index des ersten Elements. Alle indizierten Auflistungen in den System.Collections Namespaces weisen eine Untergrenze von Null auf, was bedeutet, dass sie 0 indiziert sind. Array weist standardmäßig eine untere Grenze von Null auf, aber beim Erstellen einer Instanz der Array-KlasseArray.CreateInstancekann eine andere untere Grenze definiert werden.

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

    Nicht generische Sammlungstypen im Namespace bieten eine gewisse Threadsicherheit mit der Synchronisierung; in der System.Collections Regel über die SyncRoot Elemente verfügbar IsSynchronized gemacht. Diese Auflistungen sind standardmäßig nicht threadsicher. Wenn Sie skalierbaren und effizienten Multithreadzugriff auf eine Auflistung benötigen, verwenden Sie eine der Klassen im System.Collections.Concurrent Namespace, oder erwägen Sie die Verwendung einer unveränderlichen Auflistung. Weitere Informationen finden Sie unter Thread-Safe Sammlungen.

Auswählen einer Sammlung

Im Allgemeinen sollten Sie generische Auflistungen verwenden. In der folgenden Tabelle werden einige allgemeine Sammlungsszenarien und die Auflistungsklassen beschrieben, die Sie für diese Szenarien verwenden können. Wenn Sie mit generischen Sammlungen noch nicht vertraut sind, hilft Ihnen die folgende Tabelle bei der Auswahl der generischen Sammlung, die für Ihre Aufgabe am besten geeignet ist:

Ich möchte... Generische Sammlungsoptionen Nicht generische Sammlungsoptionen Threadsichere oder unveränderliche Sammlungsoptionen
Speichern von Elementen als Schlüssel-Wert-Paare für schnelles Nachschlagen nach Schlüssel Dictionary<TKey,TValue> Hashtable

(Eine Sammlung von Schlüssel-Wert-Paaren, die basierend auf dem Hashcode des Schlüssels organisiert sind.)		 ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

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

ArrayList		 ImmutableList<T>

ImmutableArray
Verwenden von Elementen first-in-first-out (FIFO) Queue<T> Queue ConcurrentQueue<T>

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

ImmutableStack<T>
Sequenziell auf Elemente zugreifen LinkedList<T> Keine Empfehlung Keine Empfehlung
Empfangen von Benachrichtigungen, wenn Elemente entfernt oder der Sammlung hinzugefügt werden. (implementiert INotifyPropertyChanged und INotifyCollectionChanged) ObservableCollection<T> Keine Empfehlung Keine Empfehlung
Eine sortierte Sammlung 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 lohnt es sich, potenzielle Kompromisse bei der Leistung zu berücksichtigen. Verwenden Sie die folgende Tabelle, um zu referenzieren, wie verschiedene änderbare Sammlungstypen in algorithmischer Komplexität mit ihren entsprechenden unveränderlichen Gegenstücken verglichen werden. Häufig sind unveränderliche Sammlungstypen weniger leistungsfähig, bieten aber unveränderliche Möglichkeiten , was häufig ein gültiger Vergleichsvorteil ist.

Veränderlich Amortisiert Schlimmster Fall Unveränderbar Kompliziertheit
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>.Addnachschlagen 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> nachschlagen O(1) O(1) – oder streng O(n) ImmutableDictionary<T> nachschlagen O(log n)
SortedDictionary<T>.Add O(log n) O(n Protokoll n) ImmutableSortedDictionary<T>.Add O(log n)

Eine List<T> kann mithilfe einer for Schleife oder einer foreach Schleife effizient aufgezählt werden. Ein ImmutableList<T>, jedoch einen schlechten Auftrag innerhalb einer for Schleife, aufgrund der O(log n) -Zeit für seinen Indexer. Das Aufzählen einer Verwendung einer ImmutableList<T>foreach Schleife ist effizient, da ImmutableList<T> eine binäre Struktur zum Speichern der Daten anstelle eines Arrays verwendet wird, wie List<T> es verwendet wird. Ein Array kann schnell indiziert werden, während eine binäre Struktur nach unten geführt werden muss, bis der Knoten mit dem gewünschten Index gefunden wird.

Darüber hinaus hat die gleiche Komplexität wie SortedSet<T>ImmutableSortedSet<T> , da beide binäre Strukturen verwenden. Der wesentliche Unterschied besteht darin, dass ImmutableSortedSet<T> eine unveränderliche binäre Struktur verwendet wird. Da ImmutableSortedSet<T> sie auch eine System.Collections.Immutable.ImmutableSortedSet<T>.Builder Klasse bietet, die Mutationen zulässt, können Sie sowohl Unveränderlichkeit als auch Leistung haben.

Titel BESCHREIBUNG
Auswählen einer Sammlungsklasse Beschreibt die verschiedenen Sammlungen und hilft Ihnen bei der Auswahl eines für Ihr Szenario.
Häufig verwendete Sammlungstypen Beschreibt häufig verwendete generische und nicht generische Sammlungstypen, z System.Array. B. , System.Collections.Generic.List<T>und System.Collections.Generic.Dictionary<TKey,TValue>.
Gründe für die Verwendung generischer Sammlungen Erläutert die Verwendung generischer Auflistungstypen.
Vergleiche und Sortierungen innerhalb von Sammlungen Erläutert die Verwendung von Gleichheitsvergleichen und Sortiervergleichen in Auflistungen.
Sortierte Auflistungstypen Beschreibt die Leistung und Merkmale sortierter Auflistungen.
Hashtable- und Dictionary-Sammlungstypen Beschreibt die Features generischer und nicht generischer hashbasierter Wörterbuchtypen.
Thread-Safe Sammlungen Beschreibt Sammlungstypen, z System.Collections.Concurrent.BlockingCollection<T> . B. und System.Collections.Concurrent.ConcurrentBag<T> die den sicheren und effizienten gleichzeitigen Zugriff von mehreren Threads unterstützen.
System.Collections.Immutable Führt die unveränderlichen Auflistungen ein und stellt Links zu den Auflistungstypen bereit.

Referenz