Oft stellt man sich die Frage, welche Datenstruktur nutze ich eigentlich für meinen Algorithmus. Die falsche Entscheidung kann zu erheblichen Performanceeinbußen kommen. Dieser Artikel soll Ihnen die Erkenntnisse liefern, die Sie benötigen, um fundierte Entscheidungen zu treffen.

List

Stellt euch ein Schweizer Taschenmesser vor. Vielseitig, oder? Das ist unsere Liste! Es ist das Werkzeug der Wahl, wenn Du ein bisschen von allem brauchst.

Wofür ist diese gut?

  • Speicherung von Elementen in einer spezifischen Reihenfolgen.
  • Hinzufügen und Löschen von Elementen an einer beliebigen Position.
  • Zugriff auf Elemente über ihren Index.

Hier ein Codebeispiel:

Unter der Haube verwendet List ein dynamisches Array. Er ist wie ein magischer, erweiterbarer Koffer – er wächst, wenn du weitere Gegenstände hinzufügst. Aber hier ist der Clou!

Wenn es wächst, fügt es nicht nur einen weiteren Platz hinzu. Es verdoppelt die Größe!

Das bedeutet, dass das Hinzufügen von Artikeln in der Regel superschnell geht (O(1)), aber manchmal, wenn es wachsen muss, dauert es etwas länger (O(n)). Im Durchschnitt ist es aber immer noch ziemlich spritzig!

Also, wann sollte man List verwenden?
Wenn du die Ordnung aufrechterhalten musst.
Wenn du häufig auf Elemente anhand ihrer Position zugreifen möchtest.
Wenn du es mit einer Sammlung zu tun hast, deren Größe sich häufig ändert.
und:

Wann sollte man es sich zweimal überlegen?
Wenn du ständig nach Elementen anhand ihres Werts (nicht des Index) suchst.
Wenn Du es mit Millionen von Artikeln zu tun hast und blitzschnelle Nachschlagevorgänge benötigst!!

Dictionary

Wenn ein schneller schlüsselbasierter Abruf Priorität hat, erweist sich Dictionary als leistungsstarke Lösung.

Musst du etwas finden? Zapp! du bist sofort da.

Wofür ist es gut?
Blitzschnelle Suche nach Schlüsseln.
Speichern von Schlüssel-Wert-Paaren.
Überprüfen, ob ein Schlüssel vorhanden ist, ohne alles zu durchlaufen.

Code-Beispiel:

Dictionary verwendet eine Hash-Tabelle unter der Haube. Stell dir es sich wie eine superorganisierte Bibliothek vor, in der jedes Buch (Wert) eine eindeutige Signatur (Schlüssel) hat. Der Bibliothekar (Hash-Funktion) kann dir fast sofort genau sagen, wo du das Buch findest!

Ermöglichung der O(1)-Komplexität der durchschnittlichen Fallzeit für schlüsselbasierte Operationen.

Also, wann sollte man das Wörterbuch verwenden?
Wenn Du blitzschnelle Lookups benötigst.
Wenn Du mit Schlüssel-Wert-Paaren arbeiten musst.
Wenn Du schnell nach Existenz suchen musst.

Zweimal überlegen:
Wenn Du eine bestimmte Reihenfolge beibehalten musst (verwendet stattdessen SortedDictionary).
Wenn Du es mit einer kleinen Anzahl von Artikeln zu tun hast(der Aufwand lohnt sich möglicherweise nicht).

HashSet

Stellt euch einen Nachtclub vor, in dem jeder Mensch einzigartig sein muss. Das ist HashSet.

Es ist der Türsteher, der dafür sorgt, dass keine Duplikate eindringen.

Verwendung:

Speichern einer Sammlung einzigartiger Gegenstände.
Superschnelle Überprüfung der Mitgliedschaft.
Festlegen von Operationen wie Vereinigung, Schnittmenge und Differenz.

Code:

HashSet basiert auf dem gleichen Prinzip wie Dictionary, speichert jedoch nur Schlüssel, keine Werte.

Also, Wann sollte man das Hashset verwenden?
Wenn du die Einzigartigkeit sicherstellen musst.
Wenn du schnelle Mitgliedschaftstests benötigst.
Wenn du Set-Vorgänge ausführen möchtest
und, Wann man es sich zweimal überlegen sollte
Wenn du ihren Elementen Werte zuordnen musst(verwenden Sie Dictionary)
Wenn es auf die Reihenfolge ankommt (SortedSet in Betracht ziehen)

Kleine Performance Analyse:

Code:

Ergebnis:

Für Lookup-Operationen zeigen Dictionary und HashSet eine überlegene Leistung bei nahezu konstanter Zeitkomplexität. List weist eine lineare Zeitkomplexität auf, wodurch es für groß angelegte Nachschlagevorgänge weniger geeignet ist.

Bei Einfügeoperationen zeigen alle drei Strukturen eine vergleichbare Leistung für einzelne Einfügungen. Bei List kann es jedoch aufgrund der internen Array-Größenänderung gelegentlich zu Leistungseinbußen kommen.

For Memory Utilization List erweist sich als das speichereffizienteste Element pro Element. Dictionary und HashSet tauschen einen Teil der Speichereffizienz gegen ihre Geschwindigkeitsvorteile bei Nachschlagevorgängen ein.