Dictionary trong C#: Add, TryGetValue, duyệt và sắp xếp

Dictionary<TKey, TValue> lưu giá trị theo các khóa duy nhất và tìm một giá trị theo khóa trong thời gian gần như không đổi, dù có bao nhiêu phần tử đi nữa. Nó là phiên bản C# của hash map: danh bạ từ tên sang số điện thoại, bộ nhớ đệm từ ID sang bản ghi, số lần xuất hiện của mỗi từ.

Tạo dictionary và đọc giá trị

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"));
    }
}

Đầu ra:

12
2.50
2
True
False

Hai dạng khởi tạo làm cùng một việc. Dạng ["key"] = value (C# 6) dùng indexer, nên khóa lặp lại sẽ ghi đè; dạng { key, value } gọi Add, nên khóa lặp lại sẽ ném lỗi khi dòng đó chạy.

ContainsKey là một lần tra cứu hash và rất nhanh. ContainsValue phải quét qua mọi phần tử, vì giá trị không được đánh chỉ mục.

Add, indexer và TryAdd

Có ba cách thêm một phần tử, và chúng chỉ khác nhau ở chuyện xảy ra khi khóa đã tồn tại:

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"]);
    }
}

Đầu ra:

26
Caught ArgumentException
True
False
31

Add ném lỗi khi trùng khóa là một tính năng: nó làm lộ ra dữ liệu lẽ ra phải duy nhất nhưng lại không. Hãy dùng indexer khi bạn muốn "chèn hoặc cập nhật", và TryAdd (.NET Core 2.0 trở lên) khi giá trị đầu tiên phải được giữ lại.

Khóa không thể là null. Add(null, ...) hoặc dict[null] ném ArgumentNullException. Giá trị có thể là null khi kiểu giá trị cho phép.

KeyNotFoundException và TryGetValue

Đọc một khóa không tồn tại bằng indexer sẽ ném KeyNotFoundException. Đây là lỗi dictionary phổ biến nhất, và cách sửa gần như luôn là 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);
    }
}

Đầu ra:

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

TryGetValue tra cứu hash một lần và báo kết quả bằng một bool. Mẫu if (dict.ContainsKey(k)) { var v = dict[k]; } vẫn chạy nhưng tra cứu khóa hai lần. Khi khóa không có, biến out nhận giá trị mặc định của kiểu (null, 0, false).

Từ .NET Core 2.0 trở lên còn có GetValueOrDefault(key, fallback), trả về giá trị dự phòng khi khóa không có: emails.GetValueOrDefault(103, "no email").

Cập nhật và xóa phần tử

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);
    }
}

Đầu ra:

2
True
False
1
0

cart["milk"] += 1 ném KeyNotFoundException nếu milk chưa có trong dictionary, vì nó đọc trước khi ghi. Remove trả về false thay vì ném lỗi khi khóa không có, nên không cần kiểm tra ContainsKey trước.

Duyệt dictionary: KeyValuePair, Keys và Values

Vòng lặp foreach trên dictionary cho ra các phần tử KeyValuePair<TKey, TValue>, mỗi phần tử có Key và 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"]);
    }
}

Đầu ra:

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

pair.Value chỉ đọc, nên muốn cập nhật giá trị thì phải ghi qua indexer. Vòng lặp cuối duyệt một bản sao List<string> của danh sách khóa, cách này luôn an toàn; duyệt trực tiếp scores.Keys trong khi ghi đè giá trị có sẵn được phép từ .NET Core 3.0 trở lên nhưng ném InvalidOperationException trên .NET Framework.

Thêm khóa mới bên trong vòng foreach trên chính dictionary đó ném InvalidOperationException ở mọi phiên bản. Xóa trong lúc duyệt ném lỗi trên .NET Framework và được phép từ .NET Core 3.0. Code phải chạy được ở mọi nơi thì gom các khóa cần xóa trước, rồi xóa chúng sau vòng lặp.

Với C# 7 và .NET Core 2.0 trở lên, KeyValuePair có thể được tách ngay trong phần đầu vòng lặp:

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

Đếm bằng dictionary

Đếm số lần xuất hiện là cách dùng kinh điển. Đọc số đếm hiện tại bằng TryGetValue (khóa không có sẽ cho 0), rồi ghi lại.

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);
        }
    }
}

Đầu ra:

the 3
cat 1
and 2
dog 1
bird 1

Cùng cấu trúc đó dùng để nhóm phần tử: Dictionary<string, List<Order>>, trong đó bạn lấy danh sách bằng TryGetValue, tạo và lưu một danh sách mới nếu chưa có, rồi Add vào đó. Để đếm hay nhóm một lần, LINQ làm được trong một biểu thức: words.GroupBy(w => w).ToDictionary(g => g.Key, g => g.Count()). Xem LINQ.

Khóa không phân biệt chữ hoa chữ thường với comparer

Khóa chuỗi mặc định được so sánh chính xác: "Apple" và "apple" là hai khóa. Truyền một IEqualityComparer<string> cho hàm khởi tạo để thay đổi điều đó.

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);
    }
}

Đầu ra:

False
text/html
1

StringComparer.OrdinalIgnoreCase là lựa chọn đúng cho các định danh như HTTP header, đuôi tệp và tên người dùng. Gọi .ToLower() trên mọi khóa trước khi lưu cũng được, nhưng rất dễ quên ở một chỗ nào đó.

Với khóa là lớp của riêng bạn, dictionary gọi GetHashCode và Equals của khóa. Lớp không ghi đè hai phương thức này sẽ so sánh theo tham chiếu, nên hai đối tượng riêng biệt có cùng các field vẫn là hai khóa khác nhau. Xem HashSet để biết cách viết cặp phương thức đó.

Thứ tự, sắp xếp và SortedDictionary

Dictionary không hứa hẹn gì về thứ tự duyệt. Trong thực tế, một dictionary chỉ toàn được thêm phần tử sẽ duyệt theo thứ tự chèn, nhưng sau một lần Remove, một lần Add sau đó có thể dùng lại chỗ trống và xuất hiện sớm hơn. Code không bao giờ nên dựa vào điều này.

Khi cần thứ tự, hãy sắp xếp ngay tại chỗ dùng hoặc dùng một collection có sắp xếp:

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));
    }
}

Đầu ra:

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

SortedDictionary<TKey, TValue> luôn giữ khóa được sắp xếp (nó là một cây cân bằng), nên tra cứu và chèn tốn O(log n) thay vì O(1). Hãy dùng nó khi bạn thường xuyên duyệt theo thứ tự khóa; còn khi chỉ cần thứ tự một lần thì sắp xếp dictionary thường bằng LINQ. SortedList<TKey, TValue> là lựa chọn thứ ba, tốn ít bộ nhớ hơn nhưng chèn chậm khi kích thước lớn.

Tra cứu nhanh

Lỗi thường gặp

• Đọc khóa không tồn tại bằng d[k]. Ném KeyNotFoundException; hãy dùng TryGetValue.
• Gọi Add cho khóa có thể đã tồn tại. Ném ArgumentException; hãy dùng indexer hoặc TryAdd.
• Thêm khóa bên trong foreach trên dictionary. Ném InvalidOperationException; hãy gom các thay đổi rồi áp dụng sau.
• Dựa vào thứ tự duyệt. Hãy sắp xếp, hoặc dùng SortedDictionary.
• Thay đổi field của đối tượng khóa sau khi đã chèn. Hash code của nó thay đổi và phần tử không còn tìm thấy được nữa.
• ContainsKey rồi mới dùng indexer. Hai lần tra cứu; TryGetValue chỉ cần một.