Модуль 5 ⏱ ~33 мин чтения 📐 2 Mermaid диаграмм

19. Map под капотом. hmap, buckets и рост

В предыдущей статье 18. Map. Хеш-таблица в Go мы познакомились с синтаксисом и базовым поведением мап. Мы узнали, что мапа передается в функции как легковесный 8-байтный указатель. Но на какую именно структуру в памяти он указывает?

Реализация хэш-таблицы в рантайме Go (написанная Китом Рэндаллом и командой рантайма) — это подлинный триумф системной инженерии. Здесь органично переплелись криптографическая защита от сетевых атак, механическое сочувствие к кэшам процессора (L1/L2) и алгоритмы плавной дефрагментации памяти без остановки мира. Понимание того, как мапа устроена на уровне байтов, — один из главных маркеров Senior-инженера на технических собеседованиях.

В этой главе мы препарируем структуру hmap, разберем анатомию бакетов bmap, проследим путь поиска ключа и выясним, почему мапа в Go никогда не отдает захваченную память обратно операционной системе.

1. Структура hmap: Заголовок хеш-таблицы

Разделы 1–5 описывают классическую реализацию хэш-таблицы, которая служила Go с версии 1.0 по 1.23. С Go 1.24 мапа устроена иначе — на основе Swiss Tables (раздел 6), но многие идеи (хэш с солью, поиск по коротким «отпечаткам» хэша, рост с перераспределением ключей) живут и в новой модели.

Когда вы пишете make(map[string]int), классический рантайм Go аллоцирует в куче структуру hmap (Header Map). Она описана в исходниках рантайма в файле runtime/map.go и хранит управляющие метаданные:

Go 
// Упрощенная структура hmap из исходников рантайма
type hmap struct {
    count     int    // Логическое количество элементов (len)
    flags     uint8  // Флаги состояния (например, hashWriting для защиты от гонок)
    B         uint8  // Логарифм от количества бакетов (2^B = кол-во бакетов)
    noverflow uint16 // Примерное количество overflow-бакетов
    hash0     uint32 // Рандомный seed (соль) для хеш-функции

    buckets    unsafe.Pointer // Указатель на массив текущих бакетов
    oldbuckets unsafe.Pointer // Указатель на старый массив бакетов (при эвакуации)
    // ... отладочные поля и счетчики
}

Ключевые поля структуры:

  • count: счетчик элементов. Именно это поле мгновенно читается за $O(1)$, когда вы вызываете функцию len(m).
  • B: показатель степени двойки для количества бакетов. Число бакетов всегда равно $2^B$. Если B = 4, в мапе ровно $2^4 = 16$ бакетов.
  • buckets: прямой указатель на непрерывный массив бакетов в оперативной памяти.

2. Структура bmap (Бакет) и Mechanical Sympathy

Хэш-таблица в Go — это массив бакетов (buckets). Каждый бакет представлен структурой bmap и спроектирован так, чтобы вмещать ровно 8 пар «ключ-значение»:

flowchart LR
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    HMAP["hmap"]:::process -->|"buckets"| BArray["Массив бакетов"]
    BArray --> B0["Бакет 0"]
    BArray --> B1["Бакет 1"]
    BArray --> B2["Бакет 2"]

    B1 -->|"Если бакет переполнен"| OF["Overflow Бакет"]

Если вы заглянете в runtime/map.go, определение bmap покажется обманчиво пустым: там объявлено лишь одно поле tophash. Причина в том, что конкретная структура бакета компилируется динамически на лету в зависимости от типов ключа и значения.

Логическая топология бакета bmap выглядит следующим образом:

flowchart LR
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    subgraph BMAP["Структура bmap (один бакет)"]
        direction LR
        T["tophash<br>Массив из 8 байт"]:::process --> K["Keys<br>8 ключей подряд"]
        K --> V["Values<br>8 значений подряд"]
        V --> O["Overflow ptr<br>Указатель на след. бакет"]
    end

Mechanical Sympathy: Гениальная оптимизация памяти

Обратите внимание на физический порядок полей в памяти. Почему Go не хранит элементы парами K1, V1, K2, V2..., а группирует их монолитными блоками: K1, K2, K3... V1, V2, V3...?

Причина — выравнивание памяти (Memory Padding), о котором мы будем подробно говорить в главе 21. Struct. Пользовательские типы данных.

Представьте хэш-таблицу типа map[int64]int8:

  • Ключ int64 занимает 8 байт (требует выравнивания по границе 8 байт).
  • Значение int8 занимает всего 1 байт.

Если бы они чередовались парами (int64, int8), процессору требовалось бы вставлять 7 байт пустого заполнителя (padding) после каждого однобайтового значения, чтобы следующий 8-байтный ключ начинался с кратного адреса. На одном бакете впустую сгорало бы 56 байт памяти!

Сгруппировав 8 ключей вместе, а следом разместив 8 значений, классический рантайм Go (до 1.23) полностью уничтожал паразитный padding. Бакет получался компактным, для небольших ключей и значений помещаясь в одну-две кэш-линии процессора (L1 Cache). (В Swiss Tables с Go 1.24 слоты по умолчанию снова чередуются — key, elem, key, elem…; раздельная раскладка включается только экспериментом GOEXPERIMENT=mapsplitgroup.)

3. Анатомия поиска: Как Go находит элемент?

Когда программа запрашивает элемент по ключу (val := m["alice"]), процессор выполняет пятишаговый алгоритм:

  1. Хеширование: Ключ "alice" смешивается с солью hash0 и передается в хэш-функцию. На выходе получается 64-битный хэш.
  2. Выбор бакета (Low bits): Рантайм берет младшие B бит хэша. Если B = 4, берутся 4 младших бита (например, 0011 в двоичной системе = 3 в десятичной). Поиск направляется строго в Бакет №3.
  3. TopHash (Быстрый фильтр): Рантайм берет старшие 8 бит хэша (High bits) — это значение tophash.
  4. Быстрый поиск внутри бакета: Процессор не сравнивает строки! Он проходит скалярным циклом по 8 байтам массива tophash внутри бакета, сравнивая однобайтовые «отпечатки». (Параллельное SIMD-сравнение 8 контрольных байт — уже свойство Swiss Tables, раздел 6.)
  5. Финальное сравнение: Только если байт в tophash совпал со старшими битами искомого хэша, рантайм обращается к массиву ключей и выполняет честное сравнение key == "alice". Это исключает миллионы дорогостоящих сравнений тяжелых строк и структур.

4. Разрешение коллизий: Chaining (Цепочки)

Что происходит, когда в один и тот же бакет хэшируется 9-й элемент, а все 8 слотов уже заняты?

Go использует модифицированный метод связных списков (Separate Chaining). Рантайм выделяет в куче дополнительный бакет переполнения (Overflow Bucket) и записывает указатель на него в поле overflow текущего бакета, выстраивая цепочку.

5. Эвакуация (Рост мапы)

Решение о расширении таблицы рантайм Go принимает на основе двух строгих триггеров:

  1. Load Factor > 6.5. Фактор загрузки — это отношение общего числа элементов к числу бакетов (count / 2^B). Если корзины заполнены в среднем более чем на 80% (6.5 из 8 слотов), вероятность коллизий резко возрастает.
  2. Слишком много overflow-бакетов. Если фактор загрузки невелик, но создано аномально много overflow-бакетов (следствие частой вставки и удаления ключей), мапа страдает от острой фрагментации.

Инкрементальная эвакуация (Incremental Rehash)

Когда превышен Load Factor > 6.5, рантайм:

  1. Увеличивает B на 1 (общее число бакетов удваивается).
  2. Выделяет новый массив бакетов.
  3. Сохраняет указатель на старый массив в поле oldbuckets, а новый массив связывает с buckets.

Но Go никогда не копирует все данные разом.
Если в вашей таблице содержится 10 миллионов элементов, полная блокировка сервиса (Stop-The-World) ради их переноса заморозила бы сервер на секунды, сокрушив все SLA по задержкам (latency).

Вместо этого Go применяет инкрементальную эвакуацию:
При каждом последующем вызове записи (m[k] = v) или удаления (delete) рантайм эвакуирует ровно один или два бакета из oldbuckets, пересчитывает для их 8 элементов новые адреса и аккуратно перемещает их в новый массив.

Эвакуация того же размера (Same-size Evacuation)

Если эвакуацию спровоцировало переполнение overflow-бакетов при низком Load Factor, удваивать емкость бессмысленно. Рантайм выделяет массив точно такого же размера ($2^B$) и переносит ключи туда.

Это чистая дефрагментация: разрозненные элементы из длинных overflow-цепочек уплотняются обратно в основные бакеты, освобождая «дыры», оставшиеся после операций delete.

6. Go 1.24+: Swiss Tables

С Go 1.24 мапа реализована по мотивам Swiss Table из библиотеки Abseil (Google). Ключевые отличия от классической модели:

  • Группы вместо бакетов. Слоты собраны в группы по 8. У каждой группы есть контрольное слово (ctrl, 8 байт — по байту на слот), где для занятого слота хранятся 7 младших бит хэша (H2), а остальные биты хэша (H1) выбирают, с какой группы начинать поиск.
  • Поиск. Рантайм сравнивает H2 искомого ключа сразу со всеми 8 контрольными байтами группы (на amd64 — SIMD-инструкциями, на других архитектурах — арифметикой над 64-битным словом) и честно сравнивает ключи только в совпавших слотах. Цепочек overflow-бакетов нет: при заполненной группе поиск продолжается в следующих группах (открытая адресация).
  • Таблицы и директория. Одна таблица вмещает не больше 1024 слотов; большая мапа — это директория из нескольких таблиц. Таблица заполняется в среднем не больше чем на 7/8.
  • Рост. Растёт не вся мапа сразу, а одна переполненная таблица: она расщепляется на две. Поэтому пауза на рост ограничена размером одной таблицы.
  • Удаление. Удалённый слот помечается «надгробием» (tombstone), чтобы не разорвать цепочку поиска.
  • Раскладка. Слоты по умолчанию чередуются (key, elem); раздельная раскладка (KKKK…VVVV) — только с GOEXPERIMENT=mapsplitgroup.

7. Великая утечка памяти в Map

С мапами в Go связан фундаментальный архитектурный нюанс, о котором обязан помнить каждый бэкенд-разработчик:

Хэш-таблица в Go никогда не уменьшает свой размер (does not shrink).

Если под пиковой нагрузкой вы добавили в мапу 1 000 000 элементов, классический рантайм выделит под них $2^{18} = 262\,144$ бакета в куче (число бакетов — степень двойки, а при load factor 6,5 нужно не меньше 153 847) — около 54 МБ для map[string]int.
Если затем вы вызовете функцию delete для всех 1 000 000 ключей, счетчик count честно обнулится до 0. Однако физический массив из 262 144 бакетов (десятки мегабайт оперативной памяти, а для крупных значений — и больше) навсегда останется в памяти. Поле B никогда не уменьшается в меньшую сторону! Сборщик мусора бессилен, так как живая структура hmap продолжает удерживать массив корзин. Swiss Tables (Go 1.24+) в этом не отличаются: замер на Go 1.27 даёт те же ~56 МБ на миллион ключей map[string]int, и после удаления всех ключей память не освобождается.

Как бороться с этой утечкой?
Если вы используете мапу в качестве локального In-Memory кэша, который периодически раздувается, а затем сбрасывается, периодически пересоздавайте мапу заново:

Go 
// Плохой подход для In-Memory кэша (память не освобождается):
for k := range cache {
    delete(cache, k)
}

// Идиоматичный подход (старая мапа уходит в Garbage Collector):
cache = make(map[string]Data)

Итог

  1. hmap: структура хэш-таблицы в куче (~48 байт на 64-битной платформе), на которую ссылается 8-байтный указатель переменной мапы *hmap. Хранит счетчик элементов count, логарифмический размер $2^B$ и случайную соль hash0 для защиты от сетевых атак HashDOS.
  2. bmap (Бакет): Вмещает ровно 8 записей. В классической реализации (до Go 1.23) ключи и значения сгруппированы раздельно (K1..K8, V1..V8), исключая внутренний padding выравнивания; в Swiss Tables (Go 1.24+) слоты по умолчанию чередуются.
  3. TopHash: 8-битный массив старших байт хэша, позволяющий мгновенно фильтровать несовпадающие ключи инструкциями CPU.
  4. Инкрементальный рост: При Load Factor > 6.5 емкость удваивается. Перенос данных происходит порциями по 1–2 бакета при операциях мутации, гарантируя низкие задержки (low latency).
  5. Память не сжимается: Вызов delete удаляет значения, но не освобождает бакеты (и группы Swiss Tables тоже). Периодически пересоздавайте раздувающиеся мапы через make.
  6. Swiss Tables (Go 1.24+): группы по 8 слотов с контрольным словом, таблицы до 1024 слотов, рост расщеплением одной таблицы; в современных версиях Go классической реализации больше нет.

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

В следующей статье — 20. Строки в Go. Immutable string и работа с Unicode — мы заглянем под капот строк, исследуем StringHeader, интернирование (interning) и разберем высокопроизводительную конкатенацию через strings.Builder.