Карта в 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 выглядит как готовый ответ, но он оптимизирован под другой профиль — ключ пишется один раз и потом много раз читается, — и на равномерной смеси проигрывает карте под мьютексом: в bench/gomap/syncmap.go при половине записей 105,66 нс на операцию против 43,97 нс, в 2,4 раза медленнее (go1.24.7, два ядра, bench/gomap/runs/syncmap.txt).

Механизм 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) — не удаляет ничего

Записи, которые нельзя ни прочитать, ни удалить по ключу. Избавиться от них можно только целиком: clear(m) (Go 1.21+) или выбросить карту. На собеседовании это отличный ответ на вопрос «а бывает, что ключ есть, а достать нельзя».

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

Всё, что было выше, — контракт: он не зависит от версии 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 вместимости плюс один», а таблица при этом удваивается — пока не дорастёт до 1024 слотов. Что происходит дальше, разобрано ниже, в «Асимптотике».

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

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

Что это стоит

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

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

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

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

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

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

Вставка, попавшая на расширение, дороже остальных — но перекладывает она не всю карту. В go1.24 карта — это каталог (directory) и под ним отдельные Swiss-таблицы; таблицу выбирают старшие биты хеша. Таблица меньше 1024 слотов растёт удвоением: её записи переезжают в новую, вдвое большую. Таблица, дошедшая до 1024 слотов, не удваивается, а делится на две, и переносятся только её записи — не больше 896, то есть 7/8 от 1024. Если для раскола не хватает разрядов каталога, удваивается сам каталог — массив указателей на таблицы, а не записей. Комментарий в internal/runtime/maps/map.go говорит об этом прямо: таблица растёт целиком, но каждый такой рост — лишь небольшая часть карты.

Это видно и снаружи — по байтам, которые выделяет одна вставка (bench/gomap/growth.go big, go1.24.7, map[int]int до 1 048 576 записей):

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

Поэтому «худший случай вставки — O(n), потому что перекладывается всё» для go1.24 неверно, если n — число записей карты. Точнее так: перенос записей при расширении ограничен одной таблицей, не больше 1024 слотов; иногда к нему добавляется рост каталога, пропорциональный числу таблиц, — он растёт с картой, но несёт указатели, по одному на таблицу, а не записи. Вся работа на построение остаётся линейной, O(1) на вставку в среднем: тот же прогон выделил 13855 КБ на диапазоне от 65536 до 262144 записей и 55419 КБ на вчетверо большем. Всё это — устройство go1.24, а не обещание языка: спецификация не говорит ни о схеме роста, ни о сложности.

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

И худший случай поиска тоже 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; таблица удваивается до 1024 слотов, дальше делится надвое» весит больше, чем «когда заполняется». Если помните — добавьте, что расширение случается на 9, 15, 29, 57 записях: это видно замером и звучит как «я это проверял».

Асимптотику разделяйте. «В среднем O(1). Вставка, попавшая на расширение, дороже, но в go1.24 переносит записи одной таблицы, не больше 1024 слотов: маленькая таблица удваивается, дошедшая до предела делится надвое, а каталог над таблицами иногда удваивается сам — это указатели, а не записи. Худший случай поиска — O(n), но от подобранных ключей защищает случайное сеяние хеша». И оговорка: это устройство go1.24, спецификация сложность роста не обещает.

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

Про конкурентный доступ обязательно скажите «не паника». 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

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