Какая вычислительная сложность задачи удаления дубликатов? За счёт чего? Как HashSet работает изнутри?

Удаление дубликатов обычно сводится к задаче определения уникальности элементов. Если использовать структуру данных, такую как HashSet, то сложность будет примерно O(n), где n — количество элементов.

Почему O(n)? Потому что при добавлении каждого элемента в HashSet происходит вычисление хеш-кода и проверка наличия элемента. В среднем операции вставки и поиска в HashSet — O(1), поэтому для n элементов суммарно O(n).

HashSet внутри реализован на основе хеш-таблицы. Основные моменты:

• Каждый элемент преобразуется в хеш-код.
• Хеш-код используется для определения позиции в массиве бакетов.
• Если в бакете уже есть элементы (коллизия), они хранятся в связном списке или сбалансированном дереве (в новых версиях .NET).
• При добавлении проверяется, есть ли уже такой элемент (через Equals), чтобы избежать дубликатов.

Пример на C#:

var items = new List<int> {1, 2, 2, 3, 4, 4, 5};
var uniqueItems = new HashSet<int>(items);
// uniqueItems содержит {1, 2, 3, 4, 5}

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