Таблицы Map в Go — это неупорядоченные коллекции пар ключ-значение, реализованные на основе хеш-таблиц.
Основные компоненты и принципы работы:
- Хеширование ключей: Ключ хешируется для получения хеш-значения, которое определяет, в каком "ведре" (bucket) будет храниться пара ключ-значение.
- Ведра (Buckets): Массив указателей на бакеты (
[]bmap). Каждый бакет (bmap) содержит фиксированное количество пар ключ-значение (обычно 8). Бакеты могут быть связаны в списки для обработки коллизий.
- Коллизии: Если несколько ключей хешируются в одно и то же ведро, они хранятся в виде списка внутри этого ведра. Каждое ведро имеет поле
tophash для быстрого поиска внутри бакета, содержащее верхние биты хеша каждого ключа.
- Перехеширование (Resizing): При достижении определенной заполненности (load factor) таблица перехешируется. Создается новый, более крупный массив бакетов, и элементы из старых бакетов постепенно перемещаются в новые. Этот процесс может происходить при операциях чтения или записи, чтобы избежать блокировки таблицы на время перехеширования.
- Структура
hmap: Внутреннее представление map в Go представлено структурой hmap, которая включает:
count: Количество элементов в map.flags: Флаги состояния (например, идет ли перехеширование).B: Количество бит, используемых для индексации бакетов (1 << B - количество бакетов).noverflow: Ориентировочное количество бакетов-переполнений.hash0: Начальное значение для хеширования.buckets: Указатель на массив бакетов.oldbuckets: Указатель на старый массив бакетов при перехешировании.nevacuate: Индекс следующего старого бакета, который нужно перенести при перехешировании.
Операции:
- Добавление/Обновление: Хешируется ключ, находится подходящий бакет. Если бакет полон или есть коллизия, ищется место или создается переполненный бакет. Может инициировать перехеширование.
- Получение: Хешируется ключ, находится бакет. Ищется пара с соответствующим ключом.
- Удаление: Хешируется ключ, находится бакет. Элемент помечается как удаленный. Голоуборочник может освободить память позже.
go