Можно ли сделать структуру сета, которая не занимает лишнюю память?

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

Знаете ли вы, что встроенного множества в Go нет, и понимаете ли, из чего складывается его память. Вопрос с подвохом: честный ответ «лишнего почти не занимает» звучит иначе, чем «не занимает».

Как отвечать

Канонический приём: map[T]struct{}. Пустая структура имеет нулевой размер, поэтому значения в такой карте места не занимают, а уникальность ключей обеспечивает сама карта.

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

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

Сразу проговорите честную часть: дешёвой карта не бывает. Внутри лежат служебные данные для хэшей, сами ключи и запас по коэффициенту заполнения, так что относительно map[T]bool вы экономите один байт на элемент, не больше. Зато map[T]bool читается проще и умеет отличать отсутствие ключа от ключа со значением false, поэтому выбор не всегда в пользу пустой структуры.

Если памяти действительно жалко, вариантов несколько: отсортированный срез с бинарным поиском, когда множество строится один раз и дальше только читается; битовая маска для плотного диапазона чисел; фильтр Блума там, где ложноположительные ответы допустимы.

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

Первое: из слов «нулевой размер» делают вывод, что множество бесплатное. Расход всё равно линеен по числу ключей, а строковые ключи тянут за собой и сами строки, на которые они ссылаются.

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

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