Подсчёт в словаре

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

Без словаря пришлось бы для каждого имени заново просматривать все голоса. Со словарём хватает одного прохода: каждый голос сразу добавляет палочку к своему имени.

Подсчёт за один проход

string[] votes = ["Ann", "Bob", "Ann", "Cid", "Ann", "Bob"];
var counts = new Dictionary<string, int>();
foreach (string name in votes)
{
    if (counts.ContainsKey(name))
    {
        counts[name]++;
    }
    else
    {
        counts[name] = 1;
    }
}
Console.WriteLine(counts["Ann"]); // 3
Console.WriteLine(counts["Bob"]); // 2

Давайте разберём, что делает программа:

1. Сначала counts пуст: имён на листке ещё нет.
2. Для каждого голоса цикл проверяет, есть ли уже такое имя среди ключей.
3. Если есть, counts[name]++ увеличивает его значение на единицу, то есть ставит ещё одну палочку.
4. Если нет, counts[name] = 1 заводит новую пару с первым голосом.
5. После цикла у Ann три голоса, а у Bob два.

Такой подсчёт лежит в основе многих задач с собеседований:

• найти самое частое слово;
• проверить, что две строки состоят из одних и тех же букв;
• найти первый неповторяющийся символ.

Словарь решает каждую за один-два прохода по данным. Решение с двумя вложенными циклами сравнивает каждый элемент с каждым: для 10 000 элементов это 100 миллионов сравнений, а один проход — 10 000 шагов.

Обход пар

Цикл foreach по словарю выдаёт пары. У каждой пары есть ключ Key и значение Value. Полная форма такого цикла выглядит так: foreach (KeyValuePair<string, int> pair in counts), а внутри цикла пишут pair.Key и pair.Value.

Короче получится, если сразу разложить пару на две переменные: var (name, count). Найдём победителя в словаре counts из первого примера:

string winner = "";
int best = 0;
foreach (var (name, count) in counts)
{
    if (count > best)
    {
        winner = name;
        best = count;
    }
}
Console.WriteLine($"{winner} {best}"); // Ann 3

Разберём цикл:

• foreach (var (name, count) in counts) на каждой итерации кладёт ключ пары в name, а значение — в count;
• если у имени больше голосов, чем у прежнего лидера, оно становится новым победителем.

Здесь листок и словарь расходятся. На листке строки стоят в том порядке, в каком вы их писали, а словарь такого порядка не обещает. Победителю это не мешает: с тремя голосами он один, в каком бы порядке ни пришли пары. А при ничьей победителем стал бы тот, кого цикл встретит первым, и этот порядок словарь не гарантирует.

Один вызов: GetValueOrDefault

Проверку ContainsKey можно спрятать в один вызов. GetValueOrDefault(name) возвращает значение по ключу, а если ключа нет, то значение по умолчанию, которое для int равно 0:

string[] votes = ["Ann", "Bob", "Ann"];
var counts = new Dictionary<string, int>();
foreach (string name in votes)
{
    counts[name] = counts.GetValueOrDefault(name) + 1;
}
Console.WriteLine(counts["Ann"]); // 2
Console.WriteLine(counts["Bob"]); // 1

Цикл читает текущее число голосов или 0 и записывает число на единицу больше. Новое имя получает 1, знакомое — ещё один голос.

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

Голос прибавили, не проверив, есть ли уже такой ключ:

string[] votes = ["Ann", "Bob"];
var counts = new Dictionary<string, int>();
foreach (string name in votes)
{
    counts[name]++; // ✗
}

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

Программа компилируется, но на первом же голосе останавливается с исключением KeyNotFoundException. counts[name]++ сначала читает значение по ключу, а ключа Ann ещё нет. Новое имя нужно сначала завести: через проверку ContainsKey или через GetValueOrDefault, как в примерах выше.

Главное

• Словарь считает за один проход: ключ — то, что считаем; значение — сколько раз оно встретилось.
• counts[key]++ работает только для существующего ключа; новый ключ заводят через ContainsKey или GetValueOrDefault.
• foreach по словарю выдаёт пары с Key и Value, а var (name, count) раскладывает пару на две переменные.
• Порядок пар в словаре не гарантирован, поэтому результат не должен от него зависеть.