Dictionary w C#: Add, TryGetValue, iteracja i sortowanie słownika

Dictionary<TKey, TValue> przechowuje wartości pod unikalnymi kluczami i znajduje wartość po kluczu w przybliżeniu w stałym czasie, niezależnie od liczby wpisów. To odpowiednik mapy haszującej w C#: książka telefoniczna od imienia do numeru, pamięć podręczna od identyfikatora do rekordu, licznik dla każdego słowa.

Tworzenie słownika i odczyt wartości

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var stock = new Dictionary<string, int>();
        stock["apples"] = 12;
        stock["pears"] = 0;

        var prices = new Dictionary<string, decimal>
        {
            ["coffee"] = 3.20m,
            ["tea"] = 2.50m,
        };

        var capitals = new Dictionary<string, string>
        {
            { "France", "Paris" },
            { "Peru", "Lima" },
        };

        Console.WriteLine(stock["apples"]);
        Console.WriteLine(prices["tea"]);
        Console.WriteLine(capitals.Count);
        Console.WriteLine(capitals.ContainsKey("Peru"));
        Console.WriteLine(capitals.ContainsValue("Rome"));
    }
}

Wynik:

12
2.50
2
True
False

Obie formy inicjalizatora robią to samo. Forma ["key"] = value (C# 6) używa indeksera, więc powtórzony klucz nadpisuje wartość; forma { key, value } wywołuje Add, więc powtórzony klucz rzuca wyjątek w chwili wykonania tej linii.

ContainsKey to wyszukiwanie po haszu i jest szybkie. ContainsValue musi przejrzeć każdy wpis, bo wartości nie są indeksowane.

Add, indekser i TryAdd

Wpis można wstawić na trzy sposoby, a różnią się tylko tym, co się dzieje, gdy klucz już istnieje:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var ages = new Dictionary<string, int>();

        ages.Add("Ana", 31);
        ages["Ben"] = 25;     // new key: inserted
        ages["Ben"] = 26;     // existing key: overwritten
        Console.WriteLine(ages["Ben"]);

        try
        {
            ages.Add("Ana", 40); // duplicate key
        }
        catch (ArgumentException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        Console.WriteLine(ages.TryAdd("Chloe", 22)); // new: added
        Console.WriteLine(ages.TryAdd("Ana", 99));   // exists: not added
        Console.WriteLine(ages["Ana"]);
    }
}

Wynik:

26
Caught ArgumentException
True
False
31

To, że Add rzuca wyjątek przy duplikacie, jest zaletą: ujawnia dane, które powinny być unikalne, a nie były. Używaj indeksera, gdy chodzi ci o "wstaw lub zaktualizuj", a TryAdd (.NET Core 2.0 i nowsze), gdy wygrać ma pierwsza wartość.

Klucze nie mogą być null. Add(null, ...) lub dict[null] rzuca ArgumentNullException. Wartości mogą być null, jeśli pozwala na to ich typ.

KeyNotFoundException i TryGetValue

Odczyt nieistniejącego klucza przez indekser rzuca KeyNotFoundException. To najczęstszy błąd przy słownikach, a rozwiązaniem prawie zawsze jest TryGetValue.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var emails = new Dictionary<int, string>
        {
            [101] = "ana@example.com",
            [102] = "ben@example.com",
        };

        try
        {
            Console.WriteLine(emails[999]);
        }
        catch (KeyNotFoundException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        if (emails.TryGetValue(101, out string email))
        {
            Console.WriteLine("Found " + email);
        }

        if (!emails.TryGetValue(999, out string none))
        {
            Console.WriteLine("Missing, value is null: " + (none == null));
        }

        string fallback = emails.TryGetValue(103, out var e3) ? e3 : "no email";
        Console.WriteLine(fallback);
    }
}

Wynik:

Caught KeyNotFoundException
Found ana@example.com
Missing, value is null: True
no email

TryGetValue wykonuje jedno wyszukiwanie po haszu i zgłasza powodzenie jako bool. Wzorzec if (dict.ContainsKey(k)) { var v = dict[k]; } działa, ale szuka klucza dwa razy. Gdy klucza brakuje, zmienna out dostaje wartość domyślną typu (null, 0, false).

W .NET Core 2.0 i nowszych jest też GetValueOrDefault(key, fallback), które zwraca wartość zastępczą, gdy klucza brakuje: emails.GetValueOrDefault(103, "no email").

Aktualizowanie i usuwanie wpisów

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var cart = new Dictionary<string, int> { ["milk"] = 1, ["eggs"] = 6 };

        cart["milk"] += 1;                     // read, add, write back
        Console.WriteLine(cart["milk"]);

        Console.WriteLine(cart.Remove("eggs")); // true: removed
        Console.WriteLine(cart.Remove("rice")); // false: was not there
        Console.WriteLine(cart.Count);

        cart.Clear();
        Console.WriteLine(cart.Count);
    }
}

Wynik:

2
True
False
1
0

cart["milk"] += 1 rzuca KeyNotFoundException, jeśli milk jeszcze nie ma w słowniku, bo najpierw odczytuje, a potem zapisuje. Remove przy brakującym kluczu zwraca false zamiast rzucać wyjątek, więc nie trzeba wcześniej sprawdzać ContainsKey.

Iteracja: KeyValuePair, Keys i Values

foreach po słowniku daje elementy KeyValuePair<TKey, TValue>, każdy z Key i Value.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var scores = new Dictionary<string, int>
        {
            ["Ana"] = 88,
            ["Ben"] = 72,
            ["Chloe"] = 95,
        };

        foreach (KeyValuePair<string, int> pair in scores)
        {
            Console.WriteLine(pair.Key + ": " + pair.Value);
        }

        foreach (string name in scores.Keys)
        {
            Console.Write(name + " ");
        }
        Console.WriteLine();

        int total = 0;
        foreach (int s in scores.Values) total += s;
        Console.WriteLine("Total " + total);

        // Change values: loop over a copy of the keys.
        foreach (string name in new List<string>(scores.Keys))
        {
            scores[name] += 5;
        }
        Console.WriteLine(scores["Ben"]);
    }
}

Wynik:

Ana: 88
Ben: 72
Chloe: 95
Ana Ben Chloe 
Total 255
77

pair.Value jest tylko do odczytu, więc aktualizacja wartości oznacza zapis przez indekser. Ostatnia pętla iteruje po kopii kluczy typu List<string>, co jest zawsze bezpieczne; bezpośrednia iteracja po scores.Keys z nadpisywaniem istniejących wartości jest dozwolona w .NET Core 3.0 i nowszych, ale w .NET Framework rzuca InvalidOperationException.

Dodanie nowego klucza wewnątrz foreach po tym samym słowniku rzuca InvalidOperationException w każdej wersji. Usuwanie w trakcie wyliczania rzuca wyjątek w .NET Framework, a od .NET Core 3.0 jest dozwolone. Kod, który musi działać wszędzie, najpierw zbiera klucze do usunięcia, a usuwa je dopiero po pętli.

W C# 7 i .NET Core 2.0 lub nowszym KeyValuePair można zdekonstruować w nagłówku pętli:

foreach (var (name, score) in scores)
{
    Console.WriteLine($"{name}: {score}");
}

Liczenie za pomocą słownika

Liczenie wystąpień to podręcznikowe zastosowanie. Odczytaj bieżącą liczbę przez TryGetValue (brakujący klucz daje 0), a potem zapisz ją z powrotem.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string text = "the cat and the dog and the bird";
        var counts = new Dictionary<string, int>();

        foreach (string word in text.Split(' '))
        {
            counts.TryGetValue(word, out int n); // n is 0 when missing
            counts[word] = n + 1;
        }

        foreach (var pair in counts)
        {
            Console.WriteLine(pair.Key + " " + pair.Value);
        }
    }
}

Wynik:

the 3
cat 1
and 2
dog 1
bird 1

Ten sam układ służy do grupowania: Dictionary<string, List<Order>>, gdzie pobierasz listę przez TryGetValue, tworzysz i zapisujesz nową, jeśli jej brakuje, a potem wykonujesz na niej Add. Przy jednorazowym liczeniu i grupowaniu LINQ robi to w jednym wyrażeniu: words.GroupBy(w => w).ToDictionary(g => g.Key, g => g.Count()). Zobacz LINQ.

Klucze bez rozróżniania wielkości liter

Klucze typu string domyślnie porównują się dokładnie: "Apple" i "apple" to dwa klucze. Żeby to zmienić, przekaż do konstruktora IEqualityComparer<string>.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var exact = new Dictionary<string, int>();
        exact["Apple"] = 1;
        Console.WriteLine(exact.ContainsKey("apple"));

        var headers = new Dictionary<string, string>(StringComparer.OrdinalIgnoreCase);
        headers["Content-Type"] = "text/html";
        Console.WriteLine(headers["content-type"]);
        headers["CONTENT-TYPE"] = "application/json"; // same key: overwrites
        Console.WriteLine(headers.Count);
    }
}

Wynik:

False
text/html
1

StringComparer.OrdinalIgnoreCase to właściwy wybór dla identyfikatorów, takich jak nagłówki HTTP, rozszerzenia plików i nazwy użytkowników. Wywoływanie .ToLower() na każdym kluczu przed zapisaniem też działa, ale łatwo o tym zapomnieć w jednym miejscu.

Dla kluczy będących obiektami twojej klasy słownik wywołuje GetHashCode i Equals klucza. Klasa, która ich nie nadpisuje, porównuje się po referencji, więc dwa osobne obiekty z tymi samymi polami to różne klucze. Jak napisać tę parę metod, pokazuje strona o HashSet.

Kolejność, sortowanie i SortedDictionary

Dictionary nie obiecuje żadnej kolejności wyliczania. W praktyce słownik, do którego tylko dodawano wpisy, wylicza je w kolejności dodania, ale po Remove późniejsze Add może użyć zwolnionego miejsca i pojawić się wcześniej. Kod nigdy nie powinien na tym polegać.

Gdy potrzebujesz kolejności, sortuj w miejscu użycia albo użyj posortowanej kolekcji:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var sales = new Dictionary<string, int>
        {
            ["Lima"] = 340,
            ["Oslo"] = 520,
            ["Cairo"] = 210,
        };

        foreach (var pair in sales.OrderBy(p => p.Key))
            Console.WriteLine(pair.Key + " " + pair.Value);

        Console.WriteLine("By value, highest first:");
        foreach (var pair in sales.OrderByDescending(p => p.Value))
            Console.WriteLine(pair.Key + " " + pair.Value);

        var sorted = new SortedDictionary<string, int>(sales);
        sorted["Berlin"] = 90;
        Console.WriteLine(string.Join(", ", sorted.Keys));
    }
}

Wynik:

Cairo 210
Lima 340
Oslo 520
By value, highest first:
Oslo 520
Lima 340
Cairo 210
Berlin, Cairo, Lima, Oslo

SortedDictionary<TKey, TValue> cały czas utrzymuje posortowane klucze (to zrównoważone drzewo), więc wyszukiwanie i wstawianie mają złożoność O(log n) zamiast O(1). Używaj go, gdy często wyliczasz wpisy w kolejności kluczy; zwykły słownik sortuj przez LINQ, gdy kolejność potrzebna jest tylko raz. SortedList<TKey, TValue> to trzecia opcja, która zużywa mniej pamięci, ale przy dużym rozmiarze wolno się do niej wstawia.

Ściągawka

Częste błędy

• Odczyt brakującego klucza przez d[k]. Rzuca KeyNotFoundException; użyj TryGetValue.
• Wywołanie Add dla klucza, który może istnieć. Rzuca ArgumentException; użyj indeksera lub TryAdd.
• Dodawanie kluczy wewnątrz foreach po słowniku. Rzuca InvalidOperationException; zbierz zmiany i zastosuj je później.
• Poleganie na kolejności wyliczania. Sortuj albo użyj SortedDictionary.
• Zmiana pól obiektu klucza po jego wstawieniu. Zmienia się jego hash i wpisu nie da się już znaleźć.
• ContainsKey, a potem indekser. Dwa wyszukiwania; TryGetValue robi jedno.