run-dev

,

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

В C# Dictionary<TKey, TValue> — это структура данных, реализующая ассоциативный массив (хеш-таблицу) для хранения пар ключ-значение. Она обеспечивает быстрый доступ к данным по ключу.

Создание и использование Dictionary<TKey, TValue>

Пример создания словаря:

Dictionary<int, string> dict = new Dictionary<int, string>();
dict.Add(1, "Один");
dict.Add(2, "Два");

Console.WriteLine(dict[1]); // Выведет "Один"

Особенности:

  • Ключи уникальны.
  • Доступ к элементам осуществляется за O(1) в среднем случае.
  • Поддерживаются методы Add, Remove, TryGetValue и другие.

Внутреннее устройство Dictionary<TKey, TValue>

Dictionary<TKey, TValue> основан на хеш-таблице и использует массив buckets для хранения индексов элементов. Алгоритм работы:

  1. Вычисляется хеш-код ключа (GetHashCode).
  2. По хеш-коду определяется индекс в массиве buckets.
  3. Если ячейка пуста — добавляется новая пара ключ-значение.
  4. Если ключ уже существует — происходит коллизия, и используется цепочка связанных элементов (LinkedList или entry[]).

Пример работы хеширования:

int index = key.GetHashCode() % buckets.Length;

Обработка коллизий

Коллизии могут возникать, если разные ключи дают одинаковый хеш. Dictionary<TKey, TValue> использует метод цепочек (chaining) для их разрешения, то есть хранит несколько элементов в одном bucket через связанный список.

Основные особенности

  1. Быстрый доступ: поиск, добавление и удаление за O(1) в среднем.
  2. Требование уникальности ключей: одинаковый ключ не может встречаться дважды.
  3. Память: из-за хеш-таблицы расход памяти может быть выше, чем у List<T>.

Dictionary<TKey, TValue> удобен для хранения и быстрого поиска данных по ключу. Он эффективен при большом количестве элементов и частых операциях поиска.

Больше записей