Коллекции и LINQ: урок по C# и .NET к собеседованию

Коллекции и LINQ встречаются и в теории, и в live-coding. Нужно понимать, как устроены List и Dictionary, и не попадаться на отложенное выполнение.

List<T>

Внутри массив. Add в среднем O(1): когда массив заполнен, создаётся новый вдвое больше, и элементы копируются. Доступ по индексу O(1), вставка и удаление в начале O(n), Contains O(n). Если размер известен, задайте ёмкость: new List<int>(10_000).

Индексатор возвращает копию элемента-структуры, поэтому list[0].X = 1 не скомпилируется.

Dictionary<TKey, TValue> и HashSet<T>

Хеш-таблица: массив бакетов и массив записей с цепочками. Поиск, вставка, удаление в среднем O(1). Требования к ключу:

корректные Equals и GetHashCode (равные объекты дают равный хеш);
ключ не меняется, пока лежит в словаре, иначе его не найти.

TryGetValue вместо ContainsKey + индексатор: один поиск вместо двух. Для строк задавайте компаратор: new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase).

Не потокобезопасны. Для конкуренции ConcurrentDictionary, для неизменяемых справочников FrozenDictionary (.NET 8).

Другие коллекции

Queue<T>, Stack<T>: FIFO и LIFO.
SortedDictionary, SortedSet: красно-чёрное дерево, O(log n), упорядочены.
PriorityQueue<TElement, TPriority> (.NET 6): min-куча.
LinkedList<T>: удаление по узлу O(1), полезен для LRU-кеша.

IEnumerable и отложенное выполнение

Большинство операторов LINQ возвращают описание запроса, а не результат:

var list = new List<int> { 1, 5, 7 };
var q = list.Where(x => x > 2);   // ничего не выполнено
list.Add(10);
Console.WriteLine(q.Count());     // 3: запрос выполнен сейчас

Отложенные: Where, Select, OrderBy, GroupBy, Skip, Take, Distinct. Немедленные: ToList, ToArray, ToDictionary, Count, Sum, First, Any.

Каждое перечисление выполняет запрос заново. Если передать запрос дальше и вызвать Any(), Count() и foreach, работа повторится три раза. Материализуйте через ToList(), если нужен результат несколько раз.

Лямбды захватывают переменные, а не значения: изменили переменную до перечисления, запрос увидит новое значение.

IEnumerable против IQueryable

IQueryable<T> хранит дерево выражений, которое провайдер (EF Core) переводит в SQL. Если метод возвращает IEnumerable<T>, дальнейшие Where выполнятся в памяти, после загрузки всей таблицы. Это одна из самых дорогих ошибок в бэкенде на .NET.

Полезные операторы

orders.GroupBy(o => o.CustomerId)
      .Select(g => new { g.Key, Total = g.Sum(o => o.Amount) })
      .OrderByDescending(x => x.Total)
      .ThenBy(x => x.Key)
      .Take(10);

var byUser = orders.ToLookup(o => o.UserId);   // индекс для LEFT JOIN в памяти
words.Distinct(StringComparer.OrdinalIgnoreCase);
people.MaxBy(p => p.Age);                       // .NET 6
items.Chunk(100);                               // .NET 6, пакеты по 100

First бросает исключение на пустой последовательности, FirstOrDefault вернёт default. Single проверяет, что элемент ровно один. OrderBy стабилен, List.Sort нет.

Изменение коллекции во время перебора

foreach по List<T> с Remove внутри бросит InvalidOperationException. Используйте RemoveAll(predicate) или обратный цикл for.

Частые ошибки

ToList() до Where в запросах EF Core.
Многократное перечисление тяжёлого IEnumerable.
list.Contains в цикле вместо HashSet: O(n²).
Count() > 0 вместо Any().
Сортировка строк без указания компаратора.

Что спросят на собесе

Как устроены List<T> и Dictionary и какова сложность операций?
Что такое отложенное выполнение LINQ и какие операторы немедленные?
Чем IEnumerable отличается от IQueryable?
Что будет, если изменить ключ, лежащий в HashSet?
Чем First, Single и их OrDefault-варианты отличаются?

Коллекции и LINQ