Как устроен Dictionary в C#

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

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

Dictionary в C# представляет собой структуру данных, которая представляет собой коллекцию пар «ключ-значение». Каждый элемент в Dictionary состоит из уникального ключа и связанного с ним значения. Ключи должны быть уникальными в пределах одного Dictionary.

Содержание

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 и ознакомьтесь с условиями обучения, мы специализируемся только на индивидуальных занятиях, как для начинающих, так и для более продвинутых программистов. Вы можете взять как одно занятие для проработки интересующего Вас вопроса, так и несколько, для более плотной работы. Благодаря личному кабинету, каждый студент повысит качество своего обучения, в вашем распоряжении: