> Как работает алгоритм генерации уникальных чисел с генератором и map в Go (Go)

Короткий ответ

Генератор уникальных чисел в Go - это функция, возвращающая замыкание, которое при каждом вызове возвращает следующее значение из последовательности. map здесь используется для отслеживания уже выданных чисел, чтобы гарантировать уникальность. Комбинация генератора и map позволяет создавать ленивые, потокобезопасные (при использовании мьютекса) последовательности без хранения всего набора в памяти. Ключевой момент - генератор инкапсулирует состояние, а map служит быстрым хранилищем для проверки дубликатов.

Подробное объяснение

Генератор в Go реализуется через замыкание: функция возвращает анонимную функцию, которая захватывает переменные из внешней области видимости. Эти переменные сохраняют состояние между вызовами. Для уникальности чисел используется map[int]struct{} или map[int]bool - проверка наличия ключа выполняется за O(1).

Алгоритм работы:

1. Инициализируем map для хранения выданных чисел.
2. Создаём счётчик или источник случайных чисел.
3. При каждом вызове генератора:
   • генерируем кандидата (инкремент или random);
   • проверяем его наличие в map;
   • если ключ уже существует - генерируем следующего кандидата;
   • если ключа нет - добавляем в map и возвращаем значение.

Для последовательных уникальных чисел (1, 2, 3...) map избыточен - достаточно инкремента. Но для случайных или восстанавливаемых последовательностей map обязателен. Также map позволяет проверять уникальность в рамках нескольких генераторов или внешних источников данных.

Потокобезопасность достигается через sync.Mutex внутри замыкания. Без мьютекса конкурентные вызовы могут привести к гонке данных и дубликатам.

На практике

В реальном backend-коде такой генератор применяется для:

• создания уникальных ID в распределённых системах (но чаще используют snowflake или UUID);
• генерации номеров заказов в рамках одной ноды;
• тестирования - создание уникальных тестовых данных;
• пулов идентификаторов с последующим освобождением.

Важный trade-off: map растёт с каждым выданным числом, что увеличивает потребление памяти. Для больших последовательностей лучше использовать битовые карты или просто инкремент. Если нужна воспроизводимость - используйте math/rand с фиксированным seed.

Пример кода

GO
package main

import (
    "fmt"
    "sync"
)

// uniqueGenerator возвращает генератор уникальных чисел.
// start - начальное значение, step - шаг.
func uniqueGenerator(start, step int) func() int {
    mu := &sync.Mutex{}
    used := make(map[int]struct{})
    current := start

    return func() int {
        mu.Lock()
        defer mu.Unlock()

        for {
            candidate := current
            current += step

            if _, exists := used[candidate]; !exists {
                used[candidate] = struct{}{}
                return candidate
            }
        }
    }
}

func main() {
    gen := uniqueGenerator(1, 1)

    fmt.Println(gen()) // 1
    fmt.Println(gen()) // 2
    fmt.Println(gen()) // 3
}

Как отвечать на собеседовании

Начните с определения генератора как замыкания с состоянием. Затем объясните роль map - быстрая проверка дубликатов. Упомяните сложность O(1) для проверки и вставки. Обязательно скажите про потокобезопасность и мьютекс. Приведите пример, где такой подход оправдан, и где он избыточен (например, для последовательных чисел достаточно инкремента). Если спросят про альтернативы - упомяните sync/atomic для атомарного инкремента или каналы для генерации.

Что проверяет интервьюер

• понимание замыканий и захвата переменных;
• знание структур данных и их сложности;
• умение работать с конкурентностью;
• способность оценить trade-off между памятью и скоростью;
• практический опыт написания идиоматичного Go-кода.

Типичные ошибки

• использование map[int]bool вместо map[int]struct{} - лишнее выделение памяти;
• отсутствие мьютекса при конкурентном доступе;
• бесконечный цикл при исчерпании диапазона (например, при переполнении int);
• попытка использовать генератор для криптографически уникальных значений - нужен crypto/rand;
• забывают, что map не гарантирует порядок - если порядок важен, используйте слайс или отдельный счётчик.