Как устроены List и Dictionary

«Чем List отличается от массива и почему поиск в Dictionary быстрый?» — вопрос-разминка. А сразу за ним идёт вопрос-ловушка: «А что будет, если изменить ключ после того, как он попал в словарь?»

List<T> — динамический массив: элементы лежат в памяти подряд, доступ по индексу за O(1), добавление в конец амортизированно за O(1). Dictionary<TKey, TValue> — хеш-таблица: позиция элемента вычисляется из GetHashCode() ключа, поэтому поиск в среднем за O(1) независимо от размера.

Это две рабочие лошадки, на которых написано процентов девяносто всего C#-кода. Интервьюер спрашивает про них не для того, чтобы услышать заученное «лист — это список». Он проверяет, понимаете ли вы, что за list.Add(x) иногда прячется копирование всего массива, а за dict[key] — вызов вашего собственного GetHashCode(), который вы могли написать криво.

Разминка: что выведет этот код?

Не подглядывая в вывод, попробуйте ответить: сколько раз изменится Capacity, пока мы добавляем двадцать чисел?

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var list = new List<int>();
        int capacity = list.Capacity;
        Console.WriteLine($"Старт: Count={list.Count}, Capacity={list.Capacity}");

        for (int i = 0; i < 20; i++)
        {
            list.Add(i);
            if (list.Capacity != capacity)
            {
                capacity = list.Capacity;
                Console.WriteLine($"После Add({i}): Count={list.Count}, Capacity={capacity}");
            }
        }
    }
}

Результат:

Старт: Count=0, Capacity=0
После Add(0): Count=1, Capacity=4
После Add(4): Count=5, Capacity=8
После Add(8): Count=9, Capacity=16
После Add(16): Count=17, Capacity=32

Здесь важны две вещи. Первая: Count и Capacity — разные числа. Count — сколько элементов вы положили, Capacity — сколько мест зарезервировано во внутреннем массиве T[] _items. Пустой список не выделяет память вообще (ёмкость 0), при первом Add берёт массив на 4 элемента, а дальше при каждом переполнении удваивает ёмкость: 4 → 8 → 16 → 32.

Вторая: удвоение — это не «магическое расширение». Рантайм создаёт новый массив вдвое больше и копирует туда старые элементы через Array.Copy. Одна такая операция стоит O(n). Но происходит она всё реже и реже, и если размазать стоимость по всем добавлениям, получится константа — это и называется амортизированной сложностью O(1). Именно так и стоит отвечать: «Add — амортизированно O(1), в момент расширения — O(n)».

Практический вывод, который любит слышать интервьюер: если вы заранее знаете размер, передайте его в конструктор — new List<int>(10000). Это убирает все промежуточные копирования и мусор для сборщика.

Вопрос-ловушка про Dictionary и GetHashCode

А теперь классика, на которой сыпется большинство. Запустите и объясните, куда делся элемент.

using System;
using System.Collections.Generic;

class Box
{
    public int Value;

    public override int GetHashCode() => Value.GetHashCode();
    public override bool Equals(object obj) => obj is Box other && other.Value == Value;
}

class Program
{
    static void Main()
    {
        var dict = new Dictionary<Box, string>();
        var key = new Box { Value = 1 };

        dict[key] = "первый";
        Console.WriteLine($"ContainsKey до мутации:    {dict.ContainsKey(key)}");

        key.Value = 42;   // меняем поле, от которого зависит хеш

        Console.WriteLine($"ContainsKey после мутации: {dict.ContainsKey(key)}");
        Console.WriteLine($"Записей в словаре: {dict.Count}");

        foreach (var pair in dict)
            Console.WriteLine($"  внутри всё ещё лежит ключ Value={pair.Key.Value} => {pair.Value}");
    }
}

Результат:

ContainsKey до мутации:    True
ContainsKey после мутации: False
Записей в словаре: 1
  внутри всё ещё лежит ключ Value=42 => первый

Элемент никуда не пропал — Count по-прежнему 1, и перечисление его показывает. Но найти его больше нельзя тем же самым объектом-ключом. Почему? Словарь при вставке посчитал хеш (1), вычислил номер корзины и положил запись туда. Мы изменили поле — хеш стал 42, номер корзины другой. Словарь идёт искать в новую корзину, не находит ничего и честно отвечает «нет такого ключа». Получилась утечка: память занята, а данные недостижимы.

Отсюда железное правило: ключ словаря должен быть иммутабельным — по крайней мере, в той части, что участвует в хешировании. Поэтому string, int, Guid и record-типы — отличные ключи, а изменяемый класс с публичными полями — источник багов.

Контракт GetHashCode и Equals

• Равные объекты обязаны давать равный хеш. Обратное неверно: разные объекты могут случайно совпасть по хешу — это коллизия, и она допустима.
• Переопределили Equals — переопределите и GetHashCode. Иначе получите объект, который «равен» другому, но лежит в другой корзине, и словарь его не найдёт.
• Хеш не должен меняться, пока объект живёт в коллекции.
• Не пишите хеш руками — используйте HashCode.Combine(Name, Age). Он даёт хорошее распределение и защищает от наивного Name.GetHashCode() + Age, где ("a", 1) и ("a", 1) ещё совпадут, но и куча несвязанных пар тоже.

Как это работает под капотом

Dictionary<TKey, TValue> внутри — это не «массив списков», как рисуют в учебниках, а два массива:

• int[] buckets — по номеру корзины хранит индекс первой записи в цепочке;
• Entry[] entries — сами записи: hashCode, next (индекс следующей записи в той же цепочке), key, value.

Поиск выглядит так: посчитали hash = key.GetHashCode(), взяли остаток от деления на размер buckets, получили корзину, прошли по цепочке через next и на каждом шаге сравнили сначала сохранённый hashCode (дешёвое сравнение int), а уже потом — Equals. Пока цепочки короткие, это несколько операций: O(1). Если GetHashCode возвращает, скажем, всегда 0, все записи улягутся в одну цепочку, и словарь деградирует до линейного списка — O(n). Это и есть «плохой хеш» в терминах собеседования.

Когда записей становится больше, чем корзин, словарь расширяется: берёт новый размер (простое число), заново раскидывает всё по корзинам — операция O(n). Как и у списка, она редкая и амортизируется.

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

Сложность операций — таблица для ответа

И сразу практическое правило выбора: перебираете и обращаетесь по индексу — List. Ищете по ключу — Dictionary. Проверяете «есть ли такой элемент» — HashSet. Классический антипаттерн, который вылавливают на код-ревью: foreach по списку из десяти тысяч элементов внутри другого foreach — это O(n²), тогда как один ToDictionary превращает задачу в O(n).

Частые ошибки на собеседовании

• Путать Count и Capacity. Ответ «Add работает за O(1)» без оговорки про амортизацию звучит как заученный.
• Говорить, что Dictionary всегда O(1). В худшем случае, при плохом хеше, — O(n). Правильная формулировка: «в среднем O(1)».
• Переопределить Equals и забыть GetHashCode. Компилятор выдаст предупреждение, а словарь молча перестанет находить объекты.
• Использовать изменяемый объект как ключ — и потерять запись, как в примере выше.
• Считать LinkedList быстрым. Формально вставка O(1), но на практике из-за разбросанных по памяти узлов и промахов кеша он почти всегда проигрывает List. Это хороший «продвинутый» довод, который выделяет кандидата.

Итоги-шпаргалка

• List<T> — обёртка над массивом; ёмкость удваивается (0 → 4 → 8 → 16…), при расширении массив копируется целиком.
• Индекс — O(1), поиск и вставка в середину — O(n), добавление в конец — амортизированно O(1).
• Dictionary — хеш-таблица на двух массивах (buckets + entries), поиск в среднем O(1), в худшем — O(n).
• GetHashCode определяет корзину, Equals разрешает коллизии. Оба переопределяем вместе, хеш собираем через HashCode.Combine.
• Ключ обязан быть иммутабельным: мутация ключа = потерянная запись.
• Порядок перечисления словаря не гарантирован.