Карта в Go: группа из восьми, порог 7/8 и промах, который дороже попадания

Что здесь на самом деле спрашивают

Лестница почти всегда одна и та же, и первые два вопроса решают больше, чем кажется:

1. «Что вернёт m[k], если ключа нет?» — разминка, на которой отсеиваются те, кто ждёт ошибки.
2. «А как отличить отсутствующий ключ от нулевого значения?» — здесь начинается содержание.
3. «Что будет, если писать из двух горутин?» — проверяют, знаете ли вы, что это не паника.
4. «Как устроен поиск?» — назовёте ли вы хеш и группу слотов или ограничитесь словом «хеш-таблица».
5. «Что происходит при расширении?» — знаете ли вы про порог и назовёте ли его числом.
6. «Какая сложность?» — отличаете ли среднее от худшего.
7. «Почему порядок обхода случайный?» — вопрос-ловушка: он не случайный.

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

База: что карта делает

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

Спросить карту можно про любой ключ — в том числе про тот, которого в ней нет. Ошибки при этом не будет: вместо неё вернётся нулевое значение того типа, который карта хранит, — ноль для чисел, пустая строка для строк. Ничего не сломается, и в этом главная тонкость входа: ноль вернулся потому, что ключа нет, или потому, что по ключу и правда лежит ноль? По одному значению эти два случая неразличимы. Поэтому у чтения есть вторая форма — та, что отдаёт не только значение, но и ответ на вопрос «а был ли ключ». Всё, что дальше в уроке называется comma-ok, — это она.

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

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

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

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

Механизм 1: что карта обещает

Теперь то же самое, но проверенное прогоном и сказанное словами спецификации. Начнём с того, что не изменится ни от версии Go, ни от машины, — с контракта. Всё остальное в уроке объясняет, как реализация его выполняет, но сам контракт от реализации не зависит.

Отсутствующий ключ — не ошибка, а нулевое значение. Прогон bench/gomap/contract.go:

scores["alice"]              10
scores["carol"]              0
scores["dave"]               0

Три строки, два разных случая — и по значению они неразличимы. У carol ключ есть, и её счёт действительно ноль; у dave ключа нет вовсе. Это первая ловушка темы: if m[k] == 0 не отвечает на вопрос «есть ли ключ».

Отличить помогает вторая переменная — форма, которую называют comma-ok:

v, ok := scores["carol"]     0 true
v, ok := scores["dave"]      0 false

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

nil-карта читается, обходится и даже удаляется — но не пишется. Тот же прогон:

nilMap == nil                true
len(nilMap)                  0
nilMap["anything"]           0
_, ok := nilMap["anything"]  false
for range nilMap             0
delete(nilMap, ...)          ok
nilMap["anything"] = 1       panic: assignment to entry in nil map

Шесть операций работают, седьмая роняет. Спецификация формулирует это одной фразой: A nil map is equivalent to an empty map except that no elements may be added (nil-карта эквивалентна пустой карте, за исключением того, что в неё нельзя добавлять элементы).

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

Ключ обязан быть сравнимым, и это проверяет компилятор. bench/gomap/contract.sh пробует собрать карту с ключом-срезом:

badkey.go:4:17: invalid map key type []int
--- go build exit code: 1

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

Исключение одно и оно опасное: у map[any]T тип ключа формально сравним, и проверка уезжает во время выполнения. Положите туда срез — получите панику в той строке, где положили.

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

Механизм 2: карта и горутины

Этот вопрос стоит вторым, а не последним, потому что он про безопасность контракта, а не про тонкость: карта в Go не защищена ничем, и цена ошибки здесь выше, чем у всего остального в уроке.

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

fatal error: concurrent map writes

Сообщений три, и по ним видно, что столкнулось: concurrent map writes, concurrent map read and map write, concurrent map iteration and map write.

И recover тут не поможет. Разница не косметическая: panic разматывает стек, выполняет отложенные вызовы и может быть перехвачена; fatal не делает ничего из этого — процесс останавливается на месте. В комментарии к самой fatal гонка на картах названа образцовым случаем: fatal is equivalent to throw, but is used when user code is expected to be at fault for the failure, such as racing map writes (fatal эквивалентен throw, но используется, когда в сбое предполагается вина пользовательского кода — например, при состязающихся записях в карту).

Почему выбрана остановка, а не «как получится». Модель памяти Go объясняет это прямо: races on multiword data structures can lead to inconsistent values not corresponding to a single write (гонки на многословных структурах данных могут приводить к несогласованным значениям, не соответствующим ни одной отдельной записи) — и дальше про то, что такие гонки ведут к произвольному повреждению памяти. Упасть громко лучше, чем тихо испортить чужие данные.

Отдельно про детектор гонок. Проверка внутри карты — не он: она работает всегда, в обычной сборке, без -race. Но она не гарантия: две горутины могут разминуться, и тогда программа просто испортит таблицу. go test -race находит такие гонки надёжнее, потому что следит за обращениями, а не за флагом.

Чем лечится: обычным мьютексом рядом с картой. sync.Map выглядит как готовый ответ, но он оптимизирован под другой профиль — много чтений и мало записей, — и на равномерной смеси проигрывает карте под мьютексом.

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

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

Карта, переданная в функцию, меняется у вызывающей стороны:

func fill(m map[string]int) { m["a"] = 1 }   // видно снаружи

Объяснение простое: map[K]V — это указатель на структуру рантайма, а не сама структура. Копируется указатель, а таблица за ним общая.

Это отличает карту от среза интереснее, чем кажется. У среза функция может изменить элементы, но не может его удлинить — потому что длина лежит в копии заголовка. У карты «удлинить» тоже получается, потому что размер лежит за указателем, а не рядом с ним.

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

Адрес элемента взять нельзя. &m[k] не компилируется, и причина — в расширении, которое урок разберёт в «Глубже»: записи при нём физически переезжают, и адрес перестал бы быть действительным. У среза адрес взять можно, потому что там переезд виден снаружи через append, а у карты он происходит молча.

Механизм 4: краевые случаи, которые стоят падения

Сравнимость ключа проверяет компилятор — кроме одного случая. Спецификация требует: The comparison operators == and != must be fully defined for operands of the key type; thus the key type must not be a function, map, or slice (Операторы сравнения == и != должны быть полностью определены для операндов типа ключа; поэтому тип ключа не может быть функцией, картой или срезом). Обычно это ловится на сборке — «Механизм 1» показывает текст ошибки. Но у map[any]T тип ключа формально сравним, и проверка уезжает во время выполнения: положите туда срез — получите панику в той строке, где положили.

И самый тонкий случай: NaN. float64 — тип сравнимый, но NaN != NaN. Карта ищет ключ сравнением, поэтому запись по NaN в карту попадает, а найтись не может:

nan := math.NaN()
m := map[float64]int{}
m[nan] = 1
m[nan] = 2
// len(m) == 2 — ДВЕ записи по одному «ключу»
// m[nan] == 0 — ни одну не найти
// delete(m, nan) — не удаляет ничего

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

Глубже: как карта устроена внутри

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

Зачем карте хеш

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

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

Отсюда сразу три следствия, которые дальше объясняют всё остальное:

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

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

Группа из восьми и правило остановки

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

Группа — это восемь слотов и восемь управляющих байтов, лежащих рядом. Поиск сравнивает искомую метку сразу со всеми восемью — одной инструкцией, а не циклом. Совпадение метки ещё не значит совпадения ключа (семи бит мало), но несовпадение значит его отсутствие наверняка, и полное сравнение ключа делается только для совпавших меток.

Главное здесь — правило остановки, и именно оно даёт неожиданное следствие. Поиск идёт по группам, пока не найдёт ключ или не встретит группу со свободным слотом. Свободный слот означает «дальше этот ключ положить было бы некуда, значит его нет».

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

Почти все ожидают обратного: «промах же ничего не нашёл, значит быстрее». Механизм говорит иначе, и ниже урок это проверит замером.

Как карта расширяется

Вопрос «когда карта расширяется» почти всегда получает ответ «когда заполнится». Это неверно, и число известно: при заполнении 7/8.

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

9  15  29  57  113  225  449

Проверьте сами: 7/8 от 16 — это 14, и расширение случилось на пятнадцатой записи. 7/8 от 32 — это 28, расширение на двадцать девятой. И так далее. Правило: расширение на «7/8 вместимости плюс один», а таблица при этом удваивается.

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

Вот связка, которую полезно произнести на собеседовании целиком: группы по восемь дают быстрое сравнение; остановка на свободном слоте делает промах дороже попадания; и ради этой остановки карта держит 7/8 заполнения, то есть сознательно тратит восьмую часть памяти. Три факта, и они не независимы.

Что это стоит

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

Предсказание про правило остановки подтверждается. Замер на карте из ста тысяч записей:

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

Асимптотика и что прячется за средним

Правильный ответ — O(1) в среднем. Но, как и у среза, за ним стоят два разных утверждения, и второе обычно теряется.

Среднее O(1) держится на том, что хеш распределяет ключи по группам равномерно, и длина пути поиска не зависит от размера карты. Именно равномерность, а не «магия хеш-таблицы»: при плохом хеше всё вырождается.

Худший случай одной операции — O(n). Вставка, попавшая на расширение, перекладывает всю таблицу: новая таблица вдвое больше, и каждая запись считается заново. На графике задержек это выброс, и он тем крупнее, чем больше карта. Для сервиса с бюджетом на p99 карта, которая растёт под нагрузкой, — известный источник хвостов.

И худший случай поиска тоже O(n) — если все ключи попали в одну группу. В Go до этого не доводят: хеш карты засеян случайным числом при старте процесса, поэтому подобрать ключи, которые все столкнутся, снаружи нельзя. Это защита от алгоритмической DoS-атаки: во времена, когда сеяния не было, атака «послать сто тысяч ключей с одинаковым хешем» роняла веб-серверы на других языках.

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

delete, clear и подсказка размера

Три близких вопроса, и на все три интуиция отвечает неверно.

delete не возвращает память. Измерено на карте из двухсот тысяч записей:

Карта в Go не уменьшается. Таблица остаётся той, до которой доросла; delete только помечает слот, а clear обнуляет записи, не трогая размер. Единственный способ отдать память — создать новую карту и бросить старую.

Практическое следствие названо в задачах на проектирование: кеш в карте, который однажды вырос до пика нагрузки, останется такого размера навсегда. Лечится это не delete, а пересозданием карты по расписанию.

Подсказка размера уменьшает не карту, а мусор. Тот же замер, две карты на двести тысяч записей:

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

Порядок обхода: контракт и наблюдение

В «Механизме 1» сказано, что порядок обхода не гарантирован, — это контракт. Здесь про то, как негарантированность реализована, и разница между этими двумя утверждениями стоит багов в проде.

«Порядок обхода карты случаен» знают все. Утверждение недоговорено, и недоговорено в опасную сторону.

Обход начинается со случайной точки, а дальше идёт по таблице подряд. То есть различных порядков ровно столько, сколько записей — это сдвиги одной и той же последовательности, а не её перестановки. Для карты из девяти записей порядков девять, а не 362 880.

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

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

Как отвечать на собеседовании

Короткий ответ: карта — это пары «ключ — значение» с доступом по ключу, и отсутствующий ключ даёт не ошибку, а нулевое значение; отличить его от настоящего нуля позволяет форма v, ok := m[k]. Добавьте вторым предложением то, что спрашивают сразу следом: в переменной лежит указатель на структуру рантайма — поэтому карта, переданная в функцию, меняется у вызывающей стороны, и поэтому nil-карту можно читать, но не писать.

Этого достаточно, чтобы ответить верно. Дальше — то, что добавляют, если собеседник копает.

Если интервьюер копает глубже

Про устройство говорите связкой, а не перечнем — и с оговоркой, что это устройство нынешней реализации, а не правило языка. Группы по восемь → сравнение метки сразу со всеми → остановка на свободном слоте → отсюда промах дороже попадания → и ради этой остановки заполнение держится на 7/8. Связка показывает понимание; перечень фактов — заучивание.

Число называйте. «В go1.24 расширяется при 7/8, таблица удваивается» весит больше, чем «когда заполняется». Если помните — добавьте, что расширение случается на 9, 15, 29, 57 записях: это видно замером и звучит как «я это проверял».

Асимптотику разделяйте. «В среднем O(1); вставка, попавшая на расширение, O(n), потому что перекладывается вся таблица; худший случай поиска тоже O(n), но от подобранных ключей защищает случайное сеяние хеша».

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

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

Дальше спросят

Частые заблуждения

Практика

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

nan := math.NaN()
m := map[float64]int{}
m[nan] = 1
m[nan] = 2
fmt.Println(len(m))
fmt.Println(m[nan])
delete(m, nan)
fmt.Println(len(m))

2
0
2

1
2
0

2
2
1

1
0
1

Проверка знаний