Мапы: устройство, бакеты, коллизии, рост

Кратко о теме

map в Go — встроенная хеш-таблица. В коде переменная типа map[K]V — это указатель на структуру-заголовок в куче (runtime.hmap до Go 1.24, internal/runtime/maps.Map начиная с Go 1.24). Поэтому мапа передаётся в функцию «по ссылке» в бытовом смысле: копируется указатель, изменения видны вызывающему. Нулевое значение мапы — nil: из неё можно читать (вернётся нулевое значение типа), можно вызывать len, delete и range, но запись паникует. Рабочую мапу создают через make(map[K]V, hint) или литералом.

До Go 1.23 включительно реализация была классической: массив из 2^B бакетов, в каждом бакете 8 слотов, отдельный массив tophash из 8 байт (старший байт хеша каждого ключа) для быстрой отбраковки, и указатель overflow на цепочку дополнительных бакетов. Коллизии разрешались комбинацией «бакет как маленькая корзина + связный список overflow-бакетов» (chaining). Когда средняя заполненность превышала 6.5 элемента на бакет, число бакетов удваивалось, и начиналась инкрементальная эвакуация: старый массив oldbuckets жил рядом с новым, и при каждой записи/удалении переносилось 1–2 бакета. Это размазывало стоимость роста по операциям вместо одной длинной паузы.

В Go 1.24 встроенная мапа переписана на Swiss Tables (порт идеи из Abseil, реализация в internal/runtime/maps). Теперь это открытая адресация: данные лежат в группах по 8 слотов, у каждой группы есть 8-байтовое control word — по байту на слот, где 1 бит говорит «пусто / удалено», а остальные 7 бит хранят H2 (младшие 7 бит хеша). Одной 64-битной операцией сравниваются сразу все 8 слотов группы — это и даёт основной выигрыш. H1 (старшие 57 бит хеша) выбирает стартовую группу, дальше идёт квадратичное пробирование до группы с пустым слотом. Чтобы рост оставался инкрементальным без «двух массивов сразу», мапа разбита на таблицы (до 1024 элементов каждая), выбираемые через directory по старшим битам хеша (extendible hashing): растёт и перестраивается всегда только одна таблица, а не вся мапа. Слова «бакет», «overflow», «эвакуация» на собеседовании по-прежнему уместны, но правильный ответ в 2025 году звучит так: «до 1.24 — бакеты по 8 слотов с overflow-цепочками и эвакуацией; с 1.24 — swiss table с группами, control word и делением таблиц».

Что не изменилось между реализациями и что чаще всего спрашивают: порядок обхода мапы намеренно рандомизирован; элемент мапы не адресуем (&m[k] — ошибка компиляции), потому что при росте данные переезжают; мапа не потокобезопасна, и рантайм умеет ловить (не гарантированно) конкурентный доступ, роняя процесс fatal error: concurrent map writes; удаление ключей не уменьшает выделенную память; ключом может быть любой сравнимый (comparable) тип.

Вопросы и ответы

Как работают новые мапы? Чем они отличаются от старых реализаций?

Коротко. С Go 1.24 мапы реализованы как Swiss Tables: открытая адресация, группы по 8 слотов с 8-байтовым control word (по 7 бит хеша на слот), квадратичное пробирование и деление мапы на таблицы через directory (extendible hashing). Старая реализация — массив бакетов по 8 слотов с overflow-цепочками и пошаговой эвакуацией при росте.

Глубже. Ключевые отличия: (1) поиск внутри группы делается за одно 64-битное битовое сравнение всех 8 байт control word вместо последовательного прохода по tophash; (2) коллизии разрешаются пробированием по группам, а не связным списком overflow-бакетов, поэтому нет деградации на длинных цепочках; (3) удаление ставит tombstone (0b1111_1110), если в группе нет пустых слотов, иначе слот помечается пустым; (4) рост: до 1024 элементов таблица просто заменяется вдвое большей, дальше таблица расщепляется на две, а directory удваивается — перестраивается только одна таблица, поэтому долгих пауз нет и старый механизм oldbuckets/nevacuate больше не нужен; (5) мапы до 8 элементов живут в одной группе вообще без индексации — линейное сравнение control word. Максимальная средняя загрузка группы — 7 из 8 (87.5%) против ~6.5/8 (81%) в старой. Вернуть старую реализацию в Go 1.24 можно сборкой с GOEXPERIMENT=noswissmap. Замеры команды Go показывали ускорение операций доступа на десятки процентов на больших мапах; на крошечных мапах разница невелика.

Что такое map в Go и как она работает?

Коротко. map[K]V — встроенная хеш-таблица с амортизированным O(1) на вставку, поиск и удаление. Ключ хешируется, по хешу выбирается группа/бакет, внутри по короткому фрагменту хеша быстро отбрасываются неподходящие слоты, а у кандидатов ключ сравнивается полностью.

Глубже. Переменная типа map — указатель на заголовок в куче, поэтому map нельзя сравнивать (кроме как с nil) и нельзя копировать «глубоко» присваиванием. Хеш-функция берётся из типа ключа (maptype.Hasher) и солится случайным seed, созданным при инициализации мапы, — это защита от подбора коллизий (hash-flooding). Отсюда же и разный порядок обхода между запусками.

m := make(map[string]int, 100) // hint 100 — сразу выделить место под ~100 элементов
m["a"] = 1
v, ok := m["b"] // 0, false
delete(m, "a")
fmt.Println(len(m)) // 0

Что происходит при коллизиях в map ?

Коротко. Коллизия — не ошибка, а штатный режим: несколько ключей попадают в один бакет/группу. В старой реализации они кладутся в свободные слоты бакета, а когда 8 слотов заканчиваются — в overflow-бакет; в swiss-таблицах поиск переходит к следующей группе по квадратичному пробированию. Правильный элемент находят полным сравнением ключа.

Глубже. Важно различать два уровня. Первый — совпадение младших битов хеша (номера бакета) при разных хешах: это самый частый случай. Второй — полное совпадение 64-битного хеша при разных ключах: тогда tophash/H2 совпадут и спасёт только сравнение самих ключей. Оба случая обрабатываются одинаково с точки зрения кода: сначала быстрый фильтр по 1 байту (старому tophash или новому H2), потом честное == по ключу. Ложное срабатывание фильтра — примерно 1 из 128, что дешевле, чем сравнивать ключи всегда.

Можете описать внутреннюю структуру map ?

Коротко. До Go 1.24: hmap{count, flags, B, noverflow, hash0, buckets, oldbuckets, nevacuate, extra}, где buckets — массив 2^B структур bmap (8 байт tophash, затем 8 ключей, затем 8 значений, затем указатель на overflow). С Go 1.24: Map{used, seed, dirPtr, dirLen, globalDepth, ...} — directory из таблиц, таблица — массив групп, группа — control word (8 байт) + 8 слотов key/elem.

Глубже. Раскладка «сначала все ключи, потом все значения» в старом bmap сделана ради экономии на выравнивании: в map[int64]int8 при чередовании key/value было бы по 7 байт padding на элемент. Ключи и значения больше 128 байт хранятся косвенно — в слоте лежит указатель. hmap.extra держит слайс указателей на overflow-бакеты, если ключ и значение не содержат указателей: иначе GC освободил бы overflow-цепочку, потому что тип бакета помечен как беспоинтерный. flags содержит бит hashWriting, по которому рантайм детектирует конкурентную запись.

Что такое бакеты в реализации map и как они работают?

Коротко. Бакет — корзина на 8 пар ключ/значение плюс массив из 8 байт tophash для быстрой отбраковки и указатель на overflow-бакет. Номер бакета берётся из младших B бит хеша: hash & (2^B - 1). В Go 1.24 аналог бакета — группа из 8 слотов с control word.

Глубже. Работа поиска: вычислили хеш → взяли младшие B бит → нашли бакет → сравнили старший байт хеша с восемью tophash → для совпавших сравнили ключи полностью → если не нашли и есть overflow, повторили на следующем бакете цепочки. При этом слоты бакета — не «отдельные бакеты», а именно ячейки одной корзины, за счёт чего одна кэш-линия обслуживает несколько кандидатов.

Освобождается ли память сразу после удаления ключа из map ?

Коротко. Нет. delete очищает слот (обнуляя его содержимое, чтобы GC мог собрать то, на что ссылались ключ и значение), но массив бакетов/таблиц не сжимается — мапа навсегда сохраняет достигнутый размер, пока жива.

Глубже. Практическое следствие: мапа, в которую когда-то положили 10 млн ключей, а потом всё удалили, продолжит держать десятки-сотни мегабайт. clear(m) (Go 1.21+) тоже только удаляет элементы, ёмкость остаётся. Единственный способ вернуть память — пересоздать мапу (m = make(map[K]V, len(live)) с копированием живых ключей) и отпустить старую. Для долгоживущих кешей это стандартная причина «утечки», которую ищут в pprof heap-профиле по runtime.makeBucketArray / internal/runtime/maps.newTable.

Что произойдет, если попытаться получить значение по ключу, которого нет в map ?

Коротко. Вернётся нулевое значение типа значения, без паники. Отличить «нет ключа» от «есть ключ с нулевым значением» позволяет форма с двумя результатами: v, ok := m[k].

Глубже. Работает и для nil-мапы. Именно поэтому map[string]bool как множество удобен: if m[k] { ... } корректен и на отсутствующем ключе, и на nil-мапе.

Что произойдет, если записать значение в nil map ?

Коротко. Паника assignment to entry in nil map. Это обычная паника времени выполнения, её можно перехватить через recover, но правильнее не допускать: инициализировать мапу через make или литерал.

Глубже. Частая ловушка — мапа как поле структуры: нулевое значение структуры даёт nil-мапу, и первая же запись роняет код. Лечится конструктором или ленивой инициализацией if s.m == nil { s.m = make(map[K]V) }. Обратите внимание на асимметрию: чтение, len, range и delete на nil-мапе безопасны, паникует только запись.

Что такое хеш-таблицы, для чего применяются, какое основное назначение и ограничения?

Коротко. Хеш-таблица — структура для ассоциативного массива: по ключу за амортизированное O(1) находится значение. Применяется для индексов, кешей, множеств, подсчёта частот, дедупликации. Ограничения: нет порядка, худший случай O(n), требуется хорошая хеш-функция и сравнимый ключ, память тратится с запасом (load factor < 1), плохая локальность при больших ключах.

Глубже. Когда хеш-таблица не подходит: нужны запросы по диапазону и упорядоченный обход (нужно дерево/скип-лист), нужны гарантии по худшему времени (реалтайм), нужна персистентность/иммутабельность, ключи не сравнимы или дороги в хешировании. Отдельный класс проблем — hash-flooding: злоумышленник подбирает ключи с одинаковым хешем и вырождает таблицу в список; в Go это лечится случайным seed на мапу.

Есть ли в Go структура set - множество уникальный элементов. как можно сделать? Если через мапу, то что было бы в ней ключом, а что значением?

Коротко. Отдельного типа set в стандартной библиотеке нет. Делают на мапе: элемент множества — ключ, значением берут struct{} (не занимает памяти) или bool (удобнее читается: if s[x]).

Глубже. map[T]struct{} экономит по значению 1 байт на элемент и делает намерение явным, но требует _, ok := s[x] для проверки. map[T]bool чуть проще в использовании и позволяет «отрицательные» записи. Начиная с Go 1.21 полезны maps.Keys/slices для конверсий, с Go 1.23 — итераторы (iter.Seq). Обратите внимание: множество на мапе не упорядочено, обход рандомизирован — для стабильного вывода собирайте ключи в слайс и сортируйте.

type Set[T comparable] map[T]struct{}

func (s Set[T]) Add(v T)           { s[v] = struct{}{} }
func (s Set[T]) Has(v T) bool      { _, ok := s[v]; return ok }
func (s Set[T]) Delete(v T)        { delete(s, v) }

Устройство мапы. Что такое «эвакуация данных»?

Коротко. Устройство — см. выше: бакеты по 8 слотов (до Go 1.24) или группы по 8 слотов с control word (с 1.24). Эвакуация — термин старой реализации: перенос пар ключ/значение из старого массива бакетов в новый, вдвое больший, выполняемый порциями по 1–2 бакета на каждую операцию записи/удаления.

Глубже. При росте hmap.buckets начинает указывать на новый массив, а oldbuckets — на старый; поле nevacuate отмечает границу уже перенесённых бакетов. Пока эвакуация не завершена, чтение обязано смотреть и в старый массив: evacuated(b) проверяет специальные значения tophash (evacuatedX, evacuatedY, evacuatedEmpty). При удвоении каждый старый бакет расщепляется на два — «X» (тот же индекс) и «Y» (индекс + старый размер) — в зависимости от нового старшего бита хеша. Когда все бакеты перенесены, oldbuckets обнуляется, и старый массив собирает GC. В swiss-мапах Go 1.24 этого механизма нет: инкрементальность обеспечивается тем, что перестраивается только одна таблица (≤1024 элемента), а не вся мапа.

Что такое мапа, синк мапа чем от мапы отличается?

Коротко. map — встроенная хеш-таблица, не потокобезопасная. sync.Map — потокобезопасная мапа из стандартной библиотеки с API методов (Load, Store, LoadOrStore, Delete, Range, Swap, CompareAndSwap), нетипизированная (any/any), без len, оптимизированная под специфические сценарии, а не под общий случай.

Глубже. Классическая реализация sync.Map (актуальна в Go 1.24 по умолчанию) держит две мапы: read — иммутабельный снимок под atomic.Pointer, читаемый вообще без блокировок, и dirty — под мьютексом, куда попадают новые ключи. Когда промахов по read накапливается достаточно, dirty целиком продвигается в read. Отсюда сильные и слабые стороны: чтения существующих ключей почти бесплатны, а поток новых ключей или частые перезаписи разных ключей упираются в мьютекс и копирования. В internal/sync лежит новая реализация на hash-trie (HashTrieMap), которая в Go 1.24 включается через GOEXPERIMENT=synchashtriemap и решает как раз проблему записей. В большинстве прикладных случаев обычная map под sync.RWMutex или шардированная мапа быстрее и типобезопаснее, чем sync.Map.

Как работает механизм коллизий?

Коротко. См. выше про коллизии. Механически: хеш → номер корзины; в корзине 8 слотов, отбраковка по 1 байту хеша, затем полное сравнение ключей; если корзина занята — переход к overflow-бакету (до 1.23) или к следующей группе по квадратичному пробированию (с 1.24).

Глубже. Отличие двух схем важно в худшем случае. Chaining через overflow-бакеты деградирует линейно по длине цепочки и порождает много мелких аллокаций; поэтому в старой реализации был отдельный триггер tooManyOverflowBuckets, запускавший «рост того же размера» — перестроение массива без изменения B, чтобы схлопнуть цепочки, разросшиеся из-за паттерна «много вставок и удалений». Открытая адресация в swiss-таблицах не имеет overflow-аллокаций, но требует, чтобы таблица никогда не была заполнена на 100% (иначе пробирование не остановится) — отсюда лимит загрузки 7/8.

Будет ли тут эвакуации значений из бакетов?

Коротко. Вопрос вырван из контекста конкретного кода на доске. Универсальный ответ: эвакуация (в старой реализации) запускается при росте мапы, то есть когда число элементов превысило 6.5 × число бакетов или накопилось слишком много overflow-бакетов; сама переноска идёт лениво — по 1–2 бакета на каждую вставку/удаление, при чтениях ничего не эвакуируется.

Глубже. Отсюда прикладные выводы, которые обычно и хотят услышать: если мапа создана через make(map[K]V, n) с достаточным hint, роста и эвакуации при вставке n элементов не будет; если мапа только читается — эвакуации нет по определению; в Go 1.24 термин неприменим, там вместо эвакуации расщепление таблицы. Если вопрос был про конкретный фрагмент, нужно посчитать: сколько элементов кладём и с каким hint создана мапа.

Зачем нужна эвакуация?

Коротко. Чтобы рост мапы не превращался в одну длинную паузу: вместо того чтобы за раз перехешировать все элементы в новый массив, перенос размазывается по последующим операциям записи и удаления.

Глубже. Побочная задача — корректность во время роста: пока старый массив жив, любой поиск обязан проверять и его, поэтому существует состояние «мапа растёт», влияющее на код чтения. Второй сценарий эвакуации — sameSizeGrow: массив пересоздаётся того же размера, чтобы компактно уложить элементы, размазанные по overflow-бакетам после массовых удалений. Именно из-за этого нельзя брать указатель на элемент мапы: адрес слота меняется при эвакуации.

Что такое коллизии в хеш-таблицах?

Коротко. Коллизия — ситуация, когда два разных ключа отображаются в одну позицию таблицы: либо потому что совпали их хеши, либо (гораздо чаще) потому что совпал остаток хеша по размеру таблицы. Коллизии неизбежны: ключей больше, чем ячеек (принцип Дирихле).

Глубже. Даже при идеальной хеш-функции коллизии появляются раньше, чем кажется: парадокс дней рождения даёт ~50% вероятность коллизии уже при √N вставках. Поэтому качество хеш-таблицы измеряется не отсутствием коллизий, а тем, как она их разруливает и как держит load factor.

Что такое мапа в голанге?

Коротко. См. выше: map[K]V — встроенный тип-хеш-таблица, ссылочный по поведению (переменная хранит указатель на заголовок в куче), с амортизированным O(1) доступом, рандомизированным порядком обхода и без встроенной потокобезопасности.

Что такое эвакуация в мапе?

Коротко. См. выше «Устройство мапы. Что такое «эвакуация данных»?» — это пошаговый перенос элементов из старого массива бакетов в новый при росте, по 1–2 бакета за операцию записи или удаления.

Tell about the map

Коротко. map[K]V is Go’s built-in hash table: amortized O(1) lookup/insert/delete, reference-like semantics (the variable holds a pointer to a runtime header), randomized iteration order, zero value is nil (reads are fine, writes panic), and it is not safe for concurrent use with at least one writer.

Глубже. Implementation: before Go 1.24 — runtime.hmap with 2^B buckets of 8 slots each, an 8-byte tophash array per bucket, overflow bucket chains, growth at load factor 6.5 with incremental evacuation. Since Go 1.24 — Swiss Tables (internal/runtime/maps): groups of 8 slots with an 8-byte control word holding 7 bits of the hash per slot, quadratic probing, and a directory of tables (extendible hashing) so that only one table (≤1024 entries) is rehashed at a time. Practical notes worth mentioning in an interview: elements are not addressable, deletion never shrinks the map, keys must be comparable, and sync.Map or a mutex-guarded map is needed for concurrency.

Can you read from a map in multiple threads?

Коротко. Yes — concurrent reads are safe as long as no goroutine writes to the map at the same time. As soon as one writer exists, all accesses must be synchronized (sync.RWMutex, sync.Map, or sharding).

Глубже. The runtime performs best-effort detection: a concurrent write flag inside the map header causes fatal error: concurrent map writes or fatal error: concurrent map read and map write. This is a throw, not a panic — recover will not save the process. Detection is not guaranteed, so absence of a crash is not proof of correctness; use go test -race / go run -race. A read-only map that was fully populated before starting goroutines (and never written afterwards) needs no synchronization at all, provided the goroutines start after the writes (the happens-before edge comes from go statement).

Что из себя представляют мапы?

Коротко. См. выше: неупорядоченные коллекции пар ключ-значение, реализованные хеш-таблицей в рантайме; переменная — указатель на заголовок, нулевое значение — nil.

Что такое мапа?

Коротко. См. выше. Одной фразой: встроенная в язык хеш-таблица map[K]V с амортизированным O(1) доступом по сравнимому ключу.

Какой порядок обхода мапы?

Коротко. Порядок не определён и намеренно рандомизирован: каждый range начинается со случайного бакета/группы и со случайного смещения внутри неё. Полагаться на порядок нельзя; для стабильного вывода собирайте ключи в слайс и сортируйте.

Глубже. Рандомизация введена, чтобы код не «залипал» на случайно стабильном порядке конкретной реализации. Гарантий нет ни между запусками, ни между двумя range по одной и той же мапе. Правила модификации во время обхода: удалённые до момента посещения ключи гарантированно не будут выданы; ключи, добавленные во время обхода, могут быть выданы, а могут и не быть. Единственное исключение по «упорядоченности» — fmt печатает мапы отсортированными по ключу с Go 1.12, но это про форматирование, а не про range.

keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
slices.Sort(keys) // пакет "slices", Go 1.21+

Какие ключи можно использовать для мапы?

Коротко. Любой сравнимый (comparable) тип: булев, числовые, строки, указатели, каналы, интерфейсы, а также структуры и массивы, все поля/элементы которых сравнимы. Нельзя срезы, мапы и функции — это ошибка компиляции.

Глубже. Два подводных камня. Первый — интерфейс как ключ: компилируется всегда, но если в интерфейсе окажется несравнимое динамическое значение (например, срез), сравнение вызовет панику runtime error: comparing uncomparable type []int в момент операции с мапой. Второй — числа с плавающей точкой: math.NaN() != math.NaN(), поэтому каждый записанный NaN-ключ создаёт новую недостижимую запись, которую нельзя ни найти, ни удалить по ключу (только clear(m) или пересоздание). Ещё нюанс: +0.0 и -0.0 равны, поэтому это один и тот же ключ.

Как устроена мапа?

Коротко. См. подробный разбор выше: заголовок в куче + массив бакетов по 8 слотов с tophash и overflow-цепочками (до Go 1.23) либо directory таблиц, состоящих из групп по 8 слотов с control word (Go 1.24+).

Мапа, расскажи что знаешь;

Коротко. Каркас ответа на такой открытый вопрос: (1) что это — встроенная хеш-таблица map[K]V, ссылочная семантика, нулевое значение nil; (2) как устроена — бакеты/группы по 8 слотов, хеш с seed, фильтр по байту хеша, полное сравнение ключа; (3) сложность и рост — амортизированное O(1), удвоение при загрузке 6.5/8 (старая) или 7/8 (swiss), эвакуация/расщепление таблиц; (4) семантика — рандомизированный обход, неадресуемость элементов, comparable-ключи, nil-мапа; (5) конкурентность — не потокобезопасна, fatal error, варианты RWMutex/sync.Map/шардирование; (6) память — delete не уменьшает мапу, make с hint экономит рост.

Глубже. Хороший тон — сразу разграничить версии: «до 1.24 так, с 1.24 Swiss Tables». Это показывает, что вы читаете release notes, а не только старые статьи. Заканчивать стоит практикой: где вы упирались в мапы (память после массовых удалений, конкурентный доступ, аллокации на строковых ключах).

Почему мапа не потокобезопасна?

Коротко. Потому что синхронизация стоила бы производительности всем, включая однопоточный код. Go делает выбор в пользу «не платишь за то, чем не пользуешься»: безопасность обеспечивает пользователь через мьютекс, sync.Map или ограничение доступа одной горутиной.

Глубже. Технически небезопасность вытекает из устройства: запись может запустить рост и перенос данных, менять control word/tophash, переставлять слоты и переиспользовать память — параллельное чтение в этот момент увидит рваное состояние вплоть до чтения по мусорному указателю. Поэтому рантайм не пытается «сделать как-нибудь», а падает: в заголовке мапы есть флаг записи, и при обнаружении пересечения вызывается fatal error: concurrent map writes / concurrent map read and map write. Это неперехватываемый throw — сознательное решение, чтобы повреждение памяти не расползалось.

Сколько максимум бакетов может быть и как идет рост?

Коротко. В старой реализации число бакетов всегда степень двойки — 2^B, где B — uint8, то есть формальный потолок 2^255 недостижим, реально ограничение — доступная память и переполнение uintptr при вычислении размера массива. Рост: удвоение B, когда count > 6.5 * 2^B, плюс «рост того же размера» при слишком большом числе overflow-бакетов.

Глубже. В swiss-мапах Go 1.24 понятия «общее число бакетов» нет: есть directory размером 1 << globalDepth указателей на таблицы, каждая таблица содержит до 1024 элементов и растёт удвоением своей ёмкости, а по достижении лимита расщепляется на две с увеличением локальной глубины (и, при необходимости, глобальной — то есть удвоением directory). Практическая граница — та же память процесса. Полезная деталь для ответа: аллокация массива бакетов происходит лениво — пустая мапа make(map[K]V) без hint не выделяет бакеты, пока не появится первый элемент.

Что представляет nil мапа?

Коротко. nil-мапа — переменная типа map с нулевым значением, то есть без выделенного заголовка. Чтение возвращает нулевое значение, len даёт 0, range не выполняет ни одной итерации, delete — безопасный no-op, а любая запись паникует assignment to entry in nil map.

Глубже. nil-мапа полезна как «пустая мапа только для чтения»: её можно вернуть из функции вместо пустой мапы и не тратить аллокацию. Сравнивать мапы можно только с nil (m == nil), между собой — нельзя. Отличить nil от пустой инициализированной мапы можно только этим сравнением: len у обеих 0.

Когда лучше использовать синк мапу?

Коротко. Когда набор ключей стабилизируется и дальше идут в основном чтения (кеш, реестр, конфиг), либо когда разные горутины работают с непересекающимися наборами ключей. Во всех остальных случаях — обычная мапа под sync.RWMutex или шардированная мапа.

Глубже. Это буквально то, что написано в документации sync.Map, и это следствие устройства: чтение из read-снимка идёт по атомику без блокировок, а любые новые ключи проходят через мьютекс и, при промахах, влекут копирование всей dirty. Поэтому write-heavy нагрузка на sync.Map заметно проигрывает RWMutex. Минусы: нет типизации (any → аллокации на boxing и приведения типов), нет len, Range не даёт консистентного снимка. Практическое правило: начинайте с map + RWMutex, измеряйте, и переходите на sync.Map или шардирование (N мап по hash(key)%N, каждая со своим мьютексом) только по данным профилировщика.

Как работает эвакуация в мапе?

Коротко. См. выше. Кратко механика: при росте buckets указывает на новый массив, oldbuckets — на старый, nevacuate хранит границу переноса; каждая запись/удаление эвакуирует бакет, который трогает, плюс один следующий по порядку; при удвоении элементы старого бакета расщепляются на две половины X и Y по новому старшему биту хеша; чтения умеют искать в старом массиве, пока он жив.

Что такое мапа? Чем отличаются новая мапа?

Коротко. См. выше про мапу и про Swiss Tables. Отличия новой (Go 1.24): открытая адресация вместо overflow-цепочек, группы по 8 слотов с 8-байтовым control word и параллельным сравнением 8 хеш-фрагментов, квадратичное пробирование, directory таблиц вместо единого массива бакетов, лимит загрузки 7/8, отсутствие механизма oldbuckets/эвакуации.

Как мапа реализована в Go?

Коротко. См. выше: рантайм-структура в куче (runtime.hmap до 1.24 / internal/runtime/maps.Map с 1.24), компилятор превращает m[k], m[k]=v, delete, range в вызовы рантайма (mapaccess1/2, mapassign, mapdelete, mapiterinit/next) со специализированными версиями для 32-битных, 64-битных и строковых ключей.

Глубже. Специализации (mapaccess1_fast64, mapaccess2_faststr и т.п.) убирают косвенные вызовы хеш-функции и сравнения для самых частых типов ключей — это заметно на горячем пути. Компилятор также оптимизирует шаблоны вроде for k := range m { delete(m, k) } (превращается в mapclear) и _, ok := m[k]. Мапа всегда живёт в куче: m в стеке — только указатель.

Два элемента лежат в бакете. Как по ключу получить нужное значение из бакета?

Коротко. Сначала по короткому фрагменту хеша (старший байт tophash в старой реализации, младшие 7 бит H2 в новой) отбраковываются слоты, которые точно не подходят. Для оставшихся кандидатов ключ сравнивается полностью (==), и по индексу совпавшего слота берётся значение из параллельного массива значений.

Глубже. В старом bmap значение i-го слота лежит по смещению dataOffset + 8*keySize + i*elemSize — ключи и значения хранятся раздельными блоками. В swiss-группе matchH2 возвращает битовую маску совпавших слотов, и цикл проходит только по установленным битам. Ложное совпадение 7-битного фрагмента — примерно 1/128, поэтому полное сравнение ключа обязательно всегда.

Как называется ситуация, когда несколько элементов попали в один бакет?

Коротко. Коллизия (hash collision). Если совпал только номер бакета — это коллизия по индексу; если совпал и полный хеш — полная коллизия хеша.

Что происходит, когда два разных ключа имеют одинаковый хэш и попадают в один бакет?

Коротко. Оба спокойно хранятся: занимают разные слоты одного бакета/группы. Так как фильтр по байту хеша их не различит, при поиске сравниваются сами ключи, и возвращается значение того, чей ключ равен искомому.

Глубже. Если свободных слотов не осталось: старая реализация выделяет overflow-бакет и продолжает цепочку; swiss-таблица переходит к следующей группе по квадратичному пробированию. Массовые полные коллизии — это атака hash-flooding, и защита от неё — случайный seed на каждую мапу: злоумышленник не знает соли, поэтому не может подготовить набор ключей с одинаковым хешем заранее.

Мапа потокобезопасна?

Коротко. Нет. Параллельные только чтения — безопасны; как только появляется хотя бы один писатель, нужна синхронизация. Рантайм не гарантирует, но часто ловит нарушение и роняет процесс с fatal error: concurrent map writes.

Можно ли взять указатель на элемент мапы?

Коротко. Нет: элемент мапы не адресуем. &m[k] — ошибка компиляции cannot take address of m["a"] (map index expression ...), как и присваивание в поле структуры-значения: cannot assign to struct field m["a"].N in map.

Глубже. Причина в том, что элемент может физически переехать: при росте мапы происходит эвакуация/перестроение таблицы, и адрес слота меняется — указатель стал бы висячим или указывал бы на устаревшую копию. Обходные пути: хранить map[K]*V (тогда указатель берётся у значения в куче, и мутировать можно через него) или читать-менять-записывать целиком:

type S struct{ N int }

m := map[string]S{"a": {}}
s := m["a"]
s.N++
m["a"] = s // read-modify-write

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

Служит для принудительной установки значений в нули.

Коротко. Обрывок исходника, вопрос не восстанавливается — это вариант ответа из теста, а не вопрос.

Глубже. По смыслу формулировка похожа на описание встроенной функции clear (Go 1.21+). Для мапы clear(m) удаляет все элементы (а не «обнуляет значения»), длина становится 0, ёмкость сохраняется; для слайса clear(s) действительно записывает нулевые значения во все элементы, не меняя длину. Разница между этими двумя случаями — типичный подвох.

Мапы.

Коротко. Открытая тема без конкретного вопроса — отвечать по каркасу из «Мапа, расскажи что знаешь»: определение → внутреннее устройство (бакеты/группы, хеш, коллизии) → рост и эвакуация → семантика (nil, обход, неадресуемость, comparable-ключи) → конкурентность → память и практика.

Все ключи будут сброшены в исходное состояние;

Коротко. Обрывок исходника, вопрос не восстанавливается — это вариант ответа из теста с множественным выбором.

Глубже. Если это был вариант к вопросу «что делает запись в мапу / что делает clear» — правильные факты такие: запись по новому ключу добавляет запись, запись по существующему перезаписывает значение, clear(m) удаляет все пары, а «сброс ключей в исходное состояние» в Go не существует как операция.

Будет создан новый ключ с указанным значением.

Коротко. Обрывок исходника, вопрос не восстанавливается — это вариант ответа из теста.

Глубже. Как утверждение оно верно для присваивания m[k] = v в инициализированную мапу, когда ключа k в ней ещё нет: создаётся новая запись. Если мапа nil — вместо создания записи будет паника.

Как защитить срез или карту от изменений?

Коротко. В Go нет иммутабельных коллекций и нет const для них. Защита строится соглашениями: не отдавать наружу внутренние map/[]T, а возвращать копию, отдавать доступ через методы (геттер по ключу, итератор), либо прятать структуру за интерфейсом только с read-методами.

Глубже. Практические приёмы: maps.Clone/slices.Clone (Go 1.21+) для защитной копии; итератор iter.Seq2[K, V] (Go 1.23+) вместо возврата самой мапы — потребитель может только читать; неэкспортируемое поле + методы в отдельном пакете, чтобы компилятор не давал дотянуться; для конкурентного доступа — RWMutex вокруг доступа (это защита от гонок, а не от логических изменений). Помните, что копия мапы поверхностная: если значения — указатели или срезы, через них по-прежнему можно всё поменять.

func (c *Cache) Snapshot() map[string]int {
    c.mu.RLock()
    defer c.mu.RUnlock()
    return maps.Clone(c.m) // пакет "maps", Go 1.21+
}

Что такое map в Go?

Коротко. См. выше: встроенный тип-хеш-таблица map[K]V, ключ должен быть сравнимым, доступ амортизированно O(1), порядок обхода случайный, нулевое значение nil, потокобезопасности нет.

Если страницы мапятся на физическую память, то каждое обращение к памяти это поиск в некоторой мапе. Как это может работать быстро?

Коротко. Потому что трансляцию делает не программная мапа, а железо: многоуровневые таблицы страниц обходит MMU, а результаты кешируются в TLB — маленьком ассоциативном кеше внутри CPU. Подавляющее большинство обращений попадает в TLB и не требует никакого «поиска» вообще.

Глубже. Ключевые детали, которые обычно хотят услышать: (1) таблица страниц не хеш-таблица, а радиксное дерево с индексацией по фрагментам виртуального адреса — на x86-64 это 4 уровня (или 5 при 5-level paging), то есть максимум 4–5 обращений в память при промахе TLB; (2) сами эти обращения тоже кешируются в L1/L2/L3 и в специальных paging-structure caches; (3) TLB небольшой (сотни-тысячи записей), но благодаря локальности hit rate обычно 99%+; (4) huge pages (2 МБ/1 ГБ) увеличивают покрытие TLB в сотни раз и сокращают глубину обхода; (5) обход страниц идёт параллельно с исполнением, а не блокирует конвейер целиком. Промах TLB стоит десятки-сотни наносекунд — заметно, поэтому TLB-миссы и есть одна из причин, по которой структуры данных с плохой локальностью медленные.

Как обрабатываются коллизии в хэш-таблице?

Коротко. Двумя семействами методов: chaining (в ячейке — список/корзина элементов) и открытая адресация (при занятости ячейки ищем следующую по правилу пробирования). Go до 1.23 использовал гибрид «корзина на 8 слотов + overflow-цепочка», с 1.24 — открытую адресацию с квадратичным пробированием по группам.

Еще доп вопрос: какой тип данных под капотом у мапы по аналогии со слайсами на массив? (Ответ - hmap - https://go.dev/src/runtime/map.go )

Коротко. Да, до Go 1.24 это runtime.hmap (заголовок) плюс массив бакетов bmap; переменная map[K]V — указатель на hmap. С Go 1.24 роль заголовка играет internal/runtime/maps.Map, а файл runtime/map.go разделён на map_swiss.go и map_noswiss.go.

Глубже. Аналогия со слайсом не полная: слайс — это структура-значение из трёх слов (ptr, len, cap), которая копируется при передаче, поэтому append внутри функции не виден снаружи. Мапа — это одно слово-указатель на заголовок в куче, поэтому любые изменения (включая рост) видны всем держателям переменной. Именно поэтому мапу не нужно передавать как *map[K]V, а слайс иногда приходится — или возвращать.

Подробное устройство мапы и как обрабатываются коллизии?

Коротко. См. развёрнутые ответы выше: заголовок в куче + массив бакетов по 8 слотов с tophash и overflow (до 1.23) либо directory таблиц с группами по 8 слотов и control word (с 1.24); коллизии — соседние слоты корзины, дальше overflow-цепочка или квадратичное пробирование, финальная проверка всегда полным сравнением ключей.

Что из себя представляет тип map?

Коротко. См. выше. Формально по спецификации: map[K]V — неупорядоченная группа элементов типа V, индексированных уникальными ключами типа K, где K обязан быть сравнимым; нулевое значение — nil; количество элементов даёт len.

Какой порядок обхода элементов в мапе?

Коротко. См. выше — не определён и рандомизирован при каждом range. Для детерминированного вывода сортируйте ключи; fmt при печати мапы сортирует сам (с Go 1.12), но на range это не распространяется.

Какие есть особенности в работе с неинициализированной мапы?

Коротко. См. выше про nil-мапу: чтение, len, range, delete безопасны; запись паникует. Отличить nil от пустой мапы можно только сравнением m == nil.

Глубже. Отдельная тонкость — мапа как поле структуры или элемент другой мапы: m["a"]["b"] = 1 для map[string]map[string]int паникует, если внутренняя мапа не создана. Стандартный паттерн — проверить и создать:

outer := map[string]map[string]int{}
if _, ok := outer["a"]; !ok {
    outer["a"] = make(map[string]int)
}
outer["a"]["b"] = 1

Как взять указатель на значение мапы?

Коротко. Напрямую — никак: элемент мапы неадресуем. Варианты: скопировать значение в переменную и взять указатель на неё (v := m[k]; p := &v — но это копия, изменения не попадут в мапу) или хранить в мапе указатели map[K]*V и работать через них.

Глубже. См. выше «Можно ли взять указатель на элемент мапы?» — там причина (переезд слотов при росте) и примеры. Ещё вариант — держать значения в слайсе, а в мапе индексы: map[K]int → []V; тогда &vals[i] адресуем, но остаётся ограничение слайсов — append может переаллоцировать бэкинг-массив и обесценить указатели.

Что такое эвакуация бакетов?

Коротко. См. выше — перенос содержимого бакетов из старого массива в новый при росте мапы, выполняемый порциями (1–2 бакета за операцию записи/удаления), с расщеплением каждого старого бакета на два по новому старшему биту хеша.

Что такое мапа? Как хранятся внутри ключи и значения? Бакеты, хэш-функция, эвакуация.

Коротко. Мапа — хеш-таблица. Ключи и значения хранятся не парами, а раздельными блоками внутри бакета: сначала 8 байт tophash, потом 8 ключей подряд, потом 8 значений подряд, потом указатель на overflow-бакет. Хеш-функция берётся из типа ключа и солится случайным seed мапы. Эвакуация — пошаговый перенос при росте.

Глубже. Раздельное хранение ключей и значений экономит на выравнивании: в map[int64]int8 при чередовании каждый элемент занимал бы 16 байт вместо 9. Ключи и значения крупнее 128 байт хранятся косвенно — в слоте лежит указатель на объект в куче, что делает копирование при эвакуации дешевле. В swiss-мапах Go 1.24 слот группы хранит пару key/elem вместе, а роль tophash играет байт control word с 7 битами хеша; сама группа при этом остаётся кэш-дружественной, потому что control word одной группы — это ровно 8 байт.

Тип map потокобезопасен? А почему?

Коротко. Нет. Причина — цена: встроенная блокировка замедлила бы все мапы, включая однопоточные, а Go придерживается принципа «не платишь за то, чем не пользуешься». Плюс запись может перестраивать таблицу, поэтому параллельное чтение видело бы несогласованное состояние.

Глубже. См. выше «Почему мапа не потокобезопасна?». Дополнение про модель памяти: даже атомарность отдельных операций не спасла бы — типичная последовательность «прочитал, посчитал, записал» всё равно требует внешней синхронизации, так что встроенный мьютекс дал бы ложное чувство безопасности при той же необходимости писать код синхронизации.

Что можно использовать в качестве ключа мапы?

Коротко. См. выше — любой comparable-тип: числа, строки, bool, указатели, каналы, интерфейсы, структуры и массивы из сравнимых полей. Срезы, мапы и функции запрещены компилятором.

Что можешь сказать про hashmap?

Коротко. Hash map — общее название структуры «ассоциативный массив на хеш-таблице»; в Go это встроенный map. Основные характеристики: амортизированное O(1) на операции, худший случай O(n), нет упорядоченности, требуется хорошая хеш-функция и стратегия разрешения коллизий, память с запасом из-за load factor.

Глубже. Полезно уметь сравнить с альтернативами: сбалансированное дерево (O(log n), но упорядоченный обход и запросы по диапазону), trie (префиксные запросы), open-addressed vs chained (первое лучше по локальности и аллокациям, второе устойчивее к высокой загрузке). В Go нет стандартного упорядоченного словаря, поэтому его роль обычно играет map + отсортированный слайс ключей или сторонняя реализация дерева/skip-list.

Что такое мапа? Расскажи детальнее(устройство мапы - бакеты,хэш функция)

Коротко. См. выше. Сжатый скелет ответа: hash(key, seed) → младшие B бит выбирают бакет (или старшие биты выбирают таблицу, а H1 — группу в Go 1.24) → байт хеша (tophash / H2) фильтрует 8 слотов → полное сравнение ключа → значение из параллельного блока значений.

Глубже. Про хеш-функцию стоит добавить два факта. Первый: она специфична для типа ключа и берётся из дескриптора типа (maptype.Hasher), причём для строк и целых есть быстрые специализации, а на amd64 при наличии AES-NI используется aeshash. Второй: seed случаен для каждой мапы, поэтому один и тот же ключ в двух мапах даёт разные позиции, и порядок обхода отличается — это защита от hash-flooding и от кода, который случайно завязался на порядок.

Может ли структура быть ключом в мапе?

Коротко. Да, если все её поля сравнимы. struct{A int; B string} — валидный ключ; структура с полем-срезом, мапой или функцией — нет (ошибка компиляции).

Глубже. Нюансы: сравнение структур-ключей поэлементное, поэтому широкие структуры хешируются и сравниваются дороже, чем строка-суррогат; padding-байты в сравнении и хешировании не участвуют (компилятор генерирует корректный equal), так что «мусор в выравнивании» ключи не ломает. Если в структуре есть поле-интерфейс, компиляция пройдёт, но при несравнимом динамическом значении будет паника в рантайме. Массив ([N]T) как ключ тоже допустим — этим иногда пользуются для ключей вида [16]byte из хеша.

Какие существуют методы разрешения коллизий в хэш-таблицах?

Коротко. Две основные семьи: chaining (separate chaining — список, динамический массив или дерево в ячейке) и открытая адресация (linear probing, quadratic probing, double hashing, а также robin hood hashing, cuckoo hashing, hopscotch).

Глубже. Chaining прост, терпит load factor > 1, но платит аллокациями и указательной погоней; открытая адресация компактна и кэш-дружественна, но требует load factor < 1, tombstone-ов при удалении и полного перестроения при росте. Go совмещал плюсы обоих: корзина на 8 слотов (кэш-локальность) плюс overflow-цепочка (устойчивость); с 1.24 перешёл на чистую открытую адресацию с SWAR-фильтром по control word, компенсируя минусы удаления tombstone-ами и делением на таблицы. В качестве примеров из других языков полезно упомянуть Java HashMap (chaining со списком, превращающимся в красно-чёрное дерево после 8 коллизий) и Python dict (открытая адресация + отдельный массив порядка вставки).

Что такое тип map и для чего используются?

Коротко. См. выше: встроенная хеш-таблица. Используется там, где нужен доступ по ключу: индексы и справочники, кеши, множества, подсчёт частот, группировка, дедупликация, хранение конфигурации и метаданных.

Глубже. Когда мапа — не лучший выбор: маленькие наборы (до нескольких десятков элементов) часто быстрее линейным поиском по слайсу за счёт локальности и отсутствия хеширования; при необходимости упорядоченного обхода нужен слайс + сортировка; при высокой конкурентной нагрузке — шардирование или sync.Map; при жёстких требованиях к памяти — специализированные структуры (например, слайс + индексы) вместо мапы с крупными значениями.

Что можешь рассказать про тип map ?

Коротко. См. выше — тот же открытый вопрос: определение, устройство (бакеты/группы, хеш, коллизии), рост и эвакуация, семантика (nil, обход, неадресуемость, comparable-ключи), конкурентность, память.

Как растет map ?

Коротко. До Go 1.24: когда число элементов превышает 6.5 × число бакетов, B увеличивается на 1 (бакетов вдвое больше), и запускается инкрементальная эвакуация; отдельно есть «рост того же размера» при избытке overflow-бакетов. С Go 1.24: растёт отдельная таблица — удвоением ёмкости до 1024 элементов, дальше расщеплением на две таблицы с расширением directory; предел загрузки 7/8.

Глубже. Практический вывод один и тот же для обеих реализаций: рост — это перехеширование и копирование, поэтому задавайте make(map[K]V, n), если размер известен заранее. Это единственная реально работающая «оптимизация мапы» в большинстве кода. Обратной операции нет: мапа никогда не уменьшается.

Можно ли взять указатель на элемент map (порядок)?

Коротко. Нет — элемент мапы неадресуем (см. выше). Что до порядка: он рандомизирован и не гарантирован. Оба ограничения имеют общую причину — рантайм волен переставлять и перемещать элементы.

Глубже. Формулировка в скобках, видимо, объединяет два классических вопроса. Полезно проговорить связь: элементы физически переезжают при росте/эвакуации, поэтому (а) стабильного адреса у элемента нет, (б) стабильного порядка обхода тоже нет, и вдобавок Go специально рандомизирует стартовую позицию, чтобы никто не полагался на «случайно стабильный» порядок.

Как растет размер map ?

Коротко. См. выше «Как растет map?» — удвоение бакетов при среднем заполнении > 6.5 на бакет (до 1.24) либо удвоение/расщепление таблицы при загрузке > 7/8 (с 1.24). len(m) — это просто счётчик живых элементов в заголовке, он растёт на 1 при вставке нового ключа.

Мы удалили ключи из map , как сделать чтобы она освободила память? (скопировать в новую и удалить старую)

Коротко. Да, именно так: создать новую мапу нужного размера, перенести живые элементы, присвоить её переменной и отпустить старую — тогда старый массив бакетов соберёт GC. Ни delete, ни clear память не возвращают.

Глубже. Приём применяют по порогу: например, если len(m) стал меньше четверти пика, пересоздать. Альтернативы: держать данные в шардированной мапе и пересоздавать шарды по одному (меньше пиковая память и паузы), или использовать map[K]V с маленькими значениями плюс внешний слайс. Помните, что во время перекладывания на короткое время в памяти живут обе мапы.

func compact[K comparable, V any](m map[K]V) map[K]V {
    n := make(map[K]V, len(m))
    for k, v := range m {
        n[k] = v
    }
    return n // старая мапа станет мусором после переприсваивания
}

Безопасно ли удалять элемент из nil map ?

Коротко. Да. delete(nil-map, k) — no-op, паники не будет. Это специально оговорено в спецификации.

Глубже. Симметрия такая: на nil-мапе безопасны чтение, len, range, delete и clear; паникует только присваивание. Также безопасно удаление отсутствующего ключа из обычной мапы и удаление ключа во время range по этой же мапе — удалённый до посещения ключ гарантированно не будет выдан итератором.

Как понять есть ли ключ в map ?

Коротко. Через comma-ok: v, ok := m[k] — ok равно true, если ключ присутствует. Просто m[k] не отличит отсутствие ключа от нулевого значения.

Глубже. Если значение не нужно, пишут _, ok := m[k] — компилятор вызовет облегчённый mapaccess2 без копирования значения. Для map[K]bool-множества достаточно if m[k]. Идиома «проверить и вставить» делается одним доступом там, где это возможно: if _, ok := m[k]; !ok { m[k] = v } — два обращения, но конкурентно-безопасной атомарной формы у встроенной мапы нет; у sync.Map для этого есть LoadOrStore.

Что такое мапа? Что такое бакеты? Что лежит в бакетах?

Коротко. Мапа — хеш-таблица; бакет — корзина фиксированного размера на 8 пар ключ/значение; в бакете лежат: массив из 8 байт tophash (по старшему байту хеша каждого занятого слота), затем 8 ключей подряд, затем 8 значений подряд, затем указатель на overflow-бакет.

Глубже. В Go 1.24 аналогичная единица — группа: 8-байтовое control word (по байту на слот: бит «занят/пусто/удалён» + 7 бит хеша) и 8 слотов, каждый из которых хранит пару key/elem. Крупные ключи и значения (>128 байт) хранятся косвенно — в слоте указатель. Пустые слоты помечены специальным значением в tophash/control word, поэтому «дырки» после удалений не мешают поиску.

Что можно использовать в качестве ключа в мапе?

Коротко. См. выше — любой сравнимый тип: числа, строки, bool, указатели, каналы, интерфейсы, структуры и массивы из сравнимых элементов. Нельзя срезы, мапы, функции. Отдельно помните про NaN-ключи (становятся недостижимыми) и про интерфейсы с несравнимым содержимым (паника в рантайме).

Как происходит эвакуация данных?

Коротко. Это механизм роста мапы в реализации до Go 1.24. Когда мапа решает вырасти, она не переносит всё сразу: старый массив бакетов сохраняется как oldbuckets, выделяется новый вдвое больший, и при каждой записи или удалении рантайм дополнительно эвакуирует один-два старых бакета в новый. Стоимость роста размазывается по операциям, длинных пауз нет.

Глубже. Триггеров роста два. Первый — превышение load factor: count > 6.5 * 2^B, тогда B увеличивается на единицу (рост «в два раза»). Второй — слишком много overflow-бакетов при нормальной заполненности (следствие большого числа удалений и вставок): тогда делается sameSizeGrow — новый массив того же размера, данные переупаковываются плотнее, мусорные overflow-цепочки схлопываются.

Механика: hashGrow только выделяет новый массив и переставляет указатели (oldbuckets = buckets), сам перенос делает growWork — она вызывается из mapassign и mapdelete и эвакуирует бакет, соответствующий текущему ключу, плюс ещё один по счётчику nevacuate. Функция evacuate для каждого ключа старого бакета пересчитывает, куда он попадёт: при удвоении новый бит хеша делит содержимое старого бакета на два назначения — x (тот же индекс) и y (индекс + 2^oldB). После переноса в старом бакете tophash[0] помечается как evacuatedX/evacuatedY/evacuatedEmpty, чтобы читатели по oldbuckets знали, что данные уже переехали. Чтение (mapaccess) во время роста проверяет oldbuckets и, если нужный бакет ещё не эвакуирован, ищет там. Когда nevacuate доходит до конца, oldbuckets обнуляется и память отдаётся GC.

Два практических следствия, которые любят спрашивать: во время эвакуации итератор обязан «склеивать» вид из старого и нового массивов (поэтому mapiternext такой сложный), и именно переезд данных — фундаментальная причина, почему элемент мапы неадресуем: указатель на слот протух бы после роста.

Что если в значение мапы положим ссылку на объект?

Коротко. Всё работает и часто это правильный приём: map[K]*T позволяет менять объект «на месте» — m[k].Field = x компилируется, потому что разыменование указателя адресуемо, в отличие от самого элемента мапы. Платите за это лишней аллокацией на объект, разыменованием при доступе и нагрузкой на GC.

Глубже. Сравните два варианта:

type User struct{ Age int }

ms := map[string]User{"a": {}}
// ms["a"].Age = 30            // ошибка компиляции: cannot assign to struct field
u := ms["a"]; u.Age = 30; ms["a"] = u // приходится делать read-modify-write

mp := map[string]*User{"a": {}}
mp["a"].Age = 30 // ок: элемент мапы — указатель, меняем то, на что он указывает

Подводные камни. Первое: значение по отсутствующему ключу — nil-указатель, и mp["missing"].Age = 1 даст panic; проверяйте v, ok := mp[k]. Второе: мапа удерживает объекты от сборки — пока ключ не удалён, весь граф, достижимый через указатель, жив; классическая утечка «кеш, из которого никогда не удаляют». Третье: GC. Бакеты/группы мапы сканируются согласно типу; если и ключ, и значение не содержат указателей, сканировать почти нечего, а map[string]*User на миллионы элементов — это миллионы указателей, которые GC обходит каждый цикл. Для больших read-only структур часто выгоднее map[K]int с индексом в слайс. Четвёртое: копия мапы через maps.Clone — поверхностная, указатели в клоне ведут на те же объекты. И, наконец, то же самое верно для срезов, мап и каналов в значении: они сами по себе ссылочные, поэтому m[k] = append(m[k], x) обязателен (append может переаллоцировать), а вот m[k][0] = x для непустого слайса сработает без переприсваивания.

Расскажи про map

Коротко. map[K]V — встроенная хеш-таблица с амортизированным O(1) на вставку, поиск и удаление. Переменная типа map — указатель на заголовок в куче, поэтому мапа «передаётся по ссылке» в бытовом смысле. Нулевое значение — nil: читать, len, range, delete можно, писать — panic. Порядок обхода рандомизирован, элемент неадресуем, конкурентная запись не поддерживается.

Глубже. Рабочий минимум, который стоит проговорить: создание — make(map[K]V) или make(map[K]V, hint), где hint заранее выделяет место и экономит на росте; чтение с проверкой — v, ok := m[k]; удаление — delete(m, k); очистка — clear(m) (builtin с Go 1.21) вместо цикла с delete; размер — len(m). Мапы нельзя сравнивать оператором == (только с nil) — для сравнения есть maps.Equal. Мапа никогда не сжимается: после удаления миллиона ключей память под бакеты остаётся занятой, вернуть её можно только пересозданием мапы. С Go 1.21 в стандартной библиотеке есть пакет maps (Clone, Copy, DeleteFunc, Equal), с Go 1.23 — итераторы maps.All/Keys/Values/Collect/Insert. Для конкурентного доступа — sync.Map (для read-mostly и непересекающихся ключей) или обычная мапа под sync.RWMutex/шардированная мапа (обычно быстрее при write-heavy нагрузке).

Как устроен тип map?

Коротко. См. выше — это хеш-таблица. Отличие ответа «как устроен тип» в том, что говорить надо про рантайм-структуру: map[K]V компилируется в указатель на runtime.hmap (до 1.24) или internal/runtime/maps.Map (с 1.24), а операции — в вызовы runtime.mapaccess1/2, mapassign, mapdelete, mapiterinit/mapiternext, которым компилятор передаёт дескриптор типа maptype.

Глубже. Старая структура: hmap{count, flags, B, noverflow, hash0, buckets, oldbuckets, nevacuate, extra}; бакет bmap{tophash [8]uint8; keys [8]K; elems [8]V; overflow *bmap} — ключи и значения хранятся раздельными пачками, чтобы не терять место на выравнивании. Ключи и значения больше 128 байт хранятся косвенно, в слоте лежит указатель.

Новая структура (Go 1.24): Map{used, seed, dirPtr, dirLen, globalDepth, globalShift, ...}; dirPtr — directory, массив указателей на таблицы; table{groups, index, localDepth, capacity, used, growthLeft}; группа — ctrl uint64 (8 байт control word) плюс 8 слотов {key, elem}, лежащих парами. Для мапы до 8 элементов directory не нужна вообще: dirPtr указывает прямо на единственную группу — это «small map» оптимизация. Максимальная средняя загрузка — 7 слотов из 8, максимальная ёмкость одной таблицы — 1024 элемента.

Полезная деталь для собеседования: компилятор умеет оптимизировать частые случаи, подставляя специализированные функции вместо общих — mapaccess1_fast32/fast64/faststr, mapassign_fast64 и т. п., а конструкцию for k := range m { delete(m, k) } до появления clear распознавал как «очистить мапу» и превращал в быстрый сброс.

Какая функция используется для хеширования в map?

Коротко. Единой функции нет: хешер выбирается по типу ключа и хранится в дескрипторе типа (maptype.Hasher). Для «плоских» типов это memhash, для строк — strhash, для float — f32hash/f64hash, для интерфейсов — interhash/nilinterhash, для структур и массивов — сгенерированный компилятором хешер или универсальный typehash. На amd64/arm64 с AES-инструкциями memhash/strhash заменяются на aeshash, иначе используется вариант в духе wyhash/xxhash на 64-битных умножениях.

Глубже. Ко всем этим функциям примешивается соль в два уровня: глобальный runtime.hashkey (4 слова, заполняются случайными данными от ОС при старте процесса) и персональный seed мапы (hmap.hash0 до 1.24, Map.seed после), генерируемый в makemap через rand(). Поэтому один и тот же ключ в двух разных мапах в одном процессе даёт разные хеши. Это сознательная защита от hash-flooding-атак: клиент не может подобрать набор ключей, гарантированно попадающих в один бакет.

Важные частности. f64hash приводит -0 к +0 (иначе два равных по == значения имели бы разные хеши) и для NaN возвращает случайное число — отсюда известный эффект: m[math.NaN()] = 1 каждый раз кладёт новую недостижимую запись. interhash вызывает хешер динамического типа и паникует, если тип несравним (hash of unhashable type). Всё это — внутренности рантайма, из пользовательского кода они недоступны; если нужен «такой же» хеш в своём коде, используйте пакет hash/maphash, в частности maphash.Comparable[T] и maphash.WriteComparable (добавлены в Go 1.24).

Что может быть ключем в map?

Коротко. Любой сравнимый (comparable) тип, то есть тип, для которого определён оператор ==: все числовые типы, string, bool, указатели, каналы, интерфейсы, а также структуры и массивы, все поля/элементы которых сравнимы. Нельзя срезы, мапы и функции — они несравнимы, компилятор откажется.

Глубже. Три ловушки. Первая: интерфейс формально сравним, поэтому map[any]V компилируется, но если положить туда значение с несравнимым динамическим типом (например, срез), будет panic в рантайме — runtime error: hash of unhashable type []int. В дженериках это отражено разницей между comparable (строго сравнимые, проверка на этапе компиляции) и any со сравнением через рефлексию; с Go 1.20 интерфейсные типы удовлетворяют ограничению comparable в смысле «сравнимы по спецификации», но паника при несравнимом содержимом остаётся.

Вторая: NaN. math.NaN() != math.NaN(), поэтому записанный по такому ключу элемент нельзя ни прочитать, ни удалить (кроме как перебором в range — там ключ доступен) — мапа просто растёт. Не используйте float64 как ключ, если данные могут содержать NaN.

Третья: структура-ключ копируется целиком при вставке и хешируется по всем полям, включая невидимое выравнивание — точнее, компилятор для структур с «дырками» генерирует полевой хешер, а не memhash по всей памяти. Большой структурный ключ — это медленное хеширование и медленное сравнение; часто выгоднее заранее свернуть его в строку или в число. И помните: строка как ключ копируется по заголовку, но её байты мапа удерживает от сборки — подстрока огромного буфера, положенная в ключ, держит весь буфер.

Каков порядок перебора map?

Коротко. Порядок не определён и намеренно рандомизирован: при каждом range рантайм выбирает случайный стартовый бакет/группу и случайное смещение внутри неё. Полагаться на порядок нельзя даже в пределах одного процесса и одной неизменной мапы — два подряд идущих range по одной мапе дадут разный порядок.

Глубже. Это не побочный эффект, а сознательное решение авторов языка: спецификация прямо говорит «The iteration order over maps is not specified», а рандомизацию добавили, чтобы код не мог случайно «привыкнуть» к порядку и сломаться при смене реализации. Реализуется в mapiterinit: берётся случайное число, из него — стартовый бакет и offset внутри бакета; итератор идёт по кругу и останавливается, вернувшись к старту. В swiss-мапах логика та же: случайные стартовая группа и слот, плюс случайный порядок обхода таблиц directory.

Единственное исключение из «всё случайно» существовало для очень маленьких мап в старой реализации: если мапа умещалась в один бакет, рандомизировался только offset внутри него — но опираться на это всё равно нельзя. Если нужен детерминированный порядок — соберите ключи и отсортируйте:

keys := slices.Sorted(maps.Keys(m)) // Go 1.23+: maps.Keys даёт iter.Seq
for _, k := range keys {
    fmt.Println(k, m[k])
}

Отдельно: fmt при печати мапы (fmt.Println(m), %v) сортирует ключи начиная с Go 1.12 — поэтому вывод стабилен, а range — нет. И encoding/json сериализует map[string]T с отсортированными ключами.

Модификация значений мапы в цикле for range - что будет?

Коротко. Присваивание по уже существующему ключу (m[k] = newV) безопасно и сразу видно в мапе; переменная v из for k, v := range m — копия, менять её бессмысленно. Удаление во время итерации безопасно и стандартно: удалённый и ещё не пройденный ключ гарантированно не будет выдан. А вот добавление новых ключей — неопределённое поведение в смысле «новая запись может быть выдана в этой же итерации, а может быть пропущена»; цикл при этом не падает, но может стать бесконечным по смыслу и почти наверняка приведёт к росту мапы прямо под итератором.

Глубже. Формулировки из спецификации: «If a map entry that has not yet been reached is removed during iteration, the corresponding iteration value will not be produced. If a map entry is created during iteration, that entry may be produced during the iteration or may be skipped.» То есть delete внутри range — легальный и рекомендуемый способ фильтрации (или maps.DeleteFunc с Go 1.21), а вставка — «как повезёт».

for k, v := range m {
    v.Count++          // бесполезно: v — копия значения
    m[k] = v           // так — работает
    if v.Count > 100 {
        delete(m, k)   // безопасно
    }
    // m[k+"_copy"] = v // так делать не стоит: может быть выдано, может нет
}

Важно, что «модификация» из вопроса — это не гонка: всё происходит в одной горутине, детектор concurrent map iteration and map write тут не сработает. Он сработает, если писать в мапу из другой горутины во время range — тогда получите fatal error, который не ловится recover. Ещё две детали. Для структурных значений m[k].Field = x не скомпилируется (элемент неадресуем) — либо read-modify-write, как выше, либо map[K]*T. И с Go 1.22 переменные k, v создаются заново на каждой итерации, поэтому классическая ловушка с захватом k в замыкание/горутину больше не стреляет; в Go 1.21 и раньше — стреляла.

Что изменилось в работе с map в новых версиях Go?

Коротко. Четыре заметные вещи: Go 1.21 — builtin clear(m) и пакет maps в стандартной библиотеке; Go 1.22 — переменные цикла for range стали пер-итерационными; Go 1.23 — итераторы maps.All/Keys/Values/Collect/Insert на базе iter.Seq; Go 1.24 — реализация переписана на Swiss Tables плюс maphash.Comparable.

Глубже. По пунктам. clear(m) удаляет все элементы за один проход, корректно работает с NaN-ключами (которые нельзя удалить через delete) и не уменьшает выделенную память. Пакет maps в 1.21 приехал с Clone, Copy, DeleteFunc, Equal, EqualFunc; в 1.23, вместе с range-over-func, к нему добавились All, Keys, Values, Collect, Insert — заметьте, maps.Keys возвращает не слайс, а iter.Seq[K], слайс из него делают slices.Collect или slices.Sorted. Пер-итерационные переменные в 1.22 убрали самую популярную ошибку с горутинами внутри range по мапе. Swiss Tables в 1.24 — самое глубокое изменение: другой алгоритм разрешения коллизий, другой рост, ощутимо быстрее доступ на больших мапах и меньше памяти на маленьких; включается автоматически, откатывается через GOEXPERIMENT=noswissmap.

Чего не изменилось и о чём стоит сказать прямо: мапа по-прежнему не потокобезопасна, порядок обхода по-прежнему рандомизирован (и стал рандомизирован ещё чуть иначе), элемент по-прежнему неадресуем, память по-прежнему не возвращается после удалений. Публичный контракт языка не поменялся ни на йоту — в этом и был смысл переписывания «под капотом».

Как изменился алгоритм поиска в map по сравнению с ранними версиями?

Коротко. Раньше: по младшим битам хеша выбирался бакет, затем по массиву tophash последовательно сравнивались 8 байт, у совпавших слотов ключ сравнивался полностью, при неудаче — переход по цепочке overflow-бакетов. Теперь: по старшим битам выбирается таблица в directory, H1 даёт стартовую группу, а все 8 байт control word сравниваются с H2 одной 64-битной операцией (SWAR-трюк или SIMD), давая битовую маску кандидатов; при отсутствии совпадения и отсутствии пустых слотов идёт квадратичное пробирование к следующей группе.

Глубже. Разница по сути в трёх местах. Первое — сравнение: цикл по 8 байтам tophash с ветвлением превратился в пару битовых операций без ветвлений, что убирает промахи предсказателя переходов. Второе — коллизии: вместо связного списка overflow-бакетов (указатель → промах кеша → снова указатель) идёт пробирование по соседним группам, которые лежат в одном непрерывном массиве, то есть дружелюбны к кешу и префетчу. Третье — деградация: длинная overflow-цепочка могла превратить поиск в почти линейный, у открытой адресации с ограничением загрузки 7/8 такого патологического случая нет; зато появились tombstone’ы от удалений, которые чистятся при перестройке таблицы.

В обоих случаях сохраняется главный принцип: короткий фрагмент хеша (старший байт tophash / 7 бит H2) — это лишь фильтр, финальное решение всегда принимает полное сравнение ключей, иначе были бы ложные срабатывания. И в обоих случаях мапы до 8 элементов обрабатываются линейно, без индексации, — на маленьких мапах разница между реализациями невелика, выигрыш Swiss Tables проявляется на десятках тысяч элементов и больше.

Почему в Go больше нет понятия «эвакуация» применительно к map ?

Коротко. Потому что в реализации на Swiss Tables (Go 1.24+) исчезла сама конструкция, ради которой эвакуация существовала: нет пары buckets/oldbuckets, между которыми надо постепенно перетаскивать данные. Мапа разбита на таблицы не больше 1024 элементов, и растёт всегда ровно одна таблица — её просто перестраивают целиком за один раз или расщепляют на две, а directory удваивают. Работа ограничена сверху одной небольшой таблицей, поэтому размазывать её по последующим операциям не нужно.

Глубже. В старой схеме удвоение мапы на миллион элементов означало бы перенос миллиона записей в одной операции вставки — отсюда и придумали инкрементальный growWork с nevacuate, флагами evacuatedX/Y и необходимостью для каждого чтения, записи и итератора учитывать, что данные могут быть «ещё там» или «уже здесь». Это была заметная доля сложности runtime/map.go.

В новой схеме масштабирование вынесено на уровень directory (extendible hashing): пока таблица меньше 1024 элементов, при исчерпании growthLeft она заменяется таблицей вдвое большей ёмкости с полным рехешем — но это максимум ~1024 записи, десятки микросекунд в худшем случае. Когда таблица упирается в потолок, вызывается split: создаются две таблицы с увеличенным localDepth, записи расходятся по ним по очередному биту хеша, а directory либо просто обновляет свои указатели, либо удваивается, если localDepth дорос до globalDepth. Мапа целиком никогда не перестраивается.

Оговорка, которую стоит проговорить на собеседовании: понятие не исчезло из языка — оно исчезло из текущей реализации. Собрав проект с GOEXPERIMENT=noswissmap на Go 1.24 или взяв любую версию до 1.23 включительно, вы получите ровно ту же эвакуацию. И на других рантаймах (runtime/map_noswiss.go до сих пор лежит в исходниках) она тоже никуда не делась.

Нужно ли использовать json.RawMessage или map[string]interface{} ?

Коротко. Это инструменты для разных задач. json.RawMessage — когда вы хотите отложить или пробросить разбор куска JSON: сохранить сырые байты, передать дальше, распарсить позже в конкретный тип по дискриминатору. map[string]interface{} — когда структура действительно заранее неизвестна и нужно ходить по ней динамически. Если схема известна — не нужно ни то, ни другое: используйте типизированную структуру.

Глубже. Практическая разница. RawMessage — это просто []byte с методами MarshalJSON/UnmarshalJSON, поэтому он не аллоцирует дерево из мап и интерфейсов, ничего не теряет и не переупорядочивает — при обратной сериализации байты выйдут ровно такими, какими пришли. map[string]interface{}, наоборот, теряет информацию: все числа становятся float64 (int64 за пределами 2^53 испортится — лечится Decoder.UseNumber() и типом json.Number), порядок ключей теряется, дубли ключей схлопываются, а на большом документе это сотни аллокаций и медленный доступ через type assertion. Плюс к типобезопасности: любая опечатка в m["usr"]["nmae"] — это runtime, а не compile time.

Канонический паттерн с RawMessage — полиморфный разбор по полю-дискриминатору:

type Envelope struct {
    Type    string          `json:"type"`
    Payload json.RawMessage `json:"payload"`
}

var e Envelope
if err := json.Unmarshal(data, &e); err != nil {
    return err
}
switch e.Type {
case "user":
    var u User
    if err := json.Unmarshal(e.Payload, &u); err != nil {
        return err
    }
    // ...
}

Ещё случаи в пользу RawMessage: прокси/шлюз, который меняет два поля и отдаёт остальное как есть; хранение куска JSON в БД в jsonb-колонке; ленивая десериализация тяжёлого поля, которое нужно не всегда. Случаи в пользу map[string]any: конфиги и метаданные произвольной формы, merge-патчи, инструменты-«швейцарские ножи». Гибрид тоже нормален: map[string]json.RawMessage — динамический набор ключей при отложенном разборе значений. И полезно помнить про Unmarshal в структуру с полем Extra map[string]json.RawMessage, чтобы не терять неизвестные поля. Отдельно: в свежих версиях Go идёт работа над encoding/json/v2 (доступен как эксперимент под GOEXPERIMENT=jsonv2), где часть этих компромиссов решается иначе; на собеседовании достаточно упомянуть, что такая работа ведётся, не выдавая деталей за факт.

Частые ошибки на собесе

• Рассказывают устройство мапы «по статье 2019 года» и не знают, что в Go 1.24 реализация переехала на Swiss Tables; на уточняющий вопрос «а что нового?» ответить нечего.
• Путают уровни коллизии: говорят «коллизия — это когда совпал хеш», забывая, что почти всегда совпадают лишь младшие биты (номер бакета), а полный хеш разный.
• Утверждают, что мапа передаётся «по ссылке» как особый механизм языка. В Go всё передаётся по значению; просто значение мапы — указатель на заголовок в куче.
• Говорят, что delete или clear освобождают память. Нет: мапа никогда не сжимается, память возвращает только пересоздание.
• Считают, что nil-мапа падает на любой операции. Падает только запись; чтение, len, range, delete безопасны.
• Считают конкурентное чтение мапы опасным само по себе или, наоборот, надеются на recover при fatal error: concurrent map writes — это неперехватываемый throw, а параллельные чтения без писателей полностью законны.
• Предлагают sync.Map как «просто потокобезопасную мапу на все случаи», не зная её сценариев (read-mostly, непересекающиеся ключи) и того, что для write-heavy нагрузки map + RWMutex обычно быстрее.
• Обещают «указатель на элемент мапы» или полагаются на порядок обхода — обе вещи невозможны и обе имеют общую причину: элементы переезжают, а стартовая позиция итератора рандомизируется.
• Рассказывают про эвакуацию, oldbuckets и nevacuate как про «текущее устройство Go», не зная, что с 1.24 это уже не так; и наоборот — заучивают Swiss Tables и не могут объяснить старую схему, хотя половина продакшена ещё на 1.22–1.23.
• Говорят «хеш-функция в мапе — это FNV/MurmurHash/xxhash», называя одну функцию. Их несколько, они выбираются по типу ключа, и все солятся случайным seed.
• Не знают, зачем нужен случайный seed, и объясняют рандомный порядок обхода «особенностью хеш-таблицы» вместо сознательного решения плюс защиты от hash-flooding.
• Утверждают, что порядок обхода стабилен в пределах одного запуска или для маленьких мап. Не стабилен, и полагаться нельзя.
• Считают, что for k, v := range m { v.X = 1 } меняет мапу. v — копия; нужно m[k] = v или map[K]*T.
• Путают безопасность операций внутри range: думают, что delete во время итерации — UB (это законно и специфицировано), а вставка — нормально (вот она как раз не даёт гарантий).
• Считают map[string]interface{} универсальным решением для JSON и не знают ни про потерю точности чисел (float64), ни про json.Number, ни про json.RawMessage.
• Обещают, что map[K]*T «экономит память»: часто наоборот — плюс заголовок объекта на каждую запись и полноценная работа для GC на каждом цикле.

Что почитать

• Спецификация языка, раздел Map types и Index expressions: https://go.dev/ref/spec#Map_types
• Исходники новой реализации (Swiss Tables) с большим комментарием-описанием в шапке: https://go.dev/src/internal/runtime/maps/map.go и https://go.dev/src/internal/runtime/maps/table.go
• Исходники старой реализации (полезно для вопросов про бакеты и эвакуацию): https://go.dev/src/runtime/map_noswiss.go
• Go 1.24 Release Notes, раздел про производительность и новую реализацию мап: https://go.dev/doc/go1.24
• Документация sync.Map — там прямо описаны два сценария, в которых она уместна: https://pkg.go.dev/sync#Map
• Go blog, «Go maps in action» (устаревает по внутренностям, но хорош по семантике и идиомам): https://go.dev/blog/maps
• Спецификация: Map types и раздел For statements with range clause (там же — гарантии по delete/insert во время итерации): https://go.dev/ref/spec#Map_types
• Исходники новой реализации со вступительным комментарием, который подробно описывает directory, таблицы и группы: https://go.dev/src/internal/runtime/maps/map.go и https://go.dev/src/internal/runtime/maps/table.go
• Исходники старой реализации — эвакуация, growWork, evacuate, sameSizeGrow: https://go.dev/src/runtime/map_noswiss.go
• Хеш-функции рантайма (memhash, strhash, f64hash, interhash, typehash) и соль hashkey: https://go.dev/src/runtime/alg.go
• Go 1.24 Release Notes (Swiss Tables, maphash.Comparable) и Go 1.23 Release Notes (итераторы в maps): https://go.dev/doc/go1.24 и https://go.dev/doc/go1.23
• Документация encoding/json, в частности json.RawMessage, json.Number и Decoder.UseNumber: https://pkg.go.dev/encoding/json#RawMessage

---

Список исходных вопросов с привязкой к компаниям: ../questions/maps.md