Для чего нужны два экстра бита внутри бакета map Go и как они используются

Что проверяют

Внутреннее устройство map на уровне runtime. Формулировка неточная: поля «два экстра бита» в исходниках нет, и интервьюер обычно ждёт рассказа о служебной информации в бакете и о бите хеша, по которому бакет делится при росте. Следом спрашивают про эвакуацию и что поменялось в Go 1.24.

Как отвечать

Опишите классическую реализацию (до Go 1.24, runtime/map.go):

• выбор бакета: хеш считается с сидом, случайным для каждой map, младшие B бит дают номер бакета из 2^B;
• tophash: в бакете 8 ячеек и массив tophash [8]uint8 со старшими 8 битами хеша каждого ключа. Поиск сначала сравнивает этот байт и только при совпадении сравнивает сами ключи;
• служебные значения: значения tophash меньше minTopHash (5) зарезервированы под состояние ячейки: emptyOne, emptyRest (пусто здесь и дальше, поиск можно прекратить), evacuatedX, evacuatedY, evacuatedEmpty. Если настоящий старший байт попал в этот диапазон, к нему прибавляют minTopHash;
• рост и половины X/Y: когда в среднем больше 6.5 элемента на бакет, число бакетов удваивается и B растёт на единицу. Значимым становится ещё один бит хеша: 0 оставляет ключ в бакете с тем же номером (X), 1 переносит его в бакет со сдвигом на старый размер (Y). Эвакуация идёт постепенно, при записях и удалениях;
• переполнение: если 8 ячеек заняты, к бакету цепляется overflow-бакет через указатель в конце.

С Go 1.24 map построена на Swiss Tables: группы по 8 слотов и управляющее слово с байтом на слот. Старший бит байта означает «пусто или удалено», остальные 7 бит хранят часть хеша, и сравнение идёт сразу по всей группе.

Где спотыкаются

Придумывают «бит занятости и бит коллизии» и цепочки по соседним бакетам. В Go коллизии живут в том же бакете и его overflow-цепочке, открытой адресации по соседям в старой реализации нет.

Путают роли битов: младшие выбирают бакет, старшие идут в tophash.

Не знают, что рост инкрементальный и бывает рост без удвоения при большом числе overflow-бакетов, а после удаления ключей классическая map память не отдаёт.