Как устроена структура бакетов в мапе Go
Что проверяют
Знаете ли вы устройство мапы глубже, чем «хеш-таблица за O(1)», и следите ли за рантаймом: с Go 1.24 реализация сменилась. Следом спрашивают, почему нельзя взять адрес элемента мапы и почему порядок обхода случайный.
Как отвечать
Честный ответ в 2026 году состоит из двух частей.
Классическая реализация, до Go 1.23 включительно, о ней спрашивают чаще всего:
hmap: заголовок с числом элементов, сидом хеша и полемB, бакетов ровно2^B;- бакет
bmap: восемь слотов. Сначала массивtophashиз старших 8 бит хеша каждого ключа для быстрого отсева, затем восемь ключей подряд и восемь значений подряд, так меньше потерь на выравнивание; - выбор бакета: младшие
Bбит хеша. Когда бакет полон, к нему цепляется бакет переполнения; - рост: при среднем заполнении больше 6,5 элемента на бакет число бакетов удваивается, а при избытке бакетов переполнения идёт перестройка того же размера. Эвакуация инкрементальная: элементы переносятся понемногу при записях, без паузы на всю мапу.
С Go 1.24 мапа построена на Swiss Tables: слоты сгруппированы по восемь, у группы контрольное слово с 7 битами хеша на слот, и поиск сравнивает все восемь меток разом. Коллизии решаются открытой адресацией, предельная заполненность 7/8. Большая мапа делится на таблицы до 1024 слотов с каталогом над ними, и рост затрагивает одну таблицу, а не всю мапу.
Общее для обеих: сид хеша у каждой мапы свой, порядок обхода не гарантирован, память после удаления не возвращается, а make(map[K]V, n) заранее выделяет место и избавляет от перестроек.
Где спотыкаются
Говорят, что коллизии хранятся связным списком или деревом, как в Java HashMap. В Go такого нет ни в старой, ни в новой реализации.
Не могут объяснить, почему &m[k] не компилируется. Элементы переезжают при росте, и указатель на слот стал бы висячим.
Забывают про конкурентность: запись из нескольких горутин без sync.Mutex заканчивается fatal error: concurrent map writes, которую не перехватить через recover. Рантайм ловит это не всегда, поэтому тесты гоняют с -race.