Принцип работы типа 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 (английский) по данной теме:

Принцип работы типа map в GO

Получение данных из мапы

Увеличение размера мапы

Другие статьи