Теория · Списки, словари и множества · урок 6 из 10

Словарь Dictionary

Представьте телефонный справочник офиса. Рядом с каждым именем стоит внутренний номер: у Анны — 101, у Боба — 102. Чтобы позвонить Бобу, вы не листаете справочник с первой страницы, а сразу открываете его на букве «Б».

Со списком так не получится. Чтобы найти номер по имени, пришлось бы держать два списка, имён и номеров, и искать имя через IndexOf, проверяя элементы по одному.

Для поиска по имени в .NET есть словарь — набор пар, где по ключу находится значение. Это тип Dictionary<TKey, TValue>. В справочнике имя служит ключом, а номер — значением:

var phones = new Dictionary<string, int>();
phones["Ann"] = 101;
phones["Bob"] = 102;
Console.WriteLine(phones["Bob"]); // 102
Console.WriteLine(phones.Count);  // 2

Давайте разберём программу по строкам:

Dictionary<string, int> — словарь с ключами string и значениями int. У этого обобщённого типа два параметра типа: тип ключа и тип значения.
phones["Ann"] = 101; кладёт пару: ключ Ann, значение 101.
phones["Bob"] находит значение по ключу, и программа печатает 102.
Count — число пар в словаре: 2.

Ключи в словаре не повторяются: у одного имени один номер. А значения повторяться могут: два человека могут сидеть у одного телефона.

Как положить значение

Через индексатор

Индексатор вы уже видели у списка: guests[0]. У словаря в квадратных скобках стоит ключ, а не индекс: phones["Ann"]. Присваивание phones["Ann"] = 101 кладёт пару, если ключа ещё нет, и заменяет значение, если ключ уже есть.

Через `Add`

phones.Add("Ann", 101) только добавляет новую пару. Если такой ключ уже есть, программа остановится с исключением ArgumentException.

var phones = new Dictionary<string, int>();
phones.Add("Ann", 101);
phones["Ann"] = 199;
Console.WriteLine(phones["Ann"]); // 199
Console.WriteLine(phones.Count);  // 1

Add положил пару, а индексатор заменил значение у того же ключа. Пара осталась одна, поэтому Count равен 1.

Как прочитать значение

Индексатор находит значение по ключу. Если ключа нет, он не возвращает 0, а останавливает программу. Вот что сообщает программа, когда читает phones["Cid"], а ключа Cid в словаре нет:

TEXT

Unhandled exception. System.Collections.Generic.KeyNotFoundException: The given key 'Cid' was not present in the dictionary.

Когда ключа может не оказаться, его сначала проверяют. Для этого у словаря есть два метода:

ContainsKey(key) отвечает, есть ли такой ключ: true или false;
TryGetValue(key, out value) ищет ключ один раз и при успехе кладёт значение в out-переменную, как int.TryParse.

var phones = new Dictionary<string, int>();
phones["Ann"] = 101;
Console.WriteLine(phones.ContainsKey("Ann")); // True
Console.WriteLine(phones.ContainsKey("ann")); // False
if (phones.TryGetValue("Ann", out int number))
{
    Console.WriteLine(number); // 101
}
Console.WriteLine(phones.TryGetValue("Cid", out int none)); // False
Console.WriteLine(none);                 // 0
Console.WriteLine(phones.Remove("Ann")); // True
Console.WriteLine(phones.Count);         // 0

Разберём по шагам:

ContainsKey("Ann") находит ключ и возвращает true.
ContainsKey("ann") возвращает false: ключи-строки сравниваются с учётом регистра, поэтому Ann и ann — разные ключи.
TryGetValue("Ann", …) находит ключ, возвращает true и кладёт 101 в number.
Ключа Cid нет: TryGetValue возвращает false, а в none кладёт значение по умолчанию, которое для int равно 0.
Remove удаляет пару и возвращает true, потому что ключ был.

Как словарь находит ключ

Почему словарь не листает пары по одной? По ключу он вычисляет число — хеш — и по этому числу сразу идёт к небольшой группе пар, где может лежать ключ. Так справочник открывают сразу на нужной букве.

Поэтому поиск по ключу занимает почти одно и то же время и в словаре из десяти пар, и в словаре из миллиона. А IndexOf в списке проверяет элементы по одному, и чем длиннее список, тем дольше поиск. На собеседовании часто спрашивают, почему поиск в Dictionary быстрее, чем в List: ответ — хеш.

Здесь справочник и словарь расходятся. В справочнике имена стоят по алфавиту, а словарь не обещает никакого порядка пар. Если обойти его в цикле, пары придут в порядке, на который нельзя полагаться.

Частая ошибка

Номер попробовали поменять повторным Add:

var phones = new Dictionary<string, int>();
phones.Add("Ann", 101);
phones.Add("Ann", 199); // ✗