Карта в Go: контракт языка, Swiss Table и четыре следствия устройства

Что гарантирует язык

Шесть операций, и других нет:

scores := map[string]int{"alice": 10}
scores["mike"] = 12                 // записать
score := scores["alice"]            // прочитать
score, ok := scores["john"]         // прочитать с проверкой наличия
delete(scores, "alice")             // удалить
n := len(scores)                    // сколько записей
for k, v := range scores { }        // обойти

Чтение отсутствующего ключа не паникует — оно даёт нулевое значение типа элемента. Отсюда вопрос, ради которого существует форма с двумя результатами: как отличить существующий ключ со значением 0 от отсутствующего? Одноместной формой — никак.

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

Карта и горутины. Падение рантайма — не механизм защиты: прогон bench/gomap/concurrent.go показывает, что две одновременные записи роняют процесс с fatal error: concurrent map writes, а чтение одновременно с записью завершается с кодом 0 и без единого сообщения. Ту же гонку -race находит всегда. Лечится мьютексом рядом с картой или владением одной горутиной; sync.Map сделан под два узких случая, и его документация от него отговаривает.

Всё дальше — устройство реализации Go 1.24. Оно объясняет поведение, но ничего не гарантирует.

Почему изменения видны после передачи в функцию

func add(m map[string]int) { m["x"] = 1 }   // снаружи ВИДНО
func grow(s []int)         { s = append(s, 42) }   // снаружи НЕ видно

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

unsafe.Sizeof(map[int]int{})   // 8 — одно слово
unsafe.Sizeof([]int{})         // 24 — три

Механизм: управляющий байт, одна операция и правило остановки

Хеш ключа делится надвое: старшие 57 бит выбирают группу из восьми слотов, младшие 7 пишутся в байт-метку этого слота. Восемь таких байтов лежат подряд и составляют одно 64-битное управляющее слово.

Почему меток семь бит, а не восемь? Потому что восьмой различает три состояния слота:

  свободен   1 0 0 0 0 0 0 0
  удалён     1 1 1 1 1 1 1 0
  занят      0 h h h h h h h     ← семь бит метки

Старший бит — флаг занятости в перевёрнутом виде: у занятого слота он снят. Отсюда «занят», «свободен или удалён» и «свободен» — три проверки над одним и тем же битом.

Теперь главное: сравнить искомую метку сразу со всеми восемью слотами можно одной операцией над этим словом. Делается это в четыре шага: размножить метку по всем байтам умножением на 0x0101010101010101; сделать XOR — совпавший байт обнулится; вычесть по единице — нулевой байт займёт разряд, и его старший бит загорится; оставить эти биты маской 0x8080808080808080.

v := uint64(g) ^ (bitsetLSB * uint64(h))
return bitset(((v - bitsetLSB) &^ v) & bitsetMSB)

Семь бит — мало, ложное совпадение бывает примерно раз на 128, поэтому после совпадения ключ сверяется целиком. Зато несовпадение исключает слот наверняка: полное сравнение достаётся одному-двум слотам из восьми, а не всем.

Вторая половина механизма — правило остановки: поиск заканчивается, только найдя группу со свободным слотом. Логика простая: существуй ключ, он лёг бы не дальше первого свободного места. Удалённый слот при этом свободным не считается — иначе удаление одного ключа спрятало бы соседний. Вот зачем понадобилось третье состояние байта: удалённый слот свободен для вставки, но занят для поиска.

И отсюда же: свободные слоты обязаны быть. Поэтому карта растёт, не дожидаясь заполнения — при 7/8. Восьмая часть слотов держится пустой намеренно, как плата за то, чтобы поиску было где остановиться.

Следствие первое (поиск): промах дороже попадания

Попадание останавливается, найдя ключ. Промах обязан дойти до свободного слота, а их мало.

То же правило объясняет и сравнение со старой реализацией — она осталась под флагом GOEXPERIMENT=noswissmap, поэтому обе можно замерить на одной машине:

На попадании новая быстрее вдвое. На промахе — медленнее в 1,4 раза, и диапазоны прогонов не перекрываются. В старой карте промах смотрел один бакет и кончался там же; в Swiss Table он идёт до свободного слота. То, что делает попадание быстрым, делает промах длинным.

Замерена одна форма карты — map[int64]int, 100 000 записей, ключи подряд; цена промаха зависит от заполнения таблицы.

Следствие второе (обход): единственное правило — не зависеть от порядка

Унести в работу надо одну фразу: код не должен зависеть от порядка обхода карты. Всё дальше — исследование реализации: оно объясняет, почему ошибочный код может долго не ломаться, но ошибку от этого ошибкой быть не перестаёт.

Карта из девяти записей за две тысячи обходов даёт ровно девять различных порядков — не 362 880. Все девять — сдвиги одной последовательности, потому что в итераторе стоит

entryIdx := (it.entryIdx + it.entryOffset) & entryMask

а entryOffset берётся один раз на весь обход. Дальше слоты идут подряд — по той же таблице.

Это опаснее настоящей случайности. Код, зависящий от того, что A встретится раньше B, при перемешивании падал бы в половине запусков. При сдвиге — только на тех сдвигах, что разрезают ленту между этими ключами, то есть заметно реже: пройдёт тесты и сломается в проде.

Граница правила — 896 записей: это maxTableCapacity (1024), умноженный на 7/8. Дальше карта не помещается в одну таблицу, у итератора появляется второе смещение по директории таблиц, и порядков становится больше: на 897 записях их уже 1174. Граница не подобрана, а вычислена из двух констант — и подтверждена запуском.

Нужен порядок — сортируйте: slices.Sorted(maps.Keys(m)).

Следствие третье (рост): записи переезжают

При заполнении 7/8 таблица строится заново вдвое большего размера, и записи раскладываются по новым местам. Отсюда два следствия:

Адрес элемента взять нельзя — указатель, взятый до роста, вёл бы в чужую память. Запрет на этапе компиляции. Обходной путь — map[K]*V: переезжает указатель, объект стоит на месте.

Подсказка размера убирает не байты в карте, а промежуточные таблицы:

Готовая карта одинакова — второй столбец. Вдвое меньше становится мусор по дороге: без подсказки карта растёт удвоением, и сумма выброшенных таблиц примерно равна итоговой.

Следствие четвёртое (память): таблица не сжимается

миллион записей:              36,0 МБ,  len = 1 000 000
после delete всех ключей:     36,0 МБ,  len = 0
после clear(m):               36,0 МБ,  len = 0
после m = make(map[int]int):   0,1 МБ

Освобождает только замена карты. Для долгоживущего кеша это разница между «память вернулась» и «не вернулась никогда»: он будет держать её по своему историческому максимуму.

Что устройством не объясняется

Две вещи живут по своим правилам, и знать их надо отдельно.

Контракт ключа. float64 сравним, но NaN != NaN — а карта ищет по ==. Пять вставок одного NaN дают пять записей, поиск не находит ни одной, delete молчит. Убрать их можно только через clear или вместе с картой; отсекать — на входе, math.IsNaN. С nil-картой асимметрия попроще: чтение, len, range, delete работают, паникует только запись. А map[any]T откладывает проверку сравнимости на рантайм: m[[]int{1}] = 1 даёт hash of unhashable type []int, и int(1) с int64(1) там — разные ключи.

Одновременный доступ. Запись из двух горутин — не паника, а fatal error: recover не поможет, стек не разматывается. Так выбрано намеренно — гонка на многословной структуре может испортить память, и упасть громко безопаснее. Лечится мьютексом рядом с картой; sync.Map сделан под два узких случая, и его собственная документация от него отговаривает.

Что сколько стоит

• v, ok := m[k] бесплатно: 18,43 против 17,83.
• Строковый ключ дороже целого в полтора раза — хеш считается по содержимому строки.
• Плотные целые ключи: чтение из карты 15,55 нс, из среза 1,12. Обход ста тысяч записей — 855 702 нс против 37 434. Карта тут не нужна.

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

Часть I. Что гарантирует язык

Всё в этой части — контракт: оно верно в любой версии Go и не зависит от того, как карта устроена внутри.

Карта за пять минут

Шесть операций, и других нет:

scores := map[string]int{
    "alice": 10,
    "bob":   7,
}                                   // создать
 
scores["mike"] = 12                 // записать
score := scores["alice"]            // прочитать
score, ok := scores["john"]         // прочитать с проверкой наличия
delete(scores, "bob")               // удалить
n := len(scores)                    // сколько записей
 
for name, s := range scores {       // обойти
    fmt.Println(name, s)
}

Спецификация определяет карту так:

Слово неупорядоченная здесь не про то, что порядок случайный, а про то, что его нет как понятия: карта не обещает никакого порядка, и опираться не на что.

Про тип ключа спецификация требует одного — сравнимости:

Числа, строки, булевы, указатели, каналы, а также структуры и массивы из сравнимых частей — годятся. Срез, карта и функция — нет, и это ошибка компиляции. Интерфейс годится с оговоркой, к которой мы вернёмся в краевых случаях.

И nil-карта: её нулевое значение — это не пустая карта, а «карты нет».

var m map[string]int   // nil
fmt.Println(len(m))    // 0
fmt.Println(m["a"])    // 0
delete(m, "a")         // ничего не делает
for range m { }        // ноль итераций
m["a"] = 1             // паника: assignment to entry in nil map

Асимметрия тут ровно одна: паникует только запись. Поэтому забытый make доживает до первой вставки — и падает не там, где ошибка.

Ноль вместо ошибки: зачем нужна форма с двумя результатами

Чтение отсутствующего ключа не паникует и не возвращает ошибку — оно даёт нулевое значение типа элемента: 0 у int, пустую строку у string, nil у указателя.

Отсюда вопрос, который и есть вся суть этого раздела:

Как отличить существующий ключ со значением 0 от отсутствующего ключа?

Одноместной формой — никак: она вернёт ноль в обоих случаях. Различает только форма с двумя результатами.

Правило простое: v := m[k] — когда ноль и отсутствие означают одно и то же (счётчики, суммы, накопители). v, ok := m[k] — когда не одно и то же (кеши, конфигурация, «есть ли у пользователя настройка»).

Цену этой формы мы измерим позже, в третьей части: там будет видно, что она практически нулевая, — но сначала должно быть понятно, зачем форма вообще нужна.

Почему изменения видны после передачи в функцию

Это самое частое практическое отличие карты от среза, и оно наблюдаемо из программы:

func add(m map[string]int) { m["x"] = 1 }
 
func main() {
    m := make(map[string]int)
    add(m)
    fmt.Println(m["x"])   // 1
}

А вот append внутри функции снаружи не виден:

func grow(s []int) { s = append(s, 42) }   // снаружи НЕ видно

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

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

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

unsafe.Sizeof(map[int]int{})   // 8 — одно слово
unsafe.Sizeof([]int{})         // 24 — три
unsafe.Sizeof("")              // 16 — два

Что обещает язык, а что делает реализация

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

Контракт языка — верен всегда, на нём можно строить код:

• ключ обязан быть сравнимым;
• отсутствующий ключ даёт нулевое значение, форма с ok сообщает о наличии;
• порядок обхода не определён;
• nil-карта читается, но не пишется;
• одновременный доступ с записью требует синхронизации.

Реализация рантайма — верна для конкретной версии, объясняет поведение, но не гарантирует его:

• Swiss Table, группы по восемь, H1 и H2, управляющее слово;
• зондирование, надгробия, порог заполнения 7/8;
• директория таблиц и предел в 1024 слота на таблицу.

Наблюдения замера — верны для конкретной машины, версии и формы данных:

• 28,62 нс против 17,83 на промахе и попадании;
• девять порядков обхода у карты из девяти записей;
• 36,0 МБ, не освобождённые после clear.

Дальше при каждом числе будет сказано, к какому из трёх уровней оно относится.

Карта и горутины

Эта тема стоит здесь, а не в конце, потому что она нужна раньше всего остального: неверный ответ на неё стоит дороже, чем любое незнание про Swiss Table.

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

Первое, что стоит знать про это правило: в спецификации языка его нет. Раздел про карты определяет тип ключа, поведение nil-карты и рост — про горутины там не сказано ничего. Правило живёт в модели памяти:

Падение рантайма — не механизм синхронизации

Про карту принято говорить «будет fatal error», и из этого делают вывод, что ошибку хотя бы видно. Это неверно, и разница показана прогоном bench/gomap/concurrent.go в двух режимах.

Две горутины пишут — рантайм замечает и роняет процесс:

fatal error: concurrent map writes

goroutine 8 [running]:
internal/runtime/maps.fatal(...)
	/usr/local/go1.24.7/src/runtime/panic.go:1058

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

Горутина читает, пока другая пишет — тот же прогон, без детектора гонок:

  выполнение завершилось
--- код возврата: 0

Ни сообщения, ни ненулевого кода возврата. Тот же самый код под детектором гонок:

==================
WARNING: DATA RACE
Write at 0x00c00009a0f0 by goroutine 7:
  runtime.mapassign_fast64()
Previous read at 0x00c00009a0f0 by goroutine 8:
  runtime.mapaccess1_fast64()
--- код возврата: 141

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

И ещё одно: recover тут не поможет. В прогоне выше стоит defer с recover — он не напечатал ничего, потому что это не паника:

Разница не косметическая: panic разматывает стек, выполняет отложенные вызовы и может быть перехвачена; fatal не делает ничего из этого — рядом с ней в том же файле стоит fatalthrow, «неперехватываемый бросок рантайма».

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

Немедленная остановка здесь — не строгость ради строгости, а замена повреждения памяти на падение, которое видно в логе. Но, как показал прогон выше, случается она не всегда, и рассчитывать на неё нельзя.

Три работающие модели

Первая — карта под мьютексом. Самая частая и почти всегда правильная. sync.RWMutex, если читателей заметно больше писателей; обычный sync.Mutex иначе. Тот же прогон под детектором гонок с мьютексом не находит ничего:

  записей в карте: 160000 — столько и ожидалось
  ни fatal error, ни находки детектора гонок

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

Третья — sync.Map, и только под свои случаи. Его собственная документация от него отговаривает:

Случаев названо два: кеш, который только растёт, и непересекающиеся наборы ключей у разных горутин. Всё остальное — обычная карта с мьютексом.

Проверять это надо детектором гонок

Гонку на карте не найдёт ни компилятор, ни ревью. Находит её -race:

go test -race ./...
go run -race ./cmd/service

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

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

Часть II. Как устроен поиск

Отсюда и до конца второй части — реализация Go 1.24. Всё, что здесь написано, объясняет поведение, но ничего не гарантирует: в другой версии рантайма устройство может быть другим, а контракт из первой части останется прежним.

Зачем карте хеш: отпечаток и полное сравнение

Общая идея у всех хеш-таблиц одна, и она не про Go.

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

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

Отсюда приём, на котором держится Swiss Table: вторая, короткая часть хеша хранится рядом со слотом как отпечаток. Отпечаток не отвечает «этот ключ» — он короткий, совпадения у разных ключей неизбежны. Зато несовпадение исключает слот наверняка, и полное сравнение достаётся немногим кандидатам:

Всё, что дальше, — это конкретные ответы Go на четыре вопроса: как из хеша получить участок, сколько слотов проверять за раз, сколько бит отдать под отпечаток и когда прекращать поиск.

Таблица — это массив групп: откуда берётся номер

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

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

группа 0   [упр. слово: 8 байт][слот 0][слот 1] … [слот 7]
группа 1   [упр. слово: 8 байт][слот 0][слот 1] … [слот 7]
…
группа 7   [упр. слово: 8 байт][слот 0][слот 1] … [слот 7]

Отсюда сразу ответ на вопрос, что значит «H1 назвал группу». Он не нашёл ключ, не выбрал слот и вообще никуда ещё не заглядывал: он дал индекс в этом массиве — число от 0 до N−1. Поиск начнётся уже после, внутри названной группы, по её управляющему слову.

Как из H1 получается индекс

Число групп в таблице — всегда степень двойки, и окупается это решение прямо здесь:

h1    = h >> 7            отбросили 7 бит метки
номер = h1 & (N − 1)      взяли младшие биты того, что осталось

Вторая строка — остаток от деления на число групп, записанный одной операцией «И». Так можно ровно потому, что N — степень двойки: на любом другом числе & (N − 1) остатком быть перестаёт.

Смотреть на это лучше в битах. Вот младшие 16 бит хеша четырёх ключей при восьми группах, разрезанные дважды — справа метка, левее номер:

Средняя тройка бит и есть номер: его не вычисляют, его берут. Правые семь — метка, она уйдёт в управляющий байт того слота, куда ляжет ключ. Левые шесть — остаток H1: в номере они не участвуют, но участвуют в пути, если названная группа окажется занята.

Почему номер берут у H1, а не у всего хеша

Затем, чтобы биты номера и биты метки не пересекались. Цену пересечения можно посчитать. Возьмём номер у младших бит — тех самых, что уже заняты меткой, — и посмотрим, сколько разных меток тогда может оказаться внутри одной группы. Замер на 400 000 ключах при восьми группах:

• номер от H1, как в Go, — в группе встречаются все 128 значений метки;
• номер от младших бит — 16.

Метка теряет три бита, ложные совпадения при поиске становятся примерно в восемь раз чаще, и за каждое платят полным сравнением ключа. Разрез хеша на непересекающиеся части — не аккуратность, а условие, при котором метка вообще что-то отсеивает.

У ключа нет «своей» группы

Без этого всё сказанное выше вводит в заблуждение. Номер — функция от хеша и от текущего размера таблицы. Хеш ключа не меняется никогда, маска меняется при каждом росте:

Удвоение добавляет к маске один бит, и этот бит либо оставляет ключ на месте, либо переносит его ровно на прежнее число групп вперёд: k1 идёт 1 → 9, k7 — 0 → 16. На 100 000 ключей номер меняет примерно половина: 50,07 % при переходе с 4 групп на 8 и 49,97 % с 32 на 64. Отсюда и следствие третье из третьей части: рост перестраивает таблицу целиком, а значит, адрес элемента карты взять нельзя.

Ниже весь путь проигран по шагам — от 64-битного хеша до подсвеченной ячейки массива, — а на второй вкладке видно, как тот же неизменный хеш меняет номер при росте таблицы:

Анатомия группы: восемь слотов, восемь байтов и три состояния

Задача хеш-таблицы всегда одна: по ключу быстро найти его место. Хеш даёт номер, номер даёт позицию — но два разных ключа рано или поздно дадут одну и ту же позицию, и надо решить, что делать дальше.

Старая карта Go решала это цепочками: позиция вела в «бакет» на восемь пар, а если он переполнялся — к следующему бакету по ссылке. Swiss Table решает иначе, и всё её устройство подчинено одной цели: сделать так, чтобы восемь кандидатов проверялись одним сравнением, а не циклом из восьми.

Для этого рядом с восемью слотами лежит короткая сводка о них. Хеш ключа делится на две неравные части:

• старшие 57 бит (H1) выбирают, с какой группы начинать поиск;
• младшие 7 бит (H2) записываются в отдельный байт — метку слота.

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

Термины заданы в самом рантайме:

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

Дальше идёт то, что обычно пропускают, — а без этого механизм не собирается. Байт восьмибитный, метка семибитная. Куда делся восьмой бит?

Он потрачен на то, чтобы один и тот же байт различал три состояния слота. Шаблоны выписаны в исходнике дословно:

  свободен   1 0 0 0 0 0 0 0
  удалён     1 1 1 1 1 1 1 0
  занят      0 h h h h h h h     ← семь бит метки

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

• слот занят — старший бит снят;
• слот свободен или удалён — старший бит выставлен;
• слот свободен — старший бит выставлен, а второй снизу нет (у удалённого он выставлен, у свободного нет).

Так что метка семибитная не потому, что «семи бит достаточно», а потому, что восьмой отдан под состояние. Эта плата и делает возможным всё остальное.

Как восемь сравнений становятся одним

Восемь управляющих байтов лежат в памяти подряд и составляют одно 64-битное число — управляющее слово. Обычно на фразе «сравнивает восемь слотов за одну операцию» объяснение и заканчивается, а понять её нельзя, пока не видно, что происходит с байтами. Происходит вот что.

Шаг первый — размножить метку. Искомые семь бит копируются во все восемь байтов: умножением на 0x0101010101010101. Теперь сравнивать надо не со слотом, а со всем словом сразу.

Шаг второй — XOR. Байт обнуляется ровно там, где два байта совпали. Задача «найти совпавшие слоты» превратилась в задачу «найти нулевые байты», а её уже умеют решать арифметикой.

Шаг третий — поймать нулевой байт заёмом. Из каждого байта вычитается единица: v - 0x0101010101010101. У нулевого байта вычитать не из чего — он занимает разряд и становится 0xFF, то есть его старший бит загорается. У ненулевого байта старший бит так не загорится; а если он был выставлен ещё до вычитания, его гасит часть &^ v.

Шаг четвёртый — оставить по биту на слот: & 0x8080808080808080. Это готовый ответ: восемь бит, по одному на слот.

Одной строкой это и есть тело функции из рантайма:

v := uint64(g) ^ (bitsetLSB * uint64(h))
return bitset(((v - bitsetLSB) &^ v) & bitsetMSB)

Ниже те же четыре шага выполнены на настоящих байтах — переключайте шаги и метку. Все строки битов напечатаны программой bench/gomap/controlword.go, которая выполняет эти формулы и сверяет их с честным перебором восьми байтов:

Три арифметические операции над одним числом вместо цикла из восьми сравнений. На amd64 те же три шага делает одна SIMD-инструкция, а формула выше — переносимый вариант для машин, где такой инструкции нет.

Теперь про то, чем метка не является. Семь бит — это 128 значений, поэтому совпадение метки у разных ключей — дело обычное. Метка отвечает не «этот ключ», а «может быть, этот»: после совпадения ключ сверяется целиком. Зато несовпадение исключает слот наверняка, и в этом вся экономия — полное сравнение достаётся одному-двум слотам из восьми, а не всем восьми.

Сколько именно стоит эта неточность, оценено в самом рантайме:

Есть и вторая, более редкая неточность — уже у самой формулы. Заём при вычитании переходит из младшего байта в старший, поэтому изредка загорается лишний бит. Комментарий в group.go называет конкретный пример: у слова 0x0302 при поиске метки 0x02 формула называет слоты 0 и 1, а честный перебор — только слот 0. На корректности это не сказывается ровно потому, что метка и так не ответ: лишний кандидат стоит одного сравнения ключа. Прогон bench/gomap/controlword.go на двухстах тысячах случайных групп это и подтверждает: настоящих совпадений пропущено ноль, лишних названо 0,03 %.

Правило остановки: свободный слот против удалённого

Группа не всегда та, что выбрал хеш: если в ней места нет, поиск идёт к следующей по пути. Путь этот не случаен и не «просто следующая» — смещение растёт треугольником, p(i) = (i² + i)/2 + H1, и при числе групп, равном степени двойки, такая последовательность обходит каждую группу ровно один раз.

Значит, нужен признак, по которому поиск можно прекратить и сказать «ключа нет». Признак ровно один:

Логика простая: если бы ключ существовал, при вставке он лёг бы не дальше первого свободного места. Дошли до свободного слота — значит, дальше искать незачем.

Тонкость в слове свободный. Удалённый слот свободным не считается, и в исходнике объяснено, почему:

Вот зачем понадобилось третье состояние байта. Удалённый слот свободен для вставки, но занят для поиска: вставка спрашивает «свободен или удалён», поиск — «свободен». Один бит различает первое, два бита различают второе, и обе проверки остаются одной операцией над словом.

И последнее, что нужно для полной картины: свободные слоты обязаны быть. Если заполнить таблицу под завязку, поиску негде остановиться, и промах пришлось бы искать по всей таблице. Поэтому карта растёт, не дожидаясь заполнения: порог — 7/8. Восьмая часть слотов держится пустой намеренно, и это не запас прочности, а цена, заплаченная за правило остановки.

Вставка целиком: что делает H1, а что H2

Откуда берётся номер группы, разобрано выше; сколько бит у метки и почему восьмой отдан под состояние — тоже. Осталось последнее, чего не видно ни в одном из этих разделов по отдельности: почему половин хеша две и зачем такое разделение труда. Разница между H1 и H2 не в виде — оба просто куски одного числа, — а в моменте: первый работает один раз до первого взгляда на таблицу, второй на каждом шаге и потом остаётся в памяти. Момент виден только на целой операции. Возьмём вставку.

Опорное утверждение, из которого следует всё остальное:

Вставка — это поиск, который закончился неудачей. Не «нашли свободное место и положили туда». Сначала карта обязана убедиться, что такого ключа в ней нет, — и только потом занимает место. Иначе одна и та же строка m["a"] = 1, выполненная дважды, дала бы две записи.

Вот весь путь, шаг за шагом.

Шаг 0. Хеш режется по седьмому биту. h1 = h >> 7, h2 = h & 0x7f. Ни один бит не участвует в обеих ролях: совпадение метки ничего не говорит о группе, а номер группы ничего не говорит о метке.

Шаг 1. H1 применяется — один-единственный раз. h1 & (число групп − 1) даёт номер стартовой группы, и он же служит семенем треугольного пути. Всё, больше H1 не участвует ни в одном сравнении. Он не хранится, не проверяется и после этого шага не нужен.

Шаг 2. H2 вступает в дело — и участвует на каждом шаге. В каждой группе на пути её управляющее слово сравнивается с меткой одной операцией. Он же единственный, кто останется в памяти: когда ключ ляжет в слот, в управляющий байт запишется именно H2.

Шаг 3. В группе ищется КЛЮЧ, а не место. Совпадение метки даёт кандидатов, каждый кандидат сверяется полным сравнением ключа. Сошлось — значение переписывается на месте: нового слота не появляется, управляющий байт не меняется, len остаётся прежним. Вставка и обновление — одна и та же операция, разошедшаяся на последнем сравнении.

Шаг 4. Ключа в группе нет — конец ли это пути? Тот самый вопрос из предыдущего раздела. Группа занята целиком — шаг к следующей. Есть свободный слот — путь окончен, ключа в таблице точно нет. А если первым незанятым попался удалённый — место запоминается, но путь продолжается.

Шаг 5. Запись. Если по дороге был запомнен удалённый слот, ключ ложится в него, а не туда, где путь остановился, — и запас роста на него не тратится, он уже был учтён. Если запаса роста нет, таблица сначала пересобирается.

Пятый шаг — самый неочевидный, и он же самый полезный. Из него следует цена:

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

Ниже те же пять сценариев проиграны по шагам. Смотреть стоит на две вещи: в какой момент перестаёт участвовать H1 и в какой слот в итоге уходит запись в последнем сценарии:

Осталась одна деталь, из-за которой эти две половины путают чаще всего. В group.go шаблон занятого слота подписан так:

full: 0 h h h h h h h  // h represents the H1 hash bits

Комментарий называет H1 — а код рядом пишет в управляющий байт H2. Обе строки из одного пакета:

seq := makeProbeSeq(h1(hash), t.groups.lengthMask) // H1 задаёт путь
g.ctrls().set(i, ctrl(h2(hash)))                   // H2 ложится в байт

И над самой функцией h2 в map.go сказано прямо:

Так что в управляющем байте лежит H2; комментарий в group.go разошёлся с кодом. Проверено на go1.24.7 — и это стоит держать в голове, читая исходники: имена H1 и H2 пришли из Abseil, и путаница в комментарии тянется оттуда же.

Теперь устройство описано целиком: таблица → группы по восемь → H1 выбирает стартовую группу → метка H2 в управляющем слове → одна операция вместо восьми сравнений → остановка на свободном слоте → заполнение 7/8. Дальше четыре следствия, и каждое проверяется замером.

Часть III. Следствия устройства

Всё, что дальше, — следствия из второй части, и каждое подпёрто замером. Числа здесь относятся к третьему уровню из разделения выше: конкретная машина, конкретная версия, конкретная форма карты. Устойчиво в них не значение, а направление.

Следствие первое (поиск): промах дороже попадания

Попадание останавливается, найдя ключ, — в среднем на первой же группе. Промах обязан идти до группы со свободным слотом, а их по построению мало: заполнение 7/8.

Замерено на карте из ста тысяч записей:

Это ровно противоположно ожиданию: «промах ведь ничего не нашёл, значит должен быть быстрее». Механизм говорит иначе, и практический вывод из этого прямой: проверка if _, ok := m[k]; !ok дороже чтения существующего ключа, и в горячем цикле, где промахи часты, это заметно.

Та же причина видна в сравнении с прежней реализацией

Go 1.24 позволяет сравнить две реализации честно — старая осталась под флагом сборки:

Случай редкий: компилятор один, машина одна, замер один, отличается ровно один флаг. Прогоны чередовались — на виртуальной машине частота плавает, и два прогона подряд показали бы разницу, которой нет.

Диапазоны по четырём раундам не перекрываются ни в одной строке — это не шум.

Строка про промах объясняется тем же правилом остановки, только с другой стороны. В старой карте промах смотрел один бакет — восемь байт tophash — и кончался там же, если цепочки переполнения не было. В Swiss Table промах обязан идти по пути поиска до свободного слота. То, что делает попадание быстрым, делает промах длинным.

Блог команды Go оговорку про ухудшения делает, но случая не называет:

Вот один такой случай, и краевым он не выглядит: проверка «есть ли ключ» — обычная операция. Оговорка нужна и к самому замеру: это одна форма карты (map[int64]int, сто тысяч записей, ключи подряд), а цена промаха зависит от заполнения таблицы и от того, как разложены ключи.

Следствие второе (обход): единственное правило — не зависеть от порядка

Из всего этого раздела в работу надо унести одну фразу, и вот она:

Код не должен зависеть от порядка обхода карты. Никакого порядка карта не обещает, и наблюдаемый порядок не является контрактом.

Всё остальное ниже — исследование реализации. Оно объясняет, почему ошибочный код может долго не ломаться, и именно этим полезно: сама ошибка от него не становится менее ошибкой.

Что порядок обхода не определён, знают все. Рантайм при этом не просто «не гарантирует» — он рандомизирует намеренно:

Деталь реализации: почему ошибочный код может долго не ломаться

Недоговорено другое — как именно рандомизирован. И вот здесь опять вступает таблица: обход идёт по ней подряд, а случайна только точка старта.

Одна и та же карта из девяти записей, обойдённая две тысячи раз, выдаёт ровно девять различных порядков. Не 362 880. И все девять — сдвиги одной и той же последовательности. Причина в одной строке итератора:

entryIdx := (it.entryIdx + it.entryOffset) & entryMask

entryOffset берётся один раз, при создании итератора. Дальше слоты обходятся подряд. То есть последовательность одна, а случаен только её сдвиг. Сама последовательность у каждого запуска программы своя — карта засевает хеш при старте; постоянно другое: внутри одного запуска порядки отличаются только сдвигом.

Почему это опаснее настоящей случайности. Код, случайно завязавшийся на то, что ключ A встретится раньше ключа B, при настоящем перемешивании падал бы примерно в половине запусков и был бы пойман в первый же день. При сдвиге он падает только на тех сдвигах, что разрезают ленту между этими двумя ключами, — а их тем меньше, чем ближе ключи лежат друг к другу. То есть он проходит тесты, проходит ревью и ломается в проде, когда карта чуть изменится.

Граница правила считается из констант — и это та же таблица

Всё сказанное верно, пока карта помещается в одну таблицу. Предел таблицы — maxTableCapacity = 1024, а заполняется она до 7/8, то есть до 896 записей. Дальше карта делится на несколько таблиц, у итератора появляется второе независимое смещение — по директории таблиц (it.dirOffset), — лент становится несколько, и они тасуются между собой.

Замерено ровно там, где предсказывают константы: на 896 записях различных порядков 896, на 897 — уже 1174.

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

И сразу о границах этого наблюдения. Оно относится к go1.24.7, к этой форме карты и к этому размеру. Это не контракт range: в другой версии рантайма порядков может стать сколько угодно, и код, который «работал», сломается без единого изменения в нём самом. Наблюдение объясняет отсрочку, а не даёт разрешения.

Практический вывод один и старый: нужен порядок — соберите ключи и отсортируйте. slices.Sorted(maps.Keys(m)) делает это одной строкой.

Следствие третье (рост): записи переезжают

Когда заполнение доходит до 7/8, таблица не «дописывается», а строится заново вдвое большего размера, и все записи раскладываются по новым местам. Отсюда два практических следствия, которые обычно узнают порознь.

Адрес элемента взять нельзя.

p := &m["a"]        // cannot take the address of m["a"]
m["a"].field = 2    // cannot assign to struct field

Это не каприз компилятора: указатель, взятый до роста, вёл бы в чужую память. Запрет стоит на этапе компиляции, а не оставлен на «будьте осторожны». Обходной путь — map[K]*V: тогда переезжает указатель, а объект стоит на месте.

И оговорка к разделу про обход выше. Карта крупнее maxTableCapacity = 1024 хранится не одной таблицей, а несколькими — и растёт тогда по одной за раз: переезжают записи только той таблицы, которая переполнилась. Единицей роста таблица остаётся и здесь; меняется лишь то, что таблиц становится больше одной. Ровно поэтому граница правила про порядок обхода проходит по 896 записям.

Подсказка размера убирает не байты в карте, а промежуточные таблицы. Здесь ожидание обманывается в другую сторону. Миллион записей:

Готовая карта одинакова — последний столбец. Экономятся не байты в ней, а выброшенные по дороге таблицы: без подсказки карта растёт удвоением, и сумма всех промежуточных таблиц примерно равна размеру итоговой. Отсюда ровно вдвое.

То есть подсказка помогает нагрузке на сборщик мусора, а не потреблению памяти. Если вам говорили обратное — теперь есть чем проверить.

Следствие четвёртое (память): таблица не сжимается

Рост идёт таблицами — и освобождение тоже. Миллион записей map[int]int, живая куча:

миллион записей:                 36,0 МБ,  len = 1 000 000
после delete всех ключей:        36,0 МБ,  len = 0
после clear(m):                  36,0 МБ,  len = 0
после m = make(map[int]int):      0,1 МБ

Ни delete, ни clear не отдают память: таблица остаётся той же величины, просто пустой. Освобождает только замена самой карты.

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

Лечится ровно одним способом: m = make(map[K]V) вместо clear(m), когда чистка означает «начать с нуля».

На этом четыре следствия из устройства кончились.

Что это значит при выборе

Устройство разобрано; остались практические цены, которые из него прямо не следуют, но нужны, когда выбираешь между вариантами.

Форма с запятой не стоит ничего. v, ok := m[k] — 18,43 нс против 17,83 у v := m[k]; на промахе 28,44 против 28,62, то есть даже в другую сторону. Разница внутри разброса прогонов, и оба числа каждой пары взяты из одного блока замеров — иначе сравнивать их было бы нельзя. Компилятор генерирует один и тот же вызов рантайма, просто во втором случае берёт второе возвращённое значение.

Строковый ключ дороже целого в полтора раза — 28,19 против 18,06. Дело не в карте: хеш строки считается по её содержимому, а хеш int64 — по восьми байтам. Составной ключ [2]int64 при той же ширине стоит 24,95: для целых и строк у рантайма есть отдельные быстрые пути (map_fast64_swiss.go, map_faststr_swiss.go), для остальных типов работает общий код.

Если ключи — плотный диапазон целых, карта не нужна. Одно чтение по ключу, который уже под рукой: 15,55 нс из карты против 1,12 из среза. Эти два числа сопоставляются друг с другом, но не с 18,06 выше: там ключ ещё доставали из среза ключей. Обход ста тысяч записей: 855 702 нс против 37 434. В четырнадцать и в двадцать три раза.

Краевые случаи, которые стоит знать

Всё ниже — редкое, но каждое из этого хотя бы раз стоило кому-то рабочего дня. К основной модели карты эти случаи ничего не добавляют, и читать их стоит последними.

Контракт ключа: сравнимый — не значит рефлексивный

Требование к типу ключа спецификация формулирует через операторы:

Требование выглядит исчерпывающим, но между «операторы определены» и «карта работает как ожидается» есть зазор, и в него проваливаются три случая.

NaN: запись, которую нельзя ни найти, ни удалить

float64 требованию удовлетворяет: операторы для него определены. Но определённость — не рефлексивность, а карта ищет ключ именно по ==:

Что из этого выходит, видно запуском (bench/gomap/nankey.go):

после m[nan] = 1 → len(m) = 1
после m[nan] = 2 → len(m) = 2
после m[nan] = 3 → len(m) = 3
после m[nan] = 4 → len(m) = 4
после m[nan] = 5 → len(m) = 5

m[nan]        → значение 0, найдено false
len до delete: 5
len после двух delete: 5

Пять присваиваний с одной и той же переменной в качестве ключа дали пять записей. Обычный ключ дал бы одну: присваивание перезаписывает найденный ключ, а найти NaN нельзя. Поиск не находит; delete не находит и молчит, потому что удалять ему нечего. Записи при этом на месте: перебор их видит, значения хранит, память они занимают. Недоступны они только по ключу.

Это не побочный эффект, а известное поведение, записанное в рантайме:

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

Проверено: clear(m) убирает их все и возвращает len к нулю. Другого штатного способа нет.

Практический вывод. Написать NaN литералом нельзя — константное 0.0/0.0 компилятор отвергает: invalid operation: division by zero. NaN приходит из данных: деление нулевых переменных (var z float64; z/z), math.Sqrt(-1), разбор строки "NaN". Карта, чьи ключи — числа из внешнего источника, растёт от таких значений без предела, и ни одна запись из неё не переиспользуется. Отсекать надо на входе, проверкой math.IsNaN: снять их потом можно только вместе со всей картой.

И контроль, чтобы не обобщить лишнего: на остальных числах карта странностей не показывает. +0.0 и -0.0 по IEEE 754 равны, и карта честно считает их одним ключом — вторая вставка перезаписала первую, len остался 1. Ломается ровно то место, где == перестаёт быть рефлексивным, и это только NaN.

Интерфейсный ключ откладывает проверку на рантайм

map[any]T — единственное место, где несравнимый ключ не ловится компилятором:

m := map[any]int{}
m[[]int{1}] = 1   // panic: runtime error: hash of unhashable type []int

И там же: int(1) и int64(1) — разные ключи, потому что в сравнение входит тип.

nil-карта: где именно это стреляет

Само правило разобрано в первой части: читается всё, паникует только запись. Здесь важно то, где это проявляется на практике, — а проявляется оно всегда поздно.

Поле структуры. Структура с необъявленной картой внутри создаётся без ошибок, читается нормально и падает на первой записи — иногда сильно позже, чем её создали, и в другом пакете. Лечится конструктором, который делает make для всех карт структуры.

Возврат из функции. func load() map[string]int вполне может вернуть nil в ветке ошибки, и вызывающий, который только читает, ничего не заметит. Ловушка захлопнется у следующего вызывающего, который решит дописать запись.

Присваивание внутри функции. func fill(m map[string]int), сделавшая m = make(...), не изменит ничего для вызывающего: копируется значение карты, и новая карта останется в копии. Карту, которую надо создать, возвращают.

Ключ крупнее 128 байт переезжает из слота

В internal/abi стоит SwissMapMaxKeyBytes = 128. Замерено на десяти тысячах записей:

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

Как воспроизвести числа

Замеры — bench/gomap/layout.go (раскладка) и bench/gomap/cost_test.go (цена). Времени не меряет вовсе bench/gomap/nankey.go: он печатает len, результаты поиска и delete для NaN-ключа. Расширения таблицы ловит bench/gomap/growth.go. Битовую арифметику управляющего слова выполняет по шагам и сверяет с честным перебором bench/gomap/controlword.go — он тоже не меряет времени, а печатает сами биты. Путь вставки целиком проигрывает bench/gomap/insert.go, а разбор хеша на номер группы и метку — bench/gomap/groupindex.go; оба переносят правила из рантайма построчно и проверяют себя, а не просят верить на слово. Это отдельный модуль Go, поэтому запускаются они из него:

go run bench/gomap/layout.go          # работает и из корня
go run bench/gomap/growth.go
go run bench/gomap/controlword.go
go run bench/gomap/insert.go
go run bench/gomap/groupindex.go
./bench/gomap/race.sh                 # три прогона concurrent.go подряд
cd bench/gomap
go test -run '^$' -bench . -benchmem .
./ab.sh                               # старая реализация против новой

layout.go печатает наблюдения без единого замера времени. race.sh запускает bench/gomap/concurrent.go в трёх режимах — с детектором гонок и без — и складывает выводы рядом: два из трёх прогонов обязаны завершиться ненулевым кодом, и это часть результата, а не сбой скрипта. ab.sh чередует сборки с GOEXPERIMENT=noswissmap и без него и печатает строку cpu: для каждого прогона: если она в раундах разная, раунд надо выбросить, а не считать разницу.

Опубликованный прогон: go1.24.7 linux/amd64, Intel Xeon 2,10 ГГц, август 2026 года. Времена зависят от машины; столбцы B/op и allocs/op — нет.