Как реализовать множество в Go

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

Отдельного типа set в Go нет, и вопрос про то, знаете ли вы идиому map[T]struct{}, понимаете ли, зачем значение нулевого размера, и умеете ли собрать поверх неё операции над множествами.

Как отвечать

Множество это map, ключи которой и есть элементы. Значение не нужно, поэтому берут struct{}: он занимает ноль байт, и под значения память не выделяется вовсе.

type Set[T comparable] map[T]struct{}

func New[T comparable](items ...T) Set[T] {
    s := make(Set[T], len(items))
    for _, v := range items {
        s[v] = struct{}{}
    }
    return s
}

func (s Set[T]) Add(v T)      { s[v] = struct{}{} }
func (s Set[T]) Delete(v T)   { delete(s, v) }
func (s Set[T]) Has(v T) bool { _, ok := s[v]; return ok }
func (s Set[T]) Len() int     { return len(s) }

Параметр типа обязательно comparable: ключами map не могут быть слайсы, map и функции. Если элемент такой, ключом делают его каноническую строку или хеш.

Вариант map[T]bool короче на чтении (if s[v]), но хранит байт на элемент и допускает двусмысленность: ключ в map есть, а значение false. В библиотечном коде лучше struct{}.

Операции над множествами пишутся в несколько строк, важно только обходить меньший операнд:

func (s Set[T]) Intersect(o Set[T]) Set[T] {
    if len(o) < len(s) {
        s, o = o, s
    }
    res := make(Set[T])
    for v := range s {
        if o.Has(v) {
            res.Add(v)
        }
    }
    return res
}

Сложность: Add, Has, Delete амортизированно O(1); объединение O(n+m), пересечение O(min(n,m)).

Две вещи, о которых стоит сказать самому:

• Порядок обхода map рандомизирован намеренно. Метод, возвращающий элементы срезом, каждый запуск отдаёт их в новом порядке. Нужен стабильный вывод, сортируйте: slices.Sorted(maps.Keys(s)) в Go 1.23 или slices.Sort по собранному срезу раньше.
• Map небезопасна на конкурентную запись. Параллельная запись даёт fatal error, который не ловится через recover. Значит либо sync.RWMutex вокруг структуры, либо sync.Map для сценария «много читателей, редкие записи».

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

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

Пишут map[T]bool и потом ловят баг на записи s[v] = false, когда ключ есть, а проверка возвращает false; забывают про случайный порядок обхода и пишут тест, сравнивающий срез элементов с литералом.