36 вопросов
Map - хеш-таблица: массив бакетов, каждый бакет содержит до 8 пар ключ-значение и указатель на overflow-бакеты при коллизиях. Хеш ключа определяет бакет; при переполнении таблица растёт (примерно в 2 раза) и данные рехешируются.
var m map[K]V - nil map, запись в неё паникует. m := make(map[K]V) - пустая инициализированная map. m := map[K]V{"a": 1, "b": 2} - литерал. Чтение из nil map возвращает zero value.
Неопределённое поведение (data race). Runtime может обнаружить конкурентную запись и паниковать с "concurrent map writes". Синхронизация обязательна: мьютекс, sync.Map или один писатель.
Нет. Одновременные чтение и запись или две записи - data race. Параллельное чтение без записи безопасно. Для конкурентного доступа используют мьютекс вокруг обычной map или sync.Map для специфичных паттернов (много чтений, редкие записи).
Обернуть доступ в мьютекс: var mu sync.RWMutex; при записи mu.Lock()/Unlock(), при чтении mu.RLock()/RUnlock(). Либо использовать sync.Map для нагрузки с редкими записями и частыми чтениями по разным ключам.
Только типы, для которых определено сравнение (comparable): булев, числа, строки, указатели, каналы, интерфейсы, структуры и массивы из сравниваемых полей. Нельзя: слайсы, map, функции. Ключ не должен содержать указатели на изменяемые данные (сравнение по указателю).
Да, если все поля структуры сравниваемы (comparable). Структура сравнивается по полям поэлементно. Удобно для составных ключей: map[struct{ a, b int }]string. Поля-указатели сравниваются по адресу.
Нет. Map не сравниваемый тип (не comparable). Ключ map должен поддерживать ==. Слайсы и map в ключах запрещены. Для "ключа из нескольких map" используют структуру или строку (сериализованный ключ).
Нет. Порядок итерации непредсказуем и намеренно рандомизирован (с Go 1.0), чтобы не полагаться на него. При каждом проходе порядок может быть разным. Для стабильного порядка нужно собирать ключи в слайс, сортировать и итерировать по слайсу.
Рантайм намеренно рандомизирует порядок обхода, чтобы разработчики не зависели от внутреннего порядка. Это помогает находить баги, основанные на предположении о порядке. Детерминированный порядок достигается явной сортировкой ключей.
Пустая инициализированная map (make(map[K]V)) занимает место под заголовок (указатель на хеш-таблицу и метаданные) - порядка десятков байт. Сама хеш-таблица может быть минимальной. Nil map - нулевое значение (0 байт дополнительно). Точный размер зависит от реализации runtime.
Бакет хранит до 8 пар (tophash + ключ + значение). tophash - верхние биты хеша для быстрой проверки. При коллизиях создаётся цепочка overflow-бакетов. При росте map бакеты эвакуируются в новую таблицу.
Вычисляется хеш ключа (runtime использует внутреннюю хеш-функцию). Младшие биты хеша (в зависимости от размера таблицы) определяют индекс бакета. Внутри бакета tophash используется для быстрой проверки совпадения.
При росте map (переполнение, слишком много элементов) создаётся новая таблица бакетов большего размера. Данные из старых бакетов постепенно переносятся (эвакуируются) в новые. Итерация во время роста может видеть старую или новую таблицу.
Один бакет хранит до 8 записей. При коллизии (одинаковый индекс бакета) новые записи идут в тот же бакет; при переполнении создаётся overflow-бакет и связывается цепочкой. Поиск идёт по бакету и его overflow-цепочке.
Чтение из nil map не паникует: возвращается zero value типа значения. Проверка v, ok := m[key] даёт ok == false. Запись в nil map вызывает панику.
Нельзя взять адрес ячейки map (например, &m[key]), потому что при росте map элементы перемещаются и адреса становятся невалидными. Нужно хранить значение в переменной или использовать map указателей map[K]*V.
v, ok := m[key] - v значение (или zero value), ok - true если ключ был. Либо только v := m[key] - тогда по zero value нельзя отличить "нет ключа" от "значение равно zero". Для проверки наличия лучше идиома с ok.
В среднем O(1). В худшем случае при множестве коллизий - O(n) по количеству элементов в цепочке. На практике хеш-функция и рост таблицы дают почти константное время доступа.
sync.Map - потокобезопасная map из пакета sync. Оптимизирована для случая: много чтений, редкие записи; много записей по разным ключам. Методы: Load, Store, LoadOrStore, Delete, Range. Для обычного "map + mutex" чаще используют мьютекс.
map + mutex проще и предсказуемо по производительности; подходит для большинства случаев. sync.Map - когда два условия: 1) ключи в основном только пишутся один раз и много раз читаются, 2) много горутин обращаются к разным ключам. В остальных случаях мьютекс обычно лучше.
Внутренняя структура (число бакетов) увеличивается при достижении порога нагрузки (load factor). После роста выделяется новая таблица, данные рехешируются и постепенно переносятся. Рост амортизирует стоимость вставки.
set := make(map[T]struct{}). Добавление: set[x] = struct{}{}. Проверка: _, ok := set[x]. struct{} не занимает памяти под значение. Либо map[T]bool - понятнее, но bool занимает байт.
Когда в бакете уже 8 записей и приходит новая с тем же индексом бакета, создаётся дополнительный бакет (overflow), связываемый с основным. Цепочка overflow-бакетов обрабатывается при поиске и вставке. При росте map цепочки перестраиваются.
Да, параллельное чтение из map без записи безопасно. Небезопасны одновременная запись и чтение или две записи. Если есть хотя бы один писатель, доступ должен быть защищён (мьютекс или sync.Map).
Нет. Стандартная реализация использует chained hashing: массив бакетов, каждый бакет - цепочка из до 8 записей плюс overflow-бакеты. Open addressing (один массив, при коллизии искать следующую свободную ячейку) в стандартной map не используется.
Runtime использует внутренние хеш-функции для встроенных типов. Для пользовательских типов хеш вычисляется по полям. Важно: один и тот же ключ должен давать один и тот же хеш в рамках одной программы. Спецификация не фиксирует алгоритм.
Zero value типа значения и (при форме v, ok := m[key]) ok == false. Паники не будет. Запись в nil map вызовет панику.
Проверка наличия ключа: v, ok := m[key]. Если ключ есть - ok true, v - значение. Если нет - ok false, v - zero value. Позволяет отличить "ключа нет" от "значение равно zero" (например, 0 или "").
delete(m, key). Функция ничего не возвращает. Удаление несуществующего ключа не паникует. После удаления len(m) уменьшается. Освобождённая память может быть переиспользована при следующих вставках.
Zero value типа значения: 0 для int, "" для string, nil для указателей и т.д. При форме v, ok := m[key] также ok == false. Без ok нельзя отличить "нет ключа" от "значение = zero".
Load factor - отношение числа элементов к числу бакетов (или к вместимости). При превышении порога map растёт (увеличивается число бакетов), чтобы сохранять среднюю длину цепочек и время доступа. Конкретные пороги - деталь реализации runtime.
maps.Clone(m) возвращает копию map: новая map с теми же парами ключ-значение. Изменения в копии не влияют на оригинал. Клонирование nil map возвращает nil. Полезно для передачи копии без мутирования исходной.
Map - ссылочный тип: в функцию передаётся копия заголовка (указатель на хеш-таблицу и метаданные). Изменения содержимого (добавление, удаление, изменение значений) видны вызывающему. Переназначить саму map в вызывающем из функции нельзя - меняется только локальная копия заголовка.
Встроенная функция clear(m) удаляет все пары ключ-значение из map. Map остаётся инициализированной, len становится 0. Память бакетов может быть переиспользована. Для nil map clear - no-op.
Собрать ключи в слайс, отсортировать, итерировать по слайсу и брать значения из map: keys := make([]K, 0, len(m)); for k := range m { keys = append(keys, k) }; sort.Slice(keys, ...); for _, k := range keys { v := m[k] }. Пакет maps (Go 1.21+) не даёт сортировки - сортировка по ключам вручную.