В этой статье будет в основном проанализирован принцип реализации карты в golang, а также обсуждены распространенные проблемы при использовании. Версия golang, которая выполняет анализ, — 1.9.
Карта в golang реализована с помощью hashmap в качестве нижнего слоя.В исходном коде github есть два связанных кода:runtime/hashmap.goОпределяет базовую структуру и методы карты,runtime/hashmap_fast.goПредоставляет некоторые функции для быстрого управления картами.
карта базовой структуры данных
Базовая структура карты — hmap (сокращение от hashmap).Основной элемент представляет собой массив, состоящий из нескольких сегментов (сегментов, структура которых — bmap).Каждый сегмент может хранить несколько элементов (обычно 8).Ключ хэшируется с помощью алгоритмов сгруппированы в разные ведра. Когда в ведре необходимо хранить более 8 элементов, hmap будет использовать дополнительное переполнение для расширения ведра. Ниже представлена структура hmap.
type hmap struct {
count int // # 元素个数
flags uint8
B uint8 // 说明包含2^B个bucket
noverflow uint16 // 溢出的bucket的个数
hash0 uint32 // hash种子
buckets unsafe.Pointer // buckets的数组指针
oldbuckets unsafe.Pointer // 结构扩容的时候用于复制的buckets数组
nevacuate uintptr // 搬迁进度（已经搬迁的buckets数量）
extra *mapextra
}Кроме того, есть не только overflow, но и oldoverflow (для расширения) и nextoverflow (адрес prealloc).
Структура ведра (bmap) следующая
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 values.
// NOTE: packing all the keys together and then all the values together makes the
// code a bit more complicated than alternating key/value/key/value/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}- Tophash используется для записи старших 8 битов 8 значений хеш-функции ключа, чтобы можно было быстрее найти соответствующий ключ, и нет необходимости каждый раз оценивать соответствие ключа.
- Обратите внимание на комментарии в следующих строках, у hmap не только один tophash, но за ним следуют 8 наборов пар kv и указатель переполнения, так что переполнение может стать структурой связанного списка. Но эти две структуры не определены явно, а доступны напрямую через арифметику указателей.
- Форма хранения kv: "key0key1key2key3...key7val1val2val3...val7". Преимущество этого заключается в том, что он экономит место для заполнения, когда длина ключа и значения различаются. Как и в приведенном выше примере, в map[int64]int8 4 соседних int8 могут храниться в одном блоке памяти. Если используется память с чередованием kv, каждый int8 будет заполняться, чтобы занять отдельную единицу памяти (для повышения скорости адресации).
Структура hmap почти такая, как показано на рисунке.
доступ к карте
Возьмем, к примеру, mapaccess1, какой-то нерелевантный код изменяется.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// do some race detect things
// do some memory sanitizer thins
if h == nil || h.count == 0 {
return unsafe.Pointer(&zeroVal[0])
}
if h.flags&hashWriting != 0 { // 检测是否并发写，map不是gorountine安全的
throw("concurrent map read and map write")
}
alg := t.key.alg // 哈希算法 alg -> algorithm
hash := alg.hash(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// 如果老的bucket没有被移动完，那么去老的bucket中寻找 （增长部分下一节介绍）
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// There used to be half as many buckets; mask down one more power of two.
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
// 寻找过程：不断比对tophash和key
top := tophash(hash)
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey {
k = *((*unsafe.Pointer)(k))
}
if alg.equal(key, k) {
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
if t.indirectvalue {
v = *((*unsafe.Pointer)(v))
}
return v
}
}
}
return unsafe.Pointer(&zeroVal[0])
}рост карты
По мере увеличения количества элементов поиск определенного ключа в цепочке сегментов становится неэффективным, поэтому, когда количество вставленных элементов/сегментов достигает определенного порога (в настоящее время установлено значение 6,5, экспериментальное значение), карта будет расширена, подробности см. в кодефункция hashGrow. Сначала создайте массив сегментов, длина которого в два раза превышает исходную длину.
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger)После завершения расширения каждый хэш соответствует двум сегментам (одному новому и одному старому). Старое ведро не будет немедленно перенесено в новое ведро, но при доступе к ведру будет вызван метод GrowWork для переноса, который перехэширует элементы из старого ведра в новое ведро. По мере доступа все старые ведра будут постепенно перемещаться в ведро.
Но вот проблема: что делать, если миграция после последнего расширения не закончилась, когда требуется расширение? В коде мы можем видеть много тегов «опять», которые будут продолжать мигрировать, а следующее расширение будет выполнено после завершения миграции.
Распространенные проблемы при использовании
В: Будет ли освобождена память при удалении элементов на карте?
A: Нет, операция удаления только очищает соответствующий tophash[i], не освобождая память. Чтобы освободить память, вы можете только дождаться разыменования указателя системой gc.
В: Как использовать карту одновременно?
A: Карта не безопасна для горутин, поэтому она будет паниковать, когда на карту будут записываться несколько горутин. Карта чтения и записи с несколькими горунтами должна быть заблокирована (RWMutex) или использовать sync.Map (новое в 1.9, эта вещь будет представлена в следующей статье, короче говоря, это не рекомендуется).
В: Безопасен ли итератор карты?
A: Удаление карты на самом деле не является удалением, поэтому оно не влияет на итератор и является безопасным.