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 main

import "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 main

func 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 main

import "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 = 0
8.3 true
map[Дюна:8.3] 1
  • Добавление и изменение выглядят одинаково — присваивание по ключу.
  • Нет ключа — нет паники: возвращается нулевое значение типа.
  • comma-ok: v, ok := m[k]. Ноль — это «фильма нет» или «рейтинг действительно ноль»? Без ok не отличить. ok == true — ключ есть, false — нет. Один из самых частых паттернов Go, его постоянно спрашивают на собеседованиях.
  • delete(m, k) безопасна: если ключа нет, ничего не произойдёт.

Обход и порядок

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

go
package main

import (
    "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 записей. Растёт только переполнившаяся таблица, остальные не трогаются.
ключхеш ключа, 64 битаh1старшие 57 битh2младшие 7 битконтрольное слово группы8 байтсравнить h2со всеми 8 байтами разомсовпавшие слоты:сравнить сами ключиследующая группане нашли, а пустыхслотов в группе нет
До 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.

Практика

Домашнее задание

  1. Подсчёт символов. Напиши countChars(s string) map[rune]int — сколько раз каждый символ встречается в строке. Проверь на "hello world".
  2. Проверка дубликатов. Напиши hasDuplicates(nums []int) bool — true, если в слайсе есть повтор. Используй мапу как множество.
  3. Каталог. Создай catalog map[string]float64 с 5 фильмами и рейтингами и напиши три функции:
    • AddFilm — добавляет фильм, только если его ещё нет в каталоге;
    • TopFilms — возвращает слайс названий с рейтингом выше заданного;
    • AverageRating — средний рейтинг по каталогу.

Заодно перепиши removeDuplicates из 09 — Массивы и слайсы → Практика через мапу.

решениеЭталонное решение
go
package main

import (
    "fmt"
    "maps"
    "slices"
)

func countChars(s string) map[rune]int {
    counts := make(map[rune]int)
    for _, r := range s {
        counts[r]++
    }
    return counts
}

func hasDuplicates(nums []int) bool {
    seen := make(map[int]struct{}, len(nums)) // мапа как множество
    for _, n := range nums {
        if _, ok := seen[n]; ok {
            return true
        }
        seen[n] = struct{}{}
    }
    return false
}

func removeDuplicates(s []string) []string {
    seen := make(map[string]bool, len(s))
    result := make([]string, 0, len(s))
    for _, v := range s {
        if !seen[v] {
            seen[v] = true
            result = append(result, v)
        }
    }
    return result
}

func AddFilm(catalog map[string]float64, title string, rating float64) bool {
    if _, exists := catalog[title]; exists {
        return false
    }
    catalog[title] = rating
    return true
}

func TopFilms(catalog map[string]float64, minRating float64) []string {
    var top []string
    for title, rating := range catalog {
        if rating > minRating {
            top = append(top, title)
        }
    }
    slices.Sort(top) // порядок мапы случайный — сортируем для стабильного вывода
    return top
}

func AverageRating(catalog map[string]float64) float64 {
    if len(catalog) == 0 {
        return 0
    }
    sum := 0.0
    for _, rating := range catalog {
        sum += rating
    }
    return sum / float64(len(catalog))
}

func main() {
    counts := countChars("hello world")
    for _, r := range slices.Sorted(maps.Keys(counts)) {
        fmt.Printf("%q:%d ", r, counts[r])
    }
    fmt.Println()

    fmt.Println(hasDuplicates([]int{1, 2, 3}), hasDuplicates([]int{1, 2, 1}))
    fmt.Println(removeDuplicates([]string{"Дюна", "Матрица", "Дюна"}))

    catalog := map[string]float64{
        "Дюна": 8.1, "Матрица": 8.7, "Довод": 7.8, "Начало": 8.8, "Аватар": 7.6,
    }
    fmt.Println(AddFilm(catalog, "Дюна", 9.0), AddFilm(catalog, "Оппенгеймер", 8.5))
    fmt.Println(TopFilms(catalog, 8.0))
    fmt.Printf("%.2f\n", AverageRating(catalog))
}
stdout // вывод программы
' ':1 'd':1 'e':1 'h':1 'l':3 'o':2 'r':1 'w':1
false true
[Дюна Матрица]
false true
[Дюна Матрица Начало Оппенгеймер]
8.25

Тренировка: предскажи вывод

go
package main

import "fmt"

func main() {
    films := map[string][]string{}
    films["Нолан"] = append(films["Нолан"], "Начало")
    films["Нолан"] = append(films["Нолан"], "Довод")
    fmt.Println(len(films["Нолан"]), len(films["Вильнёв"]), films["Вильнёв"] == nil)
}
самопроверкаОтвет
text
2 0 true

Для отсутствующего ключа мапа возвращает нулевое значение — 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 main

import "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 main

func 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 main

import "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 0
The Matrix is not in the catalog, rating = 0
8.3 true
map[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 main

import (
    "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.1
The Matrix: 8.7
Inception: 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.
keykey hash, 64 bitsh1top 57 bitsh2low 7 bitsgroup control word8 bytescompare h2against all 8 bytes at oncematching slots:compare the keys themselvesnext groupnot found and no emptyslots in the group
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

  1. Character count. Write countChars(s string) map[rune]int — how many times each character appears in a string. Test it on "hello world".
  2. Duplicate check. Write hasDuplicates(nums []int) bool — true if the slice contains a repeat. Use a map as a set.
  3. 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.

While you're at it, rewrite removeDuplicates from 09 — Arrays and slices → Practice using a map.

solution
go
package main

import (
    "fmt"
    "maps"
    "slices"
)

func countChars(s string) map[rune]int {
    counts := make(map[rune]int)
    for _, r := range s {
        counts[r]++
    }
    return counts
}

func hasDuplicates(nums []int) bool {
    seen := make(map[int]struct{}, len(nums)) // a map used as a set
    for _, n := range nums {
        if _, ok := seen[n]; ok {
            return true
        }
        seen[n] = struct{}{}
    }
    return false
}

func removeDuplicates(s []string) []string {
    seen := make(map[string]bool, len(s))
    result := make([]string, 0, len(s))
    for _, v := range s {
        if !seen[v] {
            seen[v] = true
            result = append(result, v)
        }
    }
    return result
}

func AddFilm(catalog map[string]float64, title string, rating float64) bool {
    if _, exists := catalog[title]; exists {
        return false
    }
    catalog[title] = rating
    return true
}

func TopFilms(catalog map[string]float64, minRating float64) []string {
    var top []string
    for title, rating := range catalog {
        if rating > minRating {
            top = append(top, title)
        }
    }
    slices.Sort(top) // map order is random — sort for stable output
    return top
}

func AverageRating(catalog map[string]float64) float64 {
    if len(catalog) == 0 {
        return 0
    }
    sum := 0.0
    for _, rating := range catalog {
        sum += rating
    }
    return sum / float64(len(catalog))
}

func main() {
    counts := countChars("hello world")
    for _, r := range slices.Sorted(maps.Keys(counts)) {
        fmt.Printf("%q:%d ", r, counts[r])
    }
    fmt.Println()

    fmt.Println(hasDuplicates([]int{1, 2, 3}), hasDuplicates([]int{1, 2, 1}))
    fmt.Println(removeDuplicates([]string{"Dune", "The Matrix", "Dune"}))

    catalog := map[string]float64{
        "Dune": 8.1, "The Matrix": 8.7, "Tenet": 7.8, "Inception": 8.8, "Avatar": 7.6,
    }
    fmt.Println(AddFilm(catalog, "Dune", 9.0), AddFilm(catalog, "Oppenheimer", 8.5))
    fmt.Println(TopFilms(catalog, 8.0))
    fmt.Printf("%.2f\n", AverageRating(catalog))
}
stdout // program output
' ':1 'd':1 'e':1 'h':1 'l':3 'o':2 'r':1 'w':1
false true
[Dune The Matrix]
false true
[Dune Inception Oppenheimer The Matrix]
8.25

Drill: predict the output

go
package main

import "fmt"

func main() {
    films := map[string][]string{}
    films["Nolan"] = append(films["Nolan"], "Inception")
    films["Nolan"] = append(films["Nolan"], "Tenet")
    fmt.Println(len(films["Nolan"]), len(films["Villeneuve"]), films["Villeneuve"] == nil)
}
self-check
text
2 0 true

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.
// related topics and cheatsheets