Структура

hmap хранит count (это и есть len(m)), B (логарифм числа бакетов), hash0 (случайный seed), указатели buckets и oldbuckets, счётчик nevacuate и флаги. В бакете (bmap) лежат tophash [8]uint8, затем [8]K, затем [8]V, затем указатель на overflow-бакет. Ключи и значения идут отдельными массивами, чтобы не платить padding между K и V.

Поиск

1. Считаем h = hash(key, hash0).
2. Низкие B бит дают номер бакета.
3. Старший байт хеша (tophash) сравниваем с восемью байтами в бакете. Дешёвый фильтр: сами ключи он не трогает.
4. Только для совпавших tophash сравниваем ключ полностью.
5. Не нашли, идём по цепочке overflow-бакетов.

Рост

Триггеров два. Load factor count > 6.5 * 2^B даёт удвоение (B++). А слишком много overflow-бакетов при нормальном count включает sameSizeGrow: перекладку в массив того же размера, чтобы схлопнуть разреженность после массовых удалений.

Эвакуация инкрементальная: старый массив остаётся в oldbuckets, каждая вставка или удаление переселяет один-два бакета. При удвоении старый бакет i расщепляется ровно на два, i и i + 2^oldB: в выборе бакета стал участвовать ещё один бит хеша. Пока рост не закончен, чтение ищет в обоих массивах, а память занята обоими.

Что именно поменялось

• Хеш делится на h1 (старшие биты, они выбирают группу и последовательность проб) и h2 (младшие 7 бит, они ложатся в control-байт слота).
• Control word собирает 8 однобайтовых меток группы в одно 64-битное слово. Вопрос «есть ли в группе слот с таким h2» решается парой инструкций без ветвлений (на amd64 через SSE-инструкции, на остальных архитектурах битовыми трюками над тем же словом), а на выходе битовая маска кандидатов.
• Коллизии разрешаются открытой адресацией с квадратичным пробингом по группам, а не цепочками overflow-бакетов. Указателей между группами нет, значит и промахов кэша меньше.
• Специальные значения control-байта: EMPTY (можно прекратить поиск) и DELETED, надгробие. Через него поиск идёт дальше, иначе порвалась бы цепочка проб.
• Большая мапа разбита на directory из независимых таблиц; растёт по одной таблице, а не целиком, и латентность выходит ровнее.

Что НЕ поменялось

Ни семантика, ни гарантии. Порядок обхода по-прежнему случайный, мапа по-прежнему не потокобезопасна, &m[k] по-прежнему запрещён, comma-ok тот же. Отличие видно только в производительности: чтение больших мап быстрее примерно на 30–60 %, вставка на треть, при сопоставимой памяти. Плюс сломались тесты, которые нелегально завязались на конкретный порядок итерации.

# вернуть старую реализацию (в Go 1.27 опции уже нет)
$ GOEXPERIMENT=noswissmap go build ./...

Свойства, которые от хеша нужны

• Детерминизм. Один ключ всегда даёт одно число (в пределах одной мапы: seed у каждой свой).
• Равномерность. Ключи размазываются по бакетам, иначе всё вырождается в список.
• Скорость. Хеш считается на каждой операции. На amd64 Go берёт memhash на инструкциях AES-NI.

Функцию выбирает компилятор по типу ключа: строкам и байтовым срезам достаётся memhash, числам короткое смешивание, структурам комбинация хешей полей. У типов с указателями внутри хешируется содержимое, а не адрес.

Seed и hash flooding

Каждая мапа при создании получает случайный hash0. Без него атакующий, знающий алгоритм, подобрал бы тысячи ключей в один бакет и превратил бы O(1) в O(n). Классическая DoS-атака на сервис, который складывает заголовки или query-параметры запроса в мапу. Побочный эффект: хеш одного и того же ключа различается между мапами и между запусками, поэтому на порядок итерации нельзя полагаться в принципе.

Способы разрешения коллизий вообще

Эвакуация копирует пары ключ-значение в новый массив бакетов. Если бы язык разрешил сохранить &m[k], то после первой же вставки, запустившей рост, этот указатель смотрел бы в старую память: запись через него молча терялась бы, а чтение возвращало устаревшее значение. Go предпочитает запретить операцию на этапе компиляции.

У слайса такой проблемы нет: там при росте выделяется новый массив, но старый остаётся валидным, и указатель на старый элемент продолжает указывать на живую память (просто перестаёт быть связан со слайсом). Поэтому &s[0] легален.

Что можно, а что нельзя

m := map[string]int{"a": 1}
// p := &m["a"]     // ошибка: cannot take address of m["a"]
m["a"]++            // можно: разворачивается в чтение + сложение + запись
m["a"] += 5         // можно
m["new"]++          // можно: отсутствующий ключ = 0, станет 1

type S struct {
    N int
}
ms := map[string]S{"a": {1}}
// ms["a"].N = 2    // ошибка: cannot assign to struct field in map
v := ms["a"]; v.N = 2; ms["a"] = v      // читаем-меняем-пишем

mp := map[string]*S{"a": {1}}
mp["a"].N = 2                            // работает: адресуем то, на что указывает значение

sl := map[string][]int{"a": {1}}
sl["a"] = append(sl["a"], 2)             // слайс менять можно только через переприсваивание
sl["a"][0] = 9                           // а элемент можно напрямую: индексация идёт
                                         // по указателю внутри значения, а не по самому значению

Порядок обхода и так определяется числом бакетов, seed'ом и историей вставок. Окажись он стабильным «на практике», код начал бы на него опираться, и любое улучшение рантайма (например, переход на Swiss Tables в 1.24) ломало бы прод. Команда Go сделала недетерминированность явной и обязательной: mapiterinit выбирает случайный стартовый бакет и случайное смещение внутри бакета на каждый range.

Мотив номер два: безопасность. Вместе со случайным hash0 это прячет внутреннее распределение ключей.

Как получить детерминированный обход

keys := make([]string, 0, len(m))
for k := range m { keys = append(keys, k) }
slices.Sort(keys)
for _, k := range keys { fmt.Println(k, m[k]) }

// Go 1.23+: на итераторах это одна строка:
for _, k := range slices.Sorted(maps.Keys(m)) { fmt.Println(k, m[k]) }

// для m := map[string]int{"b": 2, "a": 1, "c": 3} оба варианта
// печатают одно и то же при любом запуске:
// a 1
// b 2
// c 3

var m map[string]int   // nil: указатель на hmap равен nil

m == nil        // true
len(m)          // 0
m["x"]          // 0     - чтение легально
v, ok := m["x"] // 0, false
for range m {}  // ноль итераций
delete(m, "x")  // no-op, без паники

m["x"] = 1      // panic: assignment to entry in nil map

Почему асимметрия

Чтение честно вернёт нулевое значение, вообще не обращаясь к памяти: рантайм видит нулевой указатель и сразу отдаёт zero, false. Запись обязана эту память создать, а создавать негде. Аллоцировать hmap сам рантайм не может: мапа передана по значению, и новый указатель некуда записать так, чтобы его увидел вызывающий. Сравни со слайсом, там append возвращает новый заголовок, поэтому и работает с nil.

Где это стреляет в реальном коде

type Config struct {
    Labels map[string]string   // забыли инициализировать в конструкторе
}
c := &Config{}
c.Labels["env"] = "prod"       // panic

// JSON: если в документе поля нет - мапа останется nil
var c2 Config
json.Unmarshal([]byte(`{}`), &c2)
c2.Labels["env"] = "prod"      // panic

// Правильно:
func NewConfig() *Config { return &Config{Labels: map[string]string{}} }
// или ленивая инициализация в сеттере:
func (c *Config) Set(k, v string) {
    if c.Labels == nil { c.Labels = make(map[string]string) }
    c.Labels[k] = v
}

Механика детектора

В заголовке мапы есть флаг записи: с Go 1.24 поле writing, раньше бит hashWriting в hmap.flags. Запись и удаление ставят его на входе и снимают на выходе. Любая операция, увидевшая флаг, вызывает fatal. Процесс падает целиком, defer не выполняются, recover бесполезен: состояние таблицы уже могло быть повреждено, и продолжать небезопасно.

Детектор best-effort: он ловит только пересечение окон операций. Гонку, где записи разошлись по времени, он не заметит, а данные всё равно испортятся. Настоящий инструмент тут go test -race. Параллельное чтение многими горутинами без единого писателя законно и безопасно.

Чем защищаться

• sync.RWMutex + map, выбор по умолчанию. Полная типизация, предсказуемая стоимость, len работает. Проседает, только когда десятки ядер бьются за один мьютекс.
• sync.Map оправдана в двух случаях, прямо названных в документации: (1) ключ пишется один раз и много раз читается; (2) горутины работают с непересекающимися наборами ключей. Минусы: any вместо типов, боксинг и лишние аллокации, нет len.
• Шардирование: массив из N структур «мьютекс + мапа», ключ ложится в шард по хешу. Снимает конкуренцию за один замок, но ломает атомарность операций «по всей мапе».
• Иммутабельный снимок на atomic.Pointer[map[K]V]: читатели берут указатель без блокировок, писатель копирует мапу целиком и подменяет указатель. Отлично для конфигов, которые обновляются раз в минуту.

// RLock не спасает от "проверил-и-записал"
c.mu.RLock()
_, ok := c.m[k]
c.mu.RUnlock()
if !ok {
    c.mu.Lock()
    c.m[k] = compute(k)   // между RUnlock и Lock кто-то мог уже положить
    c.mu.Unlock()
}
// Правильно: под Lock перепроверить (double-checked), либо singleflight
c.mu.Lock()
if _, ok := c.m[k]; !ok { c.m[k] = compute(k) }
c.mu.Unlock()

Список

type Key struct {
    UserID int64
    Region string
}
m := map[Key]int{{1, "ru"}: 10}
fmt.Println(m[Key{1, "ru"}])    // 10 - сравнение пополевое

// Слайс нельзя, но можно массив фиксированной длины:
var id [16]byte
copy(id[:], uuidBytes)
byID := map[[16]byte]string{id: "user"}

// Или сериализовать ключ в строку:
byTags := map[string]int{}
byTags[strings.Join(tags, "\x00")] = 1   // разделитель, который не встречается в данных

// Интерфейс-ключ: компилируется, но падает
var anyMap = map[any]int{}
anyMap[42] = 1         // ок: int comparable
anyMap[[]int{1}] = 1   // panic: runtime error: hash of unhashable type []int

Рантайм не умеет уменьшать B. Мапа, в которой было 10 млн ключей, после delete всех ключей продолжает держать бакеты под 10 млн: len(m) равен нулю, а RSS процесса не меняется. Работает только sameSizeGrow: он схлопывает overflow-цепочки, но основной массив не трогает.

// Не помогает вернуть память:
delete(m, k)          // обнуляет слот, бакеты остаются
clear(m)              // Go 1.21+: как "удалить все ключи", память тоже не отдаёт

// Помогает:
m = make(map[K]V)     // старая мапа становится мусором целиком

// Помогает частично: значения соберёт GC, в бакетах останутся указатели по 8 байт
mp := map[K]*V{}

Как это выглядит в проде

• Кэш без вытеснения, который растёт до пика трафика и остаётся на этом уровне навсегда. Симптом: RSS вырос и не падает, len маленький.
• Ключи-строки. Даже после delete строки собираются, но если они были подстроками одного большого буфера, держится весь буфер (см. главу про строки).
• Мапа как очередь: пишем тысячи ключей в секунду, удаляем сразу, а бакеты вырастают до пикового размера и остаются.

Что делать

1. Периодически пересоздавать: скопировать живые ключи в новую мапу нужного размера (make(map[K]V, len(old))) и заменить.
2. Взять кэш с вытеснением (LRU) вместо голой мапы.
3. Шардировать и пересоздавать шарды по очереди, тогда паузы копирования размажутся.
4. Хранить map[K]*V, если тяжёлые именно значения.

set := make(map[string]struct{}, 1024)
set["a"] = struct{}{}
_, ok := set["a"]        // проверка
delete(set, "a")
len(set)                 // размер

// Операции над множествами пишем руками:
func Union(a, b map[string]struct{}) map[string]struct{} {
    r := make(map[string]struct{}, len(a)+len(b))
    for k := range a { r[k] = struct{}{} }
    for k := range b { r[k] = struct{}{} }
    return r
}

Почему именно struct{}

unsafe.Sizeof(struct{}{}) == 0. Все экземпляры пустой структуры лежат по одному адресу, runtime.zerobase. В бакете мапы массив значений [8]struct{} занимает ноль байт, то есть накладных расходов на значение нет вообще. Для map[T]bool это был бы [8]bool = 8 байт на бакет плюс возможный padding.

Ещё две идиомы с пустой структурой

done := make(chan struct{})   // сигнальный канал: важен факт, а не значение
close(done)                   // broadcast всем читателям

type NoopLogger struct{}      // тип без состояния - экземпляры бесплатны
func (NoopLogger) Log(string) {}

Четыре сценария деградации

1. Коллизии. В обычной жизни их мало благодаря хорошему хешу, но специально подобранные ключи (или очень плохой самописный хеш в другой реализации) дают O(n). В Go от внешней атаки защищает случайный seed, поэтому подобрать коллизии снаружи нельзя.
2. Разреженность. Положили миллион, удалили 990 тысяч, а бакетов по-прежнему миллион. range проходит по всем, локальность кэша плохая.
3. Тяжёлые значения. map[string][4096]byte: каждое чтение и запись копирует 4 КБ, бакет огромный, кэш не работает. Решение: map[string]*T.
4. Нет преаллокации. Насыпать 10 млн ключей «с нуля» стоит ~23 удвоений, и каждое перекладывает всё заново. make(map[K]V, n) сразу выбирает нужный B.

// Разницу легко измерить:
func BenchmarkNoPrealloc(b *testing.B) {
    for b.Loop() {                       // Go 1.24+: b.Loop вместо b.N
        m := map[int]int{}
        for i := 0; i < 1_000_000; i++ { m[i] = i }
    }
}
func BenchmarkPrealloc(b *testing.B) {
    for b.Loop() {
        m := make(map[int]int, 1_000_000)
        for i := 0; i < 1_000_000; i++ { m[i] = i }
    }
}
// преаллоцированная версия обычно быстрее в 1.5–2 раза и делает
// на порядок меньше аллокаций

m := map[string]int{"a": 0}
v1 := m["a"]        // 0
v2 := m["zzz"]      // 0 - неотличимо
v3, ok := m["a"]    // 0, true
v4, ok := m["zzz"]  // 0, false

Синтаксическая форма, а не функция: компилятор видит присваивание в две переменные и вызывает mapaccess2 вместо mapaccess1. Поэтому её нельзя «передать дальше»: f(m[k]) всегда односложная форма.

Тот же синтаксис у трёх других конструкций

v, ok := m[k]           // мапа: ok == есть ли ключ
v, ok := i.(MyType)     // type assertion: ok == совпал ли динамический тип
v, ok := <-ch           // канал: ok == false, если канал закрыт и опустошён
for i, ok := it.Next(); ok; i, ok = it.Next() {}   // ручной итератор

Где обязательно

• Значение это число или bool, и ноль/false валиден: счётчики, лимиты, фича-флаги.
• Нужно отличить «не настроено» от «настроено в ноль», например в конфиге.
• Кэш: в v, ok := cache[k] значение ok == false означает промах, а не «в кэше лежит ноль».

Где не нужно

counts[word]++              // отсутствующий ключ = 0, станет 1, comma-ok не нужен
total += prices[id]         // «нет цены» и «цена 0» здесь одно и то же
sums[k] = append(sums[k], v) // nil-слайс аппендится нормально