Что такое Array, List, HashSet, Dictionary? Приведите примеры использования этих структур данных. Какая сложность операций с ними (поиск, вставка, удаление)?csharp-33

1. Array

Описание: Фиксированная коллекция элементов одного типа. Самый базовый тип коллекции в .NET.

// Создание и инициализация
int[] numbers = new int[3] { 1, 2, 3 };
string[] names = { "Alice", "Bob", "Charlie" };

// Доступ по индексу
numbers[0] = 10; // O(1)
int first = numbers[0]; // O(1)

Сложность операций:

• Доступ по индексу: O(1)
• Поиск элемента: O(n)
• Вставка: Не поддерживается (размер фиксирован)
• Удаление: Не поддерживается

Использование: Когда известен фиксированный размер коллекции и нужна максимальная производительность.

2. List

Описание: Динамический массив, который автоматически увеличивает capacity при необходимости.

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

// Добавление элементов
numbers.Add(4); // O(1) (амортизированная)
numbers.Insert(0, 0); // O(n)

// Поиск
bool contains = numbers.Contains(2); // O(n)
int index = numbers.IndexOf(2); // O(n)

Сложность операций:

• Доступ по индексу: O(1)
• Добавление в конец: O(1) (амортизированная)
• Вставка/удаление в середине: O(n)
• Поиск элемента: O(n)

Использование: Когда нужен динамический массив с частым доступом по индексу, но редкими вставками/удалениями в середине.

3. HashSet

Описание: Коллекция уникальных элементов, основанная на хэш-таблицах.

HashSet<string> names = new HashSet<string> { "Alice", "Bob" };

// Добавление (возвращает false если элемент уже есть)
bool added = names.Add("Charlie"); // O(1)

// Проверка наличия
bool exists = names.Contains("Alice"); // O(1)

// Удаление
names.Remove("Bob"); // O(1)

Сложность операций:

• Добавление: O(1)
• Удаление: O(1)
• Поиск: O(1)
• Нет доступа по индексу

Использование: Для хранения уникальных элементов, когда важна быстрая проверка принадлежности.

4. Dictionary<TKey, TValue>

Описание: Коллекция пар ключ-значение, основанная на хэш-таблицах.

Dictionary<string, int> ages = new Dictionary<string, int>
{
    ["Alice"] = 25,
    ["Bob"] = 30
};

// Добавление/обновление
ages["Charlie"] = 28; // O(1)

// Получение значения
int aliceAge = ages["Alice"]; // O(1)

// Проверка ключа
bool hasKey = ages.ContainsKey("Bob"); // O(1)

// Удаление
ages.Remove("Alice"); // O(1)

Сложность операций:

• Добавление: O(1)
• Удаление: O(1)
• Поиск по ключу: O(1)
• Поиск по значению: O(n)
• Нет доступа по индексу

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

Сравнение производительности

Операция	Array	List<T>	HashSet<T>	Dictionary<K,V>
Доступ по индексу	O(1)	O(1)	-	-
Поиск элемента	O(n)	O(n)	O(1)	O(1) по ключу
Вставка	-	O(1)* / O(n)	O(1)	O(1)
Удаление	-	O(n)	O(1)	O(1)

*O(1) - амортизированная сложность для добавления в конец List

Примеры выбора структуры данных

1. Фиксированный набор данных → Array
2. Частые добавления в конец + доступ по индексу → List
3. Проверка уникальности значений → HashSet
4. Телефонная книга (имя → номер) → Dictionary<string, string>

Резюмируем:

Выбор структуры данных зависит от операций, которые вы планируете выполнять чаще всего. Массивы обеспечивают лучшую производительность для фиксированных данных, List - гибкость динамического массива, HashSet - оптимален для работы с уникальными элементами, а Dictionary<K,V> - лучший выбор для ассоциативных массивов с быстрым поиском по ключу.