Знаком ли со структурой данных set

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

Знаете ли вы, что встроенного множества в Go нет, и как его правильно собрать из map. Следом спрашивают, почему значение struct{}, а не bool, и безопасен ли такой сет при работе из нескольких горутин.

Как отвечать

Множество хранит уникальные элементы и быстро отвечает на вопрос «есть ли элемент». В Go его делают на map:

• map[T]struct{}: пустая структура занимает ноль байт, память уходит только на ключи. Проверка через comma-ok: _, ok := s[x];
• map[T]bool: чуть больше памяти, зато проверка читается проще: if s[x]. На небольших наборах разница несущественна, выбор зависит от стиля команды;
• дженерики: с Go 1.18 пишут type Set[T comparable] map[T]struct{} с методами Add, Has, Delete, объединением и пересечением. Готовые реализации есть в сторонних пакетах, например github.com/deckarep/golang-set/v2.

Добавление, удаление и проверка работают в среднем за O(1). Ключом может быть только сравнимый тип: числа, строки, указатели, массивы и структуры из сравнимых полей. Слайс, map или функцию ключом сделать нельзя.

Порядок обхода map намеренно случайный. Для стабильного вывода ключи сортируют: с Go 1.23 это slices.Sorted(maps.Keys(s)). Очистить сет целиком можно встроенной функцией clear(s), она появилась в Go 1.21.

Альтернативы под задачу: для маленького диапазона целых чисел битовая маска или []bool, для набора из десятка элементов простой слайс с линейным поиском бывает быстрее хеширования.

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

Пишут в общий сет из нескольких горутин без защиты. map не потокобезопасна, и рантайм падает с concurrent map writes. Нужен sync.Mutex или sync.RWMutex, а sync.Map оправдан в узких сценариях вроде кеша с редкой записью.

Рассчитывают на порядок элементов, и тест, который сравнивает вывод со строкой, падает через раз.

Делают сет с ключом any и кладут туда слайс. Компилятор это пропускает, а в рантайме будет паника hash of unhashable type.