Словник 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. При пошуку за ключем ті самі два кроки дають індекс — і значення знаходиться без перебору.

Якщо два різних ключі дають однаковий індекс бакету (колізія), елементи зберігаються разом у тому ж бакеті у вигляді ланцюжка. Добре реалізований GetHashCode() мінімізує колізії, тому на практиці пошук майже завжди O(1).

Тип ключа K повинен коректно реалізувати GetHashCode() і Equals(). Для вбудованих типів (string, int, Guid тощо) це вже зроблено. Для власних класів — потрібно явно перевизначити ці методи або використовувати незмінні типи-значення.

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

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 — колекція всіх ключів типу ICollection<K>. Ітерується через foreach.
• Values — колекція всіх значень типу ICollection<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+ можна одразу деструктурувати пару:

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 не зберігає пар ключ-значення — тільки самі елементи.

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

• Не допускає дублікатів: повторне Add(element) ігнорується (повертає false)
• Немає гарантій порядку: елементи перебираються у довільному порядку
• О(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> коли: важливий порядок або допустимі дублікати.