Map в Go реализован как хеш-таблица.
Основные компоненты структуры map:
- Хеш-функция: Отображает ключи в хеш-значения (целые числа).
- Массив бакетов (buckets): Набор списков или массивов, где хранятся пары ключ-значение. Индекс бакета определяется хеш-значением ключа.
- Обработка коллизий: При совпадении хешей для разных ключей (коллизия) элементы с этими ключами хранятся в одном бакете, обычно в виде связанного списка или переполнения в соседний бакет.
- Нагрузочный фактор (load factor): Соотношение количества элементов к количеству бакетов. При превышении определенного порога происходит рехеширование – создание нового, большего массива бакетов и перемещение всех элементов из старых бакетов в новые.
Структура map в Go представлена типом hmap:
go
Операции:
- Вставка/Обновление: Вычисляется хеш ключа, определяется бакет. Если ключ уже существует, значение обновляется. Иначе, пара ключ-значение добавляется в бакет. При переполнении бакета или превышении Load Factor может произойти рехеширование.
- Поиск: Вычисляется хеш ключа, определяется бакет. Перебираются элементы в бакете по топ-хешу, затем полное сравнение ключей. Возвращается значение и флаг наличия.
- Удаление: Вычисляется хеш ключа, определяется бакет. Элемент отмечается как удаленный (но не немедленно удаляется из памяти). Удаление происходит при последующих операциях или при рехешировании.
Мапа в Go является несинхронизированной и не может безопасно использоваться несколькими горутинами одновременно без внешней синхронизации.