List и Dictionary

This lesson is not translated yet – the Russian original is below.

Массив хорош, пока количество элементов известно заранее. Как только их число меняется по ходу работы, нужны коллекции посложнее. Двух из них хватает почти всегда.

List: список переменной длины

var names = new List<string>();

names.Add("Аня");
names.Add("Борис");
names.Add("Вера");

Console.WriteLine(names.Count);    // 3
Console.WriteLine(names[0]);       // Аня

Запись List<string> читается как «список строк». Угловые скобки – это обобщение: один и тот же класс списка работает с любым типом, но конкретный список хранит только то, что указано. Строку в List<int> положить не выйдет.

Количество элементов у списка называется Count, у массива – Length. Разница историческая и запоминается только практикой; смысл один и тот же.

Список можно сразу заполнить:

var numbers = new List<int> { 1, 2, 3 };

Что умеет список

var names = new List<string> { "Аня", "Борис" };

names.Add("Вера");                 // в конец
names.Insert(0, "Антон");          // по индексу
names.Remove("Борис");             // по значению, первое совпадение
names.RemoveAt(0);                 // по индексу
names.Clear();                     // очистить

Проверки и поиск:

bool exists = names.Contains("Аня");
int position = names.IndexOf("Аня");    // -1, если нет

Удаление элементов внутри foreach по тому же списку бросает InvalidOperationException. Если нужно удалить по условию, есть готовый метод: names.RemoveAll(n => n.StartsWith("А")); – он делает это за один проход и безопасно.

Как список устроен внутри

Внутри List<T> лежит обычный массив. Когда место заканчивается, список создаёт новый массив вдвое больше и копирует туда содержимое.

Отсюда практические следствия:

• доступ по индексу мгновенный – это обращение к элементу массива;
• добавление в конец почти всегда дешёвое, но иногда вызывает копирование всего содержимого;
• вставка в начало дорогая – все элементы сдвигаются вправо.

Если заранее известно, сколько элементов будет, вместимость стоит задать сразу – тогда копирований не будет вовсе:

var numbers = new List<int>(10000);

Dictionary: пары «ключ – значение»

Словарь отвечает на вопрос «что связано вот с этим», не перебирая всё подряд:

var ages = new Dictionary<string, int>();

ages["Аня"] = 19;
ages["Борис"] = 25;

Console.WriteLine(ages["Аня"]);    // 19

Первый тип в скобках – ключ, второй – значение. Ключи уникальны: повторное присваивание заменяет значение, а не добавляет вторую запись.

Создать сразу с данными:

var ages = new Dictionary<string, int>
{
    ["Аня"] = 19,
    ["Борис"] = 25
};

Ключа может не быть

Обращение по несуществующему ключу – исключение, а не null:

Console.WriteLine(ages["Виктор"]);    // KeyNotFoundException

Безопасных способов два:

if (ages.ContainsKey("Виктор"))
{
    Console.WriteLine(ages["Виктор"]);
}

Лучше – TryGetValue, знакомый по int.TryParse: он ищет один раз, а не два.

if (ages.TryGetValue("Виктор", out int age))
{
    Console.WriteLine(age);
}

Разница между Add и присваиванием тоже про существование ключа:

Выбирайте осознанно. Если по смыслу задачи ключ не должен повторяться, Add честно сообщит об ошибке в данных, а присваивание молча затрёт старое значение – и вы об этом не узнаете.

Почему словарь такой быстрый

Поиск в словаре не зависит от количества элементов: и в сотне записей, и в миллионе он занимает примерно одинаковое время. Внутри считается хеш ключаХеш – короткое число, посчитанное по содержимому. У одинаковых ключей он одинаков, у разных почти всегда различается. – число, по которому сразу вычисляется место хранения.

Сравните с поиском в списке: чтобы найти элемент, придётся просмотреть все подряд. На миллионе записей разница между этими подходами – это разница между мгновенным ответом и заметной паузой.

Ключом может быть любой тип, но для своих классов придётся правильно определить сравнение и хеш – иначе словарь не найдёт запись, которую вы только что положили. Для строк, чисел и дат всё уже сделано.

Что выбрать

Последние три встречаются реже, но названия стоит знать. HashSet<T> особенно полезен: он сам отбрасывает дубликаты, и проверка «есть ли такое значение» в нём такая же быстрая, как в словаре.