Как устроены таблицы Map в языке Go?

Таблицы 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: Индекс следующего старого бакета, который нужно перенести при перехешировании.

Операции:

• Добавление/Обновление: Хешируется ключ, находится подходящий бакет. Если бакет полон или есть коллизия, ищется место или создается переполненный бакет. Может инициировать перехеширование.
• Получение: Хешируется ключ, находится бакет. Ищется пара с соответствующим ключом.
• Удаление: Хешируется ключ, находится бакет. Элемент помечается как удаленный. Голоуборочник может освободить память позже.

package main

import "fmt"

func main() {
	m := make(map[string]int) // Создание map
	m["apple"] = 1            // Добавление элемента
	m["banana"] = 2

	fmt.Println(m["apple"]) // Получение значения

	delete(m, "banana") // Удаление элемента

	_, ok := m["banana"] // Проверка наличия ключа
	fmt.Println("Does banana exist?", ok)
}