Як влаштований Dictionary у C#

[ Полезный рекламный блок ]

Попробуйте свои силы в игре, где ваши навыки программирования на C# станут решающим фактором. Переходите по ссылке 🔰.

Dictionary у C# являє собою структуру даних, яка являє собою колекцію пар “ключ-значення”. Кожен елемент у Dictionary складається з унікального ключа і пов’язаного з ним значення. Ключі мають бути унікальними в межах одного Dictionary.

Table of Contents

Dictionary є частиною простору імен System.Collections.Generic.

Dictionary<TKey, TValue> – узагальнений клас, де TKey – тип ключа, а TValue – тип значення. Ключі та значення можуть бути практично будь-якого типу, включно з вбудованими типами даних і користувацькими класами та структурами.

Хешування ключів

Під час додавання елемента в Dictionary, система обчислює хеш-код для ключа з використанням методу GetHashCode(). Хеш-код – це цілочисельне значення, яке слугує внутрішнім індексом для доступу до масиву “відер” (buckets) хеш-таблиці.

Тип ключа

Тип, який використовується як ключ словника, має перевизначати методи GetHashCode() і Equals() класу Object. Щоразу, коли клас словника має знайти місце розташування елемента, він викликає метод GetHashCode(). Ціле число, що повертається цим методом, використовується словником для обчислення індексу, куди поміщено елемент. Ми не станемо заглиблюватися в подробиці роботи цього алгоритму. Єдине, що слід знати – це те, що він використовує прості числа, тож ємність словника завжди виражається простим числом.

Створення та додавання елементів

Створимо новий екземпляр словника Dictionary із зазначенням, що ключами будуть рядки (string), а значеннями – цілі числа (int):

Dictionary<string, int> ages = new Dictionary<string, int>();

// Добавление элементов
ages.Add("Alice", 28);
ages.Add("Bob", 34);
ages["Charlie"] = 22; // Альтернативный способ добавления

Dictionary<string, int> ages = new Dictionary<string, int>();

// Добавление элементов

ages.Add("Alice", 28);

ages.Add("Bob", 34);

ages["Charlie"] = 22; // Альтернативный способ добавления

У цьому коді, після визначення словника, додається елемент ages. Ключ “Alice” пов’язується зі значенням 28. Аналогічно до попереднього кроку, додається елемент до словника. Ключ “Bob” зв’язується зі значенням 34.

Після виконання цього коду, ages міститиме три елементи:

"Alice" - 28
"Bob" - 34
"Charlie" - 22

"Alice" - 28

"Bob" - 34

"Charlie" - 22

Доступ і зміна елементів

Для отримання значення за ключем у нас є 3 варіанти, визначимо такий словник:

static void Main()
        {
            Dictionary<int, string> countries = new Dictionary<int, string>(5);
            countries.Add(1, "Russia");
            countries.Add(3, "Great Britain");
            countries.Add(2, "USA");
            countries.Add(4, "France");
            countries.Add(5, "China");
        }

static void Main()

{

Dictionary<int, string> countries = new Dictionary<int, string>(5);

countries.Add(1, "Russia");

countries.Add(3, "Great Britain");

countries.Add(2, "USA");

countries.Add(4, "France");

countries.Add(5, "China");

}

Перший варіант передбачає використання ключа в індексаторі, якщо такий ключ відсутній, ви отримаєте помилку:

string value = countries[5];
value = countries[10];// KeyNotFoundException

1 2	string value = countries[5]; value = countries[10];// KeyNotFoundException

Другий варіант полягає у використанні методу TryGetValue(), який аналогічний до того ж int.TryParse():

countries.TryGetValue(5, out string value);
countries.TryGetValue(5, out value);// ошибки не будет

1 2	countries.TryGetValue(5, out string value); countries.TryGetValue(5, out value);// ошибки не будет

Якщо необхідно отримати ключ і значення за ключем, можна скористатися методами розширення:

KeyValuePair<int, string> find = countries.Where.FirstOrDefault(e => e.Key == 3);

1	KeyValuePair<int, string> find = countries.Where.FirstOrDefault(e => e.Key == 3);

Тепер ви знаєте, як правильно знайти значення в словнику, у жодному разі не шукайте ключ, використовуючи цикл, ця операція займе набагато більше часу.

Перевірка наявності елемента

Для перевірки наявності елемента в словнику, використовуйте метод ContainsKey:

bool containsAlice = ages.ContainsKey("Alice"); // true

1	bool containsAlice = ages.ContainsKey("Alice"); // true

Видалення елемента

Для видалення елемента в словнику, використовуйте метод Remove:

ages.Remove("Charlie"); // Удаление по ключу
ages.Clear(); // Удаление всех элементов

1 2	ages.Remove("Charlie"); // Удаление по ключу ages.Clear(); // Удаление всех элементов

Застосування делегатів

Використовуючи словник і делегат Action, можна викликати метод за його назвою:

static void Main()
        {
            Dictionary<string, Action> _methods = new()
            {
                ["method1"] = Method,
                ["method2"] = Method2
            };
            string name = Console.ReadLine();
            _methods[name].Invoke();
        }
        static void Method() => Console.WriteLine("Method");
        static void Method2() => Console.WriteLine("Method 2");

static void Main()

{

Dictionary<string, Action> _methods = new()

{

["method1"] = Method,

["method2"] = Method2

};

string name = Console.ReadLine();

_methods[name].Invoke();

}

static void Method() => Console.WriteLine("Method");

static void Method2() => Console.WriteLine("Method 2");

Складність пошуку

У середньому випадку (за добре рівномірно розподілених хеш-кодів), пошук, вставка і видалення елементів у Dictionary виконуються за константний час O(1). Однак, у гіршому випадку, за великої кількості колізій, час роботи може зрости до O(n), де n – кількість елементів у словнику.

Додаткова інформація

1. Record чудово підходить для типу, який виступає як ключ для колекції Dictionary, оскільки за імутабельної версії, він перевизначає методи Equals() і GetHashCode().

2. Під час пошуку і порівняння ключів, може знадобитися не враховувати регістр символів, у такому разі можна передати об’єкт StringComparer, у конструктор класу:

static void Main()
    {
        string[] words = { "apple", "orange", "Apple", "cherry" };
        var comparer = StringComparer.OrdinalIgnoreCase;
        Dictionary<string, int> keyValuePairs = new Dictionary<string, int>(comparer);
        foreach (string item in words)
        {
            if (keyValuePairs.ContainsKey(item))
            {
                keyValuePairs[item] += 1;
            }
            else
            {
                keyValuePairs.Add(item, 1);
            }
        }
    }

static void Main()

{

string[] words = { "apple", "orange", "Apple", "cherry" };

var comparer = StringComparer.OrdinalIgnoreCase;

Dictionary<string, int> keyValuePairs = new Dictionary<string, int>(comparer);

foreach (string item in words)

{

if (keyValuePairs.ContainsKey(item))

{

keyValuePairs[item] += 1;

}

else

{

keyValuePairs.Add(item, 1);

}

Dictionary надає швидкий доступ до елементів за ключем, тому він ефективний для пошуку та зберігання пар “ключ-значення”.

Переваги Dictionary – швидкий доступ до елементів за ключем і ефективне зберігання великої кількості даних. Однак, вони вимагають унікальності ключів і можуть використовувати більше пам’яті через зберігання хеш-кодів і значень.

Я сподіваюся, що вам сподобалося читати цю статтю, і вона виявилася легкою для розуміння. Будь ласка, дайте мені знати, якщо у вас є якісь коментарі або виправлення.

Так само вам може бути цікава попередня стаття – Абстрактний Клас у C#. Місця застосування.

Ви хочете навчитися писати код мовою програмування C#?

Створювати різні інформаційні системи, що складаються з сайтів, мобільних клієнтів, десктопних додатків, телеграм-ботів тощо.

Переходьте до нас на сторінку Dijix і ознайомтеся з умовами навчання, ми спеціалізуємося тільки на індивідуальних заняттях, як для початківців, так і для просунутих програмістів. Ви можете взяти як одне заняття для опрацювання питання, що вас цікавить, так і кілька, для більш щільної роботи. Завдяки особистому кабінету, кожен студент підвищить якість свого навчання, у вашому розпорядженні: