Хэш таблицы в Go. Детали реализации
Порассуждаем об имплементации map в языке без дженериков, рассмотрим что такое хэш таблица, как она устроена в Go, какие есть плюсы и минусы данной реализации и на что стоит обратить внимание при использовании данной структуры.
Детали под катом.
Внимание! Кто уже знаком с хэш-таблицами в Go, советую пропустить основы и отправиться сюда, иначе есть риск устать к самому интересному моменту.
Что такое хэш таблица
Для начала все-таки напомню, что такое хэш таблица. Это структура данных, которая позволяет хранить пары ключ-значение, и, как правило, обладающая функциями:
- Маппинга: map(key) → value
- Вставки: insert(map, key, value)
- Удаления: delete(map, key)
- Поиска: lookup(key) → value
Хэш таблица в языке go
Хэш таблица в языке 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
Основные операции производятся так:
m[key] = valuedelete(m, key)value = m[key] value, ok = m[key] Обход таблицы в go
Рассмотрим следующую программу:
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: %t\n", k, v) >> key: 3, value: false key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true 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) Место поиска определяется рандомно, запомните это! Ходят слухи, что так разработчики рантайма заставляют пользователей не полагаться на порядок.
Поиск в таблице Go
Снова рассмотрим кусок кода. Предположим, мы хотим создать пары «число»-«число умноженное на 10»:
package main import ( "fmt" ) func main() < m := map[int]intfmt.Println(m, m[0], m[1], m[2]) > map[0:0 1:10] 0 10 0 И видим, что при попытке получить значение двойки (которую забыли положить) получили 0. Находим в документации строки, объясняющие это поведение: «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]intm2, 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
Создание таблицы в Go.
Допустим, мы хотим посчитать количество вхождений каждого слова в строке, заведем для этого словарь и пройдемся по нему.
package main func main() < var m map[string]int for _, word := range []string < 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» конструкции
map[key_type]value_type<>
и при желании даже сразу проинициализировать значениями, этот способ тоже валидный. Что касается создания с помощью new — на мой взгляд, оно не имеет смысла, потому что эта функция выделяет память под переменную и возвращает указатель на нее, заполненную zero value типа, что в случае с map будет nil (мы получим тот же результат, что в var, точнее указатель на него).
Как передается map в функцию?
Допустим у нас есть функция, которая пытается поменять число, которое ей передали. Посмотрим, что будет до и после вызова:
package main func foo(n int) < n = 10 >func main() < n := 15 println("n before foo =", n) foo(n) println("n after foo plaintext">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 go">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()
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 коллизий, в конце каждого «ведра» есть указатель на дополнительное, если вдруг предыдущее переполнилось.
Как растет map?
В исходном коде можно найти строчку:
// Maximum average load of a bucket that triggers growth is 6.5.
то есть, если в каждом «ведре» в среднем более 6,5 элементов, происходит увеличение массива buckets. При этом выделяется массив в 2 раза больше, а старые данные копируются в него маленькими порциями каждые вставку или удаление, чтобы не создавать очень крупные задержки. Поэтому все операции будут чуть медленнее в процессе эвакуации данных (при поиске тоже, нам же приходится искать в двух местах). После успешной эвакуации начинают использоваться новые данные.
Взятие адреса элемента map.
Еще один достаточно интересный момент — мне в самом начале использования языка хотелось сделать вот так:
package main import ( "fmt" ) func main()
Но Go говорит: «cannot take the address of m[1]». Объяснение почему же нельзя взять адрес значения кроется процедуре эвакуации данных. Представьте, что мы взяли адрес значения, а потом мапа выросла, выделилась новая память, данные эвакуировались, старые удалились, указатель стал неправильным, поэтому такие операции запрещены.
Как реализована map без genericов?
Ни пустой интерфейс, ни кодогенерация тут ни при чем, все дело в замене во время компиляции. Рассмотрим во что превращаются знакомые нам функции из 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
В 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
Далее мы проверяем не нулевой ли указатель на хэдер мапы, не лежит ли там 0 элементов и возвращаем нулевое значение, если это так.
hash := t.key.hash(key, m.seed) // hash := hashfn(key) bucket := hash & (1<> 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's maps under the hood
After digging in runtime package I found out that underlying map structure is following:
// 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 >buckets - is array of buckets where indexes is low-order bits of key's hash, where the bucket is:
// A bucket for a Go map. type bmap struct < // tophash generally contains the top byte of the hash value // for each key in this bucket. If tophash[0] < minTopHash, // tophash[0] is a bucket evacuation state instead. tophash [bucketCnt]uint8 // Followed by bucketCnt keys and then bucketCnt elems. // NOTE: packing all the keys together and then all the elems together makes the // code a bit more complicated than alternating key/elem/key/elem/. but it allows // us to eliminate padding which would be needed for, e.g., map[int64]int8. // Followed by an overflow pointer. >..well it's just array of uint8 where every item is first byte of key's hash. And key-value pairs are stores as key/key value/value (eight pairs per bucket). But where exactly? Considering that map may contain value of (almost) any type. There should be some kind of pointer to place in memory where array of values stored, but bmap doesn't have such info.
And since key's hashes are located in ordered array inside bucket, why it's order different every time I looping over map?
394k 64 64 gold badges 919 919 silver badges 836 836 bronze badges
asked Dec 11, 2019 at 16:50
170 1 1 silver badge 10 10 bronze badges
Dec 11, 2019 at 16:56
They are unordered for the same reason that maps/dictionaries/hashes in most languages are unordered: speed. The majority of cases don't need them ordered, which would make ordering them in all cases wasteful of CPU resources. This was (I think) a sensible tradeoff by the designers, but if you want to know why they chose that. you would have to ask them, not the community at large.
Dec 11, 2019 at 17:04
"why it's order different every time I looping over map?" so that people would not rely on any particular ordering, as the ordering is not guaranteed in any way by the language. "Where actual values are stored in memory?" yes, in memory, wherever the map has been allocated - this question is kind of unclear.
Dec 11, 2019 at 17:05
1 Answer 1
Because this gives greater freedom to the runtime to implement the map type. Although we know Go's (current) implementation is a hashmap, the language specification allows to use any map implementation like hash map, tree map etc. Also not having to remember the order, this allows the runtime to do its job more effectively and using less memory.
Adrian's comment nicely summarizes that order is rarely needed, and it would be a waste to always maintain order. When you do need order, you may use a data structure that provides the ordering. For examples, see Map in order range loop.
And since key's hashes are located in ordered array inside bucket, why it's order different every time I looping over map?
The Go authors intentionally made map's iteration order randomized (so we mortals don't get dependent on a fixed order). For more, see In Golang, why are iterations over maps random?
The "where" is specified by hmap.buckets . This is a pointer value, it points to an array in memory, an array holding the buckets.
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. So hmap.buckets points to a contiguous memory segment holding buckets. A bucket is "modeled" by bmap , but this is not its actual memory layout. A bucket starts with an array holding top hash bytes of keys being in the bucket ( tophash [bucketCnt]uint8 ), and this array is followed by bucketCnt keys of the bucket, which is then followed by bucketCnt values of the bucket. Lastly there is an overflow pointer.
Think of the bucket like this conceptual type, which "visualizes" where keys and values are located in memory:
type conceptualBucket struct
Note: bucketCnt is a compile time constant being 8 , it is the maximum number of key/elem pairs a bucket can hold.
Of course this "picture" is inaccurate, but it gives the idea where / how keys and values are stored.
Принцип работы типа map в GO
Что такое тип map в GO для разработчика отлично описано в блоге GO. Нам лишь надо помнить, что это тип данных, позволяющий получить значение по ключу. От типа map требуется сделать это максимально быстро.
Ключами в мапе могут быть любые сравниваемые типы — все простые скалярные типы, каналы, массивы.
Несравниваемые типы — срезы, мапы, функциии.
Ключи и значения мапы будут храниться в выделенном участке памяти, последовательно. Для получения адресов ячеек конкретных ключей и значений, удобно использовать хэширующую функцию.
- Детерминированность — функция должна вернуть одно и то же значение от одного и того же ключа;
- Равномерность — должны выдавать значения которые можно было каким-либо образом равномерно распределить в некотором множестве;
- Скорость — вычисляться быстро, т.к. используются часто;
Теперь рассмотрим реализацию. Упрощенно структура имеет следующий вид (исходник):
// A header for a Go map. type hmap struct count int // # live cells == size of map. Must be first (used by len() builtin) B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items) 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 >
Указатели на данные, попадающие в мапу, хранятся частями — в массиве buckets .
unsafe.Pointer — указатель на данные любого типа — способ разработчиков GO уйти от проблемы джереников (реализовать функционал мапы с различными типами ключей и значений).
Бакеты не создаются, пока данных в мапе нет. При появлении данных, создается 8 бакетов.
Получение данных из мапы
Необходимо найти адрес ячейки памяти, где хранится значение ключа, далее найдем адрес ячейки памяти со значением.
Ищем бакет с ключом. Он выбирается сравнением первых 8 битов от хэша ключа с соответствующим значением в данных бакета.
После нахождения подходящего бакета, получаем значение ключа по указателю.
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() k = *((*unsafe.Pointer)(k)) >
Далее, зная адрес первой ячейки памяти, где размещены данные мапы, размер типа ключа и типа значения, вычисляем адрес ячейки памяти, где хранится значение и получаем его.
if t.key.equal(key, k) e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() e = *((*unsafe.Pointer)(e)) > return e >
Увеличение размера мапы
Свойство oldbuckets в структуре мапы необходимо во время процесса миграции данных.
Миграция начинается при принятии решения о слишком большом кол-ве данных в бакетах. При этом текущение значение указателя buckets сохраняется в свойство oldbuckets , после чего в свойстве buckets создается новая структура бакетов, где их становится в 2 раза больше от текущего. Данные мапы копируются из oldbuckets в buckets .
Т.к. бакетов становится в 2 раза больше, кол-во бакетов всегда равно степени числа 2.
Именно поэтому в структуре мапы есть свойство B — это степерь двойки, которая показывает кол-во бакетов.
Во время миграции данных, все операции мапы остаются доступны. Поэтому во многих частях исходного кода есть обращения как к buckets , так и к oldbuckets . После завершения копирования данных, oldbuckets становится равно nil.
Из-за возможного изменения адреса памяти данных в связи с миграцией, GO не позволяет получить указатель на значение элемента:
mymap := map[string]string"1": "1"> fmt.Println(&mymap["1"]) // cannot take the address of mymap["1"]
Прекрасный доклад с конференции GopherCon 2016 (английский) по данной теме:
Другие статьи
- sync.Map
- Работа с данными в конкурентных программах на GO
- GO templates
- Принцип работы типа slice в GO
- Golang regexp: как заматчить перенос строки
Что представляет из себя map в go
Отображение или map представляет ссылку на хеш-таблицу - структуру данных, где каждый элемент представляет пару "ключ-значение". При этом каждый элемент имеет уникальный ключ, по которому можно получить значение элемента. Отображение определяется как объект типа map[K]V , где К представляет тип ключа, а V - тип значения. Причем тип ключа K должен поддерживать операцию сравнения ==, чтобы оображение могло сопоставить значение с одним из ключей и хеш-таблицы.
Например, определение отображения, которое в качестве ключей имеет тип string, а в качестве значений - тип int:
var people map[string]int // Ключи представляют тип string, значения - тип int
Установка значений отображения:
var people = map[string]int < "Tom": 1, "Bob": 2, "Sam": 4, "Alice": 8, >fmt.Println(people) // map[Tom:1 Bob:2 Sam:4 Alice:8]
Как и в массиве или в срезе элементы помещаютя в фигурные скобки. Каждый элемент представляет пару ключ -значение. Вначале идет ключ и через двоеточие значение. Определение элемента завершается запятой.
Для обращения к элементам нужно применять ключи:
var people = map[string]int < "Tom": 1, "Bob": 2, "Sam": 4, "Alice": 8, >fmt.Println(people["Alice"]) // 8 fmt.Println(people["Bob"]) // 2 people["Bob"] = 32 fmt.Println(people["Bob"]) // 32
Для проверки наличия элемента по определенному ключу можно применять выражение if:
var people = map[string]int < "Tom": 1, "Bob": 2, "Sam": 4, "Alice": 8, >if val, ok := people["Tom"]; ok
Если значение по заданному ключу имеется в отображении, то переменная ok будет равна true, а переменная val будет хранить полученное значение. Если переменная ok равна false, то значения по ключу в отображении нет.
Для перебора элементов применяется цикл for:
var people = map[string]int < "Tom": 1, "Bob": 2, "Sam": 4, "Alice": 8, >for key, value := range people
Консольный вывод программы:
Tom 1 Bob 2 Sam 4 Alice 8
Функция make представляет альтернативный вариант создания отображения. Она создает пустую хеш-таблицу:
people := make(map[string]int)
Добавление и удаление элементов
Для добавления элементов достаточно просто выполнить установку значения по новому ключу и элемент с этим ключом будет добавлен в коллекцию:
var people = map[string]int < "Tom": 1, "Bob": 2>people["Kate"] = 128 fmt.Println(people) // map[Tom:1 Bob:2 Kate:128]
Для удаления применяется встроенная функция delete(map, key) , первым параметром которой является отображение, а вторым - ключ, по которому надо удалить элемент.
var people = map[string]int < "Tom": 1, "Bob": 2, "Sam": 8>delete(people, "Bob") fmt.Println(people) // map[Tom:1 Sam:8]