Структуры данных в C#: массивы и коллекции

Привет! В этой статье речь пойдет о такой неотъемлемой вещи в программировании как структуры данных.

Структуры данных

Структура данных - это некий способ организации информации в памяти определенным образом для эффективного хранения этой информации и извлечения.

Структуры данных используются так или иначе в каждом проекте. Они позволяют упорядочивать, искать, анализировать и использовать данные с применением алгоритмов программирования. Для каждой структуры данных — свои алгоритмы.

Типы структур:

Линейные - структуры данных, в которых элементы расположены последовательно, где каждый элемент прикреплен к своему предыдущему и следующему соседним элементам.
Линейные структуры бывают статическими и динамическими:
🞄 Статическая структура данных имеет фиксированный размер памяти (например, массивы);
🞄 В динамической структуре данных размер не фиксирован. Он может обновляться во время выполнения. (списки, очереди, стек)
Нелинейные - структуры данных, в которых элементы данных расположены не последовательно. В нелинейной структуре данных мы не можем обойти все элементы только за один проход. (графы, деревья)

Как видите, существует довольно много структур со своими особенностями устройства, и задача программиста для эффективной работы с данными — правильно выбирать из уже имеющихся либо писать свои.

Массивы

Массив – это простейшая структура данных, позволяющая последовательно хранить набор однотипных данных. Массив в C# является ссылочным типом данных, т.е. мы создаем некоторую переменную, ссылающуюся на какую-то область в куче, где последовательно хранится содержимое нашего массива. Объявление массива схоже с обычным объявлением переменной, разве что после типа ставятся квадратные скобки:

Тип[] имяПеременной;

Так, например, объявляется массив целых чисел:

int[] array;

Каждое отдельное значение набора обычно именуют элементом массива. Размером (или длиной) массива называют количество его элементов, это значение неизменяемо! Каждый элемент массива идентифицируется по индексу. Индекс – это целое число из заданного диапазона, начинающегося с нуля и заканчивающегося размером массива минус один, так как индексацию в C# также как и во многих других языках программирования принято начинать с 0.

Разберемся с каждым определением на примерах!

Для инициализации массивов мы все так же пользуемся оператором new, как и при инициализации других ссылочных типов:

Тип[] имяПеременной = new Тип[размерМассива];

Например, объявим и проинициализируем массив целочисленных значений на 7 элементов:

int[] array = new int[7];

Но на данный момент у нас имеется массив элементов, которые мы никак не задавали (не проинициализировали). А как вы помните, все не проинициализированные элементы вручную инициализируются своими значениями по умолчанию, соответствующие типу, и с массивами это работает аналогично. Т.е. в данном случае мы получим набор из 7 элементов, равных 0.

Другим способом инициализации является использование инициализаторов объекта, о которых мы говорили в одной из прошлых статей:

int[] firstArray = new int[7] { 1, 2, 3, 4, 5, 6, 7 }; // массив из 7 элементов
int[] secondArray = new int[] { 1, 2, 3 }; // массив из 3 элементов
int[] thirdArray = new [] { 1, 2, 3, 4, 5 }; // массив из 5 элементов
int[] fourthArray = { 1, 2, 3, 4 }; // массив из 4 элементов

Все четыре конструкции валидны и приводят к созданию массивов, наполненных нужными нам значениями.

Для работы с элементами массива нам и понадобятся индексы! Массив – это линейная структура данных, все элементы набора расположены в памяти последовательно, каждый в своей ячейке памяти, и данная область памяти является непрерывной.

Использование индексов – это быстрый способ обратиться к конкретному элементу последовательности. Индексация массива начинается с 0, поэтому чтобы обратиться к первому элементу массива, нам необходимо использовать индекс 0, а для обращения к четвертому элементу – индекс 3. Для обращения к конкретному элементу необходимо после имени переменной массива в квадратных скобках указать индекс интересующего нас элемента:

int[] array = { 101, 3, 42, 5 }; // создали массив из 4 элементов
Console.WriteLine(array[0]); // Выводим первый элемент массива: 101
Console.WriteLine(array[1]); // Выводим второй элемент массива: 3

array[1] = 121;              // Заменяем значение второго элемента массива
Console.WriteLine(array[1]); // Выводим второй элемент массива: 121

Запомните! Обратиться мы можем только к существующим элементам, т.е. наш массив должен существовать, а индекс, по которому мы обращаемся, должен быть в пределах от нуля до размер массива минус 1 [0, n - 1]:

int[] firstArray;
Console.WriteLine(firstArray[0]); // Ошибка компиляции! Использование
                                  // неинициализированной переменной!
int[] secondArray = {1, 2, 3, 4};
Console.WriteLine(secondArray[4]); // Исключение во время работы программы!
                                   // Обращение к несуществующему элементу!

Операции с массивами

Массивы в C# представляют собой реальные объекты, а не просто адресуемые области непрерывной памяти (как это сделано в C++, например). Array является абстрактным базовым классом для всех типов массивов и содержит ряд методов и свойств для работы с массивами.

Например, с помощью свойства Length можно получить длину массива, обратившись к нему по имени массива:

int[] arr = { 21, 42, 53, 103 };
Console.WriteLine(arr.Length); // Вывод: 4

Класс Array также содержит множество статических методов (не зависящих от состояния массивов, от количества элементов в них) для работы с данными массивов:

метод Clear очищает массив, устанавливая всем элементам значения по умолчанию (в качестве аргументов принимает массив, начальный индекс диапазона, с которого происходит очистка, а также число элементов, подлежащих очистке);
Reverse располагает элементы в массиве в обратном порядке (в качестве аргумента принимает массив, который мы хотим развернуть);
IndexOf возвращает индекс переданного в качестве аргумента элемента, если он существует, или возвращающий -1, если такого элемента нет (в качестве аргументов принимает массив и элемент, индекс которого в данном массиве мы хотим узнать).
Sort сортирует элементы массива.

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

int[] arr = { 21, 42, 53, 103 };
Console.WriteLine(arr.Length); // Вывод: 4

Console.WriteLine(Array.IndexOf(arr, 42)); // Вывод: 1
Console.WriteLine(Array.IndexOf(arr, 103)); // Вывод: 3
Console.WriteLine(Array.IndexOf(arr, 2)); // Вывод: -1

Array.Reverse(arr);
Console.WriteLine(arr[0]); // Вывод: 103

Array.Clear(arr, 0, 4); // Очищаем значениями по умолчанию 4 элемента,
                        // начиная с первого (по индексу ноль)
Console.WriteLine(arr[0]); // Вывод: 0

Многомерные массивы

Размерность массива (ранг) – это количество индексов, необходимое для однозначного определения каждого элемента массива. Размерность массива можно определить с помощью свойства Rank, обратившись к нему через имя переменной массива и оператора точки:

int[] array = { 1, 2, 3 };
Console.WriteLine(array.Rank); // Вывод: 1

В предыдущих примерах мы разбирали только одномерные массивы – массивы, которые можно представить в виде ряда:

int[] array = new int[6] { 0, 1, 2, 3, 4, 5 };

Для обращения к элементу такого массива нам достаточного одного индекса.

Размерность массивов может быть больше 1. Для объявления таких массивов в квадратных скобках необходимо запятой как бы разделять измерения. Например, объявление и инициализация двумерного массива может выглядеть так:

int[,] array = new int[2, 3];
Console.WriteLine(array.Rank); //Вывод: 2

Таким нехитрым действием мы создали двумерный массив интов 2 на 3. (Грубо говоря, 2 массива по 3 элемента в каждом).

Инициализатор будет работать аналогичным образом:

int[,] firstArray= new int[2, 3] { { 0, 1, 2 }, { 3, 4, 5 } };
int[,] secondArray= new int[,] { { 0, 1, 2 }, { 3, 4, 5 } };
int[,] thirdArray = new [,] { { 0, 1, 2 }, { 3, 4, 5 } };
int[,] fourthArray = { { 0, 1, 2 }, { 3, 4, 5 } };

Такой двумерный массив можно представить в виде таблицы – сочетаний строк и столбцов:

int[,] array = { { 0, 1, 2 }, { 3, 4, 5 } };

Для обращения к элементу такого массива нам уже необходимо два индекса, как если бы мы обращались к ячейке таблицы:

Console.WriteLine(array[0, 0]); // Вывод: 0
Console.WriteLine(array[0, 1]); // Вывод: 1
Console.WriteLine(array[0, 2]); // Вывод: 2
Console.WriteLine(array[1, 0]); // Вывод: 3
Console.WriteLine(array[1, 1]); // Вывод: 4
Console.WriteLine(array[1, 2]); // Вывод: 5

Таким образом мы можем определять трехмерные, четырехмерные и даже n-мерные массивы, но на практике чаще всего встречаются одномерные и двумерные.

Массивы массивов

Массив массивов – это массив, который в качестве своих элементов хранит ссылки на другие массивы:

int[][] array = new int[10][]; // объявление и инициализация массива
                               // из десяти массивов

В результате работы кода выше будет создан массив, содержащий ссылки на 10 массивов. Эти ссылки необходимо отдельно проинициализировать:

for(int i = 0; i < array.Length; i++)
{
    array[i] = new int[10];
}

С помощью цикла for мы проходимся по нашему массиву, инициализируя каждую ссылку массивом целочисленных значений размером 10.

Нередко массив массивов называют ступенчатым (или зубчатым) массивом. Связано это с тем, что при инициализации подмассивов мы можем задавать им различные размеры:

int[][] array = new int[3][]; // Создали массив из трех массивов
array[0] = new int[3]; // Инициализируем подмассивы
array[1] = new int[5];
array[2] = new int[2];

Если сравнивать зубчатые массивы с многомерными массивами, то у многомерных массивов всегда размер всех подмассивов одинаковый.

Коллекции в C#

Хотя базовые массивы могут быть удобными для управления небольшими объемами данных фиксированного размера, есть немало случаев, когда требуются более гибкие структуры данных, такие как динамически расширяющийся и сокращающийся контейнер, ассоциативные контейнеры с доступом к элементам по ключу и прочее)

Для преодоления ограничений простого массива, библиотека базовых классов .NET Core поставляются с несколькими пространствами имен, которые содержат классы коллекций. В отличие от простого массива C# классы коллекций построены с возможностью динамического изменения своих размеров по мере вставки либо удаления из них элементов.

Динамические массивы

Динамическим называется массив, размер которого может меняться во время исполнения программы. Мы можем решить данную задачу с обычным массивом, используя статический метод Array.Resize.

int[] array = new int[5] { 1, 2, 3, 4, 5 };

Array.Resize(ref array, 7);
for (int i = 0; i < array.Length; i++)
    Console.Write(quot;{array[i]} "); //1 2 3 4 5 0 0

Array.Resize(ref array, 3);
for (int i = 0; i < array.Length; i++)
    Console.Write(quot;{array[i]} "); //1 2 3

о том, что такое ref, речь пойдет в следующей небольшой статье:)

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

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

Класс ArrayList из пространства имен System.Collections представляет собой коллекцию с массивом динамически изменяющегося размера.

using System.Collections;

ArrayList arr = new ArrayList();

Под капотом ArrayList имеет обычный массив, но в отличие от него в работе с динамическими массивами добавляется еще одно свойство – Capacity (вместимость). При создании динамического массива определенного размера, помимо самого размера определяется также значение вместимости, в соответствии с которым и выделяются необходимые объемы памяти под данную коллекцию.

При добавлении новых элементов в коллекцию ArrayList происходит проверка: не превысит ли длина массива максимально возможной, в соответствии с которой была выделена память. В случае, если выделенное место в Capacity еще есть, то оно занимается новым значением. Иначе выделяется новое место в памяти под новый массив размером в два раза больше текущего, все элементы копируются в новый массив с сохранением индексов, ссылка на новый массив присваивается переменной, хранящей ссылку на старую, а старый массив становится "мусором".

Основные свойства и методы для работы с ArrayList:

Count – свойство, возвращающее количество элементов в массиве. Для обычных массивов это свойство называлось Length, в динамических коллекциях стандартной библиотеки его стали именовать Count для логического разделения со статическими;
Capacity – свойство, возвращающее текущую вместимость динамического массива. Количество элементов, под которое выделена память для текущего массива, после превышения которого память под массив будет перевыделяться и массив копироваться;
Add – метод, позволяющий добавить элемент в массив, в качестве аргумента принимает добавляемый элемент;
Remove – метод, позволяющий удалить первое вхождение элемента, переданного в качестве аргумента;
RemoveAt – метод, позволяющий удалить элемент по индексу.

При создании ArrayList без передачи в его конструктор размера, он не содержит никаких элементов и его Capacity и Count равны 0:

ArrayList arr = new ArrayList();
Console.WriteLine(arr.Count); // Вывод: 0 
Console.WriteLine(arr.Capacity); // Вывод: 0

Но мы можем сразу зарезервировать память под наш массив передав необходимый размер в конструктор. Таким образом размер массива по-прежнему будет равен 0, но уже будет зарегистрирована некоторая память для добавления новых элементов:

ArrayList arr = new ArrayList(7);
Console.WriteLine(arr.Count); // Вывод: 0 
Console.WriteLine(arr.Capacity); // Вывод: 7

При добавлении новых элементов мы можем отследить, как меняется размер и вместимость массива:

ArrayList someArray = new ArrayList(3);

someArray.Add(1);
Console.WriteLine(someArray.Count); // Вывод: 1
Console.WriteLine(someArray.Capacity); // Вывод: 3

someArray.Add(2);
someArray.Add(3);
Console.WriteLine(someArray.Count); // Вывод: 3
Console.WriteLine(someArray.Capacity); // Вывод: 3

someArray.Add(4);
Console.WriteLine(someArray.Count); // Вывод: 4
Console.WriteLine(someArray.Capacity); // Вывод: 6

someArray.Add(5);
someArray.Add(6);
Console.WriteLine(someArray.Count); // Вывод: 6
Console.WriteLine(someArray.Capacity); // Вывод: 6

someArray.Add(7);
Console.WriteLine(someArray.Count); // Вывод: 7
Console.WriteLine(someArray.Capacity); // Вывод: 12

Также важно отметить, что ArrayList относится к неуневерсальным коллекциям, то есть не является типобезопасным и может содержать элементы сразу нескольких разных типов, что реализуется благодаря приведению всех элементов коллекции к базовому типу Object (о приведении типов мы скоро поговорим в следующих статьях:).

ArrayList arr = new ArrayList();
arr.Add(2);
arr.Add("hey");
arr.Add('c');
arr.Add(3.5);

Универсальные коллекции

Хранить всё подряд в своей коллекции может быть полезно и здорово, но не безопасно и в большинстве случаев требуется точного ограничения того, что может содержаться в нашем наборе, строго типизировать его. Библиотека классов .NET предоставляет ряд универсальных классов коллекций в пространстве имен System.Collections.Generic, являющихся строго типизированными и обычно обеспечивают более высокую производительность.

Generics(обобщенные типы) – достаточно объемная и не самая простая тема, но для базового понимания работы коллекций сейчас в нее углубляться нам не надо. В нашем случае generic служит в качестве способа указания того, что будет храниться внутри коллекции.

Среди основных универсальных коллекций отметим:

List<T> – список, типизированный аналог неуневерсальной коллекции ArrayList;
Dictionary<K, T> – словарь, типизированный аналог неуневерсального Hashtable;
Queue<T> – очередь, типизированный аналог неуневерсального Queue;
Stack<T> – стек, типизированный аналог неуневерсального Stack;
HashSet<T> – хэшсет, коллекция, содержащая элементы без повторений, хранящая их в произвольном порядке;
и другие...

Например посмотрим на пример ниже обобщенного списка значений типа int:

List<int> integerList = new List<int>();

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

Внутри треугольных скобок мы указываем тип данных, который будет храниться в списке:

List<int> firstList = new List<int>(); // Список целочисленных значений
List<string> secondList = new List<string>(); // Список строк
List<List<int>> thirdList = new List<List<int>>(); // Так тоже можно =)
                                           // Получаем список списков интов
                                           // подобно массиву массивов

Перебор коллекций

Мы уже знаем, что для обращения к какому-то конкретному индексу и для перебора индексируемых коллекций массивов/списков можно использовать обычный цикл for:

List<int> arr = new List<int>(){ 4, 3, 2, 1 };
for (int i = 0; i < arr.Count; i++)
    Console.WriteLine(arr[i]) // 4 3 2 1

Но как перебрать неиндексируемые коллекции, например Dictionary (о нем чуть ниже пойдет речь:)?!

Все коллекции, которые были и будут рассмотрены в данной статье, относятся к специальному типу коллекций – перечислимым (Enumerable). Для перебора элементов перечислимых коллекций существует специальная логика, за которую отвечает специальный объект - Enumerator. Для перебора любой перечисляемой коллекции необходимо сделать следующее:

List<int> someList = new List<int>() { 1, 2, 3, 4 };

List<int>.Enumerator it = someList.GetEnumerator(); // получаем Enumerator

while(it.MoveNext()) // Двигаемся по коллекции
{
    Console.WriteLine(it.Current); // Выводим значение
}

1) Получаем объект Enumerator, обращаясь к методу GetEnumerator() у экземпляра коллекции и сохраняя его в переменную it.

2) С помощью цикла while обращаемся к методу MoveNext() у полученного объекта, который двигает нас по коллекции.

3) Свойство Current возвращает текущее значение, на которое указывает Enumerator.

4) Метод MoveNext() возвращается false, когда элементы в коллекции заканчиваются.

Здесь важно запомнить, что Enumerator создается для текущего состояния коллекции! Это значит, что если изменить количество элементов в коллекции во время её перебора, то объект Enumerator перестанет существовать, что приведет к ошибке в программе.

Но, как мы уже говорили в одной из предыдущих статей про управляющие конструкции, в C# помимо циклов for, while и do while существует также еще foreach. По сути foreach является синтаксическим сахаром и разворачивается при компиляции ровно в ту конструкцию, что была показана в предыдущем примере, но при его использовании наш код будет гораздо компактнее и понятнее, что не может не радовать)

foreach(ТипЭлементаКоллекции имяПеременной in имяПеребираемойКоллекции)
{
    тело цикла
    (по имени переменной сможем обращаться к элементам коллекции)
}

Пример:

List<int> someList = new List<int>() { 1, 2, 3, 4 };

foreach(int i in someList)
{
    Console.WriteLine(i);
}
// Вывод построчно: 1 2 3 4

В результате работы данного цикла происходит последовательный перебор всех элементов коллекции. Тип переменной должен совпадать с типом элементов перебираемой коллекции.

List<T>

Пришло время поближе познакомиться с коллекциями, с помощью которых можно свернуть горы!

Аналогично созданию массива, мы можем создавать списки – список элементов с динамически изменяемым размером. Хоть List<T> и называется списком, но под капотом построен с использованием массива, в связи с чем по сути является динамическим массивом, а не структурой данных связанным списком:) За связанные списки в C# отвечает коллекция LinkedList<T>.

string[] s = { "hey", "hi", "bye" };

List<string> list1 = new List<string>() { "yo", "c#" };

List<string> list2 = new List<string>(s); // содержит все элемнты массива s

List<string> list3 = new List<string>(list1); // содержит все элементы
                                              // листа list1

Методы добавления элементов:

Add() – добавляет переданный в качестве аргумента элемент в конец коллекции, тип передаваемого элемента должен совпадать с типом, которые хранит коллекция;
AddRange() – добавляет переданный в качестве аргумента диапазон значений в конец коллекции, типы также должны совпадать.

List<string> list1 = new List<string> { "yo", "c#" };
List<string> list2 = new List<string> { "oy" };

list2.Add("#c"); // Добавляем элемент в конец второго списка

list1.AddRange(list2); // Добавляем все элементы второго
                       // списка в конец первого
list1.AddRange(list1); // Добавляем элементы первого списка
                       // в конец самого себя
foreach (string item in list1)
{
    Console.WriteLine(item);
}
// Вывод построчно: "yo" "c#" "oy" "#c" "yo" "c#" "oy" "#c"

При расширении List<T> изменение размера Count и вместимости Capacity происходит аналогично ArrayList.

Методы вставки элементов:

Insert() – вставка элемента, в качестве аргументов принимает индекс, на место которого мы хотим произвести вставку, и вставляемый элемент;
InsertRange() – вставка диапазона значений, в качестве аргументов принимает индекс, на место которого мы хотим произвести вставку, и вставляемую коллекцию.

List<string> list1 = new List<string> { "yo", "c#" };
List<string> list2 = new List<string> { "oy" };

list1.Insert(0, "hello world"); // вставляем в список на место
                                // первого элемента
list1.Insert(list1.Count, ".NET"); // вставляем в конец списка

list2.InsertRange(list2.Count, list1); // вставляем все элементы первого
                                       // списка в конец второго
foreach (string item in list2)
{
    Console.WriteLine(item);
}
// Вывод построчно: "oy" "hello world" "yo" "c#" ".NET"

Методы удаления элементов:

Remove() – удаляет первое вхождение элемента, переданного в качестве аргумента, возвращает true, если элемент был успешно удален, в противном случае – false (например, при передаче несуществующего в коллекции элемента);
RemoveAt() – удаляет элемент по индексу, в качестве аргумента принимает индекс, выход за границы массива как обычно приводит к ошибке;
RemoveRange() – удаляет все элементы коллекции в указанном диапазоне: с указанного индекса удаляется число указываемых элементов, выходить за границы коллекции всё еще нельзя.

List<string> list1 = new List<string>{ "1", "2", "3", "3", "3", "4"};
List<string> list2 = new List<string>{ "1", "1", "1", "1", "1", "2", "3", "4" };

list1.Remove("3");

foreach (var item in list1)
{
    Console.WriteLine(item);
}
// Вывод построчно: "1" "2" "3" "3" "4"

list1.RemoveAt(2);

foreach (var item in list1)
{
    Console.WriteLine(item);
}
//Вывод построчно: "1" "2" "3" "4"

list2.RemoveRange(0, 4);

foreach (var item in list2)
{
    Console.WriteLine(item);
}
// Вывод построчно: "1" "2" "3" "4"

Здесь стоит отметить, что операции вставки и удаления из линейных коллекций приводят к сдвигу всех элементов, что является не самым эффективным действием:

Мы можем использовать эти методы в ряде случаев, но при необходимости часто их использовать на больших объемах данных лучше прибегнуть к использованию коллекций, внутренняя реализация которых позволяет осуществлять эти операции эффективнее. О таких коллекциях мы также поговорим в будущем.

Методы поиска:

Contains() – возвращает true или false в зависимости от того, существует ли в коллекции переданный в качестве аргумента элемент;
Find() – возвращает первый элемент, удовлетворяющий условию, подробнее к этому мы обязательно вернемся в последующих статьях.

Прочие методы:

Reverse() – смена порядка элементов на обратный;
ToArray() – возвращает все элементы коллекции в виде массива соответствующего типа.

А также множество других методов, к которым мы будем обращаться по мере роста наших возможностей!

Хэш-функции

Хэш-функциями называют некоторые функции (методы), которые осуществляют преобразование некоторых входных данных произвольной длины в выходную строку фиксированной длины. Результат такого преобразования называют хэшом, хэш-суммой или хэш-кодом. Существует множество различных методов хэширования, которые отличаются друг от друга производительностью и частотой получения коллизий (случаев, когда хэш-функция дает один хэш-код для различных входных данных).

Хэш-функции используются при:

построении ассоциативных массивов;
поиске дубликатов в коллекциях, хранящих значения без повторений;
сохранении паролей в системах защиты в виде хэш-кода;
при вычислении контрольных сумм от данных (сигнала) для последующего обнаружения в них ошибок, возникающих при хранении и/или передаче данных
и другое...

Хэш-таблица - это структура данных для хранения пар ключ-значение, где каждому значению соответствует ключ-хэшкод. Основным преимуществом хэш-таблиц является то, что доступ к их элементам осуществляется за константное время (об этом мы еще успеем поговорить позже в отдельном материале про хэш таблицы и оценку скорости работы алгоритмов:)

HashSet

HashSet – неиндексируемая коллекция множества, содержащая все значения в единственном числе, т.е. без повторений. Добавление уже существующих значений в эту коллекцию не даст никакого результата, добавление не будет совершено.

HashSet<int> firstSet = new HashSet<int> { 1, 2, 2, 3, 4, 4, 4, 5, 6, 6 };

foreach (var item in firstSet)
{
    Console.WriteLine(item);
}
// Вывод построчно: 1 2 3 4 5 6

List<int> someList = new List<int>{ 6, 6, 7, 7, 8, 9, 10, 10 };
HashSet<int> secondSet = new HashSet<int>(someList);

foreach (var item in secondSet)
{
    Console.WriteLine(item);   
}
// Вывод построчно: 6 7 8 9 10

HashSet является ассоциативным контейнером (с каждым значением ассоциируется ключ) и выстраивается на основе хэш-таблицы, где каждому объекту будет соответствовать хэш-код данного объекта.

Так как HashSet является по сути хэш-таблицей, то порядок добавления элементов во множество никак не влияет на порядок их хранения, они не хранятся в той последовательности, что их добавили. HashSet упорядочивает и хранит элементы по значению их хэша. Кроме того, HashSet это неиндексируемая коллекция, т.е. мы не можем обратиться к какому-то элементу коллекции с помощью квадратных скобок, как мы делали это с массивами и списками.

Добавлять новые элементы во множество можно с помощью метода Add(), при добавлении уже существующих элементов ничего не произойдет:

HashSet<int> someHashSet = new HashSet<int>(); // создали пустой HashSet

someHashSet.Add(1);
someHashSet.Add(1);

foreach(var item in someHashSet)
{
    Console.WriteLine(item);
}
// Вывод: 1

Удаление происходит аналогично списку с помощью метода Remove() и передачи значения элемента, который мы хотим удалить:

HashSet<int> someHashSet = new HashSet<int>() { 1, 2, 3, 4};

someHashSet.Remove(2);
someHashSet.Remove(10);

foreach(var item in someHashSet)
{
    Console.WriteLine(item);
}
// Вывод построчно: 1 3 4

Метод Contains() позволяет узнать существует ли переданный элемент в коллекции, в качестве аргумента принимает интересующее значение, а возвращает значение типа bool в соответствии с результатом работы:

HashSet<int> someHashSet = new HashSet<int>() { 1, 2, 3, 4};

if(someHashSet.Contains(1))
{
    Console.WriteLine("1 is in HashSet"); // Вывод: 1 is in HashSet
}

if(someHashSet.Contains(10))
{
    Console.WriteLine("10 is in HashSet"); // Сюда мы не зайдем т.к. 10 нет
}                                          // в нашем множестве

Dictionary

Dictionary (также именуемый словарём или мапой) – ассоциативный массив, позволяющий хранить элементы в виде пар "ключ-значение", например:

1 - "Котик"
2 - "Собачка"
3 - "Птичка"

Dictionary также как и HashSet выстроен на хэш-таблице, однако вместо того, чтобы применять хэш-функцию к значения и обращаться к объектом по нему, в Dictionary для этого имеется дополнительный элемент - ключ.

Dictionary<int, string> someDict = new Dictionary<int, string>();

С помощью кода выше мы инициализируем пустой словарь, элементы которого состоят из пар целочисленного ключа и строкового значения. Инициализатор для словаря работает следующим образом:

Dictionary<int, string> someDict = new Dictionary<int, string>()
{
    { 1, "Kotik" },
    { 2, "Soba4ka" },
    { 3, "Pti4ka" }
};

Все элементы словаря хранятся в виде структур (о структурах обязательно поговорим позже) KeyValuePair, где от ключа берется хеш для доступа к значениям, т.е. порядок добавления не влияет на порядок хранения элементов. Ключ не может быть null. В качестве ключа может быть использован любой класс или структура, для которых может быть посчитан хэш-код.

Ключи для всех элементов словаря уникальны, попытка добавления элемента, по ключу которого уже существует пара, приведет к ошибке:

Dictionary<int, string> someDict = new Dictionary<int, string>();

someDict.Add(1, "Vanya"); // Добавили пару 1 - "Vanya"
someDict.Add(2, "Sanya"); // Добавили пару 2 - "Sanya"
someDict.Add(1, "Oleg"); // Олег все испортил - ошибка, по ключу 1 уже
                         // существует элемент

Для безопасного удаления необходимо осуществлять проверку существования ключа с помощью метода ContainsKey, принимающего в качестве аргумента ключ, существование которого мы хотим проверить, и возвращающий значение bool в соответствии с результатом:

Dictionary<int, string> someDict = new Dictionary<int, string>();

someDict.Add(1, "Vanya"); // Добавили пару 1 - "Vanya"
someDict.Add(2, "Sanya"); // Добавили пару 2 - "Sanya"

if (!someDict.ContainsKey(1))
{
    someDict.Add(1, "Oleg"); // Добавляем Олега только если нет элемента
}                            // с ключом 1

Или можно использовать специальный безопасный метод TryAdd():

Dictionary<int, string> someDict = new Dictionary<int, string>();

someDict.TryAdd(1, "Vanya"); // Добавили пару 1 - "Vanya"
someDict.TryAdd(2, "Sanya"); // Добавили пару 2 - "Sanya"
someDict.TryAdd(1, "Oleg"); // Мы остановили Олега, ничего не произойдет,
                            // элемент добавлен не будет

Удаление элемента из коллекции также происходит по ключу:

Dictionary<int, string> someDict = new Dictionary<int, string>()
{
    { 1, "Kotik" },
    { 2, "Soba4ka" },
    { 3, "Pti4ka" }
};

someDict.Remove(3); // Удалили пару 3 - "Pti4ka"

Для перебора элементов Dictionary также удобно использовать foreach:

Dictionary<int, string> someDict = new Dictionary<int, string>()
{
    { 1, "Kotik" },
    { 2, "Soba4ka" },
    { 3, "Pti4ka" }
};

foreach (KeyValuePair<int, string> item in someDict)
{
    Console.WriteLine(quot;{item.Key} - {item.Value}");
}
// Вывод:
// 1 - Kotik
// 2 - Soba4ka
// 3 - Pti4ka

С помощью квадратных скобок мы можем работать со значениями, находящимися в паре с соответствующим ключом:

Console.WriteLine(someDict["first"]); // Вывод: Kotik
Console.WriteLine(someDict["second"]); // Вывод: Soba4ka
Console.WriteLine(someDict["third"]); // Вывод: Pti4ka

При этом обращение к несуществующему ключу приведет к ошибке:

Console.WriteLine(someDict["fourth"]); // ОШИБКА!

Пока по структурам данных все, но мы обязательно вернемся к этой теме еще не раз, так как еще оооочень много чего следует дорасказать, и это была лишь ознакомительная статья о том, с чем предстоит в дальнейшем постоянно сталкиваться) Далее на канале выйдет небольшой пост о синтаксическом сахаре var и не большая статья о передаче объектов по значению и по ссылке, и будем начинать выкладывать различные задачки для практики и отработки материала. Так что подписывайтесь на тг-канал ставьте лайки и вот этого всего можно побольше!)