Мапы

Словарь, ассоциативный массив, хеш-таблица — распространённая в программировании структура данных, которая во многих языках встроена в базовый синтаксис, а в остальных реализована на уровне библиотек.

Ассоциативный массив — это набор пар вида «ключ-значение». Ключу можно присвоить значение Map[key] = value, а потом извлечь это значение value = Map[key] по ключу. Ключи уникальны: одному ключу соответствует только одно значение.

Адрес значения для ключа, как правило, вычисляется хеш-функцией, поэтому такую структуру данных ещё называют хеш-таблицей (hash table, hash map).

Хеш-функция — это любая функция, которая может однозначно перевести любое переданное значение в некоторое множество ограниченных значений. Удобство применения хеш-функций в том, что из неограниченного множества значений можно получить значения из конечного множества. Их можно использовать, например, для адресов массивов.

В различных языках программирования реализация ассоциативного массива различается:

• С++ — библиотечный класс std::map.
• Python — встроенный тип dict().
• PHP — класс Ds\Map.
• Lua — table.

В Go такой тип данных встроен в базовый синтаксис и называется map.

Пример кода:

m := make(map[string]string)    // создаём map — о применении функции make для создания переменных типа map будет рассказано ниже
m["foo"] = "bar"        // заполняем парами «ключ-значение»
m["ping"] = "pong"        
fmt.Println(m)            // печатаем 

Выведет:

map[foo:bar ping:pong] 

Теперь разберём подробнее.

Объявление map §

Декларируется тип map так:

var m map[KeyType]ValueType 

Ключи должны быть одного типа, значения — тоже. При этом тип ключей может не совпадать с типом значений.

В языке Go map — ссылочный тип (reference type), поэтому одного объявления типа map недостаточно.

К примеру, такой код скомпилируется:

var m map[string]string
m["foo"] = "bar" 

Но выдаст ошибку во время исполнения (run-time panic):

panic: assignment to entry in nil map 

Переменные типа map инициализируются с помощью функции make(). Встроенная функция make() — универсальный конструктор объектов ссылочного типа.

type MyMap map[string] string
 
var m1 MyMap
m1 = make(MyMap, 5)
 
// объект готов
m1["foo"] = "bar" 

Тип переменной, которую нужно инициализировать, передаётся функции make() первым параметром. Функция может опционально принимать и другие параметры, характерные для конструируемого типа. В случае map это количество элементов, под которое предварительно требуется выделить память. Нет необходимости указывать точное количество, которое нужно для начального выделения памяти, можно и вообще не передавать этот параметр.

Если впоследствии количество элементов будет расти и перестанет умещаться в выделенной памяти, то выделится дополнительная память. Поскольку выделение памяти и сборка мусора занимают время и требуют дополнительных вычислений, лучше всё же прогнозировать и указывать количество. Дело в том, что при добавлении новых данных в map память выделяется с запасом, а когда этот запас иссякнет, потребуется новое выделение памяти.

Две переменные ссылочного типа могут указывать на один и тот же объект. Для простых типов это выглядит так:

x := 5
y := x
x++
// x станет равен 6
// y останется равен 5 

А для ссылочных типов — так:

MyMap2 := MyMap1
MyMap1["foo"] = "bar"
// в MyMap2 тоже появится пара с ключом foo и значением bar
// если поменяем значение в MyMap2,
MyMap2["foo"] = "bazz"
// то изменится значение и в MyMap1 

Сложный литерал (composite literal) §

Вы можете не декларировать тип переменной, например string, а просто задать значение литерально:

MyString := "Это моя строка" 

Компилятор сам назначит переменной тип, сконструирует объект и присвоит значение.

Такая нотация работает и для сложных типов.

Для map composite literal выглядит так:

MyMap := map[KeyType]ValueType{key1: value1, key2: value2, ... , keyN: valueN,}
// например
MyStringMap := map[string]string{"first": "первый", "second": "второй",} 

В данном случае композитный литерал создаёт map без использования функции make и уже с инициализированными парами «ключ-значение».

Ограничения для типов ключей §

Для ключей должны быть определены операторы == и !=, поэтому ключ не может быть функцией, хеш-таблицей или слайсом.

Если вы попробуете сделать так,

var MyMap map[[]byte]string 

то получите ошибку компиляции:

./prog.go:6:12: invalid map key type []byte 

На тип значений не накладывается никаких ограничений.

Синтаксис map §

Значения для ключей устанавливаются оператором присваивания:

m[key] = value 

А извлекаются индексным выражением:

v, ok = m[k]
v, ok := m[k]
var v, ok = m[k] 

Можно использовать простую форму индексного выражения:

v = m[k] 

В такой форме выражение обязательно возвращает:

• значение, привязанное к ключу k, если такое существует;
• в противном случае — нулевое значение типа.

Если сделать m := make(map[int]int), не заполнить данными и всё же запросить значение ключа 100 v := m[100], запрос будет отработан и вернёт значение 0 (нулевое значение для типа int).

Если присвоить значение ключу 50 m[50] = 0 и запросить его v := m[50], ответ будет таким же — 0.

Это два разных случая:

• ключу не назначено значение;
• ключу назначено нулевое значение.

Чтобы различать их, лучше пользоваться полной формой индексного выражения: v, ok = m[k]. Тогда переменная ok примет значение true, если ключ найден, и false в противном случае.

Сокращённые формы арифметических операторов здесь будут работать:

m[k] += 2
// или
m[k]++ 

Получить адрес элемента map не получится. Это связано с тем, что при добавлении новых элементов в мапу может произойти перемещение в памяти уже существующих элементов. Указатели на эти элементы станут недействительными. Поэтому такая операция запрещена.

Такой код

addr := &m[k] 

вызовет ошибку компиляции:

cannot take the address of m[k] 

Встроенные функции для типа map §

В Go для операций с map предусмотрены встроенные функции.

Функция len(m) возвращает количество элементов в таблице. Её можно применять и к неинициализированной таблице, для которой ещё не использовали конструктор make(), — тогда len(m) возвращает 0.

var m1 map[int]int
m2 := map[int]int{1: 10, 2: 20, 3: 30}
fmt.Println(len(m1), len(m2)) 

Получим:

0 3 

Функция len() не даёт гарантии, что map инициализирована. Чтобы удостовериться, избежав run-time panic, можно сравнить таблицу с nil — нулевым значением для типа map. И nil — единственное значение, с которым можно сравнивать map. Сравнивать map друг с другом нельзя, так как оператор == не определён.

var m map[string]string
if m != nil {            // если не проверить это условие,
    m["foo"] = "bar"    // то здесь можно получить panic
} 

Функция delete(m, k) удаляет из таблицы m элемент с ключом k. Тип удаляемого ключа должен совпадать с типом ключей мапы. Если таблица не инициализирована или такого ключа в ней нет, runtime panic не будет, просто no-op.

m := map[int]string{1: "first"}
v, ok := m[1]
fmt.Println(v, ok)
delete(m, 2)  // ошибки не будет
delete(m, 1)
v, ok = m[1]
fmt.Println(v, ok) 

Выведет:

first true
false 

Использование в циклах range §

map можно использовать в цикле for c итератором range.

Для этого предусмотрен удобный синтаксис:

m := make(map[string]string)
m["foo"] = "bar"
m["bazz"] = "yup"
for k, v := range m {
    // k будет перебирать ключи,
    // v — соответствующие этим ключам значения
    fmt.Printf("Ключ %v, имеет значение %v \n", k, v)
} 

Если запустить цикл на неинициализированной map, будет сделано 0 итераций.

Если нужно изменить значения в цикле, то стоит помнить, что так не сработает:

for k, v := range m {
    v = "here key "+k
} 

В цикле переменной v итеративно присваиваются значения из таблицы. Любое присваивание в Go имеет семантику pass-by-value, то есть значения из таблицы копируются в переменную v, а сама таблица не меняется.

Если нужна модификация таблицы, лучше сделать так:

for k, v := range m {
    m[k] = "here key "+k    // применяем к таблице индексное выражение
                // и модифицируем её прямым доступом к ячейкам  
} 

Note

Go позволяет добавлять и удалять значения в map прямо внутри цикла, в процессе итерации. Удалённые ключи гарантированно не попадут в последующие итерации. С добавленными ключами таких гарантий нет. Новый ключ может попасть в последующие итерации, а может и не попасть.

Такой вариант возможен, но считается плохой практикой:

for k, _ := range m { // обратите внимание на подчёркивание _
    delete(m, k)
} 

Переменная _ используется в Go, когда оператор присваивания устанавливает несколько значений, но не все из них нужны разработчику. Однако предоставлять переменную для значения придётся, иначе будет синтаксическая ошибка, которую не пропустит компилятор. Разработчик предоставляет переменную _, чем сообщает компилятору, что значение ему не потребуется и его можно не вычислять.

В случае for range map допустимо писать for k := range m, то есть предоставить только одну переменную итерации. Можно и вовсе не предоставлять ни одной: for range m.

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

Конкурентный (concurrent) доступ §

Go — многопоточный язык. Многопоточность заложена в базовый синтаксис. При запуске горутин помните, что ни один встроенный тип в Go (кроме chan) не защищён для доступа из нескольких потоков, и map не исключение.

Note

Для безопасного использования map из нескольких потоков должны применяться механизмы защиты, иначе возможно повреждение данных или состояние гонки. Недавно в стандартной библиотеке появился потокобезопасный вариант ассоциативного массива, эквивалент map, которым можно пользоваться в многопоточной среде. Механизмы защиты в этот тип уже встроены.

Пример кода §

Посчитаем и выведем количество вхождений для всех символов, которые встречаются в указанном предложении.

// предложение
sentence := "Πολύ λίγα πράγματα συμβαίνουν στο σωστό χρόνο, και τα υπόλοιπα δεν συμβαίνουν καθόλου"
// инициализируем map
// ключами будут знаки, а значениями — количество вхождений
frequency := make(map[rune]int)
// пройдёмся по знакам в предложении
for _, v := range sentence {
    frequency[v]++    // встреченному знаку увеличиваем частоту
}
// печатаем
for k, v := range frequency {
    fmt.Printf("Знак %c встречается %d раз \n", k, v)
} 

---

📂 Go | Последнее изменение: 18.08.2024 09:58