В предыдущем разделе мы представилиКак работают массивы и срезыВ этом разделе Golang познакомится с другим набором элементов — хэшем, который является реализацией принципа Map; помимо хеш-таблицы, это массив самой распространенной структуры данных, почти во всем языке будет массив и хеш. table два элемента набора, язык и некоторые из них будут реализованы в виде массива списков, некоторые из которых известны как хэш-таблица или структура словаря, но на самом деле они представляют собой две идеи дизайна: набор элементов массива, используемых для представления последовательности элементов, хэш представляет отношение сопоставления между парами ключ-значение, но вызывается, и язык реализации немного отличается.
Обзор
хеш-таблицаЭто древняя структура данных.В 1953 году кто-то использовал метод zip для реализации хеш-таблицы.Он может напрямую обращаться к месту хранения в памяти по ключу (Key), а это значит, что мы можем напрямую найти соответствующий ключ через значение, источником имени хеш-таблицы является то, что она использует хеш-функцию для сопоставления ключа с сегментом, который может содержать значение, соответствующее этому ключу.
хэш-функция
Ключом к реализации хеш-таблицы является выбор хеш-функции. Выбор хеш-функции может в значительной степени определить производительность чтения и записи хэш-таблицы. В идеале хэш-функция должна иметь возможность сопоставлять разные ключи с уникальными Однако количество наборов ключей будет намного больше, чем диапазон сопоставления, и разные ключи должны возвращать уникальные значения после обработки хеш-функцией, что требуетВыходной диапазон хеш-функции больше, чем входной диапазон, поэтому в реальном использовании этого идеального состояния достичь невозможно.
Более практичный способ — сделать результаты хеш-функции равномерно распределенными, так что, хотя хеш-функция будет сталкиваться и сталкиваться, нам нужно только решить проблему хеш-коллизии, чтобы использовать это более практичное решение в инженерии. вызвать больше столкновений и привести к ухудшению производительности.
В хэш-функции с относительно однородными результатами добавление, удаление, изменение и проверка хэшей требуют временной сложности O(1), но очень неравномерная хэш-функция приведет к тому, что все операции будут занимать наихудшую сложность O(n), поэтому очень важно использовать хорошую хэш-функцию в хеш-таблице.
Решение конфликта
Как мы упоминали ранее, в нормальных условиях диапазон ввода хеш-функции должен быть намного больше, чем диапазон вывода, поэтому мы обязательно столкнемся с конфликтами в процессе использования хеш-таблицы, если это не так. Идеальная хэш-функция с коллизиями , то нам фактически нужно только хранить все значения в одномерном массиве.
Как уже упоминалось выше, этот сценарий в принципе не существует в реальности.Наши хеш-функции часто несовершенны и диапазон вывода ограничен, что обязательно произойдет.Столкновение, нам нужно использовать некоторые методы для решения проблемы коллизии хэшей, общие из них метод открытой адресации и метод застежки-молнии.
открытая адресация
открытая адресацияЭто метод решения хэш-столкновений в хэш-таблице. Основная идея этого методаЭто обнаружение и сравнение элементов в одномерном массиве, чтобы определить, существует ли искомый целевой ключ в текущей хеш-таблице., если мы используем открытый метод адресации для реализации хеш-таблицы, то новый массив будет создан при инициализации хеш-таблицы.Если возник конфликт, когда мы записываем новые данные в текущую «хэш-таблицу», он будет запишите пару ключ-значение в следующее ненулевое место:
На приведенном выше рисунке показано, что когда ключ Key3 конфликтует с двумя ключами Key1 и Key2, которые были сохранены в «Хеш-таблице», Key3 будет автоматически записан в свободную память после Key2, а затем мы будем читать Key3 Когда соответствующее значение используется, ключ будет хеширован и проиндексирован до Ключа 1. Если целевой ключ и Ключ 1 сравниваются и обнаруживаются несоответствия, следующие элементы будут считываться до тех пор, пока память не станет пустой или не будет найден целевой элемент.
Когда мы ищем данные, соответствующие ключу, мы выполним линейное обнаружение памяти, на которую попал хэш, и нахождение целевой пары ключ-значение или пустой памяти означает конец этой операции запроса.
Открытый метод адресации оказывает наибольшее влияние на производительность.коэффициент загрузки, которое является отношением количества элементов в массиве к размеру массива.С увеличением коэффициента загрузки среднее время линейного обнаружения будет постепенно увеличиваться, что повлияет на производительность поиска и вставки хеш-таблицы в то же время.Когда скорость загрузки превышает 70% После этого производительность хеш-таблицы резко упадет, и как только скорость загрузки достигнет 100%, вся хэш-таблица будет полностью недействительна, поэтому вы всегда должны обращать внимание на изменение коэффициента загрузки при реализации хеш-таблицы.
молния метод
По сравнению с методом открытого адреса, метод застежки-молнии является наиболее распространенным методом реализации в хэш-таблице.Большинство языков программирования используют метод застежки-молнии для реализации хэш-таблицы.Его реализация относительно проста, средняя длина поиска относительно коротка, Память, используемая для каждого узла хранения, применяется динамически, что может сэкономить много места для хранения.
Реализация метода zipper на самом деле заключается в использовании массива и связанного списка для реализации хэш-таблицы. Каждый элемент массива на самом деле представляет собой связанный список. Мы можем думать об этом как о расширяемом двумерном массиве:
Когда нам нужно добавить пару ключ-значение в хеш-таблицу, ключи в паре ключ-значение сначала будут проходить через хеш-функцию, а хеш, возвращаемый хеш-функцией, поможет нам «выбрать» ведро, а затем просмотреть текущую корзину. Удерживая связанный список, найдите пару ключ-значение с тем же ключом, чтобы выполнить операцию обновления, или перейдите в конец связанного списка, чтобы добавить новую пару ключ-значение.
Если вы хотите получить соответствующее значение в хеш-таблице с помощью ключа, вы пройдете следующий процесс:
Ключ 11 — это пример, который показывает ключ, которого нет в хэш-таблице. не находится в конце связанного списка, поэтому значение, соответствующее ключу, пусто.
В хеш-таблице с большей производительностью в каждой корзине должен быть 0 или 1 элемент, а иногда и 2-3 элемента.Редко можно встретить больше этого числа.Время хеш-таблицы в основном тратится на два процесса. поиска сегмента и обхода связанного списка. Если хэш-таблица с 1000 сегментов сохраняет 10 000 пар ключ-значение, ее производительность составляет 1/1 от сохранения 1000 пар ключ-значение. 10, но все же в 1000 раз лучше, чем связанный список.
инициализация
Теперь, когда мы представили некоторые основные принципы и методы реализации общих хеш-таблиц, мы можем начать знакомить с темой статьи, то есть с принципом реализации хэш-таблиц на языке Go.Первое, о чем нужно поговорить, это представление и инициализация хэшей в Go Два метода хеширования — через литералы и во время выполнения.
структура
Хеш-таблица в Golang находится вsrc/runtime/map.goСтруктура хеша определена в файлеhmapОн такой, есть несколько основных параметров:
type hmap struct {
count int
flags uint8
B uint8
noverflow uint16
hash0 uint32
buckets unsafe.Pointer
oldbuckets unsafe.Pointer
nevacuate uintptr
extra *mapextra
}
-
countОно используется для записи количества элементов в текущей хэш-таблице.Это поле позволяет нам больше не проходить всю хэш-таблицу для получения длины; -
BУказывает, что текущая хеш-таблица содержитbucketsОднако, поскольку расширение хеш-таблицы выполняется кратно 2, здесь для хранения будет использоваться логарифм, мы можем просто понять это какlen(buckets) == 2^B; -
hash0Это семя хэша.Это значение будет передано в качестве параметра при вызове хэш-функции.Его основная функция заключается в том, чтобы внести некоторую случайность в результат хеш-функции; -
oldbucketsХеш используется для сохранения перед масштабированиемbucketsполе, его размер является текущимbucketsполовина;
этоhmapСтруктура будет фактически существовать как во время компиляции, так и во время выполнения, и будет использоваться во время компиляции.hmapФункция строит идентичную структуру:
func hmap(t *types.Type) *types.Type {
bmap := bmap(t)
fields := []*types.Field{
makefield("count", types.Types[TINT]),
makefield("flags", types.Types[TUINT8]),
makefield("B", types.Types[TUINT8]),
makefield("noverflow", types.Types[TUINT16]),
makefield("hash0", types.Types[TUINT32]),
makefield("buckets", types.NewPtr(bmap)),
makefield("oldbuckets", types.NewPtr(bmap)),
makefield("nevacuate", types.Types[TUINTPTR]),
makefield("extra", types.Types[TUNSAFEPTR]),
}
hmap := types.New(TSTRUCT)
hmap.SetNoalg(true)
hmap.SetFields(fields)
dowidth(hmap)
t.MapType().Hmap = hmap
hmap.StructType().Map = t
return hmap
}
Поскольку большая часть кода во время выполнения не может быть выполнена во время компиляции, нам необходимо смоделироватьhmapСтруктура предоставляет «контейнер» для инициализации некоторых хэш-таблиц во время компиляции, поэтому, хотя хеш-таблица является специальной структурой данных, нижний слой все же должен использовать структуру для хранения некоторых данных для управления и записи.
буквальный
Если мы используем литеральный метод для инициализации хеш-таблицы в языке Go, очень похожем на другие языки, мы обычно используем следующий формат:
hash := map[string]int{
"1": 2,
"3": 4,
"5": 6,
}
Нам нужно пометить информацию о типе значения ключа при использовании хэша.Этот метод использования литеральной инициализации в конечном итоге пройдетmaplitФункция инициализирует переменную, после чего мы начинаем анализировать, как код выше передается при компиляции.maplitФункция инициализирована:
func maplit(n *Node, m *Node, init *Nodes) {
a := nod(OMAKE, nil, nil)
a.Esc = n.Esc
a.List.Set2(typenod(n.Type), nodintconst(int64(n.List.Len())))
litas(m, a, init)
var stat, dyn []*Node
for _, r := range n.List.Slice() {
stat = append(stat, r)
}
if len(stat) > 25 {
// ...
} else {
addMapEntries(m, stat, init)
}
}
Когда количество элементов в хеш-таблице меньше или равно 25, компилятор напрямую вызываетaddMapEntriesПреобразуйте литерально-инициализированную структуру в следующий код, добавляя все пары ключ-значение в хеш-таблицу по отдельности:
hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6
И если количество элементов в хеш-таблице превышает 25, во время компиляции создаются два массива для хранения информации о ключе и значении, и эти пары ключ-значение добавляются к целевому хэшу через цикл for следующим образом:
hash := make(map[string]int, 26)
vstatk := []string{"1", "2", "3", ... ， "26"}
vstatv := []int{1, 2, 3, ... , 26}
for i := 0; i < len(vstak); i++ {
hash[vstatk[i]] = vstatv[i]
}
Но независимо от того, какой метод используется, процесс использования литеральной инициализации будет использовать ключевые слова языка Go для инициализации нового хэша и передачи[]Синтаксис задает значение ключа в хэше. Конечно, сгенерированный здесь литерал для инициализации массива также будет расширен компилятором. Конкретный метод расширения и реализации см. в предыдущем разделе.Массивы и срезыУзнайте об этом.
Время выполнения
Используем ли мы его непосредственно в языке Gomakeили генерируется компиляторомmakeНа самом деле будетпроверка типовпериод преобразуется вmakemapфункция для создания хеш-таблицы:
func makemap(t *maptype, hint int, h *hmap) *hmap {
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
if overflow || mem > maxAlloc {
hint = 0
}
if h == nil {
h = new(hmap)
}
h.hash0 = fastrand()
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
Эта функция пройдетfastrandСоздайте случайное хэш-семя, затемhintРассчитайте минимально необходимое количество необходимых ведер, а затем используйтеmakeBucketArrayСоздайте массив для хранения ведер, этот метод фактически основан на входящемBРасчетное количество создаваемых сегментов выделяет непрерывное пространство в памяти для хранения данных.В процессе создания сегментов будут созданы дополнительные сегменты для хранения переполненных данных.Количество равно2^(B-4)Кусок.
Тип хеш-таблицы фактически хранится в каждой корзине, структура этой корзиныbmapНа самом деле определение в исходном коде языка Go содержит только простуюtophashПоле:
type bmap struct {
tophash [bucketCnt]uint8
}
Настоящая структура сегментов в хеш-таблице — это функция, которая запускается во время компиляции.bmapсоздается "динамическим" в:
func bmap(t *types.Type) *types.Type {
bucket := types.New(TSTRUCT)
keytype := t.Key()
valtype := t.Elem()
dowidth(keytype)
dowidth(valtype)
field := make([]*types.Field, 0, 5)
arr := types.NewArray(types.Types[TUINT8], BUCKETSIZE)
field = append(field, makefield("topbits", arr))
arr = types.NewArray(keytype, BUCKETSIZE)
keys := makefield("keys", arr)
field = append(field, keys)
arr = types.NewArray(valtype, BUCKETSIZE)
values := makefield("values", arr)
field = append(field, values)
if int(valtype.Align) > Widthptr || int(keytype.Align) > Widthptr {
field = append(field, makefield("pad", types.Types[TUINTPTR]))
}
otyp := types.NewPtr(bucket)
if !types.Haspointers(valtype) && !types.Haspointers(keytype) {
otyp = types.Types[TUINTPTR]
}
overflow := makefield("overflow", otyp)
field = append(field, overflow)
// ...
t.MapType().Bucket = bucket
bucket.StructType().Map = t
return bucket
}
Это потому, что язык Go будетНапрямую манипулировать пространством памяти,в то же времяИз-за разных типов значений ключа размер занимаемого пространства также отличается, что делает тип и занимаемую память неопределенными, поэтому нет возможности объявить это в исходном коде языка Go.
В соответствии с реализацией вышеуказанной функции мы можемbmapпровестиреконструкция:
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}
Ведро в каждой хеш-таблице может хранить не более 8 элементов.Если количество элементов, хранящихся в ведре, превышает 8, эффективность выполнения хэш-таблицы резко падает.Однако при реальном использовании, если хеш-таблица хранит данные постепенно увеличивается, мы будем расширять хэш-таблицу или использовать дополнительные сегменты для хранения переполненных данных, чтобы данные в одном сегменте не превышали 8:
Сегмент переполнения — это только временное решение, создание слишком большого количества сегментов переполнения в конечном итоге приведет к расширению хэша.
Среда выполнения языка Go выделяет пространство памяти для хеш-таблицы для хранения пар ключ-значение в хеш-таблице.Будь то структура хеша или структура ведра, она инициализируется во время выполнения, но последняя не хранится в исходном коде.Структура факта существует в коде, который представляет собой «виртуальную» структуру, сгенерированную с помощью кода.
действовать
В качестве структуры данных хеш-таблицы нам обязательно нужно изучить ее работу, то есть принцип реализации различных операций чтения и записи.Когда мы говорим о чтении хеш-таблицы, она обычно читается с помощью подписки и обхода. данные, хранящиеся в структуре данных:
_ = hash[key]
for k, v := range hash {
// k, v
}
Хотя оба эти метода считывают данные из хеш-таблицы, используемые функции полностью отличаются от лежащих в их основе принципов: первый должен знать хэш-ключ и может иметь значение, соответствующее только одному ключу, а второй может проходить по хеш-коду. все пары ключ-значение, и вам не нужно заранее знать соответствующие ключи при доступе к данным, мы представим в следующих главахrangeпринцип реализации.
Написание структур данных обычно относится к добавлению, удалению и изменению.Добавление и изменение полей осуществляется посредством индексации и присваивания, а удаление данных в словаре требует использования ключевых слов.delete:
hash[key] = value
hash[key] = newValue
delete(hash, key)
Мы обсудим эти различные операции одну за другой и дадим лежащие в их основе конкретные принципы реализации. Большинство этих операций реализуются во время компиляции и во время выполнения. Некоторые важные знания во время компиляции могут быть опущены в процессе введения. Можно прочитать предыдущие главы.Обзор процесса компиляцииПонимание процесса и принципов компиляции.
доступ
составлено впроверка типовэтап, все аналогичноhash[key]изOINDEXоперации превращаются вOINDEXMAPоперации, а затемГенерация промежуточного кодабудет вwalkexprгенерал-лейтенант этиOINDEXMAPОперация преобразуется в следующий код:
v := hash[key] // => v := *mapaccess1(maptype, hash, &key)
v, ok := hash[key] // => v, ok := mapaccess2(maptype, hash, &key)
Количество параметров, принятых в левой части оператора присваивания, также повлияет на параметры времени выполнения финального вызова.Когда принимается только один параметр, он будет использоватьсяmapaccess1функция, которая принимает как значение ключа, так и логическое значение, указывающее, существует ли ключmapaccess2функция,mapaccess1Функция просто возвращает указатель на целевое значение:
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
top := tophash(hash)
bucketloop:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
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])
}
Хэш-функция в этой функции, которую мы сначала настроим с помощью хеш-таблицы, получим текущий начальный ключ, соответствующий хешу, и черезbucketMaskиaddФункция получает корзину, в которой находится пара ключ-значение, и верхнее 8-значное число хэша. Эти 8-значные числа в конечном итоге совпадут со значением, хранящимся в корзине.tophashДля сравнения, каждое ведро фактически хранит 8tophash, то есть во время компиляцииtopbitsполе, каждый раз со всеми 8 в ведреuint8Для сравнения, 8-битныйtophashПо сути это как кеш первого уровня.В нем хранятся старшие 8 бит хеша, а маска сегмента используется для выбора младших битов.Этот метод может помочь нам быстро определить, является ли текущая пара ключ-значение не , Существует и уменьшает коллизии:
Каждое ведро представляет собой целый кусок пространства памяти, когда мы находим определенныйtopbitsс входящим ключомtophashКогда есть совпадение, получите ключ, хранящийся в хеше, через указатель и смещение, и сравните их, если они одинаковы, получите указатель целевого значения с помощью того же метода и верните.
Другой также используется для доступа к данным в хеш-таблице.mapaccess2Функция на самом деле простоmapaccess1На основе он также возвращает логическое значение, которое определяет, существуют ли текущие данные:
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
// ...
bucketloop:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// ...
if alg.equal(key, k) {
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
//...
return v, true
}
}
}
return unsafe.Pointer(&zeroVal[0]), false
}
использоватьv, ok := hash[k]При доступе к элементам хэш-таблицы в виде , мы можем более точно знать, когдаv == nil, является ли нулевой указатель элементом, хранящимся в хэше, или элемент, соответствующий ключу, не существует, поэтому при доступе к хэшу автор рекомендует использовать этот метод, чтобы сначала определить, существует ли элемент.
Вышеприведенный процесс на самом деле представляет собой производительность доступа к элементам в хеш-таблице в обычных условиях.Однако, как и массив, хеш-таблица может быть расширена, когда коэффициент загрузки слишком высок или область переполнения слишком велика.Как обеспечить производительность доступа во время расширения Это более интересная тема, и мы фактически опускаем здесь соответствующий код, но он будет представлен в разделе расширения ниже.
написать
когда в формеhash[k]Выражение появляется в левой части символа назначения, как когда чтение будет компилироватьпроверка типовиГенерация промежуточного кодапериод конвертируется в вызовmapassignВызов функции, мы можем разделить функцию на несколько частей, чтобы представить, во-первых, функция будет получать соответствующий хеш и ведро в соответствии с входящим ключом:
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
h.flags ^= hashWriting
again:
bucket := hash & bucketMask(h.B)
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
top := tophash(hash)
Затем сравните сохраненное в ведре, пройдяtophashИ хэш ключа, если будет найден тот же результат, будет получен и возвращен адрес целевого местоположения, независимо от того, ищет ли он ключ или значение, он будет напрямую адресован арифметическим вычислением:
var inserti *uint8
var insertk unsafe.Pointer
var val unsafe.Pointer
bucketloop:
for {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if isEmpty(b.tophash[i]) && inserti == nil {
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
}
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if !alg.equal(key, k) {
continue
}
val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
goto done
}
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}
Он будет вызываться, когда текущая хеш-таблица не находится в состоянии расширения, а коэффициент загрузки превышает 6,5 или слишком много переполненных сегментов.hashGrowРазверните текущую хеш-таблицу.
Коэффициент загрузки одновременно определяется
loadFactorNumиloadFactDenОпределяется двумя параметрами, первый определяется как 13 в исходном коде Go, а второй равен 2, поэтому коэффициент загрузки равен 6,5.
Если текущее ведро заполнено, оно будет вызваноnewoverflowСоздайте новое ведро или используйтеhmapзаблаговременноnoverflowВедро, созданное в ведре для сохранения данных, указатель вновь созданного ведра будет добавлен к существующему ведру, в то же время создание переполнения ведра увеличит хеш-таблицуnoverflowприлавок.
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
goto again
}
if inserti == nil {
newb := h.newoverflow(t, b)
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
val = add(insertk, bucketCnt*uintptr(t.keysize))
}
if t.indirectkey() {
kmem := newobject(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.indirectvalue() {
vmem := newobject(t.elem)
*(*unsafe.Pointer)(val) = vmem
}
typedmemmove(t.key, insertk, key)
*inserti = top
h.count++
done:
return val
}
Если значение ключа, хранящееся в хэш-таблице, является типом указателя, фактически для текущей пары ключ-значение будет применено новое пространство памяти, а для вставленной позиции будет применено новое пространство памяти.eypedmemmoveПереместите ключ в запрошенное пространство памяти и, наконец, верните адрес значения, соответствующего ключу.
Расширение
Точка входа в процесс расширения на самом делеhashGrowФункция. Основная функция этой функции заключается в расширении хэш-таблицы. Есть два способа увеличить емкость. Если это расширение вызвано слишком большим количеством переполненных сегментов, то это расширениеsameSizeGrow:
func hashGrow(t *maptype, h *hmap) {
bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) {
bigger = 0
h.flags |= sameSizeGrow
}
oldbuckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
h.nevacuate = 0
h.noverflow = 0
if h.extra != nil && h.extra.overflow != nil {
h.extra.oldoverflow = h.extra.overflow
h.extra.overflow = nil
}
if nextOverflow != nil {
if h.extra == nil {
h.extra = new(mapextra)
}
h.extra.nextOverflow = nextOverflow
}
}
В процессе расширения хеш-таблицы мы пройдемmakeBucketArrayСоздайте новый массив сегментов и несколько предварительно созданных сегментов переполнения, затем установите для исходного массива сегментов значениеoldbucketsи установите новое пустое ведро наbucketsВыше исходный сегмент переполнения также обновляется с использованием той же логики.
Мы пока не видим этого в функции вышеsameSizeGrowРазница, вызванная этим, заключается в том, что здесь фактически создается новое ведро, и нет копирования или передачи записи данных. Фактический процесс выполнения «миграции данных» хеш-таблицы фактически находится вevacuateв функции,evacuateФункция «перераспределит» элементы во входящем сегменте.
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
newbit := h.noldbuckets()
if !evacuated(b) {
var xy [2]evacDst
x := &xy[0]
x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
x.k = add(unsafe.Pointer(x.b), dataOffset)
x.v = add(x.k, bucketCnt*uintptr(t.keysize))
if !h.sameSizeGrow() {
y := &xy[1]
y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
y.k = add(unsafe.Pointer(y.b), dataOffset)
y.v = add(y.k, bucketCnt*uintptr(t.keysize))
}
evacuateФункция изначально создаетevacDstСтруктурный массив, в котором указатель целевого ствола, количество элементов, хранящихся в целевом сегменте, а также позиция текущего ключа и хранилища значений.
Если это расширение без размера, то дваevacDstИнициализируется только одна структура, при удвоении емкости хеш-таблицы элементы одного сегмента будут перемещены в два вновь созданных сегмента, и эти два сегмента будутevacDstСсылка на массив, следующая логика разделения элементов:
for ; b != nil; b = b.overflow(t) {
k := add(unsafe.Pointer(b), dataOffset)
v := add(k, bucketCnt*uintptr(t.keysize))
for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
top := b.tophash[i]
k2 := k
var useY uint8
if !h.sameSizeGrow() {
hash := t.key.alg.hash(k2, uintptr(h.hash0))
if hash&newbit != 0 {
useY = 1
}
}
b.tophash[i] = evacuatedX + useY
dst := &xy[useY]
if dst.i == bucketCnt {
dst.b = h.newoverflow(t, dst.b)
dst.i = 0
dst.k = add(unsafe.Pointer(dst.b), dataOffset)
dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
}
dst.b.tophash[dst.i&(bucketCnt-1)] = top
typedmemmove(t.key, dst.k, k)
typedmemmove(t.elem, dst.v, v)
dst.i++
dst.k = add(dst.k, uintptr(t.keysize))
dst.v = add(dst.v, uintptr(t.valuesize))
}
}
}
if oldbucket == h.nevacuate {
advanceEvacuationMark(h, t, newbit)
}
}
Если в новой хеш-таблице восемь сегментов, в большинстве случаев исходные данные с результатом маски сегмента, равным единице, будут выделены новым сегментам № 1 и № 5, поскольку маска сегмента увеличивается на один бит. ведро, все данные тоже будутtypedmemmoveСкопируйте ключи и значения, где находится целевое ведро и пространство памяти:
Последний вызов этой функцииadvanceEvacuationMarkфункция, которая увеличивает хэшnevacuateСчетчик, а затем удалите эти бесполезные данные после того, как все старые корзины будут шунтированы, однако, поскольку процесс миграции данных языка Go не выполняется за один раз, он будет запускаться только при записи или удалении.evacuateФункция выполняется поэтапно, поэтому мгновенное влияние на производительность отсутствует.
В предыдущем интерфейсе доступа к хеш-таблице раздел изoldbucketsКод для получения корзины, этот код представляет собой логику для получения корзины во время расширения.oldbucketsЕсли он присутствует, адрес будет находиться в предыдущем барреле, а не в текущем барреле.evacuateИспользуйте это ведро.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// ...
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
bucketloop:
// ...
}
Эффект приведенного выше кода заключается в том, что корзины в прошлом неevacuateВременно замените новое ведро, чтобы принимать запросы на чтение, потому что историческое ведро еще не обработано, а данные, которые нам нужно использовать, все еще хранятся, поэтому вновь созданное пустое ведро будет здесь заменено напрямую.
Другой фрагмент кода находится в процессе выполнения запроса на запись.Когда хэш-таблица находится в состоянии расширения, он будет запускаться каждый раз, когда устанавливается значение хеш-таблицы.growWorkСделайте инкрементную копию содержимого хеш-таблицы:
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
h.flags ^= hashWriting
again:
bucket := hash & bucketMask(h.B)
if h.growing() {
growWork(t, h, bucket)
}
// ...
}
Конечно, помимо операций записи, все операции удаления также будут запускаться во время расширения хеш-таблицы.growWork, Тригерный режим и код здесь почти идентичен логике, расположены в текущих значениях ведра, рассчитанные, а затем скопируйте элементы ведра.
Удалить
Чтобы удалить элемент в хеше, нужно использовать язык Godeleteключевое слово, единственной функцией этого ключа является удаление элемента, соответствующего ключу, из хеш-таблицы, независимо от того, существует ли значение, соответствующее ключу, или нет, эта встроенная функция не вернет никаких результатов.
Во время компиляцииdeleteКлючевое слово преобразуется в действие какODELETEnode, и эта функция будет вызываться в концеmapdeleteодна из семейства функций, в том числеmapdelete,mapdelete_faststr,mapdelete_fast32иmapdelete_fast64:
func walkexpr(n *Node, init *Nodes) *Node {
switch n.Op {
case ODELETE:
init.AppendNodes(&n.Ninit)
map_ := n.List.First()
key := n.List.Second()
map_ = walkexpr(map_, init)
key = walkexpr(key, init)
t := map_.Type
fast := mapfast(t)
if fast == mapslow {
key = nod(OADDR, key, nil)
}
n = mkcall1(mapfndel(mapdelete[fast], t), nil, init, typename(t), map_, key)
}
}
Реализация этих функций на самом деле похожа, мы все же выбираемmapdeleteВ качестве основного метода анализа, если при удалении встречается расширение хеш-таблицы, то управляемая корзина будет шунтирована, а затем целевой элемент в корзине будет найден и вызван в соответствии с типом данных.memclrHasPointersилиmemclrNoHeapPointersФункция завершает удаление пар ключ-значение.
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
bucket := hash & bucketMask(h.B)
if h.growing() {
growWork(t, h, bucket)
}
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
bOrig := b
top := tophash(hash)
search:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break search
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
k2 := k
if !alg.equal(key, k2) {
continue
}
if t.indirectkey() {
*(*unsafe.Pointer)(k) = nil
} else if t.key.kind&kindNoPointers == 0 {
memclrHasPointers(k, t.key.size)
}
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
if t.indirectvalue() {
*(*unsafe.Pointer)(v) = nil
} else if t.elem.kind&kindNoPointers == 0 {
memclrHasPointers(v, t.elem.size)
} else {
memclrNoHeapPointers(v, t.elem.size)
}
b.tophash[i] = emptyOne
}
// ...
}
}
}
Логика удаления хеш-таблицы очень похожа на логику записи, но ее метод вызова особенный, нам нужно использовать ключевое слово для «вызова».mapdeleteфункция.
Для логики удаления хеш-таблицы нам на самом деле нужно знать толькоdeleteКлючевому слову будет предшествоватьпроверка типовэтап превращается вODELETEоперации, а затемГенерация промежуточного кода SSAпреобразуется вmapdeleteКластер функций подойдет.
Суммировать
В языке Go для решения проблемы коллизии хэшей используется метод zipper, реализуется хеш-таблица, а такие операции, как доступ, запись и удаление, во время компиляции преобразуются в соответствующие функции или методы среды выполнения.
Хэш хранит первые 8 битов ключа, соответствующего хэшу в каждом блоке.При работе с хэшем этиtophashОн становится кешем первого уровня, чтобы помочь хэшу быстро перемещаться по элементам в сегментах. В каждом сегменте может храниться только 8 пар "ключ-значение". Как только определенный сегмент текущего хэша превысит 8, новые пары "ключ-значение" будут сохранены в сегменте переполнения хэша. .
По мере увеличения количества пар "ключ-значение" количество сегментов переполнения и коэффициент загрузки хэша будут постепенно увеличиваться. Когда число превысит определенный диапазон, будет запущена операция расширения. Во время расширения будет выделено количество сегментов, и процесс перераспределения элементов также выполняется постепенно, когда вызывается операция записи, и не вызывает мгновенных огромных колебаний производительности.
Статьи по Теме
- Принцип компиляции
- структура данных
Reference
О картинках и репринтах
В этой работе используетсяМеждународная лицензия Creative Commons Attribution 4.0Лицензия. При перепечатке просьба указывать ссылку на оригинал.При использовании рисунка просьба сохранять все содержание на рисунке.Его можно соответствующим образом увеличить и ссылку на статью,где находится рисунок,прикрепить к ссылке.Картинка нарисована с помощью Скетча.
Публичный аккаунт WeChat
О комментариях и сообщениях
Если эта статьяПонять принцип работы хэш-таблицы Golang MapЕсли у вас есть какие-либо вопросы по содержанию, пожалуйста, оставьте сообщение в системе комментариев ниже, спасибо.Оригинальная ссылка:Понять принцип хеш-таблицы Голанга. Карта. Программирование, ориентированное на веру.
Follow: Draveness · GitHub