Одной из наиболее полезных структур данных в информатике является хэш-таблица. Существует множество реализаций хэш-таблиц с различными свойствами, но в целом они предлагают быстрый поиск, добавление и удаление. Go предоставляет встроенный тип map (карта), который реализует хэш-таблицу.
Декларация и инициализация
Тип map в Go выглядит следующим образом:
map[KeyType]ValueType
где KeyType может быть любым типом, который сопоставим (comparable) (подробнее об этом позже), а ValueType может быть любым типом вообще, включая другую карту!
Эта переменная m является картой строковых ключей для значений int:
var m map[string]int
Типы карт (map) являются ссылочными типами, такими как указатели или срезы (slice), и поэтому значение m выше равно nil; оно не указывает на инициализированную карту. Нулевая карта (nil map) ведет себя как пустая карта при чтении, но попытки записи в нулевую карту вызовут панику во время выполнения (runtime panic). Чтобы инициализировать карту, используйте встроенную функцию make:
m = make(map[string]int)
Функция make выделяет и инициализирует структуру данных hash map и возвращает значение карты, которое указывает на нее. Специфика этой структуры данных является деталью реализации среды выполнения и не определяется самим языком. В этой посте мы сосредоточимся на использовании карт, а не на их реализации.
Работа с картами
Go предоставляет знакомый синтаксис для работы с картами. Этот оператор устанавливает ключ "route" на значение 66:
m["route"] = 66
Этот оператор извлекает значение, хранящееся под ключом "route", и присваивает его новой переменной i:
i := m["route"]
Если запрошенный ключ не существует, мы получаем нулевое значение типа значения. В этом случае типом значения является int, поэтому нулевое значение равно 0:
j := m["root"]
// j == 0
Встроенная функция len возвращает количество элементов в карте:
n := len(m)
Встроенная функция delete удаляет запись в карте:
delete(m, "route")
Функция delete ничего не возвращает и ничего не сделает, если указанный ключ не существует.
Тесты присваивания с двумя значениями для существования ключа:
i, ok := m["route"]
В этом утверждении первому значению (i) присваивается значение, хранящееся под ключом "route". Если этот ключ не существует, i является нулевым значением типа значения (0). Второе значение (ok) является логическим (bool) значением, которое имеет значение true, если ключ существует в карте, и значение false, если нет.
Чтобы проверить ключ без извлечения значения, используйте подчеркивание вместо первого значения:
_, ok := m["route"]
Чтобы перебрать содержимое карты, используйте ключевое слово range:
for key, value := range m {
fmt.Println("Key:", key, "Value:", value)
}
Чтобы инициализировать карту с некоторыми данными, используйте литерал карты:
commits := map[string]int{
"rsc": 3711,
"r": 2138,
"gri": 1908,
"adg": 912,
}
Тот же синтаксис может использоваться для инициализации пустой карты, которая функционально идентична использованию функции make:
m = map[string]int{}
Использование нулевых значений
Это может быть удобно, что поиск карты возвращает нулевое значение, когда ключ отсутствует.
Например, карта bool значений может использоваться как структура данных, подобная множеству (напомним, что нулевое значение для bool типа - false). Этот пример просматривает связанный список узлов и печатает их значения. Он использует карту указателей узлов для обнаружения циклов в списке.
type Node struct {
Next *Node
Value interface{}
}
var first *Node
visited := make(map[*Node]bool)
for n := first; n != nil; n = n.Next {
if visited[n] {
fmt.Println("cycle detected")
break
}
visited[n] = true
fmt.Println(n.Value)
}
Выражение visited[n] является истинным (true), если n было посещено, или ложным (false), если n не присутствует. Нет необходимости использовать форму с двумя значениями, чтобы проверить наличие n в карте; нулевое значение по умолчанию делает это для нас.
Другим примером полезных нулевых значений является карта срезов. При добавлении к нулевому срезу просто выделяется новый срез, поэтому добавление значения к карте срезов является однострочным; нет необходимости проверять, существует ли ключ. В следующем примере группа людей заполняется значениями Person. У каждого человека есть имя и срез лайков. В этом примере создается карта, которая связывает каждый лайк с группой людей, которым он нравится.
type Person struct {
Name string
Likes []string
}
var people []*Person
likes := make(map[string][]*Person)
for _, p := range people {
for _, l := range p.Likes {
likes[l] = append(likes[l], p)
}
}
Чтобы напечатать список людей, которые любят сыр:
for _, p := range likes["cheese"] {
fmt.Println(p.Name, "likes cheese.")
}
Чтобы напечатать количество людей, которые любят бекон:
fmt.Println(len(likes["bacon"]), "people like bacon.")
Обратите внимание, что так как range и len рассматривают нулевой срез как срез нулевой длины, эти два последних примера будут работать, даже если никто не любит сыр или бекон (хотя это маловероятно).
Типы ключей
Как упомянуто ранее, ключи карты могут быть любого типа, который сопоставим (comparable). Спецификация языка определяет это точно, но короче говоря, сопоставимые типы - это логические, числовые, строковые, указательные, каналы и интерфейсные типы, а также структуры или массивы, которые содержат только эти типы. В списке отсутствуют срезы, карты и функции; эти типы нельзя сравнивать с помощью == и нельзя использовать в качестве ключей карты.
Очевидно, что строки, целые числа и другие базовые типы должны быть доступны в качестве ключей карты, но, возможно, неожиданными являются ключи структуры. Struct может использоваться для ключевых данных по нескольким измерениям. Например, эту карту карт можно использовать для подсчета посещений веб-страниц по странам:
hits := make(map[string]map[string]int)
Это карта строк к (карте строк к int). Каждый ключ внешней карты - это путь к веб-странице со своей собственной внутренней картой. Каждый внутренний ключ карты представляет собой двухбуквенный код страны. Это выражение возвращает количество раз, когда австралиец загружал страницу документации:
n := hits["/doc/"]["au"]
К сожалению, этот подход становится громоздким при добавлении данных, так как для любого данного внешнего ключа вы должны проверить, существует ли внутренняя карта, и создать ее, если необходимо:
func add(m map[string]map[string]int, path, country string) {
mm, ok := m[path]
if !ok {
mm = make(map[string]int)
m[path] = mm
}
mm[country]++
}
add(hits, "/doc/", "au")
С другой стороны, дизайн, в котором используется одна карта с struct ключом, устраняет всю эту сложность:
type Key struct {
Path, Country string
}
hits := make(map[Key]int)
Когда вьетнамец посещает домашнюю страницу, увеличивая (и, возможно, создавая) соответствующий счетчик за одну строку:
hits[Key{"/", "vn"}]++
И точно так же просто увидеть, сколько швейцарцев прочитали спецификацию:
n := hits[Key{"/ref/spec", "ch"}]
Конкурентность
Карты не безопасны для конкурентного использования: не определено, что происходит, когда вы читаете и пишете в них одновременно. Если вам нужно читать и записывать на карту из конкурентно выполняемых go-процедур (goroutines), доступ должен быть обеспечен каким-то механизмом синхронизации. Один из распространенных способов защиты карт - это sync.RWMutex.
Этот оператор объявляет переменную-счетчик, которая является анонимной структурой, содержащей карту и встроенный sync.RWMutex.
var counter = struct{
sync.RWMutex
m map[string]int
}{m: make(map[string]int)}
Для чтения со счетчика возьмите блокировку чтения (read lock):
counter.RLock()
n := counter.m["some_key"]
counter.RUnlock()
fmt.Println("some_key:", n)
Для записи в счетчик возьмите блокировку записи (write lock):
counter.Lock()
counter.m["some_key"]++
counter.Unlock()
Порядок итерации
При итерации по карте с помощью range цикла порядок итераций не указывается и не гарантируется, что он будет одинаковым от одной итерации к следующей. Если вам требуется стабильный порядок итераций, вы должны поддерживать отдельную структуру данных, которая определяет этот порядок. В этом примере используется отдельный отсортированный срез ключей для печати map[int]string в порядке расположения ключей:
import "sort"
var m map[int]string
var keys []int
for k := range m {
keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
fmt.Println("Key:", k, "Value:", m[k])
}
Читайте также:
Комментариев нет:
Отправить комментарий