Словник Dictionary<K, V>

10.5. Словник Dictionary

Уявіть задачу: є список пацієнтів, і потрібно швидко знайти пацієнта за його ідентифікатором "P001". При використанні List<T> доведеться перебирати весь список поелементно — O(n). При 10 000 пацієнтів це 10 000 порівнянь у гіршому випадку.

Dictionary<K, V> вирішує цю задачу за O(1) в середньому. Це колекція пар ключ → значення, де ключ унікальний і забезпечує миттєвий доступ до відповідного значення. Dictionary<K, V> — правильний вибір щоразу, коли потрібен швидкий пошук за ідентифікатором, кодом або будь-яким унікальним атрибутом.

Внутрішня структура: хеш-таблиця

Всередині Dictionary<K, V> зберігає дані у хеш-таблиці. Принцип роботи:

1. При додаванні пари key → value обчислюється хеш ключа: key.GetHashCode().
2. За хешем визначається індекс бакету (bucket): index = hash % bucketCount.
3. Пара зберігається у відповідному бакеті.
4. При пошуку за ключем ті самі два кроки дають індекс — і значення знаходиться без перебору.

Якщо два різних ключі дають однаковий індекс бакету (колізія), елементи утворюють у цьому бакеті ланцюжок. У .NET цей ланцюжок влаштовано економно: словник тримає два масиви — buckets (номер бакета → індекс першого запису) і entries (самі записи: збережений хеш, ключ, значення і поле next — індекс наступного запису в ланцюжку). Тобто ланцюжок — це індекси всередині того самого масиву, а не окремі об'єкти-вузли; при пошуку словник проходить ним і порівнює ключі через Equals. Розмір таблиці — просте число (3, 7, 17, …), що краще розподіляє залишки від ділення. Добре реалізований GetHashCode() мінімізує колізії, тому на практиці пошук майже завжди O(1).

Ще одна деталь, яку легко пропустити: хеш рядка в .NET рандомізований — "P001".GetHashCode() дає різні числа при кожному запуску програми (захист від атак, що підбирають ключі з однаковим хешем). Тому хеш ніколи не можна зберігати у файл чи базу як «ідентифікатор» рядка.

Тип ключа K повинен коректно реалізувати GetHashCode() і Equals(). Для вбудованих типів (string, int, Guid тощо) це вже зроблено. Для власних класів — потрібно явно перевизначити ці методи або використовувати незмінні типи-значення. Правило узгодженості: якщо a.Equals(b), то a.GetHashCode() == b.GetHashCode(). І ще одне: ключ, що вже лежить у словнику, не можна змінювати так, щоб змінився його хеш, — запис залишиться в «старому» бакеті, і словник його більше не знайде.

Створення та ініціалізація

Dictionary<K, V> типізується двома параметрами: тип ключа K і тип значення V:

// Порожній словник: int-ключ → рядкове значення
Dictionary<int, string> rooms = new Dictionary<int, string>();

// Ключ — рядок (код пацієнта), значення — рядок (ПІБ)
var patientIndex = new Dictionary<string, string>();

// Ініціалізатор з фігурними дужками — синтаксис { ключ, значення }
var diagnoses = new Dictionary<string, string>()
{
    { "P001", "Гіпертонія" },
    { "P002", "Діабет" },
    { "P003", "Аритмія" }
};

// Альтернативний синтаксис з індексатором [ключ] = значення
var medications = new Dictionary<string, string>()
{
    ["ASP100"] = "Аспірин 100мг",
    ["IBU400"] = "Ібупрофен 400мг",
    ["MET850"] = "Метформін 850мг"
};

Обидва синтаксиси рівноцінні — використовуйте той, що читається краще для конкретної задачі.

KeyValuePair

Кожен елемент словника внутрішньо представляється структурою KeyValuePair<TKey, TValue>. Ця структура має дві властивості: Key — ключ елемента і Value — його значення. Вона з'являється при ітерації словника через foreach, при ініціалізації через конструктор, і при роботі з колекцією Keys/Values.

// Створення через KeyValuePair (рідкісний сценарій — для ініціалізації з колекції)
var pair = new KeyValuePair<string, string>("P001", "Петренко Іван");
var pairs = new List<KeyValuePair<string, string>> { pair };
var dict = new Dictionary<string, string>(pairs);

Отримання та зміна елементів

Доступ до елемента відбувається через індексатор dict[key]:

var patientNames = new Dictionary<string, string>()
{
    ["P001"] = "Петренко Іван",
    ["P002"] = "Коваль Марія",
};

// Читання
string name = patientNames["P001"];   // "Петренко Іван"

// Оновлення існуючого ключа
patientNames["P002"] = "Коваль Марія Степанівна";

// Додавання нового ключа — якщо ключ відсутній
patientNames["P003"] = "Сидоренко Олег";

Якщо звернутися за неіснуючим ключем через dict[key] — буде кинуто KeyNotFoundException. Для безпечного доступу використовуйте TryGetValue.

Властивості Dictionary

• Count — кількість пар у словнику.
• Keys — колекція всіх ключів типу Dictionary<K, V>.KeyCollection (реалізує ICollection<K>). Це не копія, а «вікно» на ключі словника; ітерується через foreach.
• Values — колекція всіх значень типу Dictionary<K, V>.ValueCollection (реалізує ICollection<V>).

Порядок перебору словника (і його Keys/Values) не гарантований документацією. Поки з словника нічого не видаляли, він на практиці збігається з порядком додавання, але після Remove нові записи займають звільнені місця — покладатися на порядок не можна. Якщо він потрібен, сортуйте ключі явно або використовуйте SortedDictionary<K, V>.

var rooms = new Dictionary<int, string>()
{
    [101] = "Кардіологія",
    [102] = "Неврологія",
    [201] = "Хірургія"
};

Console.WriteLine($"Палат: {rooms.Count}");

foreach (var roomNum in rooms.Keys)
    Console.WriteLine($"Палата {roomNum}");

foreach (var dept in rooms.Values)
    Console.WriteLine($"Відділення: {dept}");

Перебір словника

При foreach кожен елемент словника — це KeyValuePair<K, V>:

var patientNames = new Dictionary<string, string>()
{
    ["P001"] = "Петренко Іван",
    ["P002"] = "Коваль Марія",
    ["P003"] = "Сидоренко Олег"
};

foreach (var entry in patientNames)
{
    Console.WriteLine($"ID: {entry.Key}  Пацієнт: {entry.Value}");
}

Можна одразу деструктурувати пару. Синтаксис деконструкції з'явився в C# 7, але для KeyValuePair він працює завдяки методу KeyValuePair<K, V>.Deconstruct, доданому в .NET Core 2.0 (у старому .NET Framework його немає):

foreach (var (id, name) in patientNames)
{
    Console.WriteLine($"{id} → {name}");
}

Методи Dictionary

Метод	Що робить	Складність
Add(key, value)	Додає пару; виняток якщо ключ вже є	O(1)*
TryAdd(key, value)	Додає якщо ключ відсутній; повертає bool	O(1)*
Remove(key)	Видаляє пару за ключем; повертає bool	O(1)*
Remove(key, out V)	Видаляє і повертає значення через out	O(1)*
ContainsKey(key)	Чи є ключ у словнику	O(1)*
ContainsValue(value)	Чи є значення у словнику	O(n)
TryGetValue(key, out V)	Безпечне читання; false якщо ключ відсутній	O(1)*
Clear()	Очищає словник	O(n)

TryGetValue — найважливіший метод безпечного доступу

TryGetValue — рекомендований спосіб читання зі словника в production-коді. Він не кидає виняток на відсутньому ключі і повертає false:

if (patientNames.TryGetValue("P999", out var name))
    Console.WriteLine($"Знайдено: {name}");
else
    Console.WriteLine("Пацієнт P999 не знайдений.");

Порівняйте з небезпечним варіантом:

// НЕБЕЗПЕЧНО — кидає KeyNotFoundException якщо ключ відсутній:
var name = patientNames["P999"];

Каталог медикаментів — runnable приклад

Медичний каталог: пошук препарату за кодом, оновлення, видалення:

Реєстратура пацієнтів — runnable приклад

Реалістичний приклад з класом: реєстр пацієнтів за ідентифікатором:

Складність операцій

Коли Dictionary?

Dictionary<K, V> — правильний вибір коли:

• Потрібен швидкий пошук за ключем: O(1) vs O(n) у List<T>.
• Дані мають природну структуру ключ → значення: ID пацієнта → пацієнт, код препарату → препарат.
• Потрібно перевіряти наявність елемента за ідентифікатором.
• Потрібен підрахунок (ключ → кількість) або групування (ключ → список).

List<T> залишається кращим вибором, коли:

• Порядок елементів важливий і ключова операція — перебір.
• Немає унікального ідентифікатора для елементів.
• Колекція мала (< ~20 елементів) — різниця O(1) vs O(n) несуттєва.

HashSet — множина унікальних елементів

HashSet<T> — «словник без значень». Він зберігає лише унікальні елементи, дає O(1) у середньому для додавання, видалення і пошуку (так само, як Dictionary, — за умови рівномірних хешів), але на відміну від Dictionary не зберігає пар ключ-значення — тільки самі елементи.

Ключові властивості HashSet<T>:

• Не допускає дублікатів: повторне Add(element) ігнорується (повертає false)
• Немає гарантій порядку: елементи перебираються у довільному порядку
• O(1) для Contains: значно швидший за List<T>.Contains для великих колекцій
• Операції теорії множин: UnionWith, IntersectWith, ExceptWith

Операція	List<T>	HashSet<T>
Add	O(1) (amortized)	O(1) — дублікати ігноруються
Contains	O(n)	O(1)
Remove	O(n)	O(1)
Порядок	Зберігається	Не гарантується
Дублікати	Дозволені	Заборонені
Теорія множин	Ні	UnionWith, IntersectWith, ExceptWith

Використовуйте HashSet<T> коли: потрібна колекція без дублікатів, або потрібна швидка перевірка Contains для великих наборів даних, або потрібні операції над множинами. Використовуйте List<T> коли: важливий порядок або допустимі дублікати.