Developer

Массивы, List, Dictionary, HashSet, Queue, Stack

↑ 1.5 Коллекции и основы LINQ · → Следующая

Обязательно~6 мин чтенияУровень: junior

Зачем это на собесе

Коллекции — самый частый повод спросить про сложность и внутреннее устройство. Ждут понимания, как работает List<T> (рост буфера), Dictionary (хэш-таблица, корзины), чем HashSet отличается от List, когда нужна очередь или стек, и что такое инвариантность порядка.

Объяснение

Массив T[]

Фиксированная длина, элементы лежат в непрерывном блоке памяти, доступ по индексу за O(1). Ссылочный тип: сам массив в куче, даже если элементы значимые.

int[] a = new int[5];              // все нули
var b = new[] { 1, 2, 3 };
int[,] grid = new int[3, 4];       // многомерный
int[][] jagged = new int[3][];     // «рваный»: массив массивов, обычно быстрее
Span<int> slice = b.AsSpan(1, 2);  // срез без копирования

Изменить длину нельзя: Array.Resize создаёт новый массив и копирует.

List<T>

Динамический массив: внутри T[] и счётчик. Когда буфер заполнен, размер удваивается (копирование за O(n), амортизированно добавление в конец O(1)).

var list = new List<int>(capacity: 1000);   // заранее задать ёмкость, если известен размер
list.Add(1);
list.Insert(0, 5);        // O(n): сдвигает элементы
list.RemoveAt(0);         // O(n)
list.Contains(42);        // O(n)
list.Sort();              // O(n log n)
  • Индексатор O(1); добавление в конец амортизированно O(1); вставка/удаление в середине O(n).
  • Изменение списка во время foreach даёт InvalidOperationException (версионирование перечислителя).

Dictionary<TKey, TValue>

Хэш-таблица: GetHashCode ключа выбирает корзину, внутри корзины сравнение через Equals. Поиск, вставка, удаление в среднем O(1).

var map = new Dictionary<string, Patient>(StringComparer.OrdinalIgnoreCase);
map["A1"] = patient;                              // добавить или заменить
map.TryAdd("A1", other);                          // false, если ключ уже есть
if (map.TryGetValue("A1", out var p)) { ... }     // предпочтительнее, чем ContainsKey + индексатор
map.GetValueOrDefault("B2");
  • map["нет"] бросает KeyNotFoundException, а не возвращает null.
  • Порядок перебора формально не гарантирован (на практике — порядок вставки, пока не было удалений).
  • Ключ должен корректно реализовывать Equals/GetHashCode (см. тему про равенство) и не меняться.
  • SortedDictionary — дерево, O(log n), упорядоченный по ключу. ConcurrentDictionary — для многопоточности.

HashSet<T>

Набор уникальных элементов, проверка Contains за O(1) в среднем. Есть теоретико-множественные операции.

var seen = new HashSet<Guid>();
if (!seen.Add(id)) { /* дубликат */ }
a.UnionWith(b); a.IntersectWith(b); a.ExceptWith(b);

Классическая замена List.Contains в циклах: O(n·m) превращается в O(n+m).

Queue<T> и Stack<T>

  • Queue<T> — FIFO: Enqueue, Dequeue, Peek, все операции O(1). Кольцевой буфер.
  • Stack<T> — LIFO: Push, Pop, Peek, O(1). Применение: обход графа в глубину, отмена операций, разбор скобок.
  • PriorityQueue<TElement, TPriority> (с .NET 6) — извлечение элемента с минимальным приоритетом за O(log n).
  • Для потокобезопасного варианта — ConcurrentQueue<T>, Channel<T>.

Ещё пригодятся

  • LinkedList<T> — двусвязный список: вставка и удаление O(1) по узлу, но поиск O(n) и плохая локальность кэша; на практике редко выигрывает у List<T>.
  • SortedSet<T>, SortedList — упорядоченные структуры на деревьях/массивах.
  • ImmutableArray<T>, ImmutableList<T> — неизменяемые коллекции.
  • Коллекции-выражения C# 12: List<int> xs = [1, 2, 3];, int[] ys = [..xs, 4];.

Нюансы и подводные камни

  • List<T>.Contains в цикле по большому списку — типичный источник O(n²). Заменяйте на HashSet/Dictionary.
  • Не задана capacity для больших списков: многократные копирования при росте.
  • Изменение коллекции при её перечислении — исключение; собирайте изменения отдельно или итерируйтесь по копии (ToList()).
  • Dictionary не потокобезопасен: одновременная запись из потоков может зациклить или повредить структуру. Нужен ConcurrentDictionary или блокировка.
  • Изменяемый ключ (объект, у которого меняется поле, влияющее на хэш) делает запись недостижимой.
  • Массив ковариантен по ссылочным типам: object[] o = new string[1]; o[0] = 1; компилируется и падает ArrayTypeMismatchException в рантайме.

Практика

  • Дан список из миллиона идентификаторов и список из ста тысяч: найти пересечение за линейное время.
  • Реализовать LRU-кэш на Dictionary + LinkedList.
  • Проверить корректность скобок в строке через Stack<char>.

Вопросы с ответами

Связанные темы

Вид графа

Обратные ссылки