Equals/GetHashCode, коллекции/IEnumerable/IEnumerator/IQueryable, LINQ | Quizlet

Зачем нужны GetHashCode и Equals? Почему их переопределяют вместе?

- Equals определяет логическое равенство объектов

- GetHashCode — это оптимизация над Equals для быстрого сравнения

- Объекты распределяются по "ведрам" (бакетам) по хеш-коду, чтобы не сравнивать все объекты друг с другом

- Переопределяют вместе из-за контракта: если a.Equals(b) == true, то a.GetHashCode() == b.GetHashCode()

Аналогия: Ищем блондина — если видим брюнета (другой хеш-код), тест ДНК (глубокое сравнение) не делаем

Частая ошибка: Переопределить только Equals без GetHashCode — объекты не будут правильно работать в Dictionary/HashSet

Какой контракт у GetHashCode? Могут ли у разных объектов быть одинаковые хеш-коды?

- У одинаковых объектов хеш-коды точно равны

- У разных объектов хеш-коды неизвестно — могут быть одинаковые (коллизии), могут быть разные

- Хеш-код должен быть стабильным во время жизни объекта

- Коллизии неизбежны: объектов бесконечно много, хеш-код — всего лишь int (4 млрд вариантов)

Контракт простой: если a.Equals(b), то a.GetHashCode() == b.GetHashCode(). Обратное неверно!

Какой контракт у Equals? Могут ли для разных объектов возвращать true?

Нет! Equals и определяет равенство объектов. Если Equals возвращает true — объекты равны по определению.

Разница:

- Одинаковые хеш-коды ≠ равные объекты (могут быть коллизии)

- Equals == true = объекты точно равны

Как правильно переопределить GetHashCode и Equals для сравнения по части свойств?

public override bool Equals(object obj) =>

obj is Person other && Name == other.Name && Age == other.Age;

public override int GetHashCode() =>

HashCode.Combine(Name, Age); // .NET Core 2.1+

Частая ошибка: Использовать изменяемые поля в GetHashCode — если объект в Dictionary, а поле поменялось, объект "потеряется"

Можно ли из GetHashCode для простоты всегда возвращать одно значение (например, 1)?

Технически можно — контракт не нарушается, но производительность катастрофическая!

Почему плохо:

- Все объекты попадут в один бакет Dictionary/HashSet

- Поиск деградирует с O(1) до O(n) — превращается в линейный список

- Dictionary на 1000 элементов будет работать как LinkedList

Аналогия: Как если бы все дома в городе имели один адрес — почтальон обходил бы каждый дом, чтобы найти нужный

Что будет, если из GetHashCode возвращать рандомное значение?

Катастрофа! Объекты будут теряться в Dictionary/HashSet после первого обращения.

Что происходит:

Объект сохраняется в бакет по первому хеш-коду (например, 42)

При следующем обращении GetHashCode вернет другое значение (например, 73)

Поиск будет идти в бакете 73, а объект лежит в бакете 42

Результат: объект не найден, хотя он есть в коллекции

Аналогия: Как если бы дом каждый день менял свой адрес - почтальон никогда его не найдет

Как по умолчанию работают Equals и GetHashCode у ссылочных типов?

У ссылочных типов (классов) по умолчанию:

- Equals проверяет равенство ссылок (как ReferenceEquals)

- GetHashCode возвращает псевдослучайное число, сгенерированное при первом вызове

Как работает GetHashCode:

- CLR генерирует случайный хеш при первом обращении

- Хеш сохраняется в заголовке объекта (sync block)

- Остаётся неизменным, даже если GC переместит объект

Пример:

class Person { public string Name { get; set; } }

var p1 = new Person { Name = "Иван" };

var p2 = new Person { Name = "Иван" };

p1.Equals(p2) // false - разные объекты

p1.GetHashCode() == p2.GetHashCode() // случайно, но скорее всего false

Важно: Даже если все поля одинаковые, объекты не равны без переопределения GetHashCode/Equals!

Частые ошибки:

- Думать, что GetHashCode зависит от адреса объекта — это не так! Иначе хеш менялся бы при перемещении объекта сборщиком мусора

- Ожидать, что объекты с одинаковыми данными будут равны — для этого нужно переопределить Equals/GetHashCode

Как по умолчанию работают Equals и GetHashCode у значимых типов?

У значимых типов (struct) по умолчанию реализация из ValueType.

Equals работает так:

1. Сначала проверяет, что типы одинаковые

2. Fast path: если структура "простая" (только примитивы, нет gaps в памяти) — побитовое сравнение через memcmp

3. Slow path: если есть ссылочные поля или padding — рефлексия, проход по всем полям и вызов Equals для каждого

GetHashCode работает так:

1. Fast path: если первое поле примитивное — возвращает его хеш-код

2. Slow path: если первое поле ссылочное или есть сложности — через рефлексию берёт первое не-null поле

Примеры:

struct Point { public int X; public int Y; }

// Equals: побитовое сравнение 8 байт

// GetHashCode: вернёт X.GetHashCode()

struct Person { public string Name; public int Age; }

// Equals: рефлексия, вызовет Name.Equals() и Age.Equals()

// GetHashCode: вернёт Name?.GetHashCode() ?? 0

Проблемы:

- Рефлексия очень медленная

- GetHashCode от одного поля даёт плохое распределение

- Боксинг при вызове Equals(object)

Рекомендация: ВСЕГДА переопределяй для production кода!

Что такое алгоритмическая сложность?

Алгоритмическая сложность (Big O) показывает, как время выполнения алгоритма растет с увеличением размера данных.

Основные виды:

- O(1) — константное время (доступ к элементу массива по индексу)

- O(log n) — логарифмическое (бинарный поиск в отсортированном массиве)

- O(n) — линейное (поиск в неотсортированном массиве)

- O(n log n) — линейно-логарифмическое (быстрая сортировка)

- O(n²) — квадратичное (сортировка пузырьком)

Аналогия: Ищем человека в толпе

- O(1) — знаем точное место

- O(log n) — делим толпу пополам, спрашиваем "он левее или правее?"

- O(n) — проверяем каждого по порядку

Могут ли в словаре лежать ключи с одинаковыми хеш-кодами?

Да, это коллизии. Dictionary использует цепочки (chaining) — в одном бакете хранится список ключей с одинаковыми хешами

Пояснение: Хеш-код — это не уникальный идентификатор, а "почтовый индекс" для быстрого поиска района

Как работает вставка/поиск в Dictionary? Как хеш-код превращается в номер бакета?

1. hashCode = key.GetHashCode()

2. bucketIndex = hashCode % buckets.Length

3. Поиск по цепочке в бакете через Equals

Пояснение: Количество бакетов обычно простое число, растет при заполнении

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

- Вставка по ключу: O(1) амортизированная, O(n) худший случай при resize

- Поиск по ключу: O(1) амортизированная

- Поиск по значению: O(n) всегда

- Удаление: O(1) амортизированная

Что такое load factor:

- Это заполненность словаря (количество элементов / размер внутреннего массива)

- По умолчанию 0.75 — resize происходит при заполнении на 75%

- Зачем: баланс между расходом памяти и количеством коллизий

Как происходит resize:

- Когда элементов становится больше 75% от размера массива бакетов

- Размер увеличивается примерно в 2 раза (до следующего простого числа)

- Все элементы перехешируются в новые бакеты — поэтому O(n)

- Частота: log(n) раз за n вставок (всё реже с ростом словаря)

Пример: словарь на 100 элементов сделает resize примерно 7 раз (на 3, 7, 17, 37, 89, 197... элементах)

Сложность операций в HashSet?

- Вставка: O(1) амортизированная

- Поиск: O(1) амортизированная

- Работает аналогично Dictionary, но без значений

HashSet — это математическое множество:

- Гарантирует уникальность элементов

- Поддерживает операции объединения, пересечения, разности

- Порядок элементов не гарантируется

Сложность поиска в массиве и отсортированном массиве?

- Обычный массив: O(n) линейный поиск

- Отсортированный массив: O(log n) бинарный поиск (Array.BinarySearch)

Пояснение: Бинарный поиск каждый раз отбрасывает половину элементов

T[], List, LinkedList, HashSet, Dictionary — когда использовать?

- T[] — заранее известна длина, не нужно менять размер (сложно изменять количество элементов, легко менять каждый элемент)

- List — частые добавления в конец или манипуляции с концом массива

- LinkedList — частые вставки/удаления в любом месте, но сложный доступ по индексу

- HashSet — множество уникальных элементов (как Dictionary без значений), быстрый поиск/вставка

- Dictionary — связь ключ-значение, быстрый поиск по ключу

Как работают методы LINQ? Что такое отложенное выполнение?

- LINQ-методы возвращают IEnumerable и ничего не выполняют сразу

- Просто сохраняют информацию о том, что нужно будет потом сделать

- Выполнение происходит при перечислении (foreach, ToList(), First())

- При изменении исходной коллекции после LINQ-запроса изменения будут видны при перечислении

Частая ошибка:

var list = new List {1, 2, 3};

var filtered = list.Where(x => x > 1); // ничего не произошло!

list.Add(4); // добавили элемент

var result = filtered.ToList(); // {2, 3, 4} - видим изменение, Where выполнился только после реального перечисления!

Как работает foreach под капотом? Какие коллекции можно перечислить через него?

// foreach (var item in collection) превращается в:

var enumerator = collection.GetEnumerator();

try

{

while (enumerator.MoveNext())

{

var item = enumerator.Current;

// тело цикла

}

}

finally

{

enumerator?.Dispose();

}

Можно перечислить: любой тип с методом GetEnumerator() или реализующий IEnumerable, то есть коллекция НЕ ОБЯЗАТЕЛЬНО должна реализовывать IEnumerable

Duck typing в foreach — оптимизация для избежания аллокаций:

- У List/Dictionary

- Для IList будет IEnumerator (interface) — аллокация и боксинг

В чём отличие IEnumerable от IEnumerator?

- IEnumerable — коллекция, общий источник данных (имеет GetEnumerator())

- IEnumerator — конкретное состояние перечисления (MoveNext(), Current)

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

Аналогия: IEnumerable — это чат в телеграме (общий на всех), IEnumerator — это конкретное количество непрочитанных у каждого участника чата (у каждого своё).

Что такое IQueryable? Как C# код превращается в SQL?

- IQueryable — абстракция над удалённым источником данных (БД, веб-сервис)

- IEnumerable — источник данных в памяти, рядом с нами

- C# в LINQ для IQueryable компилируется не в IL, а в деревья выражений (Expression Tree)

- Деревья выражений создаются в compile time, а не в runtime

- Entity Framework в runtime анализирует дерево и переводит его в SQL

Как работают деревья выражений:

- Код хранится как структура данных, а не инструкции

- Каждая операция — это узел дерева (например, сравнение, вызов метода)

- EF проходит по дереву и генерирует SQL

Пример дерева для x => x.Age > 18:

- Корень: Lambda

- Левый узел: Parameter (x)

- Правый узел: GreaterThan

- Левый: Property (x.Age)

- Правый: Constant (18)

Частая ошибка: Смешивать IQueryable и IEnumerable — можно случайно загрузить всю таблицу в память

Какие делегаты принимают LINQ методы для IEnumerable и IQueryable?

- IEnumerable — принимает Func

- IQueryable — принимает Expression

Пояснение: Expression можно анализировать и переводить в SQL, обычный делегат — нет

Разница между IEnumerable, ICollection, IList и их ReadOnly версиями?

- IEnumerable — только перечисление в одну сторону, не знаем Count

- ICollection — IEnumerable + добавление/удаление, знаем Count

- IList — ICollection + доступ по индексу

- IReadOnlyCollection — IEnumerable + Count

- IReadOnlyList — IReadOnlyCollection + доступ по индексу

Аналогии:

- IEnumerable = колода в блэкджеке: берём карты сверху по одной, не знаем сколько осталось

- ICollection = знаем количество карт в колоде

- IList = можем взять конкретную карту: "дай мне 4-ю карту снизу"

Как работают констрейнты дженериков? Почему нет боксинга с интерфейсами?

void Method(T value) where T : IComparable

{

value.CompareTo(default); // без боксинга!

}

Почему нет боксинга:

- В runtime создается один дженерик для всех ссылочных типов

- Но для каждого значимого типа создается своя реализация

- Компилятор знает, что T реализует интерфейс, и генерирует специализированный код

Может ли хеш-код изменяться во время жизни объекта?

Не должен! Если объект находится в Dictionary/HashSet и его хеш-код изменился — объект "потеряется" и больше не будет найден.

Почему так происходит: Объект записали в бакет по старому хеш-коду, а ищем по новому — попадаем в другой бакет

Решение: Используй только неизменяемые поля или делай объекты immutable

Можно ли изменять коллекцию во время foreach?

Нет! Бросится InvalidOperationException. Коллекции отслеживают изменения через версионирование (массив не отслеживает, тут норм)

Что такое ковариантность/контравариантность интерфейсов?

Это про безопасное приведение типов в дженериках:

Ковариантность (out T) — можно положить более конкретный тип:

- IEnumerable<Кот> можно использовать как IEnumerable<Животное>

- Безопасно, потому что мы только читаем котов как животных

Контравариантность (in T) — можно принять более общий тип:

- Action<Животное> можно использовать как Action<Кот>

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

Инвариантность (просто T) — нельзя никуда приводить:

- List<Кот> НЕ является List<Животное>

- Небезопасно: могли бы добавить собаку в список котов!

Простое правило:

- out = данные выходят (читаем) → можно расширять тип

- in = данные входят (пишем) → можно сужать тип

- без модификатора = и читаем, и пишем → нельзя менять тип