Часть 3. Данные и памятьУрок 10# go# коллекции# мапы# собеседование

Мапы

comma-ok, nil-мапа, порядок обхода, бакеты и 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 записей.
  • 🔒 Мапа не потокобезопасна: конкурентная запись — фатальная ошибка.
// связанные темы и шпаргалки