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