Часть 3. Данные и памятьУрок 10# go# коллекции# мапы# собеседование
Мапы
comma-ok, nil-мапа, порядок обхода, бакеты и Swiss Tables
Part 3. Data & MemoryLesson 10# go# collections# maps# interview
Maps
comma-ok, nil map, iteration order, buckets and Swiss Tables
Цели главы
Создавать мапы тремя способами и понимать ловушку nil-мапы.
Читать, записывать, проверять наличие ключа через comma-ok и удалять.
Обходить мапу и получать стабильный порядок.
Рассказать, как мапа устроена до и после Go 1.24.
Зачем мапа
У каждого фильма в каталоге уникальный ID, и нужно найти фильм по ID. В слайсе пришлось бы перебирать элементы один за другим — это медленно. Мапа (map, хеш-таблица) отвечает сразу: дал ключ — получил значение. Как словарь: знаешь слово — сразу видишь определение, не листая все страницы.
Создание
Тип мапы: map[тип ключа]тип значения. Три способа создать:
go
package mainimport "fmt"func main() { ratings := map[string]float64{ // литерал с данными "Дюна": 8.1, "Довод": 7.8, } views := make(map[string]int) // пустая, готова к записи var cache map[string]int // nil-мапа views["Дюна"]++ fmt.Println(len(ratings), views, cache == nil, cache["любой"])}
stdout // вывод программы
2 map[Дюна:1] true 0
Ловушка nil-мапы
Читать из nil-мапы можно — вернётся нулевое значение. Но как только попробуешь записать — паника, программа падает.
go
package mainfunc main() { var m map[string]int m["Дюна"] = 1 // ожидается panic}
text
panic: assignment to entry in nil map
Какие типы могут быть ключом
Ключом может быть любой сравнимый тип: строки, числа, bool, указатели, каналы, интерфейсы, массивы и структуры, все поля которых сравнимы. Слайсы, мапы и функции ключом быть не могут: map[[]string]int даёт ошибку invalid map key type []string.
Чтение, запись и удаление
go
package mainimport "fmt"func main() { m := make(map[string]float64) m["Дюна"] = 8.1 m["Довод"] = 7.8 m["Дюна"] = 8.3 // тот же ключ — перезапись fmt.Println(m["Дюна"], m["Матрица"]) // отсутствующий ключ — нулевое значение if rating, ok := m["Матрица"]; !ok { fmt.Println("Матрицы нет в каталоге, rating =", rating) } rating, ok := m["Дюна"] fmt.Println(rating, ok) delete(m, "Довод") delete(m, "Несуществующий") // ключа нет — ничего не происходит fmt.Println(m, len(m))}
stdout // вывод программы
8.3 0Матрицы нет в каталоге, rating = 08.3 truemap[Дюна:8.3] 1
Добавление и изменение выглядят одинаково — присваивание по ключу.
Нет ключа — нет паники: возвращается нулевое значение типа.
comma-ok: v, ok := m[k]. Ноль — это «фильма нет» или «рейтинг действительно ноль»? Без ok не отличить. ok == true — ключ есть, false — нет. Один из самых частых паттернов Go, его постоянно спрашивают на собеседованиях.
delete(m, k) безопасна: если ключа нет, ничего не произойдёт.
Обход и порядок
Обходят мапу через range, как слайс: на каждом шаге — ключ и значение. Порядок при каждом запуске может быть разным: Go специально его рандомизирует, чтобы никто не завязывался на порядок элементов. Нужен конкретный порядок — собери ключи в слайс, отсортируй и обходи по нему.
go
package mainimport ( "fmt" "maps" "slices")func main() { ratings := map[string]float64{"Начало": 8.8, "Дюна": 8.1, "Матрица": 8.7} for _, title := range slices.Sorted(maps.Keys(ratings)) { // Go 1.23+ fmt.Printf("%s: %.1f\n", title, ratings[title]) }}
stdout // вывод программы
Дюна: 8.1Матрица: 8.7Начало: 8.8
Как устроена мапа
Это спрашивают на собеседованиях, и это помогает понимать поведение мапы. В Go 1.24 реализацию полностью переписали, поэтому полезно знать обе.
До Go 1.24: бакеты и цепочки
Данные лежат в бакетах — группах на 8 пар «ключ — значение».
При вставке Go считает хеш ключа и по нему выбирает бакет.
В каждом бакете есть массив tophash — по байту на слот с первыми 8 битами хеша, мини-отпечаток. При поиске Go сначала сравнивает tophash и только при совпадении — сам ключ. Это экономит время.
Если бакет заполнился, к нему цепочкой цепляется overflow-бакет (chaining). Длинные цепочки замедляют поиск.
С Go 1.24: Swiss Tables
Реализацию переписали на Swiss Tables — дизайн из Google, который используют в C++ (Abseil) и Rust. Вместо цепочек — открытая адресация: данные хранятся в группах по 8 слотов, а у каждой группы есть 64-битное контрольное слово — по байту на слот.
Хеш ключа делится на две части: h1 — старшие 57 бит, определяет, с какой группы начинать поиск; h2 — младшие 7 бит, хранится в байте контрольного слова.
Байт контрольного слова говорит, пуст ли слот, удалён или занят, а для занятого слота хранит его h2.
При поиске h2 сравнивается сразу со всеми 8 байтами контрольного слова за одну операцию — на amd64 это SIMD-инструкции. Вместо проверки слотов по одному — все 8 разом.
Если в группе не нашлось, проверяется следующая группа (probing).
Мапа разбита на несколько независимых таблиц, в каждой не больше 1024 записей. Растёт только переполнившаяся таблица, остальные не трогаются.
До Go 1.24
С Go 1.24
Структура
бакеты по 8 слотов
группы по 8 слотов + контрольное слово
Коллизии
цепочки overflow-бакетов
открытая адресация, переход к следующей группе
Мини-хеш
tophash, 8 бит
h2, 7 бит в контрольном слове
Поиск в группе
по одному слоту
все 8 слотов разом
Рост
вся мапа вдвое, с постепенной эвакуацией бакетов
растёт отдельная таблица до 1024 записей
Скорость
базовая
до 60% быстрее в микробенчмарках
На практике менять ничего не нужно: обновил Go до 1.24 — и все мапы работают на Swiss Tables.
Мапа и горутины
Мапа не потокобезопасна. Одновременная запись из нескольких горутин приводит к аварийному завершению fatal error: concurrent map writes — его нельзя перехватить через recover.
Практика
Домашнее задание
Подсчёт символов. Напиши countChars(s string) map[rune]int — сколько раз каждый символ встречается в строке. Проверь на "hello world".
Проверка дубликатов. Напиши hasDuplicates(nums []int) bool — true, если в слайсе есть повтор. Используй мапу как множество.
Каталог. Создай catalog map[string]float64 с 5 фильмами и рейтингами и напиши три функции:
AddFilm — добавляет фильм, только если его ещё нет в каталоге;
TopFilms — возвращает слайс названий с рейтингом выше заданного;
Для отсутствующего ключа мапа возвращает нулевое значение — nil-слайс, а append к nil-слайсу работает. Это стандартный приём для группировки.
Проверь себя
вопросЧто будет при чтении из nil-мапы и при записи в неё?
Чтение вернёт нулевое значение, запись вызовет panic: assignment to entry in nil map.
вопросКак отличить «ключа нет» от «значение равно нулю»?
Через comma-ok: v, ok := m[k]; ok == false — ключа нет.
вопросКакие типы не могут быть ключом мапы?
Несравнимые: слайсы, мапы и функции.
вопросПочему порядок обхода мапы меняется и как получить стабильный порядок?
Go специально рандомизирует порядок, чтобы на него не полагались. Стабильный порядок — отсортировать ключи: slices.Sorted(maps.Keys(m)).
вопросКак устроена мапа до Go 1.24?
Массив бакетов по 8 пар; tophash — первые 8 бит хеша на каждый слот для быстрого отсева; при переполнении бакета — цепочка overflow-бакетов; рост вдвое с постепенной эвакуацией.
вопросЧто такое Swiss Tables в Go 1.24?
Группы по 8 слотов с 64-битным контрольным словом. Хеш делится на h1 (57 бит, выбор группы) и h2 (7 бит, в контрольном слове); h2 сравнивается со всеми 8 слотами разом; коллизии решаются открытой адресацией; мапа делится на таблицы до 1024 записей, которые растут независимо.
вопросМожно ли писать в одну мапу из нескольких горутин?
Нет: это fatal error: concurrent map writes. Нужен sync.Mutex или sync.Map.
Ключевые выводы
⚡ Мапа — доступ по ключу без перебора; ключ должен быть сравнимым типом.
💥 Из nil-мапы читать можно, писать — паника; инициализируй через make или литерал.
✅ comma-ok v, ok := m[k] отличает отсутствие ключа от нулевого значения.
🎲 Порядок обхода случайный; для стабильного — сортируй ключи.
🧪 С Go 1.24 мапы — Swiss Tables: группы, контрольное слово, h1/h2, таблицы до 1024 записей.
🔒 Мапа не потокобезопасна: конкурентная запись — фатальная ошибка.
Chapter goals
Create maps three ways and understand the nil map trap.
Read, write, check for a key with comma-ok, and delete.
Iterate a map and get a stable order.
Explain how a map is built before and after Go 1.24.
Why a map
Every movie in the catalog has a unique ID, and you need to find a movie by its ID. With a slice you'd have to walk the elements one by one — slow. A map (a hash table) answers immediately: give it a key — get the value. Like a dictionary: you know the word, you instantly see the definition without flipping through every page.
Creation
The map type is map[key type]value type. Three ways to create one:
go
package mainimport "fmt"func main() { ratings := map[string]float64{ // literal with data "Dune": 8.1, "Tenet": 7.8, } views := make(map[string]int) // empty, ready for writes var cache map[string]int // a nil map views["Dune"]++ fmt.Println(len(ratings), views, cache == nil, cache["anything"])}
stdout // program output
2 map[Dune:1] true 0
The nil map trap
Reading from a nil map is fine — you get the zero value back. But the moment you try to write — a panic, the program crashes.
go
package mainfunc main() { var m map[string]int m["Dune"] = 1 // panic expected}
text
panic: assignment to entry in nil map
Which types can be keys
A key can be any comparable type: strings, numbers, bool, pointers, channels, interfaces, arrays, and structs whose fields are all comparable. Slices, maps, and functions cannot be keys: map[[]string]int gives the error invalid map key type []string.
Reading, writing, and deleting
go
package mainimport "fmt"func main() { m := make(map[string]float64) m["Dune"] = 8.1 m["Tenet"] = 7.8 m["Dune"] = 8.3 // same key — overwrite fmt.Println(m["Dune"], m["The Matrix"]) // missing key — zero value if rating, ok := m["The Matrix"]; !ok { fmt.Println("The Matrix is not in the catalog, rating =", rating) } rating, ok := m["Dune"] fmt.Println(rating, ok) delete(m, "Tenet") delete(m, "Missing") // no such key — nothing happens fmt.Println(m, len(m))}
stdout // program output
8.3 0The Matrix is not in the catalog, rating = 08.3 truemap[Dune:8.3] 1
Adding and updating look the same — assignment by key.
No key — no panic: the zero value of the type is returned.
comma-ok: v, ok := m[k]. Is zero «the movie isn't there» or «the rating really is zero»? Without ok you can't tell. ok == true — the key exists, false — it doesn't. One of the most common Go patterns, asked about constantly in interviews.
delete(m, k) is safe: if the key doesn't exist, nothing happens.
Iteration and order
You iterate a map with range, like a slice: each step gives a key and a value. The order may differ from run to run: Go randomizes it on purpose so that nobody relies on element order. When you need a specific order, collect the keys into a slice, sort it, and iterate over that.
go
package mainimport ( "fmt" "maps" "slices")func main() { ratings := map[string]float64{"Inception": 8.8, "Dune": 8.1, "The Matrix": 8.7} for _, title := range slices.Sorted(maps.Keys(ratings)) { // Go 1.23+ fmt.Printf("%s: %.1f\n", title, ratings[title]) }}
stdout // program output
Dune: 8.1The Matrix: 8.7Inception: 8.8
How a map works
This gets asked in interviews, and it helps to understand map behavior. In Go 1.24 the implementation was completely rewritten, so it's useful to know both.
Before Go 1.24: buckets and chains
Data lives in buckets — groups of 8 key-value pairs.
On insert, Go hashes the key and picks the bucket from the hash.
Each bucket has a tophash array — one byte per slot holding the first 8 bits of the hash, a mini-fingerprint. On lookup, Go compares tophash first and only then the key itself. It saves time.
When a bucket fills up, an overflow bucket is chained to it (chaining). Long chains slow down lookups.
Since Go 1.24: Swiss Tables
The implementation was rewritten to Swiss Tables — a design from Google used in C++ (Abseil) and Rust. Instead of chains, it uses open addressing: data is stored in groups of 8 slots, and each group has a 64-bit control word — one byte per slot.
The key hash is split in two: h1 — the top 57 bits, which determine the group where the search starts; h2 — the low 7 bits, stored in a byte of the control word.
A control word byte tells whether a slot is empty, deleted, or occupied, and for an occupied slot it holds its h2.
On lookup, h2 is compared against all 8 control word bytes in one operation — SIMD instructions on amd64. Instead of checking slots one by one — all 8 at once.
If nothing is found in the group, the next group is checked (probing).
A map is split into several independent tables, each holding at most 1024 entries. Only the overflowing table grows; the others are left alone.
Before Go 1.24
Since Go 1.24
Structure
buckets of 8 slots
groups of 8 slots + a control word
Collisions
chains of overflow buckets
open addressing, move to the next group
Mini-hash
tophash, 8 bits
h2, 7 bits in the control word
Group lookup
slot by slot
all 8 slots at once
Growth
the whole map doubles, buckets evacuated gradually
a single table of up to 1024 entries grows
Speed
baseline
up to 60% faster in microbenchmarks
In practice nothing changes for you: upgrade to Go 1.24, and every map runs on Swiss Tables.
Maps and goroutines
A map is not safe for concurrent use. Simultaneous writes from several goroutines lead to the fatal crash fatal error: concurrent map writes — it cannot be caught with recover.
Practice
Homework
Character count. Write countChars(s string) map[rune]int — how many times each character appears in a string. Test it on "hello world".
Duplicate check. Write hasDuplicates(nums []int) bool — true if the slice contains a repeat. Use a map as a set.
Catalog. Create a catalog map[string]float64 with 5 movies and ratings and write three functions:
AddFilm — adds a movie only if it isn't in the catalog yet;
TopFilms — returns a slice of titles with a rating above a given one;
AverageRating — the average rating across the catalog.
For a missing key the map returns the zero value — a nil slice — and append on a nil slice works. This is a standard grouping technique.
Check yourself
questionWhat happens when reading from and writing to a nil map?
Reading returns the zero value; writing causes panic: assignment to entry in nil map.
questionHow do you tell «no such key» apart from «the value is zero»?
With comma-ok: v, ok := m[k]; ok == false means the key doesn't exist.
questionWhich types cannot be map keys?
Non-comparable ones: slices, maps, and functions.
questionWhy does map iteration order change, and how do you get a stable order?
Go deliberately randomizes the order so nobody depends on it. For a stable order, sort the keys: slices.Sorted(maps.Keys(m)).
questionHow is a map implemented before Go 1.24?
An array of buckets holding 8 pairs each; tophash — the first 8 bits of the hash per slot for quick filtering; on bucket overflow — a chain of overflow buckets; doubling growth with gradual bucket evacuation.
questionWhat are Swiss Tables in Go 1.24?
Groups of 8 slots with a 64-bit control word. The hash is split into h1 (57 bits, group selection) and h2 (7 bits, in the control word); h2 is compared against all 8 slots at once; collisions are resolved by open addressing; the map is split into tables of up to 1024 entries that grow independently.
questionCan you write to one map from several goroutines?
No: it's fatal error: concurrent map writes. You need sync.Mutex or sync.Map.
Key takeaways
⚡ A map — key access without scanning; the key must be a comparable type.
💥 Reading from a nil map is fine, writing panics; initialize with make or a literal.
✅ comma-ok v, ok := m[k] tells a missing key apart from a zero value.
🎲 Iteration order is random; for a stable one — sort the keys.
🧪 Since Go 1.24 maps are Swiss Tables: groups, the control word, h1/h2, tables of up to 1024 entries.
🔒 A map is not safe for concurrent use: concurrent writes are a fatal error.