Dictionary ב-C#: הוספה, TryGetValue, מעבר בלולאה ומיון

Dictionary<TKey, TValue> מאחסן ערכים תחת מפתחות ייחודיים ומוצא ערך לפי המפתח שלו בזמן קבוע בקירוב, לא משנה כמה רשומות יש. זו המקבילה של C# ל-hash map: ספר טלפונים משם למספר, מטמון ממזהה לרשומה, ספירה לכל מילה.

יצירת מילון וקריאת ערכים

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

פלט:

12
2.50
2
True
False

שתי צורות האתחול עושות את אותו הדבר. הצורה ["key"] = value (C# 6) משתמשת ב-indexer, כך שמפתח חוזר דורס; הצורה { key, value } קוראת ל-Add, כך שמפתח חוזר זורק כשהשורה רצה.

ContainsKey הוא חיפוש hash והוא מהיר. ContainsValue צריך לסרוק כל רשומה, כי הערכים אינם מאונדקסים.

Add מול ה-indexer מול TryAdd

יש שלוש דרכים להכניס רשומה, והן נבדלות רק במה שקורה כשהמפתח כבר קיים:

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

פלט:

26
Caught ArgumentException
True
False
31

זה ש-Add זורק על כפילות הוא פיצ'ר: הוא חושף נתונים שהיו אמורים להיות ייחודיים ולא היו. השתמשו ב-indexer כש"הכנס או עדכן" זה מה שאתם מתכוונים אליו, וב-TryAdd (.NET Core 2.0 ואילך) כשהערך הראשון צריך לנצח.

מפתחות לא יכולים להיות null. Add(null, ...) או dict[null] זורקים ArgumentNullException. ערכים יכולים להיות null כשטיפוס הערך מאפשר זאת.

KeyNotFoundException ו-TryGetValue

קריאה של מפתח שלא קיים עם ה-indexer זורקת KeyNotFoundException. זו השגיאה הנפוצה ביותר עם מילונים, והפתרון הוא כמעט תמיד 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);
    }
}

פלט:

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

TryGetValue עושה חיפוש hash אחד ומדווחת על הצלחה כ-bool. התבנית if (dict.ContainsKey(k)) { var v = dict[k]; } עובדת, אבל מחפשת את המפתח פעמיים. כשהמפתח חסר, משתנה ה-out מקבל את ערך ברירת המחדל של הטיפוס (null, 0, false).

ב-.NET Core 2.0 ואילך יש גם GetValueOrDefault(key, fallback), שמחזירה את ערך החלופה כשהמפתח חסר: emails.GetValueOrDefault(103, "no email").

עדכון והסרה של רשומות

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

פלט:

2
True
False
1
0

cart["milk"] += 1 זורק KeyNotFoundException אם milk עוד לא במילון, כי הוא קורא לפני שהוא כותב. Remove מחזירה false במקום לזרוק על מפתח חסר, כך שאין צורך לבדוק ContainsKey קודם.

מעבר בלולאה: KeyValuePair, Keys ו-Values

לולאת foreach על מילון מפיקה פריטים מסוג KeyValuePair<TKey, TValue>, לכל אחד Key ו-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"]);
    }
}

פלט:

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

pair.Value הוא לקריאה בלבד, כך שעדכון ערכים פירושו כתיבה דרך ה-indexer. הלולאה האחרונה עוברת על עותק מסוג List<string> של המפתחות, וזה תמיד בטוח; מעבר ישיר על scores.Keys תוך דריסת ערכים קיימים מותר ב-.NET Core 3.0 ואילך, אבל זורק InvalidOperationException ב-.NET Framework.

הוספת מפתח חדש בתוך foreach על אותו מילון זורקת InvalidOperationException בכל גרסה. הסרה בזמן המעבר זורקת ב-.NET Framework ומותרת החל מ-.NET Core 3.0. קוד שחייב לרוץ בכל מקום אוסף קודם את המפתחות להסרה, ואז מסיר אותם אחרי הלולאה.

עם C# 7 ו-.NET Core 2.0 ואילך, אפשר לפרק את KeyValuePair בכותרת הלולאה:

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

ספירה עם מילון

ספירת הופעות היא השימוש הקלאסי. קראו את הספירה הנוכחית עם TryGetValue (מפתח חסר נותן 0), ואז כתבו בחזרה.

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

פלט:

the 3
cat 1
and 2
dog 1
bird 1

אותה צורה מקבצת פריטים: Dictionary<string, List<Order>>, שבו שולפים את הרשימה עם TryGetValue, יוצרים ושומרים אחת אם היא חסרה, ואז עושים לה Add. לספירה ולקיבוץ חד-פעמיים, LINQ עושה את זה בביטוי אחד: words.GroupBy(w => w).ToDictionary(g => g.Key, g => g.Count()). ראו LINQ.

מפתחות שאינם רגישים לאותיות גדולות וקטנות עם comparer

מפתחות מחרוזת מושווים בדיוק כברירת מחדל: "Apple" ו-"apple" הם שני מפתחות. העבירו 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);
    }
}

פלט:

False
text/html
1

StringComparer.OrdinalIgnoreCase היא הבחירה הנכונה למזהים כמו headers של HTTP, סיומות קבצים ושמות משתמש. קריאה ל-.ToLower() על כל מפתח לפני שמאחסנים אותו גם עובדת, אבל קל לשכוח אותה במקום אחד.

למפתחות מהמחלקה שלכם, המילון קורא ל-GetHashCode ול-Equals של המפתח. מחלקה שלא דורסת אותן משווה לפי הפניה, כך ששני אובייקטים נפרדים עם אותם שדות הם מפתחות שונים. ראו HashSet כדי ללמוד איך כותבים את הזוג הזה.

סדר, מיון ו-SortedDictionary

Dictionary לא מבטיח שום דבר לגבי סדר המעבר. בפועל מילון שרק הוסיפו לו רשומות מחזיר אותן בסדר ההכנסה, אבל אחרי Remove, Add מאוחר יותר יכול להשתמש שוב במקום שהתפנה ולהופיע מוקדם יותר. קוד אף פעם לא צריך להסתמך על זה.

כשצריך סדר, מיינו בנקודת השימוש או השתמשו באוסף ממוין:

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

פלט:

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

SortedDictionary<TKey, TValue> שומר את המפתחות שלו ממוינים כל הזמן (הוא עץ מאוזן), כך שחיפושים והכנסות הם O(log n) במקום O(1). השתמשו בו כשאתם עוברים לעיתים קרובות לפי סדר המפתחות; מיינו מילון רגיל עם LINQ כשצריך סדר רק פעם אחת. SortedList<TKey, TValue> היא אפשרות שלישית שמשתמשת בפחות זיכרון, אבל ההכנסה אליה איטית כשהיא גדולה.

עזר מהיר

טעויות נפוצות

• קריאה של מפתח חסר עם d[k]. זורק KeyNotFoundException; השתמשו ב-TryGetValue.
• קריאה ל-Add עבור מפתח שאולי קיים. זורק ArgumentException; השתמשו ב-indexer או ב-TryAdd.
• הוספת מפתחות בתוך foreach על המילון. זורק InvalidOperationException; אספו את השינויים והחילו אותם אחר כך.
• הסתמכות על סדר המעבר. מיינו, או השתמשו ב-SortedDictionary.
• שינוי השדות של אובייקט מפתח אחרי שהוכנס. ה-hash code שלו משתנה ואי אפשר יותר למצוא את הרשומה.
• ContainsKey ואחריו indexer. שני חיפושים; TryGetValue עושה אחד.