- PVSM.RU - https://www.pvsm.ru -
Порассуждаем об имплементации map в языке без дженериков, рассмотрим что такое хэш таблица, как она устроена в Go, какие есть плюсы и минусы данной реализации и на что стоит обратить внимание при использовании данной структуры.
Детали под катом.
Для начала все-таки напомню, что такое хэш таблица. Это структура данных, которая позволяет хранить пары ключ-значение, и, как правило, обладающая функциями:
map(key) → value
insert(map, key, value)
delete(map, key)
lookup(key) → value
Хэш таблица в языке go представлена ключевым словом map и может быть создана одним из способов ниже (подробнее о них позже):
m := make(map[key_type]value_type)
m := new(map[key_type]value_type)
var m map[key_type]value_type
m := map[key_type]value_type{key1: val1, key2: val2}
Основные операции производятся так:
m[key] = value
delete(m, key)
value = m[key]
или
value, ok = m[key]
Рассмотрим следующую программу:
package main
import "fmt"
func main() {
m := map[int]bool{}
for i := 0; i < 5; i++ {
m[i] = ((i % 2) == 0)
}
for k, v := range m {
fmt.Printf("key: %d, value: %tn", k, v)
}
}
Запуск 1:
key: 3, value: false
key: 4, value: true
key: 0, value: true
key: 1, value: false
key: 2, value: true
Запуск 2:
key: 4, value: true
key: 0, value: true
key: 1, value: false
key: 2, value: true
key: 3, value: false
Как видим, вывод разнится от запуска к запуску. А все потому, что мапа в Go unordered, то есть не упорядоченная. Это значит, что полагаться на порядок при обходе не надо. Причину можно найти в исходном коде рантайма языка:
// mapiterinit initializes the hiter struct used for ranging over maps.
func mapiterinit(t *maptype, h *hmap, it *hiter) {...
// decide where to start
r := uintptr(fastrand())
...
it.startBucket = r & bucketMask(h.B)...}
Место поиска определяется рандомно, запомните это! Ходят слухи, что так разработчики рантайма заставляют пользователей не полагаться на порядок.
Снова рассмотрим кусок кода. Предположим, мы хотим создать пары «число»-«число умноженное на 10»:
package main
import (
"fmt"
)
func main() {
m := map[int]int{0: 0, 1: 10}
fmt.Println(m, m[0], m[1], m[2])
}
Запускаем:
map[0:0 1:10] 0 10 0
И видим, что при попытке получить значение двойки (которую забыли положить) получили 0. Находим в документации [2] строки, объясняющие это поведение: «An attempt to fetch a map value with a key that is not present in the map will return the zero value for the type of the entries in the map.», а в переводе на русский это означает, что когда мы пытаемся получить значение из мапы, а его там нет, получаем «нулевое значение типа», что в случае числа 0. Что же делать, если мы хотим различать случаи 0 и отсутствия 2? Для этого придумали специальную форму «multiple assignment».
Правильно предыдущий кусок кода будет выглядеть так:
package main
import (
"fmt"
)
func main() {
m := map[int]int{0: 0, 1: 10}
m2, ok := m[2]
if !ok {
// somehow process this case
m2 = 20
}
fmt.Println(m, m[0], m[1], m2)
}
И при запуске получим:
map[0:0 1:10] 0 10 20
Допустим, мы хотим посчитать количество вхождений каждого слова в строке, заведем для этого словарь и пройдемся по нему.
package main
func main() {
var m map[string]int
for _, word := range []string{"hello", "world", "from", "the",
"best", "language", "in", "the", "world"} {
m[word]++
}
for k, v := range m {
println(k, v)
}
}
Вы гофера подвох видите? — А он есть!
При попытке запуска такой программы получим панику и сообщение «assignment to entry in nil map». А все потому что мапа — ссылочный тип и мало объявить переменную, надо ее проинициализировать:
m := make(map[string]int)
Чуть пониже будет понятно почему это работает именно так. В начале было представлено аж 4 способа создания мапы, два из них мы рассмотрели — это объявление как переменную и создание через make. Еще можно создать с помощью "Composite literals [3]" конструкции
map[key_type]value_type{}
и при желании даже сразу проинициализировать значениями, этот способ тоже валидный. Что касается создания с помощью new — на мой взгляд, оно не имеет смысла, потому что эта функция выделяет память под переменную и возвращает указатель на нее, заполненную zero value типа, что в случае с map будет nil (мы получим тот же результат, что в var, точнее указатель на него).
Допустим у нас есть функция, которая пытается поменять число, которое ей передали. Посмотрим, что будет до и после вызова:
package main
func foo(n int) {
n = 10
}
func main() {
n := 15
println("n before foo =", n)
foo(n)
println("n after foo =", n)
}
Пример, думаю, достаточно очевидный, но все-таки включу вывод:
n before foo = 15
n after foo = 15
Как вы наверное догадались, в функцию n пришло по значению, а не по ссылке, поэтому исходная переменная не поменялась.
Проделаем похожий трюк с мапой:
package main
func foo(m map[int]int) {
m[10] = 10
}
func main() {
m := make(map[int]int)
m[10] = 15
println("m[10] before foo =", m[10])
foo(m)
println("m[10] after foo =", m[10])
}
И о чудо:
m[10] before foo = 15
m[10] after foo = 10
Значение поменялось. «Что же, мапа передается по ссылке?», — спросите вы. Нет. В Go не бывает ссылок. Невозможно создать 2 переменные с 1 адресом, как в С++ например. Но зато можно создать 2 переменные, указывающие на один адрес (но это уже указатели, и они в Go есть).
Пусть у нас есть функция fn, которая инициализирует мапу m. В основной функции мы просто объявляем переменную, отправляем на инициализацию и смотрим что получилось после.
package main
import "fmt"
func fn(m map[int]int) {
m = make(map[int]int)
fmt.Println("m == nil in fn?:", m == nil)
}
func main() {
var m map[int]int
fn(m)
fmt.Println("m == nil in main?:", m == nil)
}
Вывод:
m == nil in fn?: false
m == nil in main?: true
Итак, переменная m передалась по значению, поэтому, как в случае с передачей в функцию обычного int, не поменялась (поменялась локальная копия значения в fn). Тогда почему же меняется значение, лежащее в самой m? Для ответа на этот вопрос рассмотрим код из рантайма языка:
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
Мапа в Go — это просто указатель на структуру hmap. Это и является ответом на вопрос, почему при том, что мапа передается в функцию по значению, сами значения, лежащие в ней меняются — все дело в указателе. Так же структура hmap содержит в себе следующее: количество элементов, количество «ведер» (представлено в виде логарифма для ускорения вычислений), seed для рандомизации хэшей (чтобы было сложнее заddosить — попытаться подобрать ключи так, что будут сплошные коллизии), всякие служебные поля и главное указатель на buckets, где хранятся значения. Давайте посмотрим на рисунок:
На картинке схематичное изображение структуры в памяти — есть хэдер hmap, указатель на который и есть map в Go (именно он создается при объявлении с помощью var, но не инициализируется, из-за чего падает программа при попытке вставки). Поле buckets — хранилище пар ключ-значение, таких «ведер» несколько, в каждом лежит 8 пар. Сначала в «ведре» лежат слоты для дополнительных битов хэшей (e0..e7 названо e — потому что extra hash bits). Далее лежат ключи и значения как сначала список всех ключей, потом список всех значений.
По хэш функции определяется в какое «ведро» мы кладем значение, внутри каждого «ведра» может лежать до 8 коллизий, в конце каждого «ведра» есть указатель на дополнительное, если вдруг предыдущее переполнилось.
В исходном коде можно найти строчку:
// Maximum average load of a bucket that triggers growth is 6.5.
то есть, если в каждом «ведре» в среднем более 6,5 элементов, происходит увеличение массива buckets. При этом выделяется массив в 2 раза больше, а старые данные копируются в него маленькими порциями каждые вставку или удаление, чтобы не создавать очень крупные задержки. Поэтому все операции будут чуть медленнее в процессе эвакуации данных (при поиске тоже, нам же приходится искать в двух местах). После успешной эвакуации начинают использоваться новые данные.
Еще один достаточно интересный момент — мне в самом начале использования языка хотелось сделать вот так:
package main
import (
"fmt"
)
func main() {
m := make(map[int]int)
m[1] = 10
a := &m[1]
fmt.Println(m[1], *a)
}
Но Go говорит: «cannot take the address of m[1]». Объяснение почему же нельзя взять адрес значения кроется процедуре эвакуации данных. Представьте, что мы взяли адрес значения, а потом мапа выросла, выделилась новая память, данные эвакуировались, старые удалились, указатель стал неправильным, поэтому такие операции запрещены.
Ни пустой интерфейс, ни кодогенерация тут ни при чем, все дело в замене во время компиляции. Рассмотрим во что превращаются знакомые нам функции из Go:
v := m["k"] → func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
v, ok := m["k"] → func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
m["k"] = 9001 → func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
delete(m, "k") → func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)
Мы видим, что для доступов есть функции mapaccess, для записи и удаления mapassign и mapdelete соответственно. Все операции используют unsafe.Pointer, которому все равно, на какой тип он указывает, а информация о каждом значении описывается дескриптором типа.
type mapType struct {
key *_type
elem *_type ...}
type _type struct {
size uintptr
alg *typeAlg ...}
type typeAlg struct {
hash func(unsafe.Pointer, uintptr) uintptr
equal func(unsafe.Pointer, unsafe.Pointer) bool...}
В mapType хранятся дескрипторы (_type) ключа и значения. Для дескриптора типа определены операции (typeAlg) сравнения, взятия хэша, размера и так далее, поэтому мы всегда знаем как произвести их.
Немного поподробнее о том как это работает. Когда мы пишем v = m[k] (пытаемся получить значение v по ключу k), компилятор генерирует примерно следующее:
kPointer := unsafe.Pointer(&k)
vPointer := mapaccess1(typeOf(m), m, kPointer)
v = *(*typeOfvalue)vPointer
То есть берем указатель на ключ, структуру mapType, из которой узнаем какие дескрипторы у ключа и значения, сам указатель на hmap (то есть мапу) и передаем это все в mapaccess1, которая вернет указатель на значение. Указатель мы приводим к нужному типу, разыменовываем и получаем значение.
Теперь посмотрим на код поиска из рантайма (который немного адаптирован для чтения):
func lookup(t *mapType, m *mapHeader, key unsafe.Pointer) unsafe.Pointer {
Функция ищет ключ в мапе и возвращает указатель на соответствующее значение, аргументы нам уже знакомы — это mapType, который хранит дескрипторы типов ключа и значения, сама map (mapHeader) и указатель на память, хранящую ключ. Возвращаем указатель на память, хранящую значение.
if m == nil || m.count == 0 {
return zero
}
Далее мы проверяем не нулевой ли указатель на хэдер мапы, не лежит ли там 0 элементов и возвращаем нулевое значение, если это так.
hash := t.key.hash(key, m.seed) // hash := hashfn(key)
bucket := hash & (1<<m.logB-1) // bucket := hash % nbuckets
extra := byte(hash >> 56) // extra := top 8 bits of hash
b := (*bucket)(add(m.buckets, bucket*t.bucketsize)) // b := &m.buckets[bucket]
Вычисляем хэш ключа (знаем как вычислить для данного ключа из дескриптора типа). Затем пытаемся понять в какое «ведро» надо пойти и посмотреть (остаток от деления на количество «ведер», просто немного ускорены вычисления). Затем вычисляем дополнительный хэш (берем 8 старших бит хэша) и определяем положение «ведра» в памяти (адресная арифметика).
for {
for i := 0; i < 8; i++ {
if b.extra[i] != extra { // check 8 extra hash bits
continue
}
k := add(b, dataOffset+i*t.key.size) // pointer to ki in bucket
if t.key.equal(key, k) {
// return pointer to vi
return add(b, dataOffset+8*t.key.size+i*t.value.size)
}
}
b = b.overflow
if b == nil {
return zero
}
}
Поиск, если разобраться, устроен не так уж и сложно: проходимся по цепочкам «ведер», переходя в следующее, если в этом не нашли. Поиск в «ведре» начинается с быстрого сравнения дополнительного хэша (вот для чего эти e0...e7 в начале каждого — это «мини» хэш пары для быстрого сравнения). Если не совпало, идем дальше, если совпало, то проверяем тщательнее — определяем где лежит в памяти ключ, подозреваемый как искомый, сравниваем равен ли он тому, что запросили. Если равен, определяем положение значения в памяти и возвращаем. Как видите, ничего сверхъестественного.
Используйте мапы, но знайте и понимайте как они работают! Можно избежать граблей, поняв некоторые тонкости — почему нельзя взять адрес значения, почему все падает при объявлении без инициализации, почему лучше выделить память заранее, если известно количество элементов (избежим эвакуаций) и многое другое.
«Go maps in action», Andrew Gerrand [4]
«How the go runtime implements maps efficiently», Dave Cheney [5]
«Understanding type in go, William Kennedy [6]
Inside map implementation, Keith Randall [7]
map source code, Go Runtime [8]
golang spec [9]
effective go [10]
картинки с гоферами [11]
Автор: darkol
Источник [12]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/322046
Ссылки в тексте:
[1] сюда: #GoMap
[2] документации: https://golang.org/doc/effective_go.html?h=map#maps
[3] Composite literals: https://golang.org/ref/spec#Composite_literals
[4] «Go maps in action», Andrew Gerrand: https://blog.golang.org/go-maps-in-action
[5] «How the go runtime implements maps efficiently», Dave Cheney: https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics#easy-footnote-1-3224
[6] «Understanding type in go, William Kennedy: https://www.ardanlabs.com/blog/2013/07/understanding-type-in-go.html
[7] Inside map implementation, Keith Randall: https://www.youtube.com/watch?v=Tl7mi9QmLns&feature=youtu.be
[8] map source code, Go Runtime: https://github.com/golang/go/blob/master/src/runtime/map.go
[9] golang spec: https://golang.org/ref/spec
[10] effective go: https://golang.org/doc/effective_go.html
[11] картинки с гоферами: https://github.com/shalakhin/gophericons
[12] Источник: https://habr.com/ru/post/457728/?utm_campaign=457728&utm_source=habrahabr&utm_medium=rss
Нажмите здесь для печати.