Соответствие ключ — значение

Мы разобрали, как хеш-таблица разрешает коллизии: цепочки, открытая адресация, расширение массива. Но всё это было про механику — про то, как элементы физически раскладываются по корзинам. Теперь посмотрим на словарь с другой стороны: не как на устройство, а как на абстракцию. Что он обещает, какие операции предоставляет, какие гарантии даёт и чего не гарантирует. Именно контракт, а не внутреннее устройство, определяет, как словарём пользоваться и чего от него ожидать.

Словарь — это соответствие ключей значениям. У каждого ключа есть ровно одно значение, и по ключу это значение можно получить. Значения при этом могут повторяться: у двух разных ключей может быть одинаковое значение, это нормально. А вот ключи уникальны — по выбранному определению равенства. В множестве, которое мы разбирали в 2.6, хранились только ключи, без значений. Словарь — это следующий шаг: у каждого ключа теперь есть связанное с ним значение.

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

Пусть у нас есть склад, и мы ведём учёт остатков по артикулам. Артикулы — строки вроде «A-10», «B-20». По каждому артикулу хранится число — сколько единиц на складе. Нам нужно уметь пополнять запас, добавлять новые артикулы, проверять остаток и отличать «остаток равен нулю» от «такого артикула нет».

Договоримся, что артикулы сравниваются без учёта регистра: «A-10» и «a-10» — один и тот же артикул. Это разумно: при ручном вводе регистр может отличаться, а товар тот же. В C# для этого есть готовый компаратор StringComparer.OrdinalIgnoreCase, который согласованно применяет одинаковое правило и к равенству, и к хешу. Мы не разбираем его реализацию — нам достаточно того, что он делает то, что нам нужно.

Программа

Соберём программу. Начнём с двух артикулов: «A-10» с остатком 5 и «B-20» с остатком 0. Затем пополним «a-10» на 3 и добавим новый «C-30» на 2. Посмотрим, как при этом ведёт себя словарь, какие операции возвращают какие результаты и как отличить отсутствующий артикул от нулевого остатка.

using System;
using System.Collections.Generic;

var stock = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
stock["A-10"] = 5;
stock["B-20"] = 0;

Restock(stock, "a-10", 3);
Restock(stock, "C-30", 2);

string[] order = { "A-10", "B-20", "C-30", "D-40" };
foreach (string article in order)
{
    if (stock.TryGetValue(article, out int qty))
    {
        Console.WriteLine(article + " остаток " + qty);
    }
    else
    {
        Console.WriteLine(article + " нет на складе");
    }
}

Console.WriteLine(stock.Remove("B-20"));
Console.WriteLine(stock.Remove("B-20"));
Console.WriteLine(stock.Count);

try
{
    stock.Add("A-10", 100);
}
catch (ArgumentException)
{
    Console.WriteLine("Повторный Add: исключение");
}

bool added = stock.TryAdd("A-10", 100);
Console.WriteLine("TryAdd " + added);
Console.WriteLine(stock["A-10"]);

stock["A-10"] = 50;
Console.WriteLine(stock["A-10"]);

void Restock(Dictionary<string, int> s, string key, int quantity)
{
    if (key == null) throw new ArgumentNullException(nameof(key));
    if (quantity < 0) throw new ArgumentOutOfRangeException(nameof(quantity));
    s.TryGetValue(key, out int current);
    s[key] = checked(current + quantity);
}

Вывод:

A-10 остаток 8
B-20 остаток 0
C-30 остаток 2
D-40 нет на складе
True
False
2
Повторный Add: исключение
TryAdd False
8
50

Разберём по шагам. После создания словаря и первичных установок: «A-10» = 5, «B-20» = 0. Функция Restock для «a-10» с количеством 3: ключ распознаётся как равный «A-10» благодаря компаратору, TryGetValue находит текущее значение 5, и в словарь записывается 5 + 3 = 8. Restock для «C-30»: TryGetValue не находит ключ, out current получает default 0, и в словарь записывается 0 + 2 = 2. Функция единообразно работает и для существующих, и для новых артикулов: если ключа нет, начальный остаток считается нулём.

Печатаем в заданном порядке. «A-10» — остаток 8. «B-20» — остаток 0, и это именно ноль на складе, а не отсутствие. «C-30» — остаток 2. «D-40» — TryGetValue вернул false, значит, артикула нет. Обратите внимание, как мы различаем ноль и отсутствие: оба случая дают qty = 0, но TryGetValue в первом случае возвращает true, а во втором — false. Опираться на одно только значение нельзя; именно результат TryGetValue несёт информацию о наличии ключа.

Remove(«B-20») возвращает true, удаляя артикул. Повторный Remove возвращает false: удалять нечего. Count становится 2: остались «A-10» и «C-30».

Повторный Add(«A-10», 100) вызывает исключение. Это документированное поведение Add: если ключ уже есть, он не перезаписывает значение, а сигнализирует об ошибке. Есть и более мягкий вариант — TryAdd, который возвращает false, не выбрасывая исключение. Мы проверяем: TryAdd(«A-10», 100) возвращает false, и значение «A-10» остаётся прежним — 8.

Наконец, indexer: stock["A-10"] = 50. Это не Add, а именно присваивание по индексу: если ключ есть, значение заменяется; если ключа нет — он создаётся. У нас ключ есть, и 8 заменяется на 50.

Соберём воедино, что обещают основные операции, потому что именно в этом и состоит контракт словаря.

Установка по индексу, stock[key] = value: если ключ есть, значение заменяется; если нет — создаётся новая пара. Повторный ключ при присваивании не является ошибкой; null-ключ для этого словаря недопустим.

Add(key, value): добавляет только новый ключ. Если ключ уже есть, выбрасывает исключение. Это полезно, когда случайная перезапись была бы ошибкой: мы явно хотим знать, что ключ уже занят.

TryAdd(key, value): как Add, но без исключения: возвращает true, если добавил, false, если ключ уже есть.

TryGetValue(key, out value): возвращает true и значение, если ключ есть; false и default, если ключа нет. Удобно тем, что не делает двух поисков, как было бы при ContainsKey + indexer. Одна операция — один ответ. Контракты методов описаны в документации Dictionary.

Remove(key): возвращает true, если ключ был и удалён; false, если ключа не было.

Важно: отсутствие ключа не то же самое, что значение по умолчанию. Для int значение по умолчанию — ноль, но ноль может быть и настоящим значением. Различать эти случаи можно только через результат TryGetValue, ContainsKey или сам факт возврата из Remove. Не стоит полагаться на «если значение равно default, значит, ключа нет»: это ошибка.

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

Порядок обхода

Ещё одно свойство, о котором полезно помнить: порядок обхода словаря не является частью контракта. В разных реализациях и в разных ситуациях элементы могут перебираться в разном порядке. В нашем примере мы печатали артикулы в заданном порядке — «A-10», «B-20», «C-30», «D-40», — потому что задали этот порядок явно через массив. Полагаться на то, что обход Dictionary даст ключи в порядке вставки или в алфавитном порядке, не стоит: это не гарантируется. Если порядок важен, его задают отдельно — например, хранят список ключей рядом со словарём.

В разных языках и разных библиотеках контракты порядка и поведения при отсутствии ключа могут отличаться. Кто-то возвращает специальный объект, кто-то выбрасывает исключение, кто-то поддерживает порядок вставки. Мы не обещаем, что везде будет одинаково: важно знать контракт той конкретной структуры, которой вы пользуетесь. В C# Dictionary порядок обхода не документирован как стабильный, и на это не стоит опираться.

В ожидаемом случае операции с словарём — поиск и удаление — выполняются за O(1), а добавление — за O(1) амортизированно с учётом расширений при условии, что хеш-функция распределяет ключи равномерно, а таблица достаточно просторна. Слово «ожидаемо» здесь важно: как и в методе цепочек из прошлого урока, при неудачном распределении все ключи могут попасть в одну корзину, и операции станут линейными. Хорошая хеш-функция и разумный порог расширения делают это маловероятным, но не невозможным.

Отдельно про ключи. Если ключ — строка длины L, то вычисление хеша занимает O(L), и это не зависит от размера таблицы. Значит, «O(1)» относится к числу записей, а не к длине ключа. Для коротких ключей это незаметно, для длинных может быть существенно. Обычно ключи стараются делать компактными.

Память — O(n) записей плюс сами ключи и значения. Каждая пара занимает место в корзине и в хранимых данных. Если ключи длинные, память под них может оказаться значительной частью общего расхода.

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