Устройство map в Go • Senior Go Interview Prep

Модуль: Core Go · Уровень: Senior

TL;DR#

map в Go — это хэш-таблица с разрешением коллизий методом цепочек через «бакеты», где каждый бакет хранит до 8 пар key/value. Таблица растёт инкрементально (эвакуация бакетов происходит порциями при записи/удалении), порядок итерации намеренно рандомизирован, map не потокобезопасна (конкурентная запись приводит к нерекаверабельному fatal error), и нельзя брать адрес элемента, потому что реаллокация при росте инвалидирует указатели. В Go 1.24 классическая реализация заменена на Swiss Tables.

Теория#

Базовая структура (классическая реализация, до Go 1.24)#

Заголовок map описывается структурой hmap (упрощённо, из runtime/map.go):

type hmap struct {
    count     int    // число элементов, возвращается len()
    flags     uint8  // флаги состояния (iterator, write, sameSizeGrow...)
    B         uint8  // log2 числа бакетов: бакетов = 2^B
    noverflow uint16 // примерное число overflow-бакетов
    hash0     uint32 // seed хэш-функции (рандомизация на старте)

    buckets    unsafe.Pointer // массив 2^B бакетов
    oldbuckets unsafe.Pointer // предыдущий массив бакетов во время роста
    nevacuate  uintptr        // прогресс эвакуации (индекс)

    extra *mapextra // overflow-бакеты и пр.
}

Переменная типа map[K]V — это указатель *hmap. Поэтому map передаётся «как ссылка»: копия переменной указывает на тот же hmap. Нулевое значение map — nil (var m map[K]V), чтение из него безопасно (вернёт zero value), но запись паникует.

Бакет (bmap)#

Каждый бакет — структура bmap, в которой:

tophash[8] — массив из 8 байт, верхние 8 бит хэша каждого ключа (плюс служебные маркеры состояния эвакуации).
8 ключей подряд.
8 значений подряд.
указатель на overflow-бакет.

bmap layout:
+-----------------------------+
| tophash[0..7]   (8 байт)    |
+-----------------------------+
| key0 key1 ... key7          |
+-----------------------------+
| val0 val1 ... val7          |
+-----------------------------+
| overflow *bmap              |
+-----------------------------+

Ключевая деталь: ключи и значения хранятся раздельными группами (k0k1...k7 v0v1...v7), а не чередуясь (k0v0 k1v1). Это убирает padding из-за выравнивания: если бы пары чередовались, например map[int64]int8, каждая пара требовала бы выравнивания под 8 байт и тратила память на padding. Раздельное хранение позволяет упаковать всё плотно.

Поле overflow — это разрешение коллизий: когда в основной бакет не помещается 9-й ключ, создаётся overflow-бакет и связывается в цепочку.

Хэширование и распределение#

При вставке/поиске ключа:

Считается хэш ключа с использованием hash0 (seed). Хэш-функции в runtime ассемблерные, для многих типов используют AES-инструкции CPU.
Младшие B бит хэша выбирают номер бакета: bucket = hash & (2^B - 1).
Старшие 8 бит хэша → tophash. При поиске сначала сравнивается дешёвый tophash (1 байт), и только при совпадении сравниваются полные ключи. Это быстрый фильтр, отсекающий большинство несовпадений без дорогого сравнения ключей.

tophash со значением < minTopHash зарезервированы как маркеры состояний (пустая ячейка, эвакуированная и т.д.); реальные tophash сдвигаются вверх, чтобы не пересекаться с маркерами.

Рост и инкрементальная эвакуация#

Load factor = 6.5 — среднее число элементов на бакет, при превышении которого таблица растёт. Порог 6.5 подобран эмпирически как компромисс между перерасходом памяти (мало элементов на бакет) и большим числом overflow-цепочек (много элементов).

Есть два вида роста:

Вид роста	Когда	Что делает
Удвоение (double)	`count / 2^B > 6.5`	B увеличивается на 1, число бакетов удваивается
Same-size grow	слишком много overflow-бакетов при невысоком заполнении	число бакетов то же, но элементы перепаковываются плотнее, убирая «дыры» от удалений

Рост не происходит за один проход — это убило бы предсказуемость задержек на больших map. Вместо этого:

При старте роста текущие buckets становятся oldbuckets, выделяется новый массив buckets.
На каждую операцию записи/удаления вызывается growWork, который эвакуирует 1–2 старых бакета в новые (тот, что сейчас трогаем, плюс один по nevacuate для гарантии прогресса).
nevacuate отслеживает, сколько старых бакетов уже переселено.
Поиск во время роста проверяет: если бакет ещё не эвакуирован — ищет в oldbuckets, иначе в новых.

При удвоении каждый старый бакет распределяется на два новых (X и Y): новый бит хэша (бит номер B-1 относительно старого) решает, в верхнюю или нижнюю половину попадёт ключ. Поэтому эвакуация одного старого бакета порождает до двух новых.

// схематично, что делает growWork при записи
func growWork(t, h, bucket) {
    evacuate(t, h, bucket & h.oldbucketmask()) // эвакуировать бакет, который трогаем
    if h.growing() {
        evacuate(t, h, h.nevacuate) // плюс ещё один для прогресса
    }
}

Рандомизация порядка итерации#

for k, v := range m каждый раз обходит элементы в разном порядке. Это сделано намеренно:

mapiterinit выбирает случайный стартовый бакет и случайный стартовый offset внутри бакета (через fastrand).
Итератор идёт по кругу от случайной точки.

Цель — не дать разработчикам случайно завязаться на порядок (которого у хэш-таблицы и так нет по семантике). Без рандомизации код работал бы «случайно правильно» из-за стабильного порядка конкретной реализации, а потом сломался бы при смене версии Go. Это защита от хрупких зависимостей. Если нужен детерминированный порядок — собирайте ключи в slice и сортируйте.

Concurrent access: map не потокобезопасна#

Runtime активно детектирует конкурентный доступ через флаг hashWriting в h.flags:

Перед записью флаг выставляется, после — снимается.
Если при входе в запись/чтение замечен уже выставленный флаг — это значит, что другая горутина пишет одновременно → fatal error: concurrent map read and map write / concurrent map writes.

Важнейший нюанс: это fatal error, а не panic. Его нельзя поймать через recover() — программа падает целиком. Детектор не гарантированный (он best-effort, не race detector), но если сработал — это всегда настоящая гонка.

Решения для конкурентного доступа:

sync.RWMutex поверх обычной map.
sync.Map — для специфичных паттернов (много чтений / write-once, disjoint keys).

var (
    mu sync.RWMutex
    m  = make(map[string]int)
)
func get(k string) (int, bool) {
    mu.RLock(); defer mu.RUnlock()
    v, ok := m[k]
    return v, ok
}

Почему нельзя брать адрес элемента map#

m := map[string]int{"a": 1}
p := &m["a"] // compile error: cannot take the address of m["a"]
m["a"]++     // ОК
m["a"].field = 5 // если значение — структура, это ошибка компиляции

Причина — рост и эвакуация: при вставке map может реаллоцировать бакеты и физически переместить key/value в другую область памяти. Любой ранее взятый указатель стал бы висячим (dangling). Поскольку компилятор не может гарантировать стабильность адреса, он запрещает &m[k] в принципе.

Следствия:

Нельзя мутировать поле структуры-значения напрямую: m[k].field = x — ошибка. Нужно: достать копию, изменить, положить обратно; либо хранить map[K]*V (указатели) и мутировать через них.

type P struct{ X int }
m := map[string]P{"a": {}}
// m["a"].X = 1  // ошибка
v := m["a"]; v.X = 1; m["a"] = v // правильно
// или: map[string]*P, тогда m["a"].X = 1 работает

Comparable ключи#

Ключом может быть только comparable-тип (тот, к которому применим ==):

Можно: все числовые типы, bool, string, указатели, каналы, интерфейсы, массивы из comparable-элементов, структуры из comparable-полей.

Нельзя: срезы (slice), map, функции — они не comparable. Попытка → ошибка компиляции invalid map key type.

Подводные камни comparable:

interface{} как ключ опасен: тип comparable, но если в интерфейс положить несравнимое значение (например, slice), сравнение при доступе к map вызовет runtime panic (runtime error: hash of unhashable type). Компилятор это не ловит.
NaN: math.NaN() != math.NaN(). Если использовать float-ключи, NaN-ключ нельзя найти после вставки (каждый NaN «уникален»), и такой элемент невозможно ни прочитать, ни удалить через ключ — только итерацией.
Структура с float-полем → те же проблемы с NaN.

Zero value и comma-ok#

Доступ к отсутствующему ключу возвращает zero value типа значения, а не панику:

m := map[string]int{}
x := m["missing"] // x == 0, без ошибки

Чтобы отличить «ключ есть со значением zero» от «ключа нет» — форма comma-ok:

v, ok := m["k"] // ok == false, если ключа нет
if v, ok := m["k"]; ok { /* ключ существует */ }

Удаление: delete(m, k) — безопасно даже если ключа нет (no-op), не паникует.

Удаление во время итерации#

Спецификация Go явно разрешает удалять элементы во время range:

Если элемент удалён до того, как итератор до него дошёл, он не будет отдан.
Элементы, добавленные во время итерации, могут быть отданы, а могут и нет — поведение неопределено. Полагаться на это нельзя.

for k := range m {
    if shouldDelete(k) {
        delete(m, k) // легально и безопасно
    }
}

Предразмер: make(map, n)#

make(map[K]V, n) создаёт map с заранее выделенными бакетами под ~n элементов:

Runtime подбирает B так, чтобы n элементов поместились без немедленного роста (с учётом load factor 6.5).
Это избегает многократных ростов/эвакуаций при наполнении: вместо O(log n) ростов с перепаковкой — одно выделение.
На больших объёмах даёт заметный выигрыш по времени и снижает фрагментацию/GC-нагрузку.

m := make(map[int]int, 1_000_000) // одно выделение, без серии ростов

n — это подсказка (hint), не жёсткий лимит: map всё равно вырастет при превышении.

Эволюция: Swiss Tables (Go 1.24)#

Начиная с Go 1.24 runtime-реализация map переписана на основе Swiss Tables (дизайн из Abseil/C++):

Вместо бакетов с overflow-цепочками — группы по 8 слотов с компактными метаданными управления (control bytes), которые сканируются через SIMD/побитовые операции сразу для всей группы.
Открытая адресация вместо цепочек overflow → лучше cache locality, меньше pointer-chasing.
Быстрее поиск/вставка (особенно на больших map), часто меньше памяти.

Важно: это внутренняя оптимизация. Внешняя семантика сохранена — рандомизация итерации, запрет конкурентного доступа, запрет адреса элемента, comma-ok и пр. остаются прежними. Код, корректно использующий map, продолжает работать без изменений; код, завязанный на детали старой реализации (например, на конкретный порядок), и так был некорректен.

Подводные камни / gotchas#

Запись в nil-map паникует. var m map[string]int; m["x"]=1 → panic. Чтение из nil-map — безопасно (zero value). Всегда инициализируйте через make или литерал перед записью.
fatal error при гонке нельзя поймать. recover() не спасёт от concurrent map writes. Тестируйте под -race, защищайте мьютексом.
m[k].field = x не компилируется для структур-значений. Используйте копию-обратно или map[K]*V.
interface{}-ключ с несравнимым значением — runtime panic, не compile error.
NaN-ключи недостижимы после вставки.
Нельзя полагаться на порядок итерации — он рандомизирован специально.
Итерация не атомарна и не делает snapshot. Изменения во время range частично видны, частично нет (для добавлений — неопределено).
Память не возвращается ОС после delete. map не уменьшает число бакетов; после массового удаления память остаётся занятой. Чтобы реально освободить — создайте новую map и скопируйте нужное.
Большие значения копируются. v := m[k] копирует значение целиком; для крупных структур это дорого — рассмотрите map[K]*V.
Указатель на значение в map нельзя получить штатно — следствие запрета &m[k].

Вопросы на собеседовании#

В: Как устроена map внутри? Что такое бакет и сколько пар в нём? О: map — это указатель на hmap. Данные лежат в массиве бакетов (bmap), число которых = 2^B. Каждый бакет хранит до 8 пар key/value плюс массив tophash (8 байт верхних бит хэша) и указатель на overflow-бакет. Ключи и значения хранятся раздельными группами (все ключи, потом все значения) для устранения padding. Номер бакета выбирается младшими B битами хэша, поиск внутри бакета ускоряется сравнением tophash перед полным сравнением ключей.

В: Что происходит при росте map? Что такое инкрементальная эвакуация? О: При превышении load factor 6.5 (или избытке overflow-бакетов) запускается рост: текущие бакеты становятся oldbuckets, выделяется новый массив (удвоенный — double grow, или того же размера — same-size grow для дефрагментации). Эвакуация не делается разом: на каждую запись/удаление growWork переселяет 1–2 старых бакета в новые, прогресс отслеживается nevacuate. До завершения поиск проверяет, эвакуирован ли нужный старый бакет, и читает из old или new. Это размазывает стоимость роста, избегая длинных пауз.

В: Почему &m[k] запрещён? О: Потому что при росте map бакеты реаллоцируются и элементы физически перемещаются в новую память. Любой удержанный указатель стал бы висячим. Компилятор не может гарантировать стабильность адреса, поэтому запрещает взятие адреса элемента в принципе. Следствие — нельзя мутировать поле структуры-значения напрямую (m[k].field=x); используют копию-обратно или map[K]*V.

В: Что будет при конкурентной записи в map? Можно ли это поймать? О: Runtime детектирует гонку через флаг hashWriting и выдаёт fatal error: concurrent map writes (или read and write). Это не panic, а fatal error — его нельзя перехватить через recover(), программа падает целиком. Детектор best-effort, но ложных срабатываний не даёт. Решение: sync.RWMutex или sync.Map.

В: Почему порядок итерации каждый раз разный? О: Это сделано намеренно. mapiterinit выбирает случайный стартовый бакет и offset. Цель — не дать коду завязаться на порядок, которого у хэш-таблицы нет семантически, чтобы исключить хрупкие зависимости, ломающиеся при смене реализации/версии. Для детерминизма ключи собирают в slice и сортируют.

В: Какие типы можно использовать как ключи? О: Только comparable: числа, bool, string, указатели, каналы, интерфейсы, массивы и структуры из comparable-элементов. Нельзя: slice, map, функции (compile error). Опасности: interface{}-ключ с несравнимым динамическим значением даёт runtime panic; NaN-ключи недостижимы после вставки, т.к. NaN != NaN.

В: В чём разница между v := m[k] и v, ok := m[k]? О: Первая форма всегда возвращает значение: zero value, если ключа нет — поэтому нельзя отличить «нет ключа» от «значение равно zero». Comma-ok возвращает второй bool ok, который точно говорит о наличии ключа. Это важно для типов, где zero value — валидное значение (0, “”, false).

В: Зачем нужен make(map, n) с числом? О: Это подсказка о предполагаемом размере. Runtime сразу выделяет достаточно бакетов под n элементов с учётом load factor, избегая серии ростов и эвакуаций при наполнении. На больших объёмах заметно ускоряет заполнение и снижает GC-давление. Это hint, а не лимит — map всё равно вырастет при превышении.

В: Можно ли удалять элементы во время range? О: Да, спецификация это разрешает. Уже удалённый (до прохода итератора) элемент не будет отдан. А вот добавленные во время итерации элементы могут быть отданы или нет — поведение неопределено, полагаться нельзя.

В: Что изменилось в map в Go 1.24? О: Реализация переведена на Swiss Tables: группы слотов с control-байтами, сканируемыми SIMD-операциями, открытая адресация вместо overflow-цепочек. Это даёт лучше cache locality, меньше pointer-chasing, обычно быстрее и компактнее. Внешняя семантика (рандомизация, запрет гонок и &m[k], comma-ok) не изменилась.

На что копают на senior+#

Почему именно load factor 6.5, а не степень двойки? Ожидают рассуждение о компромиссе память/скорость и о том, что значение подобрано эмпирически бенчмарками; senior упомянет, что слишком высокий фактор раздувает overflow-цепочки, а слишком низкий — тратит память на полупустые бакеты.
Раздельное хранение ключей и значений. Follow-up: «почему не k0v0 k1v1?» — ответ про устранение padding из-за выравнивания. Это признак понимания layout памяти, а не только API.
fatal error vs panic. Граница между recoverable и non-recoverable. Часто докапываются: «а race detector и этот детектор — одно и то же?» (нет: детектор map — дешёвый best-effort флаг в runtime, race detector — отдельный инструмент с shadow memory).
Same-size grow. Многие знают про удвоение, но не про рост того же размера для дефрагментации после массовых удалений. Знание этого выделяет кандидата.
Память не возвращается после delete. Follow-up про долгоживущие map с большим оборотом ключей и как с этим бороться (пересоздание map).
Поведение во время роста при поиске. «Где лежит ключ, если бакет ещё не эвакуирован?» — в oldbuckets; проверяется через маркеры в tophash.
sync.Map — когда он лучше мьютекса? Senior знает, что sync.Map оптимизирован под конкретные паттерны (read-mostly, disjoint key sets) и в общем случае мьютекс+map может быть быстрее; не предлагает sync.Map как универсальное решение.
Эволюция к Swiss Tables и неизменность контракта. Способность отделить детали реализации от гарантий языка — ключевой senior-навык: «код, сломавшийся от перехода на Swiss Tables, и так был некорректен».
Хэш-seed hash0. Зачем рандомизировать сам хэш на старте (помимо порядка итерации) — защита от hash-flooding DoS-атак на предсказуемые коллизии.