Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Подробное объяснение Map для начала работы с языком Go.

1.Основное определение

карта — это неупорядоченная коллекция пар ключ-значение в формате kv.

(1) Особенности

• Характеристики типа: карта является ссылочным типом, поэтому обновление значения в функции приведет к его необратимому изменению.
• Последовательные характеристики: Обход карты неупорядочен, поскольку нижний слой представляет собой хеш-таблицу, а хеш-таблица неупорядочена.
• Использование инициализации: значение 0 или неинициализированное значение равно нулю. Неинициализированное значение не может быть назначено, в противном случае произойдет непосредственная паника.
• Пара ключ-значение: ключ и значение всегда появляются парами, ключ уникален и может быть любого сопоставимого типа.
• Динамический: пары ключ-значение можно добавлять или удалять динамически во время выполнения без необходимости заранее объявлять размер.
• Быстрый поиск: карта обеспечивает быстрые операции поиска, вставки и удаления со средней временной сложностью O (1).
• Параллелизм: не потокобезопасен, для обеспечения безопасности требуется блокировка.

(2) Формулировка определения

var name map[key_type]value_type
1

• имя: имя переменной
• key_type: тип ключа
• value_type: тип значения

// 方式一
var m map[int]string = map[int]string{}

// 方式二
m := map[int]string{
    1 : "老一",
    2 : "老二",
    3 : "老三",
}

// 方式三：5代表容量，也就是在内存中占用多大的空间，可以省略
m := make(map[int]string,5)
1
2
3
4
5
6
7
8
9
10
11
12

2. Основное использование

(1) Добавить элементы

• 1. Самый распространенный метод — добавить его при объявлении карты через литералы, как показано в методе 2 выше.
• 2. Второй шаг — напрямую установить соответствующее значение для указанного ключа.

mapName[key] = value

// 假设map名为m，key为int，value为string
m[5] = "老五"
1
2
3
4

(2) Удалить элементы

Удалите элементы на основе ключей, и при удалении несуществующих ключей не будет сообщено об ошибке.

delete(mapName, key)  

// 假设map名为m，key为int，value为string
delete(m, 5)
1
2
3
4

(3) Изменение элементов

Для изменения вы можете напрямую изменить значение, соответствующее указанному ключу.

mapName[key] = newValue 

// 假设map名为m，key为int，value为string
m[5] = "五"
1
2
3
4

(4) Получить элементы

Получите значение в соответствии с ключом, ок — это бит флага, если он найден, тип — логический

Если значение не найдено, об ошибке не будет сообщено и будет возвращено нулевое значение соответствующего типа.

value, ok := mapName[key]
if !ok {
		fmt.Println(ok)
	}
1
2
3
4

(5) Обход всех элементов

Примечание: обход карты неупорядочен.

for key, value := range myMap {
   // 处理每对键值
}

// 例子
for i, s := range m {
		fmt.Println(i, s)
	}
1
2
3
4
5
6
7
8

3. Основополагающие принципы

Основная суть карты в языке Голанг заключается в использованииhashmapреализован, поэтому карта по сути哈希表。

哈希表это использование哈希函数Организуйте данные в структуры данных, которые поддерживают быструю вставку и поиск.

哈希函数 , также известная как хеш-функция, — это функция, которая преобразует входные данные любой длины (например, строку) в выходные данные фиксированной длины с помощью определенного хэш-алгоритма. Хэш-значения обычно хранятся в виде массива, чтобы обеспечить производительность доступа к хеш-значениям.

Если диапазон входных данных превышает диапазон отображаемых выходных данных, это может привести к тому, что разные входные данные получат один и тот же выходной сигнал.哈希冲突。

Обычно есть два пути решения этой проблемы:开放地址法и拉链法

(1) План реализации карты

Метод открытого адреса:

Структуры данных обычно реализуются с использованием массивов.

• 1. Во-первых, массив состоит из различных хеш-значений, называемых хеш-таблицей.
• 2. Затем выполните множество ключей и выполните хэш-функцию, чтобы подтвердить, что адрес помещен в соответствующую позицию. Если этот слот хеш-таблицы уже занят, используйте последовательность обнаружения (например, линейное обнаружение, вторичное обнаружение или двойное хеширование). и т. д.), чтобы найти следующий доступный слот и сохранить там конфликтующие ключи.

недостаток:

Этот подход требует больше места для разрешения конфликтов, поскольку не только сохраняются данные, но и требуется дополнительное пространство для разрешения конфликтов.

Метод Zipper (языковая карта go использует этот метод):

Массивы и связанные списки обычно используются в качестве базовых структур данных.

• 1. Прежде всего, массив состоит из различных хэш-значений, называемых хеш-таблицей. В каждом слоте хеш-таблицы будет храниться связанный список.
• 2. Тогда придет много ключей. После хеширования разных ключей хеш-значение вычисляется по модулю и привязывается к массиву. В случае одинакового хеш-значения (хэш-коллизия) новый ключ будет подвешен в существующем списке ключей. . позже
• 3. Если вам нужно найти определенный ключ, сначала используйте хеш-функцию, чтобы определить его местоположение, а затем выполните линейный поиск в связанном списке в этом месте, пока не найдете соответствующий ключ или не достигнете конца связанного списка.

Связанный список, связанный с разными индексами массива, также называется ведром.

(2) Базовая структура карты

hmap

type hmap struct {
 count     int // 当前哈希表中的元素数量，即键值对数量，可用内置函数len()获取
 flags     uint8  // 标志位，标记map状态和属性的字段，如正在迭代等状态
 B         uint8  // 表示哈希表桶（buckets）的数量为2的B次方
 noverflow uint16 // 溢出桶的大致数量，扩容时会用到
 hash0     uint32 // 哈希种子，对key做哈希是加入种子计算哈希值，确保map安全性

 buckets    unsafe.Pointer // 存储桶数组的指针
 oldbuckets unsafe.Pointer // 扩容时用于保存旧桶数组的指针 , 大小为新桶数组的一半
 nevacuate  uintptr        // 扩容时的迁移进度器，迁移桶下标小于此值说明完成迁移

 extra *mapextra // 溢出桶的指针，指向mapextra结构体，用于存储一些额外的字段和信息
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// mapextra 处理桶溢出的结构体
type mapextra struct {
 overflow    *[]*bmap    // 溢出桶数组指针，仅当key和elem非指针时才使用
 oldoverflow *[]*bmap    // 旧的溢出桶数组指针，仅当key和elem非指针时才使用

 nextOverflow *bmap      // 下一个可用的溢出桶地址
}

1
2
3
4
5
6
7
8

bmap

В исходном коде тип bmap имеет только одно поле tophash.Но во время компиляции компилятор Go автоматически внедрит соответствующие ключи, значения и другие структуры в соответствии с пользовательским кодом.

Карта поверхности

type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

1
2
3
4
5
6
7
8
9
10
11
12

фактическое bmap

// 编译期间会动态地创建一个新的结构：
type bmap struct {
   topbits  [8]uint8   // 这里存储哈希值的高八位，用于在确定key的时候快速试错，加快增删改查寻址效率,有时候也叫tophash
   keys     [8]keytype   // 存储key的数组，这里bmap最多存储8个键值对
   elems   [8]valuetype    // 存储value的数组，这里bmap也最多存储8个键值对
   ...
   overflow uintptr     // 溢出桶指针
}

1
2
3
4
5
6
7
8
9

Базовая диаграмма карты

Расширение карты

В языке Go расширение карты выполняется автоматически для поддержания производительности карты.

Во-первых, при записи карта проходитruntime.mapassignОпределите, необходимо ли расширение

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
 // If we hit the max load factor or we have too many overflow buckets,
 // and we're not already in the middle of growing, start growing.
 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  hashGrow(t, h)
  goto again // Growing the table invalidates everything, so try again
 }
...
}

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
 return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
 if B > 15 {
  B = 15
 }
 return noverflow >= uint16(1)<<(B&15)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Согласно приведенному выше коду, существует два условия для оценки расширения:

• Коэффициент нагрузки превышает порог 6,5:overLoadFactor(h.count+1, h.B) , коэффициент загрузки = количество элементов ÷ количество сегментов
• Использовано слишком много сегментов переполнения (превышено 32768):tooManyOverflowBuckets(h.noverflow, h.B))

Метод расширения:

• Постепенное расширение:

Если коэффициент загрузки слишком велик, создается новый сегмент. Длина нового сегмента в два раза превышает исходную длину, а затем данные старого сегмента перемещаются в новый сегмент.

• Равномерное расширение мощности

Данных не так много, но слишком много сегментов переполнения.Во время расширения количество сегментов остается неизменным. Операции перемещения, аналогичные инкрементному расширению, выполняются снова, а свободные пары «ключ-значение» перестраиваются, чтобы увеличить использование сегментов и обеспечить более быстрый доступ.

Шаги расширения:

• 1. Новый массив сегментов:Создать новый с оригинальным размером.двойнойНовый массив сегментов будет помечен как расширенный.

func hashGrow(t *maptype, h *hmap) {
 ...
 // 原有桶设置给oldbuckets
 oldbuckets := h.buckets   
 // 创建新桶
 newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

 flags := h.flags &^ (iterator | oldIterator)
 if h.flags&iterator != 0 {
  flags |= oldIterator
 }
 // commit the grow (atomic wrt gc)
 h.B += bigger
 h.flags = flags
 h.oldbuckets = oldbuckets
 h.buckets = newbuckets
 h.nevacuate = 0
 h.noverflow = 0

 ...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 2. Перефразировать: используйте oldbuckets, чтобы указать на исходный массив сегментов, сегменты, чтобы указать на новый массив сегментов, просмотрите все пары ключ-значение в старом массиве сегментов и используйте хеш-функцию, чтобы пересчитать положение каждого ключа и вставить их в новый. массив ведер.

// 这个是mapdelete函数中的处理迁移的位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
 if h.growing() {
  // 
  growWork(t, h, bucket)
 }
...
}

1
2
3
4
5
6
7
8
9
10

• 3. Постепенная миграция: Чтобы избежать приостановки всей программы во время расширения, реализация Go Map может выбрать渐进式驱逐 Перенесите пары ключ-значение. Это означает, что во время расширения старый массив сегментов и новый массив сегментов будут существовать одновременно, новые вставленные пары ключ-значение будут помещены непосредственно в новый сегмент, а доступ к старому сегменту вызовет операцию миграции.

// 进入后是一个简单的判断，之后的evacuate是核心逻辑处理，特别多，感兴趣自己看源码
func growWork(t *maptype, h *hmap, bucket uintptr) {
	// make sure we evacuate the oldbucket corresponding
	// to the bucket we're about to use
	evacuate(t, h, bucket&h.oldbucketmask())

	// evacuate one more oldbucket to make progress on growing
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

1
2
3
4
5
6
7
8
9
10
11
12

• 4. Обновить внутренний статус: Когда все пары ключ-значение в старых бакетах будут перемещены, внутреннее состояние карты будет обновлено, а старые бакеты будут удалены.

4.Сценарии использования

• 1.Быстрый поиск: Когда вам нужно быстро найти значение на основе ключа, Map обеспечивает производительность поиска со средней временной сложностью O(1).
• 2.Удалить дубликаты: Когда необходимо сохранить уникальные ключи, ключи карты не могут повторяться, и функция дедупликации может быть реализована естественным образом.
• 3.динамическая коллекция: Карта обеспечивает гибкие операции, когда пары ключ-значение необходимо динамически добавлять или удалять.
• 4.Связанные данные: Карта — хороший выбор, когда данные существуют в форме пар ключ-значение и их необходимо часто обновлять или запрашивать.

5. Рекомендации по использованию

1. предварительно выделенный: Попробуйте использовать функцию make, чтобы выделить место на карте известного размера.
2. Выбор типа данных: используйте более крупные типы данных, напримерintилиint64。
3. Хранение указателей: Для структур или переменных с большими объемами данных попробуйте использовать указатели для передачи и хранения значений.
4. Управление параллелизмом: Для одновременного доступа используйтеsync.MapИли реализуйте свою собственную, одновременно безопасную карту.

6.Справочные материалы

• https://cloud.tencent.com/developer/article/2400014
• https://blog.csdn.net/qq_35289736/article/details/137480760/
• https://zhuanlan.zhihu.com/p/675715169/