Памятка по map в Go #

Тип map в Go — это указатель на хеш-таблицу.

Начиная с Go 1.24, map реализованы с помощью алгоритма Swiss Tables:

• теперь это хеш-таблица с открытой адресацией (в более ранних версиях Go была закрытая адресация)
• алгоритм снижает перерасход памяти хеш-таблицей из-за открытой адресации, сохраняя при этом высокую эффективность
• алгоритм использует SIMD для ускорения квадратичного пробирования (quadratic probing)

Непосредственно map — это лишь указатель, занимающий 8 байт на 64-битных системах и 4 байта на 32-битных.

Примерное расположение данных в памяти:

Случайное зерно в map #

Как и в большинстве современных языков, реализация хеш-таблиц в Go использует случайное зерно:

• это избавляет от уязвимостей, связанных с намеренным заполнением хеш-таблицы ключами с одинаковым хешем
• как известно, хеш-таблица имеет амортизированную сложность O(1), но при коллизиях хешей ключей она может деградировать до O(N)
• со случайным зерном для хеширования вероятность такой деградации стремится к нулю, а создать эту ситуацию преднамеренно злоумышленник не сможет

Пакет maps #

Описанные ниже примеры работы с map по возможности используют пакет maps](https://pkg.go.dev/maps):

• пакет “maps” добавлен в Go 1.21 и содержит generic-функции для обработки объектов типа map
• generic-функции появились в Go 1.18, но пакета “maps” тогда ещё не было
• в более ранних версиях Go приходилось обрабатывать каждый типизированный вариант map вручную

Встроенные функции #

Операции над map #

Создание map #

Значение типа map всегда надо инициализировать до первого использования:

// Литерал map
wordCount := map[string]int{
    "tiger": 2,
    "burning": 1,
    "bright": 1,
}

// Пустой map ёмкостью не менее n
wordCount := make(map[string]int, n)

Копирование map #

Копировать map в новый map можно с помощью maps.Clone:

func TestClone(t *testing.T) {
	wordCount := map[string]int{
		"tiger":   1,
		"burning": 1,
		"bright":  1,
	}

    // Клонируем map и проверяем, что копия не отличается.
	cloned := maps.Clone(wordCount)
	require.Equal(t, wordCount, cloned)

    // Меняем оригинал и проверяем, что копия теперь отличается от оригинала.
	wordCount["tiger"] = 2
	require.NotEqual(t, wordCount, cloned)
}

Добавление, обновление и удаление ключа #

Добавить или обновить пару ключ-значение можно оператором доступа по ключу:

m[key] = value

Удалить пару ключ-значение можно встроенной функцией delete:

delete(m, key)

Ключи map #

В качестве ключа map можно использовать любой тип со встроенным оператором сравнения (точнее, реализующий интерфейс comparable), в том числе:

• целые числа: int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr
• числа с плавающей точкой: float32, float64
• строки: string
• остальные примитивные типа: bool, byte, rune
• массивы фиксированного размера: например, map[[3]int]bool отображает массивы [3]int на bool, что можно использовать для реализации множества троек целых чисел
• структуры, все поля которых реализуют интерфейс comparable
• указатели

Проверка наличия ключа #

Оператор доступа по ключу возвращает до 2 значений:

1. Значение по указанному ключу либо нулевое значение, если ключ отсутствует в map
2. Булево значение — false, если ключ отсутствует в map

value, ok := m[key]
if !ok {
    // ключ отсутствует в словаре, value равен нулевому значению своего типа
}

Перебор по ключам #

Перебрать ключи можно обычным for range:

// Перебор по ключам
for key := range m {
    // key - очередной ключ из map
}

// Перебор по ключам и значениям
for key, value := range m {
    // key - очередной ключ из map
    // value - соответствующее ему значение
}

Следует учесть, что каждый for range по map происходит в случайном порядке — это сделано специально, чтобы при прогоне тестов можно было заметить, что код полагается на порядок перебора ключей и значений в map.

Собрать ключи в новый слайс #

Собрать ключи map в новый слайс можно комбинацией функций maps.Keys и slices.Collect:

func TestListKeys(t *testing.T) {
	wordCount := map[string]int{
		"tiger":   2,
		"burning": 1,
		"bright":  1,
	}

	// Извлекаем ключи из map.
	words := slices.Collect(maps.Keys(wordCount))

	// Сортируем ключи, поскольку они извлечены в случайном порядке
	slices.Sort(words)
	// Проверяем, что получены ожидаемые ключи.
	require.Equal(t, []string{"bright", "burning", "tiger"}, words)
}

Аналогично с помощью maps.Values и slices.Collect можно извлечь значения.

Ссылки #

1. Документация пакета maps
2. Анонс новой реализации map в блоге Go: Faster Go maps with Swiss Tables
3. Статья с деталями новой реализации map (Go 1.24 и выше): Швейцария в картах Go: путешествие по Swiss Tables
4. Статья с деталями старой реализации map (Go 1.23 и ниже): Go Maps Explained: How Key-Value Pairs Are Actually Stored