Коллекции - Продолжение (Словари)

Коллекции - Продолжение (Словари)

Язык C# позволяет работать со словарями, содержащих в качестве элементов пары <Ключ> → <Значение>. Где «Ключ» жестко связан за следующим за ним значением. Примерами могут служить любой словарь иностранного языка, глоссарий и т. д.
Ассоциативные множества (словари) состоят из следующих типов:
• Класс HashTable. (это словарь, для доступа к элементам которого выполняется преобразование ключа, и доступ к элементам выполняется с помощью этого преобразованного ключа). Обобщенный вариант класса HashTable называется Dictionary. Имеется также класс SortedList и SortedDictionary.
• Множества HashSet<T> и SortedSet<T>, содержат списки, обычно строк, например, списки для реализации IntelliSense (Подсказка для выбора компонентов при разработке программ).
Класс HashTable — позволяет создавать коллекции, реализующие интерфейс ассоциативного множества, состоящих из пар <Ключ> → <Значение> и обеспечивающих выполнение операций, которые необходимы для работы с коллекцией.
Схематически хеш-таблицу можно представить в следующем виде:

Для каждой пары <Ключ> → <Значение> для заданного значения ключа вычисляется некоторое случайное число, которое играет роль индекса. Вводятся следующие предположения:
• Выделенная для коллекции память намного превышает действительный размер коллекции.
• Индексы для последовательных элементов не совпадают с порядком их следования.
• Сформированные индексы подчинены равномерному распределению.
Благодаря такой структуре коллекции практически не возникают проблемы, связанные с удалением и вставкой элементов, поскольку всегда можно найти место для вставки или исключения без перемещения остальных элементов.
Однако при генерации случайных чисел возможна ситуация, при которой будет сформирован уже существующий индекс. Вероятность такого события тем больше, чем больше коэффициент заполнения таблицы (load factor). Этот коэффициент определяется как отношение имеющихся в коллекции элементов к общему количеству элементов в коллекции.
При вставке элемента сначала проверяется, не совпадает ли вычисленный индекс с имеющимся. При совпадении отыскивается свободный индекс, который и закрепляется за ключом.
При удалении элемента его удаляют не сразу, а устанавливают флаг для пометки, что элемент удален. Тогда при добавлении очередного элемента, если снова будет получен этот индекс, ранее удаленный элемент заменяют новым.
Операции поиска, вставки и удаления элементов выполняются автоматическиавтоматически.
Для реализации словарей существует универсальный класс Dictionary<TKey, TValue>. При реализации словаря ключ не может быть пустым. Нельзя добавить в словарь значение, не задав ключ. Но для одного ключа может быть несколько значений (если оно является ссылочным значением), например, у одного абонента может быть несколько телефонов.
Ключи в словаре должны быть уникальны. Однако, понятие уникальности требует уточнений, поскольку понятие равенства не однозначно. Так слова могут отличаться строчными и заглавными буквами. Имеющиеся интерфейсы IEqualityComparer<T> и IEquatable<T> позволяют уточнить условие равенства.
Если создан пустой объект класса Dictionary<TKey, TValue> для добавления элементов в словарь применяется метод Add. При добавлении часто требуется проверка на совпадение нового ключа с существующим. Это можно выполнить несколькими способами. Пусть объявлен пустой словарь:
Dictionary<string, string> Dic = new Dictionary<string, string>();
В этот словарь добавляются строки:
Dic.Add("кошка", "ловит мышей");
Dic.Add("собака", "сторожит дом");
Тогда проверку отсутствия нового ключа при добавлении элемента требуется:
• Проверить добавление с помощью блока try-catch и обработать исключительную ситуацию ArgumentException. (в блок вставить соответствующий оператор)
• Использовать индексатор и с помощью блока try-catch обработать исключительную ситуацию KeyNotFoundException. Пример добавления
try
{
Dic.Add ["мышь"] = "вредитель".
}
catch (KeyNotFoundException) { действие}
• Использовать метод TryGetValue для проверки существования ключа. Пример
if (Dic.TryGetValue("кошка", out value)) // Найден
• Использовать метод ContainsKey для проверки существования ключа
if (!Dic.ContainsKey("корка")) // Не найден
В примере ниже показано, как выполнить перечисление ключей и значений в словаре, используя свойства Keys и Values класса KeyValuePair. Ключами являются фамилии, причем в файле нет дублирования фамилий. (Если фамилия будет продублирована, будет выдана исключительная ситуация ArgumentException)
class Program
{
class Block
{
public string sl;
public int skil;
public double wage;
public Block(string s, int k, double w)
{
sl = s;
skil = k;
wage = w;
}
}
static void Main(string[] args)
{
StreamReader file = new StreamReader
("C:\Temp\blockd.txt", Encoding.Default);
string s;
int sk;
double wg;
string[ ] str;
Dictionary<string, Block> proflst = new Dictionary<string, Block>();
while ((s = file.ReadLine()) != null)
{
str = s.Split( );
sk = int.Parse(str[2]);
wg = double.Parse(str[3]);
proflst.Add(str[0], new Block( str[1], sk, wg));
}
foreach (KeyValuePair<string, Block> kvp in proflst)
Console.WriteLine("{0,-12} {1,-8} {2} {3}",
kvp.Key, kvp.Value.sl, kvp.Value.skil, kvp.Value.wage);
Console.ReadKey();
}
При объявлении словаря типа Dictionary словарь не сортируется по ключу, и вывод будет иметь вид (сохранен порядок следования элементов в файле).

Если заменить строку объявления, записав вместо Dictionary сортированный список SortedList
SortedList<string, Block> proflst = new SortedList<string, Block>();
То вывод будет иметь вид. Список отсортирован по фамилиям.

Если объявлена переменная типа KeyValuePair (в примере kvp), с ее помощью можно вывести на экран только ключи, либо только значения. В нашем примере «значением» является объект класса Block, поэтому для обращения к полям этого класса применяется форма kvp.Value.skil. (первая точка для обращения к свойству Value объекта kvp, вторая точка к полю класса Block).