Какой тип данных использовать для множества уникальных значений в Go

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

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

Как отвечать

Идиоматичный вариант map[T]struct{}: ключи map уникальны, а пустая структура как значение занимает ноль байт. Добавление set[x] = struct{}{}, проверка _, ok := set[x], удаление delete(set, x), всё в среднем за O(1). С дженериками это оборачивают в тип type Set[T comparable] map[T]struct{} с методами Add и Has.

Что стоит добавить:

• map[T]bool: тоже рабочий вариант, проверка короче (if set[x]), но на значение уходит байт и появляется двусмысленность между false и отсутствием ключа;
• ограничение comparable: ключом может быть число, строка, указатель, массив или структура из сравнимых полей, а срез, map и функция нельзя;
• маленькие наборы: на десятке элементов срез с slices.Contains бывает быстрее map и не аллоцирует лишнего, а дедупликацию среза делает связка slices.Sort и slices.Compact;
• плотные целые: если значения это небольшие неотрицательные числа, битовое множество на []uint64 на порядки компактнее.

Про память честнее сказать так: значение struct{} ничего не весит, но сама map хранит ключи, служебные метаданные и запас свободных слотов, так что бесплатным такое множество не назовёшь. Готовые библиотеки множеств есть, но в стандартной библиотеке их нет, и в большинстве кодовых баз обходятся map.

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

Пишут в map из нескольких горутин без синхронизации. Рантайм часто это обнаруживает и завершает программу с fatal error: concurrent map writes, и recover здесь не спасает. Нужен sync.Mutex или sync.RWMutex, реже sync.Map.

Рассчитывают на порядок обхода. Порядок range по map намеренно не фиксирован, для стабильного вывода ключи собирают в срез и сортируют.

Объявляют var s map[string]struct{} и сразу пишут в неё. Чтение из nil map работает, а запись вызывает панику, map нужно создать через make или литерал.