Към съдържанието
wannacode

Dictionary и HashSet

Накратко: Речникът (map) пази двойки ключ и стойност с уникални ключове и намира стойността по ключ бързо, а множеството (set) пази уникални стойности.

Проблем

Кой е този потребител?

Потребителите на сайта са в списък. При всяко влизане търсиш имейла по потребителското име:

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

С три потребителя това е мигновено. С 2 000 000 всяко влизане сравнява до 2 000 000 имена, а влизанията са хиляди в минута. Телефонен указател не се чете от първата страница. Отиваш направо на буквата.

Идеята

Речник: ключ → стойност

Искаш да питаш „кой е имейлът на georgiev?“ и да получиш отговор веднага. Колекцията за това се казва речник (map). Тя пази двойки: ключ и стойност. В C# речникът е Dictionary:

Dictionary<string, string> emails = new Dictionary<string, string>();
emails["ivanov"] = "ivanov@example.com";
emails["mpetrova"] = "mpetrova@example.com";
emails["georgiev"] = "georgiev@example.com";


Console.WriteLine(emails["georgiev"]);
Console.WriteLine(emails.ContainsKey("nobody"));
Console.WriteLine("Потребители: " + emails.Count);
Изход
georgiev@example.com
False
Потребители: 3
  • Типовите параметри са два: на ключа и на стойността. Dictionary<string, string> е „от текст към текст“.
  • emails[ключ] = стойност слага двойка, а emails[ключ] връща стойността.
  • ContainsKey(ключ) пита дали ключът е вътре, а Count е броят двойки.
  • Dictionary е в System.Collections.Generic, като List. Не е нужен using: той е включен във всяка нова програма.

emails[ключ] за ключ, който го няма, не дава null, а хвърля KeyNotFoundException. Когато не знаеш дали ключът е вътре, питай с TryGetValue: той връща дали го е намерил, а стойността дава през out. Речникът може да се напише и наведнъж, с двойки [ключ] = стойност:

Dictionary<string, string> emails = new Dictionary<string, string>
{
    ["ivanov"] = "ivanov@example.com",
    ["mpetrova"] = "mpetrova@example.com",
};
if (emails.TryGetValue("ivanov", out string email))
{
    Console.WriteLine(email);
}
try
{
    Console.WriteLine(emails["nobody"]);
}
catch (KeyNotFoundException e)
{
    Console.WriteLine("KeyNotFoundException: " + e.Message);
}
Изход
ivanov@example.com
KeyNotFoundException: The given key 'nobody' was not present in the dictionary.

emails[ключ] не обхожда всички двойки, а намира мястото на ключа почти веднага, без значение колко са. Как го прави, е следващият урок.

Идеята

Складът: промени и проверки

Наличностите в склада: продукт → брой.

Dictionary<string, int> stock = new Dictionary<string, int>();
stock["лаптоп"] = 4;
stock["мишка"] = 25;
stock["лаптоп"] = 3;


Console.WriteLine(stock["лаптоп"]);
Console.WriteLine(stock.ContainsKey("монитор"));
Console.WriteLine(stock.GetValueOrDefault("монитор", 0));
stock.Remove("мишка");
Console.WriteLine(stock.Count);
Изход
3
False
0
1
  • Ключовете са уникални. Второто stock["лаптоп"] = 3 не добавя нов ред, а заменя 4 с 3.
  • ContainsKey пита дали ключът е вътре.
  • GetValueOrDefault(ключ, 0) връща стойността или 0, ако ключа го няма. Това пази от KeyNotFoundException.
  • Remove(ключ) маха двойката.
По-точно, за любопитните
  • Стойностите могат да се повтарят: лаптоп и мишка може да са по 3. Ключовете не могат.
  • Има и ContainsValue. Той обаче обхожда всички стойности, защото речникът е бърз само по ключ.
  • Двойка се слага и с Add(ключ, стойност). Разликата е при ключ, който вече е вътре: [ключ] = заменя стойността, а Add хвърля ArgumentException и не пипа старата:
Dictionary<string, int> stock = new Dictionary<string, int>();
stock.Add("лаптоп", 4);
try
{
    stock.Add("лаптоп", 3);
}
catch (ArgumentException e)
{
    Console.WriteLine(e.Message);
}
Console.WriteLine(stock["лаптоп"]);
Изход
An item with the same key has already been added. Key: лаптоп
4

Пробвай

Колко са в менюто?

Какво ще отпечата програмата?

Dictionary<string, int> menu = new Dictionary<string, int>();
menu["кафе"] = 2;
menu["чай"] = 2;
menu["кафе"] = 3;
Console.WriteLine(menu.Count + " " + menu["кафе"]);
Отговор

Идеята

Обхождане и редът

Цената на доставката по градове. foreach по речника дава двойките: всяка е KeyValuePair<string, double>, с Key и Value:

Dictionary<string, double> delivery = new Dictionary<string, double>();
delivery["София"] = 4.5;
delivery["Пловдив"] = 5.2;
delivery["Варна"] = 6.0;
delivery["Бургас"] = 6.0;
delivery["Русе"] = 5.8;


foreach (KeyValuePair<string, double> e in delivery)
{
    Console.WriteLine($"{e.Key}: {e.Value:F2} €");
}
Изход
София: 4.50 €
Пловдив: 5.20 €
Варна: 6.00 €
Бургас: 6.00 €
Русе: 5.80 €

Градовете излязоха в реда, в който са добавени. Но Dictionary не обещава ред. Докато само добавяш, той обикновено пази реда на добавяне. След Remove обаче новият ключ заема мястото на махнатия. Със същите пет града:

delivery.Remove("Пловдив");
delivery["Плевен"] = 5.0;
Console.WriteLine(string.Join(", ", delivery.Keys));
Изход
София, Плевен, Варна, Бургас, Русе

Плевен е добавен последен, а излезе втори. Не пиши код, който разчита на реда на Dictionary. Когато редът има значение, смени само класа:

  • OrderedDictionary пази реда на добавяне и го обещава. Със същите градове, Remove и добавяне Плевен отива накрая:
Изход
София, Варна, Бургас, Русе, Плевен
  • SortedDictionary подрежда ключовете:
SortedDictionary<string, double> delivery = new SortedDictionary<string, double>();
delivery["София"] = 4.5;
delivery["Пловдив"] = 5.2;
delivery["Варна"] = 6.0;
delivery["Бургас"] = 6.0;
delivery["Русе"] = 5.8;


foreach (KeyValuePair<string, double> e in delivery)
{
    Console.WriteLine($"{e.Key}: {e.Value:F2} €");
}
Изход
Бургас: 6.00 €
Варна: 6.00 €
Пловдив: 5.20 €
Русе: 5.80 €
София: 4.50 €

{e.Value:F2} печата цената с два знака след точката: иначе 6.0 излиза като 6.

По-точно, за любопитните
  • Ако ти трябват само ключовете, обхождай Keys. Ако ти трябват само стойностите, обхождай 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($"Средно: {sum / delivery.Count:F2} €");
Изход
София Пловдив Варна Бургас Русе
Средно: 5.50 €
  • SortedDictionary е по-бавен от Dictionary, защото пази ключовете подредени. Ползвай го, когато редът ти трябва.
  • OrderedDictionary с типови параметри е нов: има го от .NET 9.

Идеята

Броене

Колко пъти е поръчан всеки продукт? Ключът е продуктът, стойността е броят. При всяка поръчка вземаш стария брой (или 0) и добавяш 1:

string orders = "кафе чай кафе вода кафе чай";
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));
Изход
[вода, 1], [кафе, 3], [чай, 2]

Това е най-честата употреба на речник: броене на думи, гласове, грешки по вид, продажби по град. Тук е SortedDictionary, за да излязат продуктите подредени. string.Join(", ", counts) печата всяка двойка като [ключ, стойност].

string orders = "кафе чай кафе вода кафе чай";
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));
Стъпка по стъпка, с думи
  1. 6 поръчки и празен SortedDictionary.
  2. „кафе“ го няма: GetValueOrDefault дава 0, а записът в counts[item] добавя ключа с 1.
  3. „чай“ го няма: GetValueOrDefault дава 0, а записът в counts[item] добавя ключа с 1.
  4. „кафе“ вече е вътре: GetValueOrDefault дава 1, а записът в counts[item] заменя стойността с 2.
  5. „вода“ го няма: GetValueOrDefault дава 0, а записът в counts[item] добавя ключа с 1. SortedDictionary го слага преди „кафе“: ключовете са подредени.
  6. „кафе“ вече е вътре: GetValueOrDefault дава 2, а записът в counts[item] заменя стойността с 3.
  7. „чай“ вече е вътре: GetValueOrDefault дава 1, а записът в counts[item] заменя стойността с 2.
  8. Всеки продукт е ключ веднъж, а стойността е колко пъти е поръчан.
По-точно, за любопитните
  • split(" ") от урока за текста разделя реда на думи.
  • В модул „Модерен C#“ ще видиш LINQ. Там има готово броене, CountBy, което дава двойките в реда, в който продуктите са видени за първи път: 
string orders = "кафе чай кафе вода кафе чай";
Console.WriteLine(string.Join(", ", orders.Split(' ').CountBy(item => item)));
Изход
[кафе, 3], [чай, 2], [вода, 1]

Пробвай

Намери грешката

Програмата трябва да преброи поръчките. Вместо това спира още на първата:
Грешка
Unhandled exception. System.Collections.Generic.KeyNotFoundException: The given key 'кафе' was not present in the dictionary.

На кой ред е грешката?

Избери реда с грешката.

Идеята

HashSet: всяко по веднъж

Колко различни хора са влезли в сайта днес? Ако някой влезе пет пъти, трябва да се брои веднъж. Колекция, която пази всяка стойност само по веднъж, се казва множество (set):

string[] visits = { "ana@example.com", "boris@example.com", "ana@example.com", "vera@example.com", "boris@example.com" };
HashSet<string> visitors = new HashSet<string>();
foreach (string email in visits)
{
    visitors.Add(email);
}
Console.WriteLine("Посещения: " + visits.Length);
Console.WriteLine("Различни посетители: " + visitors.Count);
Console.WriteLine(visitors.Contains("vera@example.com"));
Изход
Посещения: 5
Различни посетители: 3
True
  • Add на стойност, която вече е вътре, не прави нищо и връща False. Ако е нова, връща True:
HashSet<string> seen = new HashSet<string>();
Console.WriteLine(seen.Add("F-101"));
Console.WriteLine(seen.Add("F-101"));
Изход
True
False
  • Contains е бърз като ContainsKey на речника. Отвътре HashSet е като Dictionary, в който пазиш само ключовете.
  • Индекси няма. Множеството отговаря само на въпроса „вътре ли е?“.
По-точно, за любопитните
  • Редът на HashSet не е обещан, както при Dictionary. SortedSet подрежда. Множество може да се напише и наведнъж, в {} със стойности:
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));
Изход
git, java, sql
java, sql
docker, git, java, sql
  • IntersectWith оставя само общите елементи на две множества, а UnionWith ги обединява. И двата сменят множеството, на което ги викаш, затова общите са в копие: new SortedSet<string>(tags). Ще ти трябват в упражнението.

Пробвай

Повторена фактура

Счетоводителката иска да види номерата на фактури, въведени два пъти. Кой метод едновременно проверява и добавя?
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("Повторена фактура: " + number);
    }
}

Упражнение

Речници в работа

Реши задачите в редактора си.

1. Таблица с потребители. Клас UserTable с методи Add(string username, string email), Get(string username) и Size(). Отвътре е Dictionary. За потребител, когото го няма, Get връща null: GetValueOrDefault без втори аргумент дава точно това. Добави ivanov, mpetrova и georgiev с имейли във вида ivanov@example.com и потърси mpetrova и nobody. В следващия урок ще направиш и своя хеш таблица, без Dictionary.

Изход
mpetrova: mpetrova@example.com
nobody: няма такъв потребител
Потребители: 3

2. Честота на думите. Прочети ред текст, направи го с малки букви и преброй всяка дума. Отпечатай думите по азбучен ред.

Вход
Кафе с мляко и кафе без захар и кафе
Изход
без: 1
захар: 1
и: 2
кафе: 3
мляко: 1
с: 1

3. Документи по ключова дума. Клас DocumentIndex с методи AddDocument(int id, params string[] keywords) и Search(string keyword), който връща списък с номерата на документите с тази дума. Отвътре е Dictionary<string, List<int>>: за всяка дума списък от документи. Добави документ 1 с „ООП“ и „Java“, документ 2 със „SQL“ и „бази данни“, документ 3 с „Java“ и „колекции“. Потърси „Java“, „SQL“ и „Python“ и отпечатай номерата в [], разделени със запетая.

Изход
Java: [1, 3]
SQL: [2]
Python: []

4. Мрежа от контакти. Клас Contact с име и имейл и клас ContactNetwork с методи AddContact(string name, string email), AddConnection(string a, string b) (връзката е в двете посоки), FriendsOf(string name), Common(string a, string b) (общите познати) и EmailOf(string name). Пази контактите в Dictionary<string, Contact>, а връзките в Dictionary<string, SortedSet<string>>, за да излизат имената подредени. Свържи Иван с Мария и Иван с Петър.

Изход
Иван: [Мария, Петър]
Мария: [Иван]
Общи познати на Мария и Петър: [Иван]
Имейл на Петър: petar@example.com

Още задачи

  • Уникален идентификатор. Метод GenerateUserId(string email) дава на всеки нов имейл номер U001, U002 и т.н., а за вече видян имейл връща същия номер. Големи и малки букви в имейла не се различават. Вариант с хеш функция има в следващия урок.
  • Каталог на книги. Ключът е ISBN, например 978-954-28-0001-2, а стойността е заглавието. Добави, потърси и отпечатай всички книги, подредени по ISBN.
  • Организатор на пътуване. За всяка дестинация пази списък от дейности: „Париж“ → „Айфеловата кула“, „Лувъра“. Отпечатай програмата в реда, в който са добавени дестинациите. Кой речник ще избереш?
  • Електронен речник. Дума → определение. Чети думи, докато не дойде „край“. За непозната дума отпечатай „Няма такава дума.“
  • Оценки по предмет. Чети редове „Математика 6“, „Физика 5“, „Математика 4“ и отпечатай средния успех по всеки предмет, подредени по име.

Тест

Провери се

1. Кога Dictionary е по-добър избор от списък?
2. В menu вече има ключ "кафе" със стойност 2. Какво прави menu["кафе"] = 3?
3. Ключа "чай" го няма в menu. Какво прави menu["чай"]?
4. Обхождаш Dictionary. В какъв ред излизат ключовете?
5. Какво връща Add на HashSet, ако стойността вече е вътре?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·