Как работает Dictionary?

Как работает Dictionary<TKey, TValue> в C#

Dictionary<TKey, TValue> — это коллекция, реализующая интерфейс IDictionary<TKey, TValue> и представляющая собой хэш-таблицу (hash table). Он хранит данные в виде пар ключ-значение, обеспечивая быстрый поиск, добавление и удаление элементов, основанный на уникальных ключах. Его производительность в идеальных условиях близка к O(1) (константное время) для основных операций.

Внутренняя структура и механизм работы

В основе Dictionary лежат три ключевых массива:

1. int[] buckets — содержит индексы на элементы в массиве entries. Это "корзины" хэш-таблицы.
2. Entry[] entries — хранит сами данные: ключ, значение, следующую запись в корзине (для разрешения коллизий) и хэш-код.
3. Служебные переменные для управления размером и счетчик свободных entries.

Entry — это внутренняя структура:

private struct Entry
{
    public int hashCode;    // Хэш-код ключа (может быть отрицательным)
    public int next;        // Индекс следующей Entry в той же корзине (-1, если последняя)
    public TKey key;        // Ключ элемента
    public TValue value;    // Значение элемента
}

Ключевые этапы операций

1. Добавление элемента (Add или установка через индексатор)

• Вычисляется хэш-код ключа через метод GetHashCode() (или компаратор, если задан в конструкторе).
• Хэш-код преобразуется в индекс корзины (bucket). Например: bucketIndex = hashCode % buckets.Length.
• Проверяется корзина по этому индексу:

    *   Если она пуста (`buckets[bucketIndex] == -1`), запись помещается в первую свободную позицию в `entries`, и индекс этой записи сохраняется в корзине.
    *   Если корзина занята (уже есть записи), происходит **перебор связного списка** внутри корзины (через поле `next` в Entry) для проверки **коллизий** по хэш-коду и, если нужно, по ключу (через `Equals`). Если ключ найден — исключение (для `Add`) или перезаписывается значение (для индексатора). Если не найден — новая запись добавляется в конец списка корзины и в `entries`.

2. Поиск значения по ключу (TryGetValue или индексатор)

• Вычисляется хэш-код и индекс корзины.
• Происходит последовательный поиск в связном списке этой корзины, сравнивая сначала хэшКод, а затем (при совпадении хэшей) сам ключ через Equals.
• Если найдено — возвращается значение. Если не найдено — возвращается false (для TryGetValue) или исключение (для индексатора).

3. Удаление элемента (Remove)

• Находится запись через тот же механизм поиска по ключу.
• Запись маркируется как удаленная (поле key устанавливается в специальное значение, а next может указывать на следующую свободную запись для оптимизации). Корзина и цепочки перестраиваются.
• Физически запись не сразу удаляется из массива entries, чтобы избежать дорогостоящего сдвига элементов.

Обработка коллизий и важные особенности

• Коллизии (когда разные ключи дают одинаковый индекс корзины) разрешаются через связные списки внутри корзины (chaining). Это отличается от открытой адресации.
• При высоком уровне коллизий производительность снижается до O(n) в худшем случае (все ключи в одной корзине).
• Качество хэш-функции ключа критично. Хорошая реализация GetHashCode() должна давать равномерное распределение и быть быстрой.
• Равенство ключей определяется сначала по hashCode, а затем по методу Equals. Поэтому важно, чтобы Equals и GetHashCode были согласованы: равные ключи должны давать одинаковый хэш.
• Резервирование (resizing). Когда количество элементов превышает определенный порог (связь с buckets.Length), происходит автоматическое увеличение размеров массива buckets и entries. Все элементы перехешируются и перемещаются в новые корзины. Это операция O(n), поэтому важно задавать предполагаемую начальную емкость (capacity) в конструкторе, если она известна, чтобы минимизировать ресайзы.

Пример использования и ключевые свойства

// Создание Dictionary с начальной емкостью 10
var dict = new Dictionary<string, int>(10);

// Добавление элементов
dict.Add("apple", 5);
dict["banana"] = 3;

// Поиск элемента (без исключения)
if (dict.TryGetValue("apple", out int count))
{
    Console.WriteLine($"Apple count: {count}");
}

// Удаление элемента
dict.Remove("banana");

// Итерация по элементам
foreach (var kvp in dict)
{
    Console.WriteLine($"Key: {kvp.Key}, Value: {kvp.Value}");
}

// Важные свойства:
Console.WriteLine($"Count: {dict.Count}"); // Текущее количество элементов
Console.WriteLine($"Comparer: {dict.Comparer}"); // Компаратор, используемый для ключей

Отличия от аналогичных коллекций

• Hashtable (устаревший, негенерический) — похожая хэш-таблица, но работает с объектами object, требует боксинг/анбоксинг и менее эффективна.
• SortedDictionary<TKey, TValue> — основан на бинарном дереве поиска, поддерживает порядок ключей, но операции O(log n).
• ConcurrentDictionary<TKey, TValue> — потокобезопасная версия для многопоточных сценариев.

Таким образом, Dictionary в C# — это высокооптимизированная хэш-таблица с разрешением коллизий через связные списки, обеспечивающая исключительно высокую скорость операций при условии хорошего хэширования ключей и умеренного уровня коллизий. Его внутренняя структура массивами buckets и entries позволяет эффективно управлять памятью и производительностью.