Dictionary und HashSet

Kurz gesagt: Eine Map (Dictionary) speichert Paare aus Schlüssel und Wert mit eindeutigen Schlüsseln und findet einen Wert schnell über seinen Schlüssel, und ein Set speichert eindeutige Werte.

Problem

Wer ist dieser Benutzer?

Die Benutzer der Website stehen in einer Liste. Bei jeder Anmeldung suchst du die E-Mail zum Benutzernamen:

static string FindEmail(List<User> users, string username)
{
    foreach (User u in users)
    {
        if (u.Username == username)
        {
            return u.Email;
        }
    }
    return null;
}

Bei drei Benutzern geht das sofort. Bei 2 000 000 vergleicht jede Anmeldung bis zu 2 000 000 Namen, und es gibt Tausende Anmeldungen pro Minute. Ein Telefonbuch liest du auch nicht ab der ersten Seite. Du schlägst direkt beim Buchstaben auf.

Die Idee

Map: Schlüssel → Wert

Du willst fragen „Welche E-Mail hat weber?“ und sofort die Antwort bekommen. Die Collection dafür heißt Map (auch Wörterbuch oder Dictionary). Sie speichert Paare: einen Schlüssel und einen Wert. In C# heißt sie Dictionary:

Dictionary<string, string> emails = new Dictionary<string, string>();
emails["mueller"] = "mueller@example.com";
emails["mschmidt"] = "mschmidt@example.com";
emails["weber"] = "weber@example.com";

Console.WriteLine(emails["weber"]);
Console.WriteLine(emails.ContainsKey("niemand"));
Console.WriteLine("Benutzer: " + emails.Count);

Ausgabe

weber@example.com
False
Benutzer: 3

• Es gibt zwei Typparameter: einen für den Schlüssel und einen für den Wert. Dictionary<string, string> ist „von Text zu Text“.
• emails[key] = value legt ein Paar hinein, und emails[key] gibt den Wert zurück.
• ContainsKey(key) fragt, ob der Schlüssel darin ist, und Count ist die Anzahl der Paare.
• Dictionary ist in System.Collections.Generic, wie List. Du brauchst kein using: Es ist in jedem neuen Programm schon dabei.

emails[key] für einen Schlüssel, den es nicht gibt, ergibt nicht null, sondern wirft KeyNotFoundException. Wenn du nicht weißt, ob der Schlüssel darin ist, frag mit TryGetValue: Es gibt zurück, ob es den Schlüssel gefunden hat, und liefert den Wert über out. Du kannst ein Dictionary auch auf einmal schreiben, mit Paaren [key] = value:

Dictionary<string, string> emails = new Dictionary<string, string>
{
    ["mueller"] = "mueller@example.com",
    ["mschmidt"] = "mschmidt@example.com",
};
if (emails.TryGetValue("mueller", out string email))
{
    Console.WriteLine(email);
}
try
{
    Console.WriteLine(emails["niemand"]);
}
catch (KeyNotFoundException e)
{
    Console.WriteLine("KeyNotFoundException: " + e.Message);
}

Ausgabe

mueller@example.com
KeyNotFoundException: The given key 'niemand' was not present in the dictionary.

emails[key] durchläuft nicht alle Paare. Es findet den Platz des Schlüssels fast sofort, egal wie viele es sind. Wie das geht, zeigt die nächste Lektion.

Die Idee

Das Lager: ändern und prüfen

Der Bestand im Lager: Artikel → Anzahl.

Dictionary<string, int> stock = new Dictionary<string, int>();
stock["Laptop"] = 4;
stock["Maus"] = 25;
stock["Laptop"] = 3;

Console.WriteLine(stock["Laptop"]);
Console.WriteLine(stock.ContainsKey("Monitor"));
Console.WriteLine(stock.GetValueOrDefault("Monitor", 0));
stock.Remove("Maus");
Console.WriteLine(stock.Count);

Ausgabe

3
False
0
1

• Schlüssel sind eindeutig. Das zweite stock["Laptop"] = 3 fügt keine neue Zeile hinzu. Es ersetzt 4 durch 3.
• ContainsKey fragt, ob der Schlüssel im Dictionary ist.
• GetValueOrDefault(key, 0) gibt den Wert zurück, oder 0, wenn es den Schlüssel nicht gibt. Das schützt dich vor KeyNotFoundException.
• Remove(key) entfernt das Paar.

Genauer, für Neugierige

• Werte dürfen sich wiederholen: Laptop und Maus können beide 3 sein. Schlüssel nicht.
• Es gibt auch ContainsValue. Es durchläuft aber alle Werte, denn ein Dictionary ist nur nach Schlüssel schnell.

• Ein Paar legst du auch mit Add(key, value) hinein. Der Unterschied zeigt sich bei einem Schlüssel, der schon darin ist: [key] = ersetzt den Wert, aber Add wirft ArgumentException und lässt den alten Wert stehen:

Dictionary<string, int> stock = new Dictionary<string, int>();
stock.Add("Laptop", 4);
try
{
    stock.Add("Laptop", 3);
}
catch (ArgumentException e)
{
    Console.WriteLine(e.Message);
}
Console.WriteLine(stock["Laptop"]);

Ausgabe

An item with the same key has already been added. Key: Laptop
4

Probier es aus

Wie viele stehen auf der Karte?

Was gibt das Programm aus?

Dictionary<string, int> menu = new Dictionary<string, int>();
menu["Kaffee"] = 2;
menu["Tee"] = 2;
menu["Kaffee"] = 3;
Console.WriteLine(menu.Count + " " + menu["Kaffee"]);

Antwort

2 3

3 3

2 2

3 2

Prüfen

Die Idee

Durchlaufen und Reihenfolge

Die Lieferkosten nach Stadt. foreach über das Dictionary liefert die Paare: Jedes ist ein KeyValuePair<string, double>, mit Key und Value:

Dictionary<string, double> delivery = new Dictionary<string, double>();
delivery["Berlin"] = 4.5;
delivery["Hamburg"] = 5.2;
delivery["Bremen"] = 6.0;
delivery["Dresden"] = 6.0;
delivery["Leipzig"] = 5.8;

foreach (KeyValuePair<string, double> e in delivery)
{
    Console.WriteLine($"{e.Key}: {e.Value:F2} €");
}

Ausgabe

Berlin: 4.50 €
Hamburg: 5.20 €
Bremen: 6.00 €
Dresden: 6.00 €
Leipzig: 5.80 €

Die Städte kamen in der Reihenfolge heraus, in der sie hinzugefügt wurden. Aber Dictionary verspricht keine Reihenfolge. Solange du nur hinzufügst, behält es meist die Reihenfolge des Hinzufügens. Nach Remove nimmt der neue Schlüssel aber den Platz des entfernten ein. Mit denselben fünf Städten:

delivery.Remove("Hamburg");
delivery["Hannover"] = 5.0;
Console.WriteLine(string.Join(", ", delivery.Keys));

Ausgabe

Berlin, Hannover, Bremen, Dresden, Leipzig

Hannover wurde als Letztes hinzugefügt, kam aber als Zweites heraus. Schreib keinen Code, der sich auf die Reihenfolge eines Dictionary verlässt. Wenn die Reihenfolge wichtig ist, ändere nur die Klasse:

• OrderedDictionary behält die Reihenfolge des Hinzufügens und verspricht sie. Mit denselben Städten, Remove und dem Hinzufügen kommt Hannover ans Ende:

Ausgabe

Berlin, Bremen, Dresden, Leipzig, Hannover

• SortedDictionary sortiert die Schlüssel:

SortedDictionary<string, double> delivery = new SortedDictionary<string, double>();
delivery["Berlin"] = 4.5;
delivery["Hamburg"] = 5.2;
delivery["Bremen"] = 6.0;
delivery["Dresden"] = 6.0;
delivery["Leipzig"] = 5.8;

foreach (KeyValuePair<string, double> e in delivery)
{
    Console.WriteLine($"{e.Key}: {e.Value:F2} €");
}

Ausgabe

Berlin: 4.50 €
Bremen: 6.00 €
Dresden: 6.00 €
Hamburg: 5.20 €
Leipzig: 5.80 €

{e.Value:F2} gibt den Preis mit zwei Stellen nach dem Punkt aus: Sonst kommt 6.0 als 6 heraus.

Genauer, für Neugierige

• Wenn du nur die Schlüssel brauchst, durchlaufe Keys. Wenn du nur die Werte brauchst, durchlaufe Values:

foreach (string city in delivery.Keys)
{
    Console.Write(city + " ");
}
Console.WriteLine();

double sum = 0;
foreach (double price in delivery.Values)
{
    sum += price;
}
Console.WriteLine($"Durchschnitt: {sum / delivery.Count:F2} €");

Ausgabe

Berlin Hamburg Bremen Dresden Leipzig
Durchschnitt: 5.50 €

• SortedDictionary ist langsamer als Dictionary, weil es die Schlüssel sortiert hält. Nimm es, wenn du die Reihenfolge brauchst.
• OrderedDictionary mit Typparametern ist neu: Es gibt es seit .NET 9.

Die Idee

Zählen

Wie oft wurde jeder Artikel bestellt? Der Schlüssel ist der Artikel, der Wert ist die Anzahl. Bei jeder Bestellung nimmst du die alte Anzahl (oder 0) und addierst 1:

string orders = "Kaffee Tee Kaffee Cola Kaffee Tee";
SortedDictionary<string, int> counts = new SortedDictionary<string, int>();
foreach (string item in orders.Split(' '))
{
    counts[item] = counts.GetValueOrDefault(item, 0) + 1;
}
Console.WriteLine(string.Join(", ", counts));

Ausgabe

[Cola, 1], [Kaffee, 3], [Tee, 2]

Das ist die häufigste Verwendung einer Map: Wörter zählen, Stimmen, Fehler nach Art, Verkäufe nach Stadt. Hier ist es ein SortedDictionary, damit die Artikel sortiert herauskommen. string.Join(", ", counts) gibt jedes Paar als [key, value] aus.

string orders = "Kaffee Tee Kaffee Cola Kaffee Tee";
SortedDictionary<string, int> counts = new SortedDictionary<string, int>();
foreach (string item in orders.Split(' '))
{
    counts[item] = counts.GetValueOrDefault(item, 0) + 1;
}
Console.WriteLine(string.Join(", ", counts));

Schritt für Schritt, in Worten

1. 6 Bestellungen und ein leeres SortedDictionary.
2. „Kaffee“ ist noch nicht da: GetValueOrDefault gibt 0, und das Schreiben in counts[item] fügt den Schlüssel mit 1 hinzu.
3. „Tee“ ist noch nicht da: GetValueOrDefault gibt 0, und das Schreiben in counts[item] fügt den Schlüssel mit 1 hinzu.
4. „Kaffee“ ist schon da: GetValueOrDefault gibt 1, und das Schreiben in counts[item] ersetzt den Wert durch 2.
5. „Cola“ ist noch nicht da: GetValueOrDefault gibt 0, und das Schreiben in counts[item] fügt den Schlüssel mit 1 hinzu. SortedDictionary stellt ihn vor „Kaffee“: Die Schlüssel sind sortiert.
6. „Kaffee“ ist schon da: GetValueOrDefault gibt 2, und das Schreiben in counts[item] ersetzt den Wert durch 3.
7. „Tee“ ist schon da: GetValueOrDefault gibt 1, und das Schreiben in counts[item] ersetzt den Wert durch 2.
8. Jeder Artikel ist nur einmal ein Schlüssel, und der Wert sagt, wie oft er bestellt wurde.

Genauer, für Neugierige

• split(" ") aus der Lektion über Strings teilt die Zeile in Wörter.
• Im Modul „Modernes C#“ siehst du LINQ. Dort gibt es fertiges Zählen, CountBy, das die Paare in der Reihenfolge liefert, in der die Artikel zum ersten Mal vorkamen:

string orders = "Kaffee Tee Kaffee Cola Kaffee Tee";
Console.WriteLine(string.Join(", ", orders.Split(' ').CountBy(item => item)));

Ausgabe

[Kaffee, 3], [Tee, 2], [Cola, 1]

Probier es aus

Finde den Fehler

Das Programm soll die Bestellungen zählen. Stattdessen bricht es schon bei der ersten ab:

Fehler

Unhandled exception. System.Collections.Generic.KeyNotFoundException: The given key 'Kaffee' was not present in the dictionary.

In welcher Zeile ist der Fehler?

Wähle die Zeile mit dem Fehler.

1string[] orders = { "Kaffee", "Tee", "Kaffee" };2SortedDictionary<string, int> counts = new SortedDictionary<string, int>();3foreach (string item in orders)4{5 counts[item] = counts[item] + 1;6}7Console.WriteLine(string.Join(", ", counts));

Prüfen

Die Idee

HashSet: jedes nur einmal

Wie viele verschiedene Leute haben sich heute auf der Website angemeldet? Wer sich fünfmal anmeldet, soll nur einmal zählen. Eine Collection, die jeden Wert nur einmal speichert, heißt Set (Menge):

string[] visits = { "anna@example.com", "jonas@example.com", "anna@example.com", "maria@example.com", "jonas@example.com" };
HashSet<string> visitors = new HashSet<string>();
foreach (string email in visits)
{
    visitors.Add(email);
}
Console.WriteLine("Besuche: " + visits.Length);
Console.WriteLine("Verschiedene Besucher: " + visitors.Count);
Console.WriteLine(visitors.Contains("maria@example.com"));

Ausgabe

Besuche: 5
Verschiedene Besucher: 3
True

• Add auf einen Wert, der schon darin ist, macht nichts und gibt False zurück. Ist er neu, gibt es True zurück:

HashSet<string> seen = new HashSet<string>();
Console.WriteLine(seen.Add("F-101"));
Console.WriteLine(seen.Add("F-101"));

Ausgabe

True
False

• Contains ist so schnell wie ContainsKey bei einem Dictionary. Innen ist ein HashSet wie ein Dictionary, in dem du nur die Schlüssel speicherst.
• Es gibt keine Indizes. Ein Set beantwortet nur die Frage „Ist es hier drin?“.

Genauer, für Neugierige

• Die Reihenfolge eines HashSet ist nicht versprochen, genau wie bei Dictionary. SortedSet sortiert. Du kannst ein Set auch auf einmal schreiben, in {} mit Werten:

SortedSet<string> tags = new SortedSet<string> { "java", "sql", "git", "java" };
Console.WriteLine(string.Join(", ", tags));

HashSet<string> backend = new HashSet<string> { "java", "sql", "docker" };
SortedSet<string> common = new SortedSet<string>(tags);
common.IntersectWith(backend);
Console.WriteLine(string.Join(", ", common));
tags.UnionWith(backend);
Console.WriteLine(string.Join(", ", tags));

Ausgabe

git, java, sql
java, sql
docker, git, java, sql

• IntersectWith behält nur die Elemente, die zwei Sets gemeinsam haben, und UnionWith vereinigt sie. Beide ändern das Set, auf dem du sie aufrufst, darum stehen die gemeinsamen in einer Kopie: new SortedSet<string>(tags). Du brauchst sie in der Übung.

Probier es aus

Eine doppelte Rechnung

Die Buchhalterin will die Rechnungsnummern sehen, die zweimal eingegeben wurden. Welche Methode prüft und fügt gleichzeitig hinzu?

string[] invoices = { "F-101", "F-102", "F-101", "F-103" };
HashSet<string> seen = new HashSet<string>();
foreach (string number in invoices)
{
    if (!seen.(number))
    {
        Console.WriteLine("Doppelte Rechnung: " + number);
    }
}

Prüfen

Übung

Maps im Einsatz

Löse die Aufgaben in deinem Editor.

1. Eine Benutzertabelle. Eine Klasse UserTable mit den Methoden Add(string username, string email), Get(string username) und Size(). Innen ist sie ein Dictionary. Für einen Benutzer, den es nicht gibt, gibt Get null zurück: GetValueOrDefault ohne zweites Argument liefert genau das. Füge mueller, mschmidt und weber mit E-Mails der Form mueller@example.com hinzu und suche mschmidt und niemand. In der nächsten Lektion baust du auch deine eigene Hashtabelle, ohne Dictionary.

Ausgabe

mschmidt: mschmidt@example.com
niemand: unbekannter Benutzer
Benutzer: 3

2. Worthäufigkeit. Lies eine Zeile Text ein, schreib sie klein und zähle jedes Wort. Gib die Wörter in alphabetischer Reihenfolge aus.

Eingabe

Kaffee mit Milch und Kaffee ohne Zucker und Kaffee

Ausgabe

kaffee: 3
milch: 1
mit: 1
ohne: 1
und: 2
zucker: 1

3. Dokumente nach Stichwort. Eine Klasse DocumentIndex mit den Methoden AddDocument(int id, params string[] keywords) und Search(string keyword), die eine Liste mit den Nummern der Dokumente mit diesem Wort zurückgibt. Innen ist sie ein Dictionary<string, List<int>>: für jedes Wort eine Liste von Dokumenten. Füge Dokument 1 mit „OOP“ und „Java“ hinzu, Dokument 2 mit „SQL“ und „Datenbanken“ und Dokument 3 mit „Java“ und „Collections“. Suche nach „Java“, „SQL“ und „Python“ und gib die Nummern in [] aus, durch Kommas getrennt.

Ausgabe

Java: [1, 3]
SQL: [2]
Python: []

4. Ein Kontaktnetz. Eine Klasse Contact mit Name und E-Mail und eine Klasse ContactNetwork mit den Methoden AddContact(string name, string email), AddConnection(string a, string b) (die Verbindung gilt in beide Richtungen), FriendsOf(string name), Common(string a, string b) (gemeinsame Freunde) und EmailOf(string name). Speichere die Kontakte in einem Dictionary<string, Contact> und die Verbindungen in einem Dictionary<string, SortedSet<string>>, damit die Namen sortiert herauskommen. Verbinde Jonas mit Maria und Jonas mit Peter.

Ausgabe

Jonas: [Maria, Peter]
Maria: [Jonas]
Gemeinsame Freunde von Maria und Peter: [Jonas]
E-Mail von Peter: peter@example.com

Weitere Aufgaben

• Eine eindeutige ID. Eine Methode GenerateUserId(string email) gibt jeder neuen E-Mail eine Nummer, U001, U002 und so weiter, und für eine schon gesehene E-Mail gibt sie dieselbe Nummer zurück. Groß- und Kleinbuchstaben in der E-Mail gelten als gleich. Eine Variante mit einer Hashfunktion gibt es in der nächsten Lektion.
• Ein Buchkatalog. Der Schlüssel ist die ISBN, zum Beispiel 978-3-16-148410-0, und der Wert ist der Titel. Füge Bücher hinzu, suche eines und gib alle aus, sortiert nach ISBN.
• Ein Reiseplaner. Speichere für jedes Reiseziel eine Liste von Aktivitäten: „Paris“ → „der Eiffelturm“, „der Louvre“. Gib den Plan in der Reihenfolge aus, in der die Reiseziele hinzugefügt wurden. Welches Dictionary wählst du?
• Ein Online-Wörterbuch. Wort → Erklärung. Lies Wörter ein, bis „ende“ kommt. Für ein unbekanntes Wort gib „Dieses Wort gibt es nicht.“ aus.
• Noten nach Fach. Lies Zeilen wie „Mathe 6“, „Physik 5“, „Mathe 4“ ein und gib die Durchschnittsnote für jedes Fach aus, sortiert nach Namen.

Test

Teste dich

1. Wann ist ein Dictionary besser als eine Liste?

Wenn du die Elemente nach Index brauchstWenn du nach Schlüssel suchst, zum Beispiel die E-Mail zum BenutzernamenWenn du wiederholte Werte hintereinander brauchst

2. In menu gibt es schon den Schlüssel "Kaffee" mit dem Wert 2. Was macht menu["Kaffee"] = 3?

Ersetzt den Wert durch 3; der Schlüssel bleibt einerWirft eine ExceptionFügt einen zweiten Schlüssel "Kaffee" hinzu

3. Den Schlüssel "Tee" gibt es in menu nicht. Was macht menu["Tee"]?

Wirft KeyNotFoundExceptionGibt null zurückGibt 0 zurück

4. Du durchläufst ein Dictionary. In welcher Reihenfolge kommen die Schlüssel heraus?

AlphabetischImmer in der Reihenfolge des HinzufügensIn einer Reihenfolge, die Dictionary nicht verspricht

5. Was gibt Add auf einem HashSet zurück, wenn der Wert schon darin ist?

True, und es fügt ihn ein zweites Mal hinzuEs wirft eine ExceptionFalse, und das Set ändert sich nicht

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Polymorphie · Interfaces · Exceptions · Listen
• Geht weiter in: Hashcodes und Hashfunktionen · Klassen in Klassen · Lambdas und Delegates · LINQ
• Aufgaben zum Thema: Collections