C# Academy · Урок

Выбор коллекции

Компромиссы и производительность.

«Выбор коллекции» — бесплатный урок C# Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C# Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C# Academy содержит 4 уроков всего.

Сначала один вопрос

Выбор коллекции начинается с одного вопроса: как вы будете обращаться к данным — по позиции, по ключу или только проверять наличие?

List, Dictionary и HashSet предназначены для разных способов доступа. Подберите инструмент под задачу — и код останется быстрым и понятным.

Доступ по позиции: список

Если важен порядок и вы обращаетесь к элементам по индексу, выберите List<T>. Он сохраняет порядок добавления и обеспечивает индексацию за O(1).

Примеры: очередь шагов (steps), строки в порядке отображения или любая последовательность, которую вы перебираете от начала до конца. Дубликаты разрешены.

var steps = new List<string> { "mix", "bake", "cool" };
string first = steps[0]; // O(1) by index

Доступ по ключу: словарь

Если вы ищете объекты по уникальному идентификатору (unique), выберите Dictionary<K,V>. Он сопоставляет ключ со значением в среднем за O(1).

Примеры: идентификатор пользователя и пользователь, код страны и название, слово и его частота. Ключ отвечает на вопрос «какой именно», а значение содержит данные.

var users = new Dictionary<int, string> {
    [101] = "Ann",
    [102] = "Bob"
};
string name = users[101];

Наличие и уникальность: HashSet

Если вас интересует только наличие значения или нужно отклонять дубликаты, выберите HashSet<T>. Contains в среднем работает за O(1).

Примеры: посещённые URL (visited), разрешённые разрешения и неповторяющиеся теги. С элементом не связано никакое значение — важен только сам факт его наличия.

var visited = new HashSet<string>();
if (visited.Add(url)) {
    // first time seeing this url
}

Таблица затрат

Средняя стоимость операций: индексация List — O(1), а Contains — O(n). Поиск в Dictionary и HashSet выполняется за O(1).

List.Add в конце работает за амортизированное O(1), а вставка или удаление в середине — за O(n). Добавление и удаление в словаре и HashSet в среднем выполняются за O(1).

// List:       index O(1),  Contains O(n)
// Dictionary: by-key O(1), no index
// HashSet:    Contains O(1), no value, no index

Contains у списка — тревожный признак

Многократный вызов list.Contains внутри цикла — ловушка с квадратичной сложностью O(n²). Каждая проверка просматривает весь список.

Если проверки наличия занимают основное время, переключитесь на HashSet. Одно изменение может превратить медленный цикл в практически мгновенный даже на больших объёмах данных.

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        var allow = new HashSet<int> { 2, 4, 6 };
        foreach (int n in new[] { 1, 2, 3, 4 })
            if (allow.Contains(n)) Console.Write(n + " ");
    }
}

Когда нужны и ключ, и порядок

Нужен поиск по ключу, но также важен предсказуемый порядок? Стандартный Dictionary его не гарантирует.

Можно хранить List для порядка и Dictionary для поиска либо использовать SortedDictionary<K,V>, который поддерживает ключи в отсортированном порядке (sorted) при стоимости операций O(log n).

var sorted = new SortedDictionary<string, int>();
sorted["b"] = 2;
sorted["a"] = 1;
// enumerates a then b, in key order

Компромиссы по памяти

Коллекции на основе хеширования обменивают дополнительную память на скорость. Dictionary и HashSet хранят внутренние корзины, используя больше памяти, чем компактные List или массив.

Для небольших коллекций из нескольких элементов проход по List может оказаться вполне подходящим и потребует меньше памяти. На больших объёмах хеширование окупается.

Program через интерфейсы

Сигнатуры методов должны запрашивать наименее конкретный подходящий тип. Принимайте IEnumerable<T> для чтения, IReadOnlyList<T> для чтения по индексу и IDictionary<K,V> для доступа по ключу.

Это отделяет вызывающий код от конкретного выбранного типа и позволяет позже заменить реализацию, не меняя сигнатуры.

int Sum(IEnumerable<int> values) {
    int total = 0;
    foreach (int v in values) total += v;
    return total;
}

Практический пример

Для подсчёта уникальных (unique) слов в тексте используются две коллекции. Множество (set) отслеживает уже встречавшиеся слова (seen), а словарь подсчитывает частоты (counts).

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

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        var counts = new Dictionary<string, int>();
        foreach (var w in "a b a c b a".Split(' '))
            counts[w] = counts.GetValueOrDefault(w) + 1;
        Console.WriteLine(counts["a"]); // 3
    }
}

Список решений

Задавайте вопросы по порядку: нужна ли мне связь ключа со значением? Используйте Dictionary. Нужны ли только уникальность или проверка наличия? Используйте HashSet.

Если нет, нужны ли порядок и доступ по индексу, возможно с дубликатами? Используйте List. Этот короткий список охватывает большинство повседневных случаев.

Быстрая проверка

Примените список решений к конкретной задаче.

Итоги

Выбирайте по способу доступа: List — для упорядоченных последовательностей с индексацией; Dictionary — для поиска по связи «ключ — значение»; HashSet — для уникальности и проверки наличия.

Следите за асимптотикой: избегайте List.Contains в критичных циклах, используйте хеш-поиск за O(1) и программируйте через интерфейсы, чтобы выбор реализации оставался гибким.

Часто задаваемые вопросы

Урок «Выбор коллекции» бесплатный?

Да — полный текст урока «Выбор коллекции» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C# Academy, подпишись на CoddyKit PRO. Курс C# Academy содержит 4 уроков всего.

Чему я научусь в уроке «Выбор коллекции»?

Компромиссы и производительность. Ты практикуешь C# Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C# Academy?

Предыдущий опыт не требуется. C# Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «Выбор коллекции»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C# Academy?

Да. Каждый урок C# Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к C# Academy