10. June 2018

LINQ: .NET Collection-Klassen

Guten Morgen,

Various collectionsLINQ ist eine der interessantes Funktionen von C#. Immer, wenn man mit Daten in Listen arbeitet (was meistens der Fall ist), werden Methoden gebraucht, diese Daten zu filtern und zu manipulieren. LINQ ermöglicht a) einfachen und konsistenten Zugriff auf Listen, und b) einen Funktionalen Ansatz, mit Listen zu Arbeiten.

Dieser Artikel ist der Erste in einer Reihe von Artikeln zu LINQ. In dieser Reihe werden wir

  • uns die Collection-Klassen von .NET anschauen
  • über Lambda-Expressions, Closures, Action<> und Func<> lernen
  • uns die Macht von Extension-Methods zu Nutze machen
  • das IEnumerable<>-Interface verwenden
  • in die diversen Methoden von LINQ eintauchen
  • und uns an PLINQ (parallel LINQ) versuchen.

Also, fangen wir direkt an, die mit den verschiedenen Collection-Klassen, die in .NET Framework1 zur Verfügung stehen. Da die meisten Business-Anwendungen rein datengetrieben sind (an wie vielen richtigen Programmen ohne Datenbank haben Sie bisher gearbeitet?), ist Wissen über die Collection-Klassen einer Sprache meiner Meinung nach ähnlich grundlegend, wie Wissen über die Basis-Datentypen der jeweiligen Sprache.

Die wichtigsten Collections in .NET finden sich im Namespace System.Collections.Generic. Ihre nicht-generischen Equivalente aus dem Namespace System.Collections sollten nicht verwendet werden. Sie existieren nur noch für Abwärtskompatibilität. Concurrent Collections (concurrent = nebenläufig; in diesem Zusammenhang: multithreading-fähig) können im Namespace System.Collections.Concurrent gefunden werden.

Array / List<T>

Ein Array (bzw. eine List<T>, die im Grunde nur ein Wrapper um Array ist), ist in C# ziemlich genau das, was man von einem Array in jeder anderen Sprache erwarten würde: Eine Sammlung von Elementen, die einen zusammenhängenden Block im RAM belegt. Zugriff mittels Index ist daher sehr schnell. Einträge anhand ihrer Attribute zu suchen, erfordert aber einen vollständigen Scan des Arrays.

Einem Array Einträge hinzu zu fügen, ist normalerweise günstig, da C# das RAM in Blöcken reserviert. Nur Einfügen und Löschen von Elementen in der Mitte des Arrays ist etwas teurer, weil alle nachfolgenden Einträge verschoben werden müssen. Ist das Ihr Anwendungsfall, sollten Sie sich die LinkedList<T> anschauen (siehe unten).

HashSet<T>

Wie der Name vermuten lässt, speichert das HashSet<T> einen Hash für jeden Eintrag in der Collection. Im Gegensatz zu einem Array, garantiert das HashSet<T> aber nicht, dass die Reihenfolge der Einträge erhalten bleibt. Außerdem kann jeder Eintrag nur ein einziges Mal vorkommen, womit das HashSet<T> optimal geeignet ist, wenn jeder Eintrag in der Collection eindeutig sein muss. Ob Einträge gleich sind, wird über die Equals()-Methode der Einträge bestimmt.2

Das HashSet<T> ist fantastisch, wenn ein Eintrag mittels einer Instanz (oder eher: eines "Dings", was als identisch angesehen wird) gefunden werden soll. Ein gutes Beispiel ist eine Zufällige Liste von Zeichenfolgen. Da identische (in Hinsicht auf ihren Inhalt) Zeichenfolgen als gleich angesehen werden, ist die Konvertierung einer List<string> in ein HashSet<string> eine simple Variante, jeden String in der Collection eindeutig zu machen.

var list = new List<string> {
    "One", "Two", "Three", "Two", "Three"
};
var set = new HashSet<string>(list); // Output: "One", "Two", "Three"

Dictionary<T, U>

Das Dictionary<T, U> ist eine Key-Value-Collection. Jeder Schlüssel (vom Typ T) ist einem Eintrag (vom Typ U) zugeordnet. Zugriff über den Schlüssel ist sehr effizient, was das Dictionary<T, U> exzellent macht, um Einträge über ein Attribut (wie den Primärschlüssel) zu finden.

Die Schlüssel eines Dictionary<T, U> müssen eindeutig sein. Im Gegensatz zu dem HashSet<T>, was doppelte Einträge einfach ignoriert, wirft ein Dictionary<T, U> eine Exception, wenn ein Schlüssel zwei Mal hinzugefügt wird. Analog zu dem HashSet<T> wird die Gleichheit von Schlüsseln über die Equals()-Methode geprüft.

Wann immer man mehrfach über eine Liste iteriert, um einen einzelnen Eintrag über ein bestimmtes Feld zu finden (bspw. eine Person in einer List<Person> über ihren Namen), sollte man sich überlegen, ein Dictionary<T, U> zu verwenden. Selbst bei ein paar Iterationen kann es sich lohnen, temporär ein Dictionary<T, U> zu erstellen. LINQs ToDictionary()-Method hilft hier weiter.3

ConcurrentDictionary<T, U>

Alle Concurrent-Collections erlauben paralleles Lesen und Schreiben von mehreren Threads. Da sie üblicherweise eine Kopie der Collection auf jedem Thread halten müssen, und die Kopien synchronisiert werden müssen, ist es nicht ratsam Concurrent Collections in einem nicht-parallelen Anwendungsfall zu benutzen. Sie sind aber mächtige Werkzeuge in hochgradig parallelen Szenarien.

Die nützlichste Concurrent-Collection ist das ConcurrentDictionary<T, U>. Es stellt eine thread-sichere Implementierung des Dictionary<T, U> dar und ist besonders hilfreich bei der Zwischenspeicherung von Daten oder bei Multi-Threading-fähigen Service-Implementierungen.

Auch wenn alle Concurrent-Collections grundlegend thread-safe sind, ist nicht sichergestellt, dass alle Operationen auf diese Collections ebenfalls thread-sicher sind. Die Dokumentation schließt Thread-Sicherheit sogar aus für explizite Interface-Implementierungen, Extension-Methods (muss jemand an LINQ denken?) und Methoden, die Delegaten als Parameter annehmen.4 Bitte prüfen Sie immer die Dokumentation der jeweiligen Methode, insbesondere wenn Sie LINQ auf eine Concurrent-Collection anwenden.

Andere nützliche Collections

Natürlich gibt es noch eine Reihe hilfreicher, aber speziellerer Collections:

  • Stack<T>: Eine "first in last out" (FILO) Collection
  • Queue<T>: Eine "first in first out" (FIFO) Collection
  • LinkedList<T>: Eine typische "Linked List". Nützlich, wenn man häufig Einträge in der Mitte einer größeren Collection hinzufügen oder entfernen möchte.
  • SortedList<T>, SortedSet<T>, SortedDictionary<T>: Varianten von List<T>, HashSet<T> und Dictionary<T, U>, die die beinhalteten Einträge sortieren.5
  • Die anderen Collections im Namespace System.Collections.Concurrent: ConcurrentStack<T> und ConcurrentQueue<T> sind nebenläufige Implementierungen von Stack<T> und Queue<T>. ConcurrentBag<T> ist etwas speziell, da es tatsächlich einen Sack von Einträgen darstellt: Einträge sind unsortiert und können weder mittels Index noch per Instanz abgefragt werden. Man stopft Sachen hinein und iteriert über Alles, wenn man einen Eintrag herausholen will (bin ich der Einzige, der an seine Schubladen denken muss?).
  • Die verschiedenen Collections aus dem Namespace System.Collections.ObjectModel: Sie werden üblicherweise für UI-Entwicklung verwendet. Besonders die ObservableCollection<T>, die INotifyCollectionChanged implementiert und häufig für DataBindings in WPF genutzt wird.
  • Die brandneuen ImmutableCollections aus dem NuGet-Package System.Collections.Immutable:6 Die Idea ist einfach: Collections, die nicht verändert werden können, können problemlos von mehreren Threads gelesen werden. Es stehen Implementierungen für alle üblichen Collektions zur Verfügung, ImmutableList<T>, ImmutableDictionary<T, U>, ImmutableQueue<T>, usw. Obwohl diese Collections nicht direkt Teil von .NET sind, wollte ich sie erwähnt haben, weil sie eine weitere Möglichkeit schaffen, Collections von mehreren Threads aus zu verwenden.7