Стоит ли использовать хэш-таблицу для эффективного удаления дубликатов

Что проверяют

Знаете ли вы стоимость операций у стандартных коллекций и откуда у хэш-множества берётся константное время. Заодно проверяют контракт Equals и GetHashCode: именно на нём ломается удаление дубликатов у пользовательских типов.

Как отвечать

Да, для дедупликации хэш-множество это обычный и правильный выбор. HashSet<T> даёт в среднем константную вставку и проверку, значит весь проход линейный по числу элементов, а память линейная по числу уникальных значений. Сортировка добавила бы логарифмический множитель, а вложенный цикл с Contains по списку дал бы квадрат.

Отдельно стоит сказать, что Add возвращает bool, и это позволяет одним проходом отфильтровать дубликаты, сохранив исходный порядок:

var seen = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
var unique = source.Where(x => seen.Add(x)).ToList();

Упомяните, что в LINQ уже есть Distinct и DistinctBy, устроенные внутри так же, и писать цикл руками стоит только когда нужна побочная логика или нестандартное сравнение. Само сравнение задаётся через IEqualityComparer<T>: регистр строк, культура, сравнение по одному полю сущности.

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

Где спотыкаются

Кладут в множество экземпляры своего класса, не переопределив Equals и GetHashCode. Для класса сравнение идёт по ссылке, и дубликаты спокойно остаются, тогда как record и кортежи сравниваются по значению и работают сразу.

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

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