Что поменялось в map начиная с Go 1.24?

В Go 1.24 встроенная map получила новую реализацию на основе Swiss Table. Идея в том, чтобы проверять группы слотов эффективнее и лучше использовать кеш процессора.

Нужно ли переписывать код с map?

Нет. Пользовательский API остался тем же: make, запись по ключу, чтение, delete и range работают как раньше. Изменение находится внутри runtime.

Что важно сказать на собеседовании про Swiss Table?

Можно сказать, что map хранит элементы группами, рядом лежит control word с частью хеша, lookup сначала ищет кандидатов по этим коротким хешам и только потом сравнивает ключи полностью.

Мапы в Go 1.24: Swiss Table под капотом

Начиная с Go 1.24 встроенная map получила новую реализацию на основе подхода Swiss Table. Для обычного кода это почти незаметно: синтаксис не поменялся, старые программы не нужно переписывать. Но для собеседований и понимания runtime это полезная тема.

Как было раньше на уровне идеи

Если сильно упростить, раньше map можно было представлять как набор бакетов:

m["user123"] = user

Go считал хеш ключа и отправлял его в определенное место хранения:

Bucket 1
  key1
  key2
  key3

Bucket 2
  key4
  key5

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

Что дает Swiss Table

Swiss Table тоже остается хеш-таблицей, но хранение и поиск организованы иначе. Ключевая идея: элементы проверяются группами, а рядом с группой хранится компактная метаинформация.

В реализации Go группа содержит 8 слотов и control word. В control word для каждого слота хранится состояние слота и маленький кусочек хеша ключа.

Условно это можно представить так:

[3A][7F][22][3A][11][FF][00][3A]

Это не весь хеш, а только короткая часть, по которой можно быстро отсеять большинство неподходящих слотов.

Как работает поиск

Когда Go ищет ключ в map, он:

Считает хеш ключа.
Выбирает группу слотов, с которой нужно начать поиск.
Сравнивает короткую часть хеша сразу с метаданными группы.
Получает список кандидатов.
Только для кандидатов сравнивает полноценные ключи.

Если короткая часть хеша не совпала, реальный ключ можно вообще не читать из памяти. Это экономит работу и лучше использует CPU cache.

Важно: коллизии никуда не исчезли. Короткая часть хеша может совпасть у разных ключей, поэтому Go все равно проверяет полный ключ перед тем, как вернуть значение.

Почему это быстрее

Раньше упрощенная логика выглядела так:

Проверить элемент
Проверить элемент
Проверить элемент
Проверить элемент

С Swiss Table идея ближе к этому:

Проверить группу элементов

За счет control word Go может быстро понять, какие слоты вообще похожи на нужный ключ. Меньше лишних сравнений, меньше случайных обращений к памяти, лучше локальность данных.

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

Ничего в обычном API не поменялось:

m := make(map[string]int)
m["go"] = 1

v, ok := m["go"]
delete(m, "go")

Код продолжает работать так же. Все улучшения находятся под капотом runtime.

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

Что сказать на собеседовании

Если коротко, достаточно уверенно объяснить несколько пунктов:

начиная с Go 1.24 встроенная map использует реализацию на основе Swiss Table;
вместо поиска только по старым бакетам активно используются группы слотов;
рядом с группой хранится control word с частью хеша;
по этой части хеша Go быстро находит кандидатов;
полный ключ сравнивается только для кандидатов;
это лучше использует CPU cache и уменьшает лишние обращения к памяти;
обычный код с map менять не нужно.

Оригинальный пост: t.me/go_for_us/41.

Дополнительно: официальная статья Go про Swiss Tables.