Как устроен Map в Go?

Map в Go реализован как хеш-таблица.

Основные компоненты структуры map:

• Хеш-функция: Отображает ключи в хеш-значения (целые числа).
• Массив бакетов (buckets): Набор списков или массивов, где хранятся пары ключ-значение. Индекс бакета определяется хеш-значением ключа.
• Обработка коллизий: При совпадении хешей для разных ключей (коллизия) элементы с этими ключами хранятся в одном бакете, обычно в виде связанного списка или переполнения в соседний бакет.
• Нагрузочный фактор (load factor): Соотношение количества элементов к количеству бакетов. При превышении определенного порога происходит рехеширование – создание нового, большего массива бакетов и перемещение всех элементов из старых бакетов в новые.

Структура map в Go представлена типом hmap:

type hmap struct {
    count     int // Количество элементов
    flags     uint8 // Флаги состояния
    B         uint8 // log_2 количества бакетов (buckets number is 2^B)
    noverflow uint16 // Количество переполненных бакетов (только для статистики)
    hash0     uint32 // Начальное значение хеш-функции

    buckets    unsafe.Pointer // указатель на массив бакетов (основной и переполненные)
    oldbuckets unsafe.Pointer // указатель на старый массив бакетов во время миграции
    nevacuate  uintptr // Обозначает, до какого старого бакета завершена миграция

    extra *mapextra // Дополнительная информация (опционально)
}

type mapextra struct {
    overflow    *[2]*[]*bmap // Указатели на массивы переполненных бакетов
    oldoverflow *[2]*[]*bmap // Указатели на старые массивы переполненных бакетов
    nextOverflow *bmap // Следующий свободный переполненный бакет
}

type bmap struct {
    tophash [8]uint8 // Топ-хеш (верхние биты хеша) для ускорения поиска в бакете
    // Далее следуют ключи, значения и указатель на следующий bmap (если бакет переполнен)
    // lay out all the data for hmap.buckets in a single malloc chunk
    // see ../../runtime/map.go for details
}

Операции:

• Вставка/Обновление: Вычисляется хеш ключа, определяется бакет. Если ключ уже существует, значение обновляется. Иначе, пара ключ-значение добавляется в бакет. При переполнении бакета или превышении Load Factor может произойти рехеширование.
• Поиск: Вычисляется хеш ключа, определяется бакет. Перебираются элементы в бакете по топ-хешу, затем полное сравнение ключей. Возвращается значение и флаг наличия.
• Удаление: Вычисляется хеш ключа, определяется бакет. Элемент отмечается как удаленный (но не немедленно удаляется из памяти). Удаление происходит при последующих операциях или при рехешировании.

Мапа в Go является несинхронизированной и не может безопасно использоваться несколькими горутинами одновременно без внешней синхронизации.