Как растет мапа в Go и что влияет на ее увеличение?
Что проверяют
Знаете ли вы, что мапа в Go это хэш-таблица, которая растёт порциями, и что её реализация сменилась в Go 1.24. Следом спрашивают, почему нельзя взять адрес элемента мапы и что будет при конкурентной записи.
Как отвечать
Стоит описать обе реализации, потому что на собеседованиях всё ещё спрашивают про старую:
- до Go 1.24: массив из
2^Bбакетов по 8 пар ключ-значение плюс цепочки overflow-бакетов. Рост запускается, когда среднее заполнение превышает 6,5 элемента на бакет: число бакетов удваивается. Если overflow-бакетов слишком много при нормальном заполнении, случается рост того же размера, просто для уплотнения. Перенос идёт постепенно: каждая запись и удаление эвакуирует пару старых бакетов, так что пауза на всю таблицу не возникает; - с Go 1.24: Swiss Tables. Слоты сгруппированы по 8 с управляющим словом, по которому проверяются сразу все слоты группы. Мапа состоит из каталога отдельных таблиц до 1024 слотов, максимальное заполнение 7/8. Переполненная таблица делится на две, остальные не трогаются, и рост снова получается частями;
- что влияет: число вставок и подсказка
make(map[K]V, n), которая выделяет память сразу и снимает промежуточные расширения. Удаление мапу не уменьшает: после массовыхdeleteпамять остаётся занятой, помогает только пересоздание мапы; - хэш-функция: её выбирает рантайм, со случайным сидом для каждой мапы, поэтому порядок обхода не гарантирован. Повлиять вы можете только на тип ключа.
Функции cap для мапы нет, len возвращает число элементов, а не ёмкость.
Где спотыкаются
Говорят, что мапа удваивается, «когда заполнена целиком». Порог срабатывает раньше, иначе коллизии съели бы скорость поиска.
Не могут объяснить, почему &m[k] не компилируется: при росте элементы переезжают, и указатель стал бы висячим.
Пишут в мапу из нескольких горутин без мьютекса. Это не гонка с редким багом, а fatal error: concurrent map writes, которую не перехватить через recover. Нужен sync.Mutex или sync.Map, если ключи в основном читаются.