В этой статье в основном рассказывается о конкретном процессе выполнения назначения карты, удаления, запроса и расширения, все еще с точки зрения нижнего уровня. В сочетании с исходным кодом после прочтения этой статьи вы обязательно поймете основной принцип карты.
На что я хочу обратить внимание, так это на то, что основное использование карты здесь менее вовлечено, и я считаю, что этому можно научиться, прочитав другие вводные книги. Содержание этой статьи более подробное, но, поскольку я нарисовал различные диаграммы, думаю, его легко понять.
что такое карта
Википедия определяет карту следующим образом:
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.
Кратко: в информатике то, что называется ассоциативным массивом, картой, таблицей символов или словарем, представляет собой набор<key, value>Абстрактная структура данных, состоящая из пар, и один и тот же ключ встречается только один раз.
Есть два ключевых момента: карта определяетсяkey-valueсостоит из пар;keyПоявляется только один раз.
Операции, связанные с картой, в основном:
- Добавить пару k-v - Добавить или вставить;
- Удалить пару k-v - Удалить или удалить;
- Изменить v, соответствующий a k - Переназначить;
- Запросить vLookup, соответствующий k;
Просто самое основное增删查改.
Дизайн карты также известен как «проблема словаря», и его задача состоит в том, чтобы разработать структуру данных для хранения данных коллекции, а также для добавления, удаления, запроса и изменения коллекции одновременно. Существуют две основные структуры данных:哈希查找表（Hash table）,搜索树（Search tree）.
Таблицы поиска хэшей используют хеш-функцию для назначения ключей разным блокам (блокам, то есть разным индексам массива). Таким образом, накладные расходы в основном связаны с вычислением хеш-функции и постоянным временем доступа к массиву. Во многих сценариях хеш-таблицы поиска очень эффективны.
Таблицы поиска хэшей обычно имеют проблему «коллизии», то есть разные ключи хэшируются в одно и то же ведро. Как правило, есть два способа справиться с этим:链表法и开放地址法.链表法Ведро реализуется как связанный список, а ключи в том же ведре будут вставлены в связанный список.开放地址法После того, как произойдет столкновение, по определенному правилу выберите «вакансию» в конце массива, чтобы разместить новый ключ.
Метод дерева поиска обычно использует самобалансирующиеся деревья поиска, в том числе: дерево AVL, красно-черное дерево. Во время собеседований их часто просят и даже просят написать красно-черный древовидный код от руки, часто интервьюер не может написать его сам, что очень избыточно.
Наихудшая эффективность поиска метода самобалансирующегося дерева поиска составляет O(logN), а наихудшая эффективность хеш-таблицы поиска — O(N). Конечно, средняя эффективность поиска в хеш-таблице поиска составляет O (1).Если хэш-функция хорошо спроектирована, наихудший случай вряд ли произойдет. Еще один момент, обходя самобалансирующееся дерево поиска, возвращаемая последовательность ключей, как правило, упорядочена от меньшего к большему, в то время как хэш-таблица поиска не в порядке.
Зачем использовать карту
Выдержка из официального блога Go:
One of the most useful data structures in computer science is the hash table. Many hash table implementations exist with varying properties, but in general they offer fast lookups, adds, and deletes. Go provides a built-in map type that implements a hash table.
Хеш-таблица является одним из наиболее важных элементов компьютерной структуры данных. Большинство хеш-таблиц реализуют функции быстрого поиска, добавления и удаления. Встроенная карта языка Go реализует все вышеперечисленные функции.
Трудно представить себе написание программы, не использующей карты, и трудно ответить на вопрос, для чего используются карты.
Итак, зачем вообще использовать карту? Поскольку он такой мощный, эффективность работы различных дополнений, удалений и изменений очень высока.
Как реализован нижний слой карты
Сначала объявите версию Go, которую я использую:
go version go1.9.2 darwin/amd64
Как упоминалось выше, существует несколько решений для реализации карты.Язык Go использует хеш-справочную таблицу и использует связанный список для разрешения хеш-конфликтов.
Далее мы рассмотрим основные принципы карты и взглянем на ее внутреннюю структуру.
модель памяти карты
В исходном коде структура, представляющая карту, называется hmap, что является «аббревиатурой» от hashmap:
// A header for a Go map.
type hmap struct {
// 元素个数，调用 len(map) 时，直接返回此值
count int
flags uint8
// buckets 的对数 log_2
B uint8
// overflow 的 bucket 近似数
noverflow uint16
// 计算 key 的哈希的时候会传入哈希函数
hash0 uint32
// 指向 buckets 数组，大小为 2^B
// 如果元素个数为0，就为 nil
buckets unsafe.Pointer
// 扩容的时候，buckets 长度会是 oldbuckets 的两倍
oldbuckets unsafe.Pointer
// 指示扩容进度，小于此地址的 buckets 迁移完成
nevacuate uintptr
extra *mapextra // optional fields
}
Объяснять,Bявляется логарифмом длины массива сегментов, что означает, что длина массива сегментов равна 2^B. Ключ и значение хранятся в ведре, о котором мы поговорим позже.
Buckets — это указатель, который в конечном итоге указывает на структуру:
type bmap struct {
tophash [bucketCnt]uint8
}
Но это всего лишь структура поверхности (src/runtime/hashmap.go), которая загружается во время компиляции, динамически создавая новую структуру:
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}
bmapЭто то, что мы часто называем "сегментами". Максимальное количество ключей в сегменте будет 8. Причина, по которой эти ключи попадают в одно и то же хранилище, заключается в том, что после их хэширования результат хеширования "один класс". В корзине старшие 8 бит хеш-значения, вычисленного по ключу, используются для определения того, куда попадает ключ в корзину (в корзине не более 8 мест).
Приходите к целой картине:
Когда ключ и значение карты не являются указателями, а размер меньше 128 байт, bmap будет помечен как не содержащий указателей, что позволяет избежать сканирования всего hmap при сборке мусора. Однако мы видим, что в bmap на самом деле есть поле переполнения, которое имеет тип указателя, что разрушает представление о том, что bmap не содержит указателей, а в это время переполнение будет перемещено в дополнительное поле.
type mapextra struct {
// overflow[0] contains overflow buckets for hmap.buckets.
// overflow[1] contains overflow buckets for hmap.oldbuckets.
overflow [2]*[]*bmap
// nextOverflow 包含空闲的 overflow bucket，这是预分配的 bucket
nextOverflow *bmap
}
bmap — это место, где хранится k-v.Давайте увеличим масштаб и посмотрим на внутренний состав bmap.
Вышеприведенное изображение представляет собой модель памяти ведра,HOB HashОтносится к верхнему хешу. Обратите внимание, что ключ и значение объединяются отдельно, а неkey/value/key/value/...такая форма. Преимущество этого объясняется в исходном коде тем, что в некоторых случаях поле заполнения может быть опущено для экономии места в памяти.
Например, есть такой тип карты:
map[int64]int8
Если согласноkey/value/key/value/...В этом режиме хранения после каждой пары ключ/значение требуются дополнительные 7 байтов заполнения; и все ключи и значения связаны вместе, эта формаkey/key/.../value/value/..., вам нужно только добавить отступ в конце.
Каждая корзина предназначена для хранения не более 8 пар "ключ-значение". Если 9-я пара "ключ-значение" попадает в текущую корзину, то необходимо создать другую корзину.overflowуказатели подключены.
создать карту
На синтаксическом уровне создать карту просто:
ageMp := make(map[string]int)
// 指定 map 长度
ageMp := make(map[string]int, 8)
// ageMp 为 nil，不能向其添加元素，会直接panic
var ageMp map[string]int
Как видно из языка ассемблера, лежащий в основе вызов на самом делеmakemapфункция, основная задача — инициализироватьhmapРазличные поля структуры, такие как вычисление размера B, установка хеш-сида hash0 и т. д.
func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap {
// 省略各种条件检查...
// 找到一个 B，使得 map 的装载因子在正常范围内
B := uint8(0)
for ; overLoadFactor(hint, B); B++ {
}
// 初始化 hash table
// 如果 B 等于 0，那么 buckets 就会在赋值的时候再分配
// 如果长度比较大，分配内存会花费长一点
buckets := bucket
var extra *mapextra
if B != 0 {
var nextOverflow *bmap
buckets, nextOverflow = makeBucketArray(t, B)
if nextOverflow != nil {
extra = new(mapextra)
extra.nextOverflow = nextOverflow
}
}
// 初始化 hamp
if h == nil {
h = (*hmap)(newobject(t.hmap))
}
h.count = 0
h.B = B
h.extra = extra
h.flags = 0
h.hash0 = fastrand()
h.buckets = buckets
h.oldbuckets = nil
h.nevacuate = 0
h.noverflow = 0
return h
}
Обратите внимание, что эта функция возвращает результат:*hmap, который является указателем, о котором мы говорили ранееmakesliceФункция возвращаетSliceСтруктура:
func makeslice(et *_type, len, cap int) slice
Просмотрите определение структуры slice:
// runtime/slice.go
type slice struct {
array unsafe.Pointer // 元素指针
len int // 长度
cap int // 容量
}
Структура содержит базовый указатель данных.
Разница между makemap и makeslice вносит различие: когда map и slice используются в качестве параметров функции, операция map внутри параметра функции повлияет на саму карту; ).
Основная причина: один указатель (*hmap), один представляет собой структуру (slice). Параметры функции в языке Go передаются по значению, внутри функции параметры будут скопированы в локалку.*hmapПосле того, как указатель скопирован, он по-прежнему указывает на ту же карту, поэтому работа карты внутри функции повлияет на фактические параметры. После того, как слайс будет скопирован, он станет новым слайсом, и операции над ним не повлияют на фактические параметры.
хэш-функция
Ключевым моментом карты является выбор хэш-функции. Когда программа запустится, она определит, поддерживает ли процессор aes, если да, используйте хеш aes, в противном случае используйте memhash. Это в функцииalginit()сделано по пути:src/runtime/alg.goВниз.
Хеш-функция, зашифрованная и незашифрованная. Тип шифрования обычно используется для шифрования данных, цифрового дайджеста и т. д. Типичными представителями являются md5, sha1, sha256, aes256; Незашифрованный тип обычно является поиском. В сценарии применения карты используется поиск. При выборе хэш-функции в основном исследуются два момента: производительность и вероятность коллизии.
Как мы уже говорили, структура, представляющая тип:
type _type struct {
size uintptr
ptrdata uintptr // size of memory prefix holding all pointers
hash uint32
tflag tflag
align uint8
fieldalign uint8
kind uint8
alg *typeAlg
gcdata *byte
str nameOff
ptrToThis typeOff
}
вalgПоля связаны с хэшами, которые являются указателями на следующие структуры:
// src/runtime/alg.go
type typeAlg struct {
// (ptr to object, seed) -> hash
hash func(unsafe.Pointer, uintptr) uintptr
// (ptr to object A, ptr to object B) -> ==?
equal func(unsafe.Pointer, unsafe.Pointer) bool
}
typeAlg содержит две функции: хеш-функция вычисляет хеш-значение типа, а функция equal вычисляет, являются ли два типа «хеш-равными».
Для строкового типа его хеш-функции и эквивалентные функции выглядят следующим образом:
func strhash(a unsafe.Pointer, h uintptr) uintptr {
x := (*stringStruct)(a)
return memhash(x.str, h, uintptr(x.len))
}
func strequal(p, q unsafe.Pointer) bool {
return *(*string)(p) == *(*string)(q)
}
В зависимости от типа ключа в поле alg структуры _type будут установлены функции hash и equals соответствующего типа.
процесс позиционирования ключей
После хэширования ключа получается значение хэша, всего 64 бита (64-битные компьютеры, 32-битные компьютеры обсуждаться не будут, а сейчас мейнстрим это 64-битные компьютеры), при расчете какой корзины будет падают, используются только последние B битов. Помните букву B, упомянутую ранее? Если B = 5, то количество сегментов, равное длине массива сегментов, равно 2^5 = 32.
Например, после вычисления ключа с помощью хэш-функции полученный результат хэширования будет следующим:
10010111 | 000011110110110010001111001010100010010110010101010 │ 01010
Используйте последние 5 бит, т.е.01010, значение равно 10, что соответствует 10-му сегменту. Эта операция на самом деле является операцией с остатком, но остаток слишком затратен, поэтому в кодовой реализации вместо этого используются битовые операции.
Затем используйте старшие 8 бит хеш-значения, чтобы найти положение этого ключа в корзине, которая ищет существующий ключ. В начале в ведре нет ключа, а вновь добавленный ключ найдет первую вакансию и вставит ее.
Номер корзины — это номер корзины.Когда два разных ключа попадают в одну и ту же корзину, происходит коллизия хэшей. Метод разрешения конфликта заключается в использовании метода связанного списка: в ведре найдите первую вакансию спереди назад. Таким образом, при поиске ключа сначала найдите соответствующее ведро, а затем пройдитесь по ключам в ведре.
Вот картинка из блога Цао Да на гитхабе. Оригинальное изображение - это ascii-картинка, полная гиковского вкуса. Вы можете найти блог Цао Да в справочных материалах. Всем рекомендую посмотреть.
На изображении выше предположим, что B = 5, поэтому общее количество сегментов равно 2^5 = 32. Сначала вычислите хэш ключа для поиска, используя младшие 5 бит.00110, найдите соответствующее ведро № 6 и используйте старшие 8 бит10010111, соответствующий десятичному числу 151, найти ключ со значением tophash (хэш HOB) 151 в корзине № 6 и найти слот № 2, так что весь процесс поиска завершен.
Если он не найден в корзине, а переполнение не пусто, продолжайте поиск в переполнении, пока оно не будет найдено, или пока не будут найдены все ключевые слоты, включая все переполнения.
Давайте посмотрим на исходный код, ха-ха! Как вы можете видеть из языка ассемблера, основная функция для поиска ключаmapacessРяд функций, функция функции аналогична, разница будет упомянута в следующем разделе. Здесь мы смотрим прямоmapacess1функция:
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// ……
// 如果 h 什么都没有，返回零值
if h == nil || h.count == 0 {
return unsafe.Pointer(&zeroVal[0])
}
// 写和读冲突
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
// 不同类型 key 使用的 hash 算法在编译期确定
alg := t.key.alg
// 计算哈希值，并且加入 hash0 引入随机性
hash := alg.hash(key, uintptr(h.hash0))
// 比如 B=5，那 m 就是31，二进制是全 1
// 求 bucket num 时，将 hash 与 m 相与，
// 达到 bucket num 由 hash 的低 8 位决定的效果
m := uintptr(1)<<h.B - 1
// b 就是 bucket 的地址
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// oldbuckets 不为 nil，说明发生了扩容
if c := h.oldbuckets; c != nil {
// 如果不是同 size 扩容（看后面扩容的内容）
// 对应条件 1 的解决方案
if !h.sameSizeGrow() {
// 新 bucket 数量是老的 2 倍
m >>= 1
}
// 求出 key 在老的 map 中的 bucket 位置
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
// 如果 oldb 没有搬迁到新的 bucket
// 那就在老的 bucket 中寻找
if !evacuated(oldb) {
b = oldb
}
}
// 计算出高 8 位的 hash
// 相当于右移 56 位，只取高8位
top := uint8(hash >> (sys.PtrSize*8 - 8))
// 增加一个 minTopHash
if top < minTopHash {
top += minTopHash
}
for {
// 遍历 8 个 bucket
for i := uintptr(0); i < bucketCnt; i++ {
// tophash 不匹配，继续
if b.tophash[i] != top {
continue
}
// tophash 匹配，定位到 key 的位置
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// key 是指针
if t.indirectkey {
// 解引用
k = *((*unsafe.Pointer)(k))
}
// 如果 key 相等
if alg.equal(key, k) {
// 定位到 value 的位置
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
// value 解引用
if t.indirectvalue {
v = *((*unsafe.Pointer)(v))
}
return v
}
}
// bucket 找完（还没找到），继续到 overflow bucket 里找
b = b.overflow(t)
// overflow bucket 也找完了，说明没有目标 key
// 返回零值
if b == nil {
return unsafe.Pointer(&zeroVal[0])
}
}
}
Функция возвращает указатель на h[key], если такого ключа в h нет, то она вернет нулевое значение соответствующего типа ключа, а не nil.
Код в целом относительно прост, и в нем нет ничего сложного для понимания. Просто следуйте приведенным выше примечаниям, чтобы понять шаг за шагом.
Здесь давайте поговорим о том, как найти ключ и значение и как написать весь цикл.
// key 定位公式
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// value 定位公式
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
b — это адрес bmap, где bmap по-прежнему является структурой, определенной в исходном коде, она содержит только массив tophash, а структура, расширенная компилятором, содержит такие поля, как ключ, значение и переполнение. dataOffset — это смещение ключа относительно начального адреса bmap:
dataOffset = unsafe.Offsetof(struct {
b bmap
v int64
}{}.v)
Поэтому начальный адрес ключа в корзине небезопасен.Pointer(b)+dataOffset. На этом основании адрес i-го ключа должен пересечь размер i-го ключа, а мы знаем, что адрес значения находится после всех ключей, поэтому адрес i-го значения также должен добавить смещение всех ключей. Поняв это, формулу позиционирования ключа и значения, приведенную выше, легко понять.
Давайте поговорим о способе написания всего большого цикла.Самый внешний слой — это бесконечный цикл.
b = b.overflow(t)
Пройдите все сегменты, что эквивалентно списку сегментов.
Когда определенное ведро находится, внутренний цикл должен пройти через все ячейки в ведре или все слоты, то есть BucketCnt=8 слотов. Весь процесс цикла:
Давайте поговорим о minTopHash.Когда значение tophash ячейки меньше, чем minTopHash, оно отмечает состояние миграции ячейки. Поскольку это значение состояния помещается в массив tophash, чтобы отличить его от нормального значения хеш-функции, к хеш-значению, вычисляемому по ключу, добавляется приращение: minTopHash. Это позволяет различать обычное верхнее хеш-значение и хеш-значение, представляющее состояние.
Следующие состояния представляют состояние корзины:
// 空的 cell，也是初始时 bucket 的状态
empty = 0
// 空的 cell，表示 cell 已经被迁移到新的 bucket
evacuatedEmpty = 1
// key,value 已经搬迁完毕，但是 key 都在新 bucket 前半部分，
// 后面扩容部分会再讲到。
evacuatedX = 2
// 同上，key 在后半部分
evacuatedY = 3
// tophash 的最小正常值
minTopHash = 4
В исходном коде для определения того, было ли перемещено ведро, использовалась функция:
func evacuated(b *bmap) bool {
h := b.tophash[0]
return h > empty && h < minTopHash
}
Берется только первое значение массива tophash, чтобы определить, находится ли оно в диапазоне от 0 до 4. В отличие от вышеуказанных констант, когда верхний хешevacuatedEmpty,evacuatedX,evacuatedYОдно из этих трех значений указывает на то, что все ключи в этом сегменте были перемещены в новый сегмент.
Две операции получения карты
В языке Go есть два синтаксиса для чтения карты: с запятой и без запятой. Когда запрашиваемый ключ отсутствует на карте, использование с запятой вернет логическую переменную, указывающую, находится ли ключ в карте; оператор без запятой вернет нулевое значение типа значения. Возвращает 0, если значение имеет тип int, и возвращает пустую строку, если значение имеет тип string.
package main
import "fmt"
func main() {
ageMap := make(map[string]int)
ageMap["qcrao"] = 18
// 不带 comma 用法
age1 := ageMap["stefno"]
fmt.Println(age1)
// 带 comma 用法
age2, ok := ageMap["stefno"]
fmt.Println(age2, ok)
}
результат операции:
0
0 false
Я всегда думал, что это потрясающе, как это произошло? На самом деле это то, что компилятор делает за кулисами: после анализа кода он сопоставляет два синтаксиса с двумя разными базовыми функциями.
// src/runtime/hashmap.go
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
В исходном коде имена функций неформальны, с суффиксом 1, 2 напрямую, полностью игнорируя набор методов именования в «Энциклопедии кода». Вы также можете увидеть разницу между объявлениями двух функций выше.mapaccess2Возвращаемое значение функции имеет еще одну логическую переменную, и коды двух точно такие же, за исключением того, что после возвращаемого значения добавляется ложь или истина.
Кроме того, в соответствии с различными типами ключей компилятор также заменит функции поиска, вставки и удаления более конкретными функциями для оптимизации эффективности:
| тип ключа | найти |
|---|---|
| uint32 | mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer |
| uint32 | mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool) |
| uint64 | mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer |
| uint64 | mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool) |
| string | mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer |
| string | mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) |
Типы параметров этих функций напрямую зависят от uint32, unt64 и string.Поскольку тип ключа заранее известен внутри функции, структура памяти очень понятна, поэтому это может сэкономить много операций и повысить эффективность.
Все вышеперечисленные функции находятся в файлеsrc/runtime/hashmap_fast.goвнутри.
Как расширить
Цель использования хеш-таблицы — быстро найти целевой ключ, однако по мере того, как на карту добавляется все больше и больше ключей, возрастает и вероятность коллизии ключей. 8 ячеек в корзине будут постепенно заполняться, а эффективность поиска, вставки и удаления ключей будет становиться все ниже и ниже. Идеальная ситуация — в ведре установлен только один ключ, чтобы он мог достичьO(1)Однако потребление пространства слишком велико, а стоимость использования пространства за время слишком высока.
Язык Go использует ведро для загрузки ключей 8. После нахождения ведра необходимо найти конкретный ключ, что на самом деле занимает время для места.
Разумеется, для этого должна быть степень, иначе все ключи попадут в одно ведро и напрямую выродятся в связанный список, а эффективность различных операций напрямую сведется к O(n), что не приемлемый.
Следовательно, необходим показатель для измерения ситуации, описанной ранее, т.е.装载因子. Это определено в исходном коде Go.装载因子:
loadFactor := count / (2^B)
count — это количество элементов на карте, а 2^B — это количество сегментов.
Поговорим о времени срабатывания расширения карты: при вставке нового ключа в карту будет выполняться определение условия, при выполнении следующих двух условий расширение будет запущено:
- Коэффициент загрузки превышает порог, порог, определенный в исходном коде, равен 6,5.
- Слишком много сегментов переполнения: когда B меньше 15, то есть общее количество сегментов 2^B меньше 2^15, если количество сегментов переполнения превышает 2^B; когда B >= 15, то есть общее количество сегментов 2^B больше или равно 2^15, если число сегментов переполнения превышает 2^15.
Функцию в исходном коде, соответствующую операции присваивания, можно найти на языке ассемблера.mapassign, исходный код, соответствующий условиям расширения, выглядит следующим образом:
// src/runtime/hashmap.go/mapassign
// 触发扩容时机
if !h.growing() && (overLoadFactor(int64(h.count), h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
}
// 装载因子超过 6.5
func overLoadFactor(count int64, B uint8) bool {
return count >= bucketCnt && float32(count) >= loadFactor*float32((uint64(1)<<B))
}
// overflow buckets 太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
if B < 16 {
return noverflow >= uint16(1)<<B
}
return noverflow >= 1<<15
}
объяснять:
Пункт 1: мы знаем, что в каждом ведре есть 8 вакансий, и если нет переполнения и все ведра заполнены, коэффициент загрузки рассчитывается равным 8. Поэтому, когда коэффициент загрузки превышает 6,5, это указывает на то, что многие корзины вот-вот будут заполнены, а эффективность поиска и эффективность вставки снижаются. В это время необходимо расширение.
Пункт 2: Дополнение к пункту 1. То есть, когда коэффициент загрузки относительно невелик, эффективность поиска и вставки карты в это время также очень низкая, и первая точка не может определить эту ситуацию. Поверхностное явление заключается в том, что молекула для расчета коэффициента загрузки относительно мала, то есть общее количество элементов в карте мало, но количество сегментов велико (фактически выделенное количество сегментов велико, включая большой количество переливных ковшей).
Нетрудно представить причину этого: элементы постоянно вставляются и удаляются. Многие элементы были вставлены первыми, в результате чего было создано много сегментов, но коэффициент загрузки не достиг критического значения точки 1, и расширение не было запущено для облегчения этой ситуации. После этого удалите элементы, чтобы уменьшить общее количество элементов, и вставьте много элементов, что приведет к созданию множества переполненных сегментов, но это не нарушит положения пункта 1. Что вы можете сделать со мной? Количество переполнения бакетов слишком велико, что приводит к разбросу ключей и пугающей неэффективности поиска и вставки, поэтому вводится пункт 2. Это как город-призрак, где много домов, но мало дворов, они разбросаны и найти людей очень сложно.
Для ограничений условий попадания 1 и 2 произойдет расширение. Однако стратегии экспансии неодинаковы, ведь два условия имеют дело с разными сценариями.
Для условия 1 слишком много элементов и слишком мало сегментов Это очень просто: прибавьте 1 к B, и максимальное количество сегментов (2^B) сразу станет вдвое больше исходного количества сегментов. Итак, есть новые и старые ведра. Обратите внимание, что в настоящее время все элементы находятся в старом сегменте и не были перенесены в новый сегмент. Более того, новое ведро просто имеет максимальное число, в 2 раза превышающее исходное максимальное число (2 ^ B) (2 ^ B * 2).
Для условия 2 элементов не так много, но количество переполненных сегментов особенно велико, что указывает на то, что многие сегменты не заполнены. Решение состоит в том, чтобы открыть новое пространство корзины и переместить элементы из старой корзины в новую корзину, чтобы ключи в той же корзине располагались более близко друг к другу. Таким образом получается, что ключ в переливном ведре можно переместить в ведро. Результатом является экономия места, улучшение использования корзины и, естественно, повышение эффективности поиска и вставки карты.
Для решения условия 2 в блоге Цао Да также предложен крайний случай: если хэши ключей, вставленные в карту, одинаковые, то они попадут в один и тот же бакет, а если их больше 8, то будут сгенерированы бакеты переполнения, и результат тоже будет тот же, это вызовет слишком много переполненных сегментов. Перемещение элементов не может решить проблему, потому что в это время вся хэш-таблица выродилась в связанный список, а эффективность работы сталаO(n).
Давайте подробно рассмотрим, как происходит расширение. Поскольку при расширении карты необходимо переместить исходный ключ/значение на новый адрес памяти, если необходимо переместить большое количество ключей/значений, это сильно повлияет на производительность. Таким образом, расширение карты Go использует метод, называемый «прогрессивным».Исходный ключ не будет перемещаться за один раз, и каждый раз будет перемещаться только 2 сегмента.
сказано вышеhashGrow()На самом деле функция не «перемещается», она просто выделяет новые сегменты и прикрепляет старые сегменты к полю oldbuckets. Реальный шаг к перемещению ведер находится вgrowWork()функция, при вызовеgrowWork()Действие функции находится в функциях mapassign и mapdelete. То есть при вставке, изменении или удалении ключа он попытается переместить сегменты. Во-первых, проверьте, не было ли перемещено хранилище oldbuckets, в частности, проверьте, равно ли значение oldbuckets нулю.
давайте сначала посмотримhashGrow()Работа, проделанная функцией, давайте посмотрим, как выполняется конкретное перемещение сегментов.
func hashGrow(t *maptype, h *hmap) {
// B+1 相当于是原来 2 倍的空间
bigger := uint8(1)
// 对应条件 2
if !overLoadFactor(int64(h.count), h.B) {
// 进行等量的内存扩容，所以 B 不变
bigger = 0
h.flags |= sameSizeGrow
}
// 将老 buckets 挂到 buckets 上
oldbuckets := h.buckets
// 申请新的 buckets 空间
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger)
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
// 提交 grow 的动作
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
// 搬迁进度为 0
h.nevacuate = 0
// overflow buckets 数为 0
h.noverflow = 0
// ……
}
Основная причина заключается в том, чтобы подать заявку на новое пространство сегментов и обработать соответствующие биты флага: например, флаг nevacuate установлен на 0, указывая, что текущий прогресс перемещения равен 0.
Стоит сказать даh.flagsобработка:
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
Здесь мы должны говорить об операторе: &^. это называется按位置 0оператор. Например:
x = 01010011
y = 01010100
z = x &^ y = 00000011
Если бит y равен 1, то бит, соответствующий z, равен 0, в противном случае бит, соответствующий z, имеет то же значение, что и бит, соответствующий x.
Таким образом, приведенный выше абзац кода для работы с флагами означает: сначала очистить соответствующие биты итератора и старого итератора в h.flags до 0, а затем, если бит итератора равен 1, то передать его биту старого итератора, сделав старый итератор бит флага становится равным 1. Подтекст такой: бакеты теперь под именем oldBuckets, и соответствующие флаги тоже надо перенести.
Вот несколько флагов:
// 可能有迭代器使用 buckets
iterator = 1
// 可能有迭代器使用 oldbuckets
oldIterator = 2
// 有协程正在向 map 中写入 key
hashWriting = 4
// 等量扩容（对应条件 2）
sameSizeGrow = 8
Давайте взглянем на функциюrowWork(), которая фактически выполняет работу по перемещению.
func growWork(t *maptype, h *hmap, bucket uintptr) {
// 确认搬迁老的 bucket 对应正在使用的 bucket
evacuate(t, h, bucket&h.oldbucketmask())
// 再搬迁一个 bucket，以加快搬迁进程
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}
Функция h.growing() очень проста:
func (h *hmap) growing() bool {
return h.oldbuckets != nil
}
еслиoldbucketsЕсли он не пуст, значит, перемещение не было завершено и необходимо продолжить перемещение.
bucket&h.oldbucketmask()Эта строка кода, как указано в комментариях к исходному коду, предназначена для подтверждения того, что перемещенное ведро — это то, которое мы используем.oldbucketmask()Функция возвращает маску сегмента карты перед масштабированием.
Так называемая маска ведра используется для добавления хеш-значения, вычисленного по ключу, к маске ведра, а результатом является ведро, в которое должен попасть ключ. Например, B = 5, тогда младшие 5 битов маски ведра равны11111, остальные биты0, комбинация хеш-значения и это означает, что только младшие 5 бит хэш-значения определяют, в какое ведро попадает ключ.
Далее мы сосредоточим все наши усилия на перемещении ключа с функцией эвакуации. Исходный код выложен ниже, не нервничайте, я добавлю большую площадь комментариев, которые точно можно будет понять по комментариям. Я расскажу подробнее о процессе переезда позже.
Исходный код выглядит следующим образом:
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
// 定位老的 bucket 地址
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
// 结果是 2^B，如 B = 5，结果为32
newbit := h.noldbuckets()
// key 的哈希函数
alg := t.key.alg
// 如果 b 没有被搬迁过
if !evacuated(b) {
var (
// 表示bucket 移动的目标地址
x, y *bmap
// 指向 x,y 中的 key/val
xi, yi int
// 指向 x，y 中的 key
xk, yk unsafe.Pointer
// 指向 x，y 中的 value
xv, yv unsafe.Pointer
)
// 默认是等 size 扩容，前后 bucket 序号不变
// 使用 x 来进行搬迁
x = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
xi = 0
xk = add(unsafe.Pointer(x), dataOffset)
xv = add(xk, bucketCnt*uintptr(t.keysize))、
// 如果不是等 size 扩容，前后 bucket 序号有变
// 使用 y 来进行搬迁
if !h.sameSizeGrow() {
// y 代表的 bucket 序号增加了 2^B
y = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
yi = 0
yk = add(unsafe.Pointer(y), dataOffset)
yv = add(yk, bucketCnt*uintptr(t.keysize))
}
// 遍历所有的 bucket，包括 overflow buckets
// b 是老的 bucket 地址
for ; b != nil; b = b.overflow(t) {
k := add(unsafe.Pointer(b), dataOffset)
v := add(k, bucketCnt*uintptr(t.keysize))
// 遍历 bucket 中的所有 cell
for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
// 当前 cell 的 top hash 值
top := b.tophash[i]
// 如果 cell 为空，即没有 key
if top == empty {
// 那就标志它被"搬迁"过
b.tophash[i] = evacuatedEmpty
// 继续下个 cell
continue
}
// 正常不会出现这种情况
// 未被搬迁的 cell 只可能是 empty 或是
// 正常的 top hash（大于 minTopHash）
if top < minTopHash {
throw("bad map state")
}
k2 := k
// 如果 key 是指针，则解引用
if t.indirectkey {
k2 = *((*unsafe.Pointer)(k2))
}
// 默认使用 X，等量扩容
useX := true
// 如果不是等量扩容
if !h.sameSizeGrow() {
// 计算 hash 值，和 key 第一次写入时一样
hash := alg.hash(k2, uintptr(h.hash0))
// 如果有协程正在遍历 map
if h.flags&iterator != 0 {
// 如果出现 相同的 key 值，算出来的 hash 值不同
if !t.reflexivekey && !alg.equal(k2, k2) {
// 只有在 float 变量的 NaN() 情况下会出现
if top&1 != 0 {
// 第 B 位置 1
hash |= newbit
} else {
// 第 B 位置 0
hash &^= newbit
}
// 取高 8 位作为 top hash 值
top = uint8(hash >> (sys.PtrSize*8 - 8))
if top < minTopHash {
top += minTopHash
}
}
}
// 取决于新哈希值的 oldB+1 位是 0 还是 1
// 详细看后面的文章
useX = hash&newbit == 0
}
// 如果 key 搬到 X 部分
if useX {
// 标志老的 cell 的 top hash 值，表示搬移到 X 部分
b.tophash[i] = evacuatedX
// 如果 xi 等于 8，说明要溢出了
if xi == bucketCnt {
// 新建一个 bucket
newx := h.newoverflow(t, x)
x = newx
// xi 从 0 开始计数
xi = 0
// xk 表示 key 要移动到的位置
xk = add(unsafe.Pointer(x), dataOffset)
// xv 表示 value 要移动到的位置
xv = add(xk, bucketCnt*uintptr(t.keysize))
}
// 设置 top hash 值
x.tophash[xi] = top
// key 是指针
if t.indirectkey {
// 将原 key（是指针）复制到新位置
*(*unsafe.Pointer)(xk) = k2 // copy pointer
} else {
// 将原 key（是值）复制到新位置
typedmemmove(t.key, xk, k) // copy value
}
// value 是指针，操作同 key
if t.indirectvalue {
*(*unsafe.Pointer)(xv) = *(*unsafe.Pointer)(v)
} else {
typedmemmove(t.elem, xv, v)
}
// 定位到下一个 cell
xi++
xk = add(xk, uintptr(t.keysize))
xv = add(xv, uintptr(t.valuesize))
} else { // key 搬到 Y 部分，操作同 X 部分
// ……
// 省略了这部分，操作和 X 部分相同
}
}
}
// 如果没有协程在使用老的 buckets，就把老 buckets 清除掉，帮助gc
if h.flags&oldIterator == 0 {
b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
// 只清除bucket 的 key,value 部分，保留 top hash 部分，指示搬迁状态
if t.bucket.kind&kindNoPointers == 0 {
memclrHasPointers(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset)
} else {
memclrNoHeapPointers(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset)
}
}
}
// 更新搬迁进度
// 如果此次搬迁的 bucket 等于当前进度
if oldbucket == h.nevacuate {
// 进度加 1
h.nevacuate = oldbucket + 1
// Experiments suggest that 1024 is overkill by at least an order of magnitude.
// Put it in there as a safeguard anyway, to ensure O(1) behavior.
// 尝试往后看 1024 个 bucket
stop := h.nevacuate + 1024
if stop > newbit {
stop = newbit
}
// 寻找没有搬迁的 bucket
for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
h.nevacuate++
}
// 现在 h.nevacuate 之前的 bucket 都被搬迁完毕
// 所有的 buckets 搬迁完毕
if h.nevacuate == newbit {
// 清除老的 buckets
h.oldbuckets = nil
// 清除老的 overflow bucket
// 回忆一下：[0] 表示当前 overflow bucket
// [1] 表示 old overflow bucket
if h.extra != nil {
h.extra.overflow[1] = nil
}
// 清除正在扩容的标志位
h.flags &^= sameSizeGrow
}
}
}
Комментарии к коду функции эвакуации очень четкие.По коду и комментариям легко понять весь процесс перемещения.Наберитесь терпения.
Цель перемещения — переместить старые корзины в новые корзины. Из предыдущего описания мы знаем, что для условия 1 количество новых бакетов удваивается, а для условия 2 количество новых бакетов такое же, как и раньше.
Для условия 1 при переходе со старых корзин на новые корзины, так как количество корзин остается неизменным, его можно перемещать по порядковому номеру, например, корзины, которые изначально были под номером 0, все равно будут помещены в корзины № 0 после переезд на новое место.
Для условия 2 все не так просто. Хэш ключа необходимо пересчитать, чтобы определить, в какое ведро он попадает. Например, исходное B = 5, после вычисления хэша ключа можно определить, в какое ведро он попадает, только взглянув на его младшие 5 бит. После расширения B становится равным 6, поэтому вам нужно посмотреть еще один бит, его младшие 6 бит определяют, на какое ведро попадает ключ. это называетсяrehash.
Следовательно, номер корзины ключа до и после перемещения может быть таким же, как исходный, или может быть добавлено 2 ^ B (исходное значение B) по сравнению с исходным, в зависимости от того, является ли 6-й бит хэша значение равно 0 или 1.
Разобравшись с изменением номера корзины выше, мы можем ответить на другой вопрос: почему карта обхода неупорядочена?
После расширения карты ключ будет перемещен, а ключи, которые изначально принадлежали одному корзине, после перемещения улетят (к серийному номеру корзины добавляется 2^B). Процесс обхода заключается в обходе сегментов по порядку и одновременном обходе ключей в сегменте по порядку. После переезда положение клавиш претерпело серьезные изменения, некоторые клавиши улетают на высокие ветки, а некоторые остаются на месте. Таким образом, результаты обхода карты не могут быть в исходном порядке.
Конечно, если у меня есть только жестко закодированная карта, я не буду вставлять или удалять карту, Само собой разумеется, что каждый раз, когда такая карта проходится, будет возвращена последовательность ключ/значение фиксированного порядка. Это правда, но Go избегает этой практики, потому что у начинающих программистов создается неправильное представление о том, что это обязательно произойдет, а в некоторых случаях может быть большой ошибкой.
Конечно, Go делает это еще лучше, когда мы обходим карту, мы не начинаем обход фиксированно с корзины 0. Каждый раз мы обходим из корзины со случайным значением порядкового номера, и со случайного порядкового номера этой корзины. начинает проходить. Таким образом, даже если вы являетесь жестко закодированной картой, простое ее перемещение вряд ли вернет фиксированную последовательность пар ключ/значение.
Еще одна вещь, с версии go 1.0 добавлена функция «результат перебора карты неупорядочен».
Еще один вопрос: Если после расширения B увеличивается на 1, это означает, что общее количество ведер в два раза больше исходного числа, а исходное ведро № 1 «делится» на два ведра.
Например, исходный B = 2, младшие 3 бита хэш-значения двух ключей в сегменте 1: 010, 110 соответственно. Поскольку исходное B = 2, младшие 2 бита10Решите, что они попадают в ведро 2, и теперь B становится 3, поэтому010,110в ведрах 2 и 6 соответственно.
Поняв это, мы будем использовать его позже, когда будем говорить об итерации карты.
Давайте поговорим о нескольких ключевых моментах в функции релокации:
Функция эвакуации завершает перемещение только одной корзины за раз, поэтому после обхода всех ячеек в этой корзине скопируйте ячейки со значением на новое место. Сегменты также связаны с сегментами переполнения, которые также необходимо переместить. Следовательно, будет два слоя петель, внешний слой проходит через ведро и переливное ведро, а внутренний слой проходит через все ячейки ведра. Такие циклы есть везде в исходном коде карты, и в них нужно разбираться досконально.
Части X и Y, упомянутые в исходном коде, на самом деле то, о чем мы говорим. Если емкость увеличивается до удвоенного исходного размера, количество сегментов будет удвоено. вторая половина ковшей называется частью Y. Ключ в сегменте может быть разделен на 2 сегмента: один в X-части и один в Y-части. Поэтому, прежде чем перемещать ячейку, вам нужно знать, к какой части относится ключ в ячейке. Это очень просто, пересчитайте хэш ключа в ячейке и "загляните" еще на один бит вперед, чтобы решить, в какую часть он попадает. Это также подробно объяснено ранее.
Есть частный случай: есть ключ, и каждый раз, когда для него вычисляется хэш, результат разный. Этот ключmath.NaN()результат, значитnot a number, тип float64. Когда он используется в качестве ключа карты, при перемещении он столкнется с проблемой: значение хеш-функции, вычисленное повторно, не совпадает с значением хеш-функции, рассчитанным при его вставке в карту!
Как вы могли подумать, одним из следствий этого является то, что этот ключ никогда не будет получен операцией Get! когда я используюm[math.NaN()]Когда оператор используется, результат не может быть найден. Этот ключ может появиться только тогда, когда он пересекает всю карту. Таким образом, вы можете вставить любое количествоmath.NaN()как ключ.
Когда переселение встречаетсяmath.NaN()Когда ключ установлен, только младший бит tophash определяет, выделяется ли он для части X или части Y (если расширение в 2 раза превышает исходное количество сегментов). Если младший значащий бит tophash равен 0, он назначается части X; если он равен 1, он назначается части Y.
Это достигается операцией значения tophash с вновь рассчитанным значением хеш-функции:
if top&1 != 0 {
// top hash 最低位为 1
// 新算出来的 hash 值的 B 位置 1
hash |= newbit
} else {
// 新算出来的 hash 值的 B 位置 0
hash &^= newbit
}
// hash 值的 B 位为 0，则搬迁到 x part
// 当 B = 5时，newbit = 32，二进制低 6 位为 10 0000
useX = hash&newbit == 0
На самом деле, я могу переместить такой ключ в любое ведро, но, конечно, мне еще нужно переместить его в два ведра на картинке деления выше. Но это выгодно, я объясню это подробно позже, когда буду говорить об итерации карты, достаточно знать, что пока она распределяется так.
После того как целевой ковш для перемещения определен, операцию перемещения выполнить проще. Скопируйте исходное значение ключа/значения в соответствующее место назначения.
Установите ключ в верхней части исходных ведер наevacuatedXилиevacuatedY, указывая на то, что он был перемещен в часть x или часть y новой карты. Tophash новой карты обычно занимает старшие 8 бит хеш-значения ключа.
Давайте взглянем на макрос изменений до и после расширения на рисунке ниже.
Перед расширением B = 2 всего имеется 4 сегмента, а lowbits представляет младший бит хеш-значения. Предположим, мы не обращаем внимания на другие корзины и фокусируемся на корзине 2. И если предположить, что переполнения слишком много, срабатывает равное расширение (соответствующее предыдущему условию 2).
После завершения расширения переполнение ведра исчезает, а ключи концентрируются в одном ведре, что более компактно и повышает эффективность поиска.
Предполагая, что запущено 2-кратное расширение, после завершения расширения ключи в старых сегментах разбиваются на 2 новых сегмента. Один в части x и один в части y. Основой являются младшие биты хеша. на новой карте0-3называется x часть,4-7называется частью у.
Обратите внимание, что на двух приведенных выше рисунках не учитывается перемещение других сегментов, что указывает на ситуацию после перемещения всех сегментов. На самом деле мы знаем, что переселение — это «постепенный» процесс, и переселение не будет завершено сразу. Поэтому во время процесса перемещения указатель oldbuckets по-прежнему будет указывать на старую []bmap, а значение tophash перемещенного ключа будет значением состояния, указывающим на перемещение ключа.
обход карты
Изначально процесс обхода карты относительно прост: пройтись по всем корзинам и висящим за ней переполненным корзинам, а затем по одной пройти по всем ячейкам в корзине. Каждое ведро содержит 8 ячеек, вынимаем ключ и значение из ячейки с ключом, и процесс завершен.
Однако реальность не так проста. Помните процесс расширения, о котором я говорил ранее? Процесс расширения не является атомарной операцией, он перемещает только до 2-х корзин за раз, поэтому, если операция расширения запущена, состояние карты будет находиться в промежуточном состоянии в течение длительного времени: некоторые корзины были перемещены в новые дома, а некоторые ведра до сих пор стоят на своих старых местах.
Следовательно, если обход происходит во время процесса расширения, он будет включать в себя процесс обхода старого и нового сегментов, что является трудностью.
Сначала я напишу простой пример кода, притворившись, что не знаю, какую функцию вызывает процесс обхода:
package main
import "fmt"
func main() {
ageMp := make(map[string]int)
ageMp["qcrao"] = 18
for name, age := range ageMp {
fmt.Println(name, age)
}
}
Выполнение заказа:
go tool compile -S main.go
Получить команду сборки. Я не буду объяснять это здесь построчно, вы можете прочитать предыдущие статьи, которые очень подробны.
Ключевые строки ассемблерного кода следующие:
// ......
0x0124 00292 (test16.go:9) CALL runtime.mapiterinit(SB)
// ......
0x01fb 00507 (test16.go:9) CALL runtime.mapiternext(SB)
0x0200 00512 (test16.go:9) MOVQ ""..autotmp_4+160(SP), AX
0x0208 00520 (test16.go:9) TESTQ AX, AX
0x020b 00523 (test16.go:9) JNE 302
// ......
Таким образом, в отношении итерации карты, базовая связь вызова функции ясна с первого взгляда. первый звонокmapiterinitФункция инициализирует итератор, а затем вызывает его в цикле.mapiternextФункция выполняет итерацию карты.
Определение структуры итератора:
type hiter struct {
// key 指针
key unsafe.Pointer
// value 指针
value unsafe.Pointer
// map 类型，包含如 key size 大小等
t *maptype
// map header
h *hmap
// 初始化时指向的 bucket
buckets unsafe.Pointer
// 当前遍历到的 bmap
bptr *bmap
overflow [2]*[]*bmap
// 起始遍历的 bucet 编号
startBucket uintptr
// 遍历开始时 cell 的编号（每个 bucket 中有 8 个 cell）
offset uint8
// 是否从头遍历了
wrapped bool
// B 的大小
B uint8
// 指示当前 cell 序号
i uint8
// 指向当前的 bucket
bucket uintptr
// 因为扩容，需要检查的 bucket
checkBucket uintptr
}
mapiterinitОн предназначен для инициализации и назначения полей в структуре хитера.
Как упоминалось ранее, даже если просматривается жестко запрограммированная карта, результаты каждый раз не соответствуют порядку. Ниже мы можем подробнее рассмотреть их реализацию.
// 生成随机数 r
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
r += uintptr(fastrand()) << 31
}
// 从哪个 bucket 开始遍历
it.startBucket = r & (uintptr(1)<<h.B - 1)
// 从 bucket 的哪个 cell 开始遍历
it.offset = uint8(r >> h.B & (bucketCnt - 1))
Например, В = 2, тогдаuintptr(1)<<h.B - 1Результат равен 3, а младшие 8 бит0000 0011, и с ним мы можем получить0~3серийный номер бакета; BucketCnt - 1 равно 7, младшие 8 бит0000 0111, сдвинув r вправо на 2 бита и добавив к нему 7, можно получить0~7количество ячеек.
Итак, вmapiternextФункция начнет обход с ячейки it.offset номер it.startBucket, достанет в ней ключ и значение и вернется в стартовую корзину для завершения процесса обхода.
Часть исходного кода относительно проста для понимания, особенно после понимания кода в предыдущих комментариях, нет необходимости читать эту часть кода снова. Итак, далее я объясню весь процесс обхода графически, надеясь быть ясным и легким для понимания.
Предположим, у нас есть карта, как показано на рисунке ниже.В начале B = 1, есть два сегмента, а затем срабатывает расширение (здесь не вдавайтесь в условия расширения, просто настройка), и B становится 2. И содержимое корзины № 1 было перемещено в новую корзину,1 号расщепление на1 号и3 号;0 号Ковш до сих пор не перемещен. старое ведро висит*oldbucketsНад указателем висит новое ведро*bucketsнад указателем.
В этот момент мы пересекаем эту карту. Предположим, после инициализации startBucket = 3, offset = 2. Следовательно, отправной точкой обхода будет ячейка № 2 корзины № 3. На следующей картинке показано состояние при запуске обхода:
Красная метка указывает начальную позицию, а порядок обхода ковша: 3 -> 0 -> 1 -> 2.
Поскольку ведро № 3 соответствует старому ведру № 1, сначала проверьте, не было ли перемещено старое ведро № 1. Метод суждения таков:
func evacuated(b *bmap) bool {
h := b.tophash[0]
return h > empty && h < minTopHash
}
Если значение b.tophash[0] находится в диапазоне значений флага, то есть в интервале (0,4), это означает, что он был перемещен.
empty = 0
evacuatedEmpty = 1
evacuatedX = 2
evacuatedY = 3
minTopHash = 4
В этом примере старое ведро 1 было перемещено. Таким образом, его значение tophash[0] находится в диапазоне (0,4), так что просто пройдите через новое ведро номер 3.
Пройдите по очереди ячейки корзины 3 и затем найдите первый непустой ключ: элемент e. В этот момент функция mapiternext возвращает значение, и наш результат обхода имеет только один элемент:
Поскольку возвращенный ключ не пуст, функция mapiternext будет продолжать вызываться.
Продолжайте обход с последнего обхода и найдите элемент f и элемент g из нового переливного ведра №3.
Обход результирующего набора также растет:
После прохождения нового ковша № 3 он возвращается в новый ковш № 0. Ковш 0 соответствует старому ковшу 0. После проверки старый ковш 0 не перемещался, поэтому обход нового ковша 0 меняется на обход старого ковша 0. Это достает все ключи в старом ведре № 0?
Это не так просто, вспомним, что старая корзина 0 после перемещения разделится на 2 корзины: новую 0 и новую 2. И то, что мы проходим в это время, — это только новое ведро № 0 (обратите внимание, что обход — это весь обход).*bucketуказатели, так называемые новые ведра). Поэтому мы будем извлекать только те ключи из старого сегмента 0, которые назначены новому сегменту 0 после деления.
следовательно,lowbits == 00войдет в набор результатов обхода:
Как и в предыдущем процессе, продолжайте обход новой корзины № 1 и обнаружите, что старая корзина № 1 была перемещена, просто пройдитесь по существующим элементам в новой корзине № 1. Результирующий набор становится:
Продолжайте пересекать новое ведро № 2, которое происходит от старого ведра № 0, поэтому нужны ключи в старом ведре № 0, которые будут разделены на новое ведро № 2, то естьlowbit == 10эти ключи.
Таким образом, обход набора результатов становится:
Наконец, когда мы продолжим обход к новой корзине № 3, мы обнаружим, что все корзины пройдены, и весь процесс итерации завершен.
Кстати, если вы нажмете клавишу, этоmath.NaN()Этот вид обработки аналогичен. Ядро по-прежнему зависит от того, в какое ведро оно попадает после разделения. Просто посмотрите на самый младший бит его верхнего хеша. Если младший бит верхнего хеша равен 0, он назначается части X, если равен 1, он назначается части Y. На основании этого принимается решение о том, вынимать ли ключ и помещать его в набор результатов обхода.
Суть обхода карты заключается в том, чтобы понять, что при удвоении емкости старое ведро будет разделено на два новых ведра. Операция обхода будет выполняться в порядке порядкового номера новой корзины.Если старая корзина не перемещена, ключ для перемещения в новую корзину должен быть найден в старом корзине в будущем.
назначение карты
Как вы можете видеть из языка ассемблера, вставьте или измените ключ в карту, и окончательный вызов будетmapassignфункция.
Фактически синтаксис для вставки или изменения ключа такой же, за исключением того, что ключ для первой операции не существует в карте, а ключ для второй операции существует в карте.
mapassign имеет семейство функций, которые компилятор оптимизирует в соответствующие «быстрые функции» в зависимости от типа ключа.
| тип ключа | вставлять |
|---|---|
| uint32 | mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer |
| uint64 | mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer |
| string | mapassign_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer |
Мы изучаем только самые общие функции присваиванияmapassign.
В целом, процесс очень прост: вычислить хеш-значение для ключа и в соответствии с предыдущим процессом найти место, которое нужно назначить (может быть вставка нового ключа или обновление старого ключа), и назначить соответствующее место .
Исходный код в целом похож на то, что было упомянуто ранее, ядро по-прежнему представляет собой двухслойный цикл: внешний слой проходит по бакету и его переполненному бакету, а внутренний слой проходит по ячейкам всего бакета. Из-за нехватки места я не буду приводить комментарии к этой части кода, если вам интересно, вы можете прочитать его и убедиться, что сможете его понять после понимания содержания этой статьи.
Здесь я упомяну несколько важных моментов об этом процессе.
Функция сначала проверяет флаги карты. Если бит флага записи флагов в это время установлен в 1, это означает, что другие сопрограммы выполняют операцию «записи», что, в свою очередь, вызывает панику программы. Это также показывает, что карта небезопасна для сопрограмм.
Из предыдущей статьи мы знаем, что расширение происходит постепенно.Если карта находится в процессе расширения, когда ключ находится в ведре, необходимо убедиться, что старое ведро, соответствующее ведру, завершило процесс миграции . То есть ключи из старого сегмента должны быть перенесены в новый сегмент (разделены на 2 новых сегмента), прежде чем в новом сегменте можно будет выполнять операции вставки или обновления.
Операции, упомянутые выше, выполняются в начале функции, и только после завершения этой операции перемещения мы можем безопасно определить адрес, по которому ключ должен быть помещен в новое ведро, а затем выполнять последующие операции.
Теперь пришло время разместить ключ позиционирования, очень важно найти свое собственное положение. Подготовьте два указателя, один (inserti) указывает на расположение хэш-значения ключа в массиве tophash, другой (insertk) указывает на расположение ячейки (то есть адрес, по которому наконец помещается ключ), конечно, местоположение соответствующего значения легко найти. Эти три элемента на самом деле связаны: положение индекса в массиве tophash определяет положение ключа во всей корзине (всего 8 ключей), а положение значения должно «охватывать» длину 8 ключей.
Во время цикла вставки i и вставки k соответственно указывают на первую найденную свободную ячейку. Если ключ не найден в карте позже, то есть в исходной карте такого ключа нет, значит, вставлен новый ключ. Адрес размещения финального ключа — это «пустая позиция», найденная впервые (тофаш пуст).
Если все 8 ключей этого ведра заполнены, то после выскока из цикла обнаруживается, что и вставки и вставки пусты В это время нужно повесить за ведром переливное ведро. Конечно, за переливным ведром также можно повесить еще одно переливное ведро. Это означает, что в это ведро попало слишком много хэшей ключей.
Перед официальным размещением ключа проверьте состояние карты, чтобы увидеть, не нужно ли ее расширить. Если условия расширения соблюдены, операция расширения будет активно запущена.
После этого весь предыдущий процесс поиска и определения местоположения ключа должен быть выполнен снова. Потому что после расширения изменилось распределение ключей.
Наконец, значения, связанные с картой, будут обновлены.Если вставить новый ключ, значение счетчика количества элементов в карте будет увеличено на 1, оно установлено в начале функции.hashWritingЗапись флага очистит его.
Также стоит отметить важный момент. Упомянутая выше позиция поиска ключа и выполнения операции присваивания на самом деле неточна. мы видимmapassignПрототип функции знает, что функция не передает значение value, поэтому когда выполняется операция присваивания?
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
Ответ должен быть найден на языке ассемблера. Я раскрою ответ напрямую, если вам интересно, вы можете изучить его в частном порядке.mapassignУказатель, возвращаемый функцией, представляет собой позицию значения, соответствующую указываемой клавише.С адресом легко работать и назначать.
удаление карты
Базовая функция выполнения операции записиmapdelete:
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)
В зависимости от типа ключа операции удаления оптимизированы для более конкретных функций:
| тип ключа | Удалить |
|---|---|
| uint32 | mapdelete_fast32(t *maptype, h *hmap, key uint32) |
| uint64 | mapdelete_fast64(t *maptype, h *hmap, key uint64) |
| string | mapdelete_faststr(t *maptype, h *hmap, ky string) |
Конечно, мы заботимся только оmapdeleteфункция. Сначала он проверяет флаг h.flags, и если обнаруживает, что флаг записи равен 1, сразу же вызывает панику, потому что это указывает на то, что другие сопрограммы записывают в то же время.
Вычислите хэш ключа и найдите ведро, в которое он попадает. Проверьте, находится ли эта карта в процессе расширения, и непосредственно инициируйте операцию перемещения.
Операция удаления также является двухуровневым циклом, и ядром является поиск конкретного местоположения ключа. Процесс поиска аналогичен поиску ячейки за ячейкой в корзине.
Найдя соответствующую позицию, выполните «нулевую» операцию над ключом или значением:
// 对 key 清零
if t.indirectkey {
*(*unsafe.Pointer)(k) = nil
} else {
typedmemclr(t.key, k)
}
// 对 value 清零
if t.indirectvalue {
*(*unsafe.Pointer)(v) = nil
} else {
typedmemclr(t.elem, v)
}
Наконец, вычтите 1 из значения счетчика и установите значение tophash соответствующей позиции равнымEmpty.
Этот исходный код также относительно прост, не стесняйтесь смотреть на код напрямую.
расширенная карта
Можно ли удалять во время обхода?
map не является потокобезопасной структурой данных. Чтение и запись карты в одно и то же время — это поведение undefined, и если оно будет обнаружено, оно сразу вызовет панику.
В общем случае это решается блокировками чтения-записи:sync.RWMutex.
позвонил перед чтениемRLock()функция, вызываемая после чтенияRUnlock()функция разблокировки; вызывается перед записьюLock()функция, после написания, вызовUnlock()Разблокировать.
Кроме того,sync.Mapявляется поточно-ориентированной картой, которую также можно использовать. Принцип его реализации в этот раз не скажу.
Может ли ключ быть типа float?
Грамматически да. В языке Go в качестве ключа может использоваться любой сравнимый тип. За исключением фрагмента, карты, функций, другие типы в порядке. В частности, сюда входят: логические значения, числа, строки, указатели, каналы, типы интерфейсов, структуры и массивы, содержащие только указанные выше типы. Общей чертой этих типов является то, что они поддерживают==и!=оператор,k1 == k2, k1 и k2 можно считать одним и тем же ключом. Если это структура, значения ее полей должны быть равны, чтобы считаться одним и тем же ключом.
Кстати, в качестве значения можно использовать любой тип, в том числе и тип карты.
Давайте посмотрим пример:
func main() {
m := make(map[float64]int)
m[1.4] = 1
m[2.4] = 2
m[math.NaN()] = 3
m[math.NaN()] = 3
for k, v := range m {
fmt.Printf("[%v, %d] ", k, v)
}
fmt.Printf("\nk: %v, v: %d\n", math.NaN(), m[math.NaN()])
fmt.Printf("k: %v, v: %d\n", 2.400000000001, m[2.400000000001])
fmt.Printf("k: %v, v: %d\n", 2.4000000000000000000000001, m[2.4000000000000000000000001])
fmt.Println(math.NaN() == math.NaN())
}
Вывод программы:
[2.4, 2] [NaN, 3] [NaN, 3] [1.4, 1]
k: NaN, v: 0
k: 2.400000000001, v: 0
k: 2.4, v: 2
false
В примере определяется карта с типом ключа float, и в нее вставляются 4 ключа: 1.4, 2.4, NAN, NAN.
При печати тоже печатает 4 ключа, если знать, что NAN != NAN, то не удивительно. Поскольку результаты их сравнения не равны, естественно, в представлении карты это два разных ключа.
Затем мы запросили несколько ключей и обнаружили, что NAN не существует, как и 2.4000000000000000000000000001, но 2.4000000000000000000000001 существует.
Как-то странно, не так ли?
Далее я нашел следующие факты через сборку:
При использовании float64 в качестве ключа сначала преобразуйте его в тип unit64, а затем вставьте в ключ.
Конкретно черезFloat64frombitsФункция завершается:
// Float64frombits returns the floating point number corresponding
// the IEEE 754 binary representation b.
func Float64frombits(b uint64) float64 { return *(*float64)(unsafe.Pointer(&b)) }
То есть число с плавающей запятой представляется в формате, определенном IEEE 754. Например, оператор присваивания:
0x00bd 00189 (test18.go:9) LEAQ "".statictmp_0(SB), DX
0x00c4 00196 (test18.go:9) MOVQ DX, 16(SP)
0x00c9 00201 (test18.go:9) PCDATA $0, $2
0x00c9 00201 (test18.go:9) CALL runtime.mapassign(SB)
"".statictmp_0(SB)Переменные такие:
"".statictmp_0 SRODATA size=8
0x0000 33 33 33 33 33 33 03 40
"".statictmp_1 SRODATA size=8
0x0000 ff 3b 33 33 33 33 03 40
"".statictmp_2 SRODATA size=8
0x0000 33 33 33 33 33 33 03 40
Давайте снова выведем что-нибудь:
package main
import (
"fmt"
"math"
)
func main() {
m := make(map[float64]int)
m[2.4] = 2
fmt.Println(math.Float64bits(2.4))
fmt.Println(math.Float64bits(2.400000000001))
fmt.Println(math.Float64bits(2.4000000000000000000000001))
}
4612586738352864255
4612586738352862003
4612586738352862003
Преобразуется в шестнадцатеричный как:
0x4003333333333333
0x4003333333333BFF
0x4003333333333333
и предыдущий"".statictmp_0Сравните, это довольно ясно.2.4и2.4000000000000000000000001проходить черезmath.Float64bits()Результат преобразования функции тот же. Естественно, с точки зрения карты это один и тот же ключ.
Давайте еще раз посмотрим на NAN (не число):
// NaN returns an IEEE 754 ``not-a-number'' value.
func NaN() float64 { return Float64frombits(uvnan) }
уван определяется как:
uvnan = 0x7FF8000000000001
NAN() вызывается напрямуюFloat64frombits, передать жестко закодированную константную переменную0x7FF8000000000001, чтобы получить значение типа NAN. Поскольку NAN анализируется из константы, почему при вставке в карту он считается другим ключом?
Это определяется хеш-функцией типа, например, для 64-битных чисел с плавающей запятой ее хеш-функция выглядит следующим образом:
func f64hash(p unsafe.Pointer, h uintptr) uintptr {
f := *(*float64)(p)
switch {
case f == 0:
return c1 * (c0 ^ h) // +0, -0
case f != f:
return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN
default:
return memhash(p, h, 8)
}
}
Второй случай,f != fнацелен наNAN, здесь будет добавлено случайное число.
Таким образом решаются все загадки.
Благодаря свойствам НАН:
NAN != NAN
hash(NAN) != hash(NAN)
Поэтому, когда искомый в карте ключ NAN, ничего не может быть найдено, если к нему добавить 4 NAN, то обход получит 4 NAN.
Наконец, вывод: тип float можно использовать в качестве ключа, но из-за проблемы точности это приведет к некоторым странным проблемам, поэтому используйте его с осторожностью.
Суммировать
На момент написания этой статьи есть несколько вопросов, которые я прочитал во всех блогах китайского мира и не могу найти ответы. Конечно, исходный код может ответить на любой вопрос. Тем не менее, вы не можете сразу перейти к деталям исходного кода, вы должны сначала получить общее представление.
Итак, я начал искать англоязычные статьи об исходном коде, но их немного. Но я нашел качественную статью и поместил ее в первую статью справочного материала, она ведет читателя к оптимизации шаг за шагом, и наконец реализует случайный ключ с карты. Рекомендую к прочтению, очень увлекательно. Особенно после того, как вы знаете конкретный процесс базового обхода и расширения карты.
Подводя итог, в языке Go карта реализована с помощью таблицы поиска хэшей, а коллизия хэшей решается методом связанного списка.
Ключ разбросан по разным корзинам по хеш-значению ключа, и в каждой корзине 8 ячеек. Младшие биты хеш-значения определяют порядковый номер корзины, а старшие биты определяют разные ключи в одной и той же корзине.
Когда в ведро добавляется много ключей, что приводит к слишком большому количеству элементов или слишком большому переполнению ведра, расширение будет запущено. Расширение емкости делится на равное расширение емкости и двукратное расширение емкости. После расширения ключи в исходной корзине делятся на две части и переназначаются на две корзины.
Процесс расширения является постепенным, главным образом, чтобы предотвратить количество ключей, которые необходимо переместить для одного расширения и вызвать проблемы с производительностью. Время запуска расширения — это добавление новых элементов, а время перемещения корзины — во время назначения и удаления, и каждый раз перемещается максимум две корзины.
Очень важным содержанием поиска, присвоения и удаления является то, как определить местоположение ключа, что необходимо понять. После понимания можно понять исходный код карты.
Наконец, если статья оказалась для вас полезной, пожалуйста, помогите мне поделиться ею или нажмите, чтобы прочитать, спасибо!
Наконец, нажмитечитать оригинал, вы можете стать свидетелем тысячезвездочного проекта с нуля.
использованная литература
[английский, как случайным образом выбрать ключ карты, очень увлекательно]Приюты Люка.com/hackmap.htm…
[Википедия для карты]En. Wikipedia.org/wiki/assoc i…
[анализ исходного кода sync.map]GitHub.com/cha die NY/B…
[Блок-схема различных операций, связанных с картой]woo woo Краткое описание.com/afraid/ahah 0's 4808 from…
[анализ исходного кода карты]Woohoo. Блог TW на .net/ah/5 Baidu 78, 2 из 5…
[Статья Цао Да о карте не нуждается в пояснениях]GitHub.com/часто123/потяните…
【английский с картинками】Woohoo. AR, но labs.com/blog/2013/1…
[английский сравнивает реализацию карты java и c++]Дэйв.Чейни.net/2018/05/29/…
【почему го карта чувствительна к конкуренции】Dave.Cheney.net/2015/12/07/…
【Карта блога Golang】blog.golang.org/go-maps-in-…
[случайная карта с открытым исходным кодом]GitHub.com/Люк Чай Известный…
【Картинка хорошая】Hashtag.com/article/153…
[Проблема ночного чтения]GitHub.com/developer - Приходите...
[Недавно обнаруженный блог, очень глубокий]D Raven ES это What/go wave-Hashi...
[Процесс расширения + схема]no.OSCHINA.net/люди где/блог/…
【Оператор】nuggets.capable/post/684490…
【английский】woohoo.digital ocean.com/community/he…
[простое объяснение исходного кода обхода карты]перейти cn.VIP/article/170…
[Короткий текст, можно одновременно перемещаться и удалять ключи]cloud.Tencent.com/developer/ ах…
[Программирование, ориентированное на веру, диапазон golang]D Raven ES есть.
[Разница между слайсом и картой как параметрами]stackoverflow.com/questions/4…
[Перейдите в официальный блог о карте]blog.golang.org/go-maps-in-…
[Совместимые типы в языке Go]gowave.org/hotwind/spec#co…
【тип ключа】Lanlingzi.Вы можете /пост/специальность…
[Сравнение производительности хэш-функции]aras-afraid.info/blog/2016/0…
[Выбор хэш-функции, сравнение C++/Java]изучите golang.com/articles/15…
[срез и карта как параметры функции]stackoverflow.com/questions/4…
[Карта блога босса жареной рыбы1]GitHub.com/Эдди C JY/Нет…
[Карта блога босса жареной рыбы2]GitHub.com/Эдди C JY/Нет…
[Определение хэш-функции]Чжан Шуай.Люди/2018/05/16/…
[Как сравнить две карты на равенство]golangbot.com/maps/
【НАН-хеш】research.swtch.com/randhash
[Объяснение параллельной безопасности]Для этого есть место GitHub.IO/post/в это время/иди сюда…