Что такое мапа (map)??

Мапа в Go - это тип данных, который предназначен для хранения пар “ключ-значение”. Это структура данных, также известная как хэш-таблица, словарь или ассоциативный массив. Мапа позволяет получить значение по ключу. Ключами в мапе могут быть любые сравниваемые типы — все сравнимые типы.

1
2
3
4
5
6
7
8
9
10

package main

import "fmt"

func main() {
    m := make(map[string]int)
    m["apple"] = 1
    m["banana"] = 2
    fmt.Println(m)
}

Что произойдет при конкурентной записи в мапу?

Мапы в Go не являются потокобезопасными. Это означает, что если вы попытаетесь записать данные в мапу из нескольких горутин одновременно, это может привести к состоянию гонки. Если вам нужно работать с мапой из нескольких горутин, вы должны использовать механизмы синхронизации, такие как sync.Mutex или sync.RWMutex, чтобы гарантировать, что в любой момент времени только одна горутина может изменять мапу. Вот пример использования sync.Mutex для безопасной записи в мапу из нескольких горутин:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

package main

import (
    "fmt"
    "sync"
)

func main() {
    var wg sync.WaitGroup
    var mu sync.Mutex
    m := make(map[int]int)

    for i := 0; i < 10; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            mu.Lock()
            m[i] = i * 2
            mu.Unlock()
        }(i)
    }

    wg.Wait()
    fmt.Println(m)
}

Как устроена мапа под капотом?

Мапа в Go - это структура данных, которая хранит пары “ключ-значение”. Внутри мапы ключи и значения хранятся в выделенном участке памяти, последовательно. Для получения адресов ячеек конкретных ключей и значений используется хэширующая функция.

Вот некоторые детали о том, как устроена мапа в Go:

• Мапа разбивается на бакеты для более эффективного поиска.
• Хэш-функция используется для равномерного распределения ключей по бакетам.
• При переполнении бакета происходит рост мапы.
• Эвакуация данных происходит при заполнении мапы.
• Порядок обхода мапы является случайным.

Какие ключи могут быть у мапы?

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

Какая сложность работы с мапой?

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

Можно ли взять адрес элемента мапы и почему?

Нет, нельзя взять адрес элемента мапы в Go. Это связано с тем, как устроена мапа внутри. Мапа разбита на бакеты, и при росте мапы элементы могут переходить из одного бакета в другой. Это означает, что адрес элемента в памяти может меняться, и поэтому Go не позволяет взять адрес элемента мапы. Если вы попытаетесь это сделать, компилятор выдаст ошибку.

Как работает эвакуация данных?

Эвакуация данных в мапе Go происходит при переполнении мапы. Когда количество элементов в мапе достигает определенного порога, мапа “растет” - создается новая, большая мапа, и все элементы из старой мапы копируются в новую. Этот процесс называется “эвакуацией”. Важно отметить, что в Go рост мапы происходит асинхронно. Это означает, что во время роста мапы могут возникать ситуации, когда при попытке доступа к данным часть бакетов уже переехала в новую мапу, а часть еще нет. Благодаря этому не происходит просадок во время роста большой мапы.

Как разрешаются коллизии в мапе?

В мапе Go коллизии разрешаются с помощью бакетов. Каждый бакет может содержать до восьми элементов. Если все ячейки в бакете заняты, то происходит переполнение и мапа “растет” - создается новая, большая мапа, и все элементы из старой мапы копируются в новую. Этот процесс называется “эвакуацией”. При этом, благодаря использованию хэш-функции, ключи равномерно распределяются по бакетам. Это позволяет минимизировать количество коллизий и обеспечивает быстрый доступ к данным.

В функции make для мапы мы указываем число. Что оно дает?

Число, указываемое в функции make для мапы в Go, определяет начальную вместимость мапы. Это число элементов, которые мапа сможет хранить без необходимости расширения. Если вы заранее знаете, сколько элементов будет в мапе, вы можете использовать это число при создании мапы, чтобы уменьшить количество операций реаллокации памяти, что может улучшить производительность. Вот пример создания мапы с начальной вместимостью 10:

1

m := make(map[string]int, 10)

Стало слишком много коллизий в мапе, как решить проблему?

Если в мапе Go стало слишком много коллизий, вы можете использовать следующие подходы для решения проблемы:

Изменить размер мапы: Если мапа слишком мала, она может быстро заполняться, что приводит к большому количеству коллизий. В этом случае вы можете увеличить размер мапы, чтобы уменьшить вероятность коллизий.

Использовать метод раздельного связывания: Это метод, при котором внутри хеш-таблицы хранится массив фиксированного размера, элементы которого - связанные списки. По хешу ключа определяется элемент массива (bucket - корзину) и потом смотрится в списке, нет ли такого элемента и действуется соответствующее (добавляется/удаляется/модифицируется).

Чем мапа отличается от sync.Map?

sync.Map и обычная мапа в Go имеют различия в использовании и производительности

1. Потокобезопасность: Обычная мапа в Go не является потокобезопасной, что означает, что одновременная запись в мапу из нескольких горутин может привести к состоянию гонки. В то время как sync.Map разработана для использования в многопоточных ситуациях и обеспечивает потокобезопасность.
2. Производительность sync.Map обычно близка по скорости к обычной мапе с sync.RWMutex, но может быть лучше в случае чтения. Когда происходит чтение и обновление, sync.Map будет иметь элементы и в чтении, и в “грязном” состоянии.
3. Использование sync.Map - это структура с методами, предоставляющими обычные операции с мапой. Вы не можете использовать синтаксис a_map["key"] с sync.Map, вместо этого нужно использовать методы, такие как Load, Store и Delete.
4. Структура sync.Map - это сложная структура, обычно состоящая из двух мап - одной для чтения и одной для новых элементов.

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

Какая функция используется при хешировании ключа в мапе?

При хешировании ключа в мапе golang используется функция runtime.mapaccess1_faststr, которая принимает тип мапы, саму мапу и ключ в виде строки. Функция ищет ключ в мапе и возвращает указатель на соответствующее значение. Функция runtime.mapaccess1_faststr является специализированной версией функции runtime.mapaccess1, которая работает с любым типом ключа.

Хеширование ключа в мапе golang основано на алгоритме MurmurHash, который быстро и равномерно распределяет ключи по хеш-таблице. Хеш-таблица в golang состоит из массива корзин (buckets), каждая из которых содержит до восьми пар ключ-значение. Кроме того, каждая корзина имеет указатель на переполненную корзину, которая создается при коллизии хешей.

Если вы хотите узнать больше о реализации мапы в golang, вы можете почитать эту статью или эту статью на Хабре. Они объясняют детали работы мапы в golang с примерами кода и иллюстрациями. 😊

Источники:

• Habr
• Habr
• GolangForAll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

package main

import "fmt"

type Vertex struct {
  Lat, Long float64
}

var m map[string]Vertex

func main() {
  m = make(map[string]Vertex) // иначе паника
  m["Bell Labs"] = Vertex{40.68433, -74.39967,}
  m["A2"] = Vertex{42, -24,}	
  
  fmt.Println(m)     // реализовано так, что детерменированный вывод
  for _, val := range m {  // произвольный обход
    fmt.Println(val)
  }
}

Хорошая статья Pro Map