Словарь: класс Dictionary<TKey, TValue>
79C# --- Руководство по C# --- Словарь: класс Dictionary<TKey, TValue>
Словарь (dictionary) представляет собой сложную структуру данных, позволяющую обеспечить доступ к элементам по ключу. Главное свойство словарей — быстрый поиск на основе ключей. Можно также свободно добавлять и удалять элементы, подобно тому, как это делается в List<T>, но без накладных расходов производительности, связанных с необходимостью смещения последующих элементов в памяти.
На следующем рисунке представлена упрощенная модель словаря. Здесь ключами словаря служат идентификаторы сотрудников, такие как В4711. Ключ трансформируется в хеш. В хеше создается число для ассоциации индекса со значением. После этого индекс содержит ссылку на значение. Изображенная модель является упрощенной, поскольку существует возможность того, что единственное вхождение индекса может быть ассоциировано с несколькими значениями, и индекс может храниться в виде дерева.
В .NET Framework предлагается несколько классов словарей. Главный класс, который можно использовать — это Dictionary<TKey, TValue>.
Тип ключа
Тип, используемый в качестве ключа словаря, должен переопределять метод GetHashCode() класса Object. Всякий раз, когда класс словаря должен найти местоположение элемента, он вызывает метод GetHashCode().
Целое число, возвращаемое этим методом, используется словарем для вычисления индекса, куда помещен элемент. Мы не станем углубляться в подробности работы этого алгоритма. Единственное, что следует знать — это то, что он использует простые числа, так что емкость словаря всегда выражается простым числом.
Реализация метода GetHashCode() должна удовлетворять перечисленным ниже требованиям:
Один и тот же объект должен всегда возвращать одно и то же значение.
Разные объекты могут возвращать одно и то же значение.
Он должен выполняться насколько возможно быстро, не требуя значительных вычислительных затрат.
Он не должен генерировать исключений.
Он должен использовать как минимум одно поле экземпляра.
Значения хеш-кода должны распределяться равномерно по всему диапазону чисел, которые может хранить int.
Хеш-код не должен изменяться на протяжении времени существования объекта.
Чем вызвана необходимость равномерного распределения значений хеш-кода по диапазону целых чисел? Если два ключа возвращают хеш-значения, дающие один и тот же индекс, класс словаря вынужден искать ближайшее доступное свободное место для сохранения второго элемента, к тому же ему придется выполнять некоторый поиск, чтобы впоследствии извлечь требуемое значение. Понятно, что это наносит ущерб производительности, и если множество ключей дают одни и те же индексы, куда их следует поместить, вероятность конфликтов значительно возрастает. Однако благодаря способу, которым работает часть алгоритма, принадлежащая Microsoft, риск снижается до минимума, когда вычисляемое значение хеш-кода равномерно распределено между int.MinValue и int.MaxValue.
Помимо реализации GetHashCode() тип ключа также должен реализовывать метод IEquatable<T>.Equals() либо переопределять метод Equals() класса Object. Поскольку разные объекты ключа могут возвращать один и тот же хеш-код, метод Equals() используется при сравнении ключей словаря. Словарь проверяет два ключа А и В на эквивалентность, вызывая A.Equals(В). Это означает, что потребуется обеспечить истинность следующего утверждения:
Если истинно А.Equals(В) , значит, А.GetHashCode() и В.GetHashCode() всегда должны возвращать один и тот же хеш-код.
Класс Dictionary<TKey, TValue>
В классе Dictionary<TKey, TValue> реализуются интерфейсы IDictionary, IDictionary<TKey, TValue>, ICollection, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable, IEnumerable<KeyValuePair<TKey, TValue>>, ISerializable и IDeserializationCallback. В двух последних интерфейсах поддерживается сериализация списка. Словари имеют динамический характер, расширяясь по мере необходимости.
В классе Dictionary<TKey, TValue> предоставляется немало конструкторов. Ниже перечислены наиболее часто используемые из них:
public Dictionary()
public Dictionary(IDictionary<TKey, TValue> dictionary)
public Dictionary(int capacity)В первом конструкторе создается пустой словарь с выбираемой по умолчанию первоначальной емкостью. Во втором конструкторе создается словарь с указанным количеством элементов dictionary. А в третьем конструкторе с помощью параметра capacity указывается емкость коллекции, создаваемой в виде словаря. Если размер словаря заранее известен, то, указав емкость создаваемой коллекции, можно исключить изменение размера словаря во время выполнения, что, как правило, требует дополнительных затрат вычислительных ресурсов.
В классе Dictionary<TKey, TValue> определяется также ряд методов:
- Add()
Добавляет в словарь пару "ключ-значение", определяемую параметрами key и value. Если ключ key уже находится в словаре, то его значение не изменяется, и генерируется исключение ArgumentException
- ContainsKey()
Возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; а иначе — логическое значение false
- ContainsValue()
Возвращает логическое значение true, если вызывающий словарь содержит значение value; в противном случае — логическое значение false
- Remove()
Удаляет ключ key из словаря. При удачном исходе операции возвращается логическое значение true, а если ключ key отсутствует в словаре — логическое значение false
Кроме того, в классе Dictionary<TKey, TValue> определяются собственные свойства, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Эти свойства приведены ниже:
- Comparer
Получает метод сравнения для вызывающего словаря
- Keys
Получает коллекцию ключей
- Values
Получает коллекцию значений
Следует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступны отдельными списками с помощью свойств Keys и Values. В коллекциях типа Dictionary<TKey, TValue>.KeyCollection и Dictionary<TKey, TValue>.ValueCollection реализуются как обобщенные, так и необобщенные формы интерфейсов ICollection и IEnumerable.
И наконец, в классе Dictionary<TKey, TValue> реализуется приведенный ниже индексатор, определенный в интерфейсе IDictionary<TKey, TValue>
public TValue this[TKey key] { get; set; }Этот индексатор служит для получения и установки значения элемента коллекции, а также для добавления в коллекцию нового элемента. Но в качестве индекса в данном случае служит ключ элемента, а не сам индекс. При перечислении коллекции типа Dictionary<TKey, TValue> из нее возвращаются пары "ключ-значение" в форме структуры KeyValuePair<TKey, TValue>. Напомним, что в этой структуре определяются два поля.
public TKey Key;
public TValue Value;В этих полях содержится ключ или значение соответствующего элемента коллекции. Как правило, структура KeyValuePair<TKey, TValue> не используется непосредственно, поскольку средства класса Dictionary<TKey, TValue> позволяют работать с ключами и значениями по отдельности. Но при перечислении коллекции типа Dictionary<TKey, TValue>, например, в цикле foreach перечисляемыми объектами являются пары типа KeyValuePair.
Давайте рассмотрим пример использования словарей:
using System;
using System.Collections.Generic;
namespace ConsoleApplication1
{
class UserInfo
{
// Метод, реализующий словарь
public static Dictionary<int, string> MyDic(int i)
{
Dictionary<int, string> dic = new Dictionary<int,string>();
Console.WriteLine("Введите имя сотрудника: \n");
string s;
for (int j = 0; j < i; j++)
{
Console.Write("Name{0} --> ",j);
s = Console.ReadLine();
dic.Add(j, s);
Console.Clear();
}
return dic;
}
}
class Program
{
static void Main()
{
Console.Write("Сколько сотрудников добавить? ");
try
{
int i = int.Parse(Console.ReadLine());
Dictionary<int, string> dic = UserInfo.MyDic(i);
// Получить коллекцию ключей
ICollection<int> keys = dic.Keys;
Console.WriteLine("База данных содержит: ");
foreach (int j in keys)
Console.WriteLine("ID -> {0} Name -> {1}",j,dic[j]);
}
catch (FormatException)
{
Console.WriteLine("Неверный ввод");
}
Console.ReadLine();
}
}
}
