Как расположены ключи и значения в бакетах хэш-таблицы в Go?

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

Знаете ли вы устройство map глубже, чем «хэш-таблица за O(1)». Интервьюер ждёт классическую раскладку бакета и объяснение, почему ключи и значения лежат раздельно. Сильный кандидат добавит, что с Go 1.24 реализация сменилась на Swiss Tables.

Как отвечать

Классическая схема, которая работала до Go 1.23 включительно:

• заголовок hmap: число элементов, B (бакетов 2^B), seed хэша, указатели на buckets и oldbuckets;
• бакет bmap хранит до 8 пар. Сначала массив tophash [8]uint8 со старшими 8 битами хэша каждого ключа, потом 8 ключей подряд, потом 8 значений подряд, в конце указатель на overflow-бакет;
• зачем раздельно: раскладка k0 k1 ... k7 v0 v1 ... v7 не требует выравнивания между ключом и значением. Для map[int64]int8 чередование пар съело бы память на padding;
• поиск: младшие B бит хэша выбирают бакет, tophash быстро отсеивает чужие слоты, полное сравнение ключа идёт только при совпадении;
• коллизии: заполненному бакету подвешивается overflow-бакет, получается цепочка бакетов по 8 элементов;
• рост: при среднем заполнении 6.5 элемента на бакет число бакетов удваивается, при избытке overflow делается перестройка того же размера. Эвакуация идёт постепенно, при последующих записях, поэтому одна вставка не платит за перенос всей таблицы;
• крупные ключи и значения больше 128 байт хранятся по указателю.

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

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

Говорят, что коллизии решаются связным списком отдельных пар. Цепочка была, но из бакетов по 8 элементов, а в новой реализации её нет вовсе.

Не могут объяснить, почему нельзя взять &m[k]: при росте элементы переезжают, и указатель стал бы висячим.

Считают map безопасным для горутин. Одновременная запись даёт fatal error: concurrent map writes, которую recover не перехватит. Нужен sync.Mutex или sync.Map.