Partage de technologie

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

Explication détaillée de Map pour démarrer avec le langage Go

1.Définition de base

map est une collection non ordonnée de paires clé-valeur au format kv

(1) Caractéristiques

• Caractéristiques du type : map est un type de référence, donc la mise à jour de la valeur dans la fonction la modifiera définitivement.
• Caractéristiques séquentielles : le parcours de la carte n'est pas ordonné, car la couche inférieure est une table de hachage et la table de hachage n'est pas ordonnée.
• Utilisation de l'initialisation : la valeur 0 ou la valeur non initialisée est nulle. La valeur non initialisée ne peut pas être attribuée, sinon elle paniquera directement.
• Paire clé-valeur : la clé et la valeur apparaissent toujours par paires, la clé est unique et peut être de n'importe quel type comparable
• Dynamique : les paires clé-valeur peuvent être ajoutées ou supprimées dynamiquement au moment de l'exécution sans qu'il soit nécessaire de déclarer la taille à l'avance
• Recherche rapide : la carte fournit des opérations de recherche, d'insertion et de suppression rapides, avec une complexité temporelle moyenne de O(1)
• Concurrence : non thread-safe, le verrouillage est requis pour garantir la sécurité

(2) Énoncé de définition

var name map[key_type]value_type
1

• nom : nom de la variable
• key_type : type de clé
• value_type : type de valeur

// 方式一
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.Utilisation de base

(1) Ajouter des éléments

• 1. La méthode la plus courante consiste à l'ajouter lors de la déclaration de map via des littéraux, comme indiqué dans la méthode 2 ci-dessus.
• 2. La deuxième étape consiste à définir directement la valeur correspondante pour la clé spécifiée.

mapName[key] = value

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

(2) Supprimer des éléments

Supprimez les éléments en fonction des clés et aucune erreur ne sera signalée lors de la suppression de clés inexistantes.

delete(mapName, key)  

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

(3) Modifier des éléments

Pour modifier, vous pouvez modifier directement la valeur correspondant à la clé spécifiée.

mapName[key] = newValue 

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

(4) Obtenir des éléments

Obtenez la valeur en fonction de la clé, ok est le bit d'indicateur s'il est trouvé, le type est booléen

Si la valeur n'est pas trouvée, aucune erreur ne sera signalée et une valeur nulle du type correspondant sera renvoyée.

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

(5) Traverser tous les éléments

Remarque : la traversée de la carte n'est pas ordonnée

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

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

3. Principes sous-jacents

L'essence sous-jacente de la carte en langage golang est d'utiliserhashmapest implémenté, donc la carte est essentiellement哈希表。

哈希表est une utilisation哈希函数Organisez les données dans des structures de données qui prennent en charge une insertion et une recherche rapides.

哈希函数 , également connue sous le nom de fonction de hachage, est une fonction qui convertit une entrée de n'importe quelle longueur (comme une chaîne) en une sortie de longueur fixe via un algorithme de hachage spécifique. Les valeurs de hachage sont généralement stockées sous forme de tableau pour garantir les performances d'accès aux valeurs de hachage.

Si la plage de l'entrée dépasse la plage de la sortie mappée, différentes entrées peuvent obtenir la même sortie.哈希冲突。

Il existe généralement deux manières de résoudre ce problème :开放地址法et拉链法

(1) Plan de mise en œuvre de la carte

Méthode d'adresse ouverte :

Les structures de données sont généralement implémentées à l'aide de tableaux

• 1. Premièrement, le tableau est composé de différentes valeurs de hachage, appelées table de hachage.
• 2. Effectuez ensuite de nombreuses touches et effectuez une fonction de hachage pour confirmer que l'adresse est placée dans la position correspondante. Si cet emplacement de la table de hachage est déjà occupé, utilisez une séquence de détection (telle qu'une détection linéaire, une détection secondaire ou un double hachage. , etc.) pour trouver la clé suivante Un emplacement disponible et y stocker les clés en conflit.

défaut:

Cette approche nécessite plus d'espace pour résoudre les conflits, car non seulement les données sont stockées, mais un espace supplémentaire est également nécessaire pour résoudre les collisions.

Méthode Zipper (go Language Map utilise cette méthode) :

Les tableaux et les listes chaînées sont généralement utilisés comme structures de données sous-jacentes

• 1. Tout d'abord, le tableau est composé de différentes valeurs de hachage, appelées table de hachage. Chaque emplacement de la table de hachage stockera une liste chaînée.
• 2. Ensuite, de nombreuses clés entreront. Après avoir haché différentes clés, la valeur de hachage est calculée modulo et liée au tableau. Dans le cas de la même valeur de hachage (collision de hachage), la nouvelle clé sera accrochée dans la liste de clés existante. . plus tard
• 3. Lorsque vous avez besoin de trouver une clé spécifique, utilisez d'abord une fonction de hachage pour déterminer son emplacement, puis effectuez une recherche linéaire sur la liste chaînée à cet emplacement jusqu'à ce que vous trouviez une clé correspondante ou atteigniez la fin de la liste chaînée.

Une liste chaînée liée à différents index d’un tableau est également appelée compartiment.

(2) La structure sous-jacente de la carte

carte h

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

carte b

Dans le code source, le type bmap n'a qu'un seul champ tophash.Mais lors de la compilation, le compilateur Go injectera automatiquement la clé, la valeur et d'autres structures correspondantes en fonction du code utilisateur.

Carte bmap de surface

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 réel

// 编译期间会动态地创建一个新的结构：
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

Diagramme sous-jacent

Extension de la carte

Dans le langage Go, l'expansion de la carte est effectuée automatiquement pour maintenir les performances de la carte.

Premièrement, lors de l'écriture, la carte passeruntime.mapassignDéterminer si une expansion est nécessaire

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

Selon le code ci-dessus, il y a deux conditions pour juger de l’expansion :

• Le facteur de charge dépasse le seuil 6,5 :overLoadFactor(h.count+1, h.B) , facteur de charge = nombre d'éléments ÷ nombre de godets
• Trop de seaux de trop-plein utilisés (dépassé 32 768) :tooManyOverflowBuckets(h.noverflow, h.B))

Méthode d'expansion :

• Expansion incrémentielle :

Lorsque le facteur de charge est trop grand, un nouveau compartiment est créé. La nouvelle longueur du compartiment est le double de la longueur d'origine, puis les anciennes données du compartiment sont déplacées vers le nouveau compartiment.

• Extension de capacité égale

Il n'y a pas beaucoup de données, mais il y a trop de compartiments de débordement.Pendant l'expansion, le nombre de compartiments reste inchangé. Les opérations de relocalisation similaires à l'expansion incrémentielle sont à nouveau effectuées et les paires clé-valeur lâches sont réorganisées pour augmenter l'utilisation du compartiment et garantir un accès plus rapide.

Étapes d'extension :

• 1. Nouveau tableau de compartiments:Créez-en un nouveau avec la taille d'originedoubleLe nouveau tableau de compartiments sera marqué comme développé.

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. Répétez: utilisez oldbuckets pour pointer vers le tableau de compartiments d'origine, les compartiments pour pointer vers le nouveau tableau de compartiments, parcourez toutes les paires clé-valeur de l'ancien tableau de compartiments et utilisez la fonction de hachage pour recalculer la position de chaque clé et les insérer dans le nouveau tableau de seau.

// 这个是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. Migration progressive: Afin d'éviter de suspendre l'ensemble du programme pendant l'expansion, l'implémentation de Go's Map peut choisir渐进式驱逐 Migrez les paires clé-valeur. Cela signifie que lors de l'expansion, l'ancien tableau de compartiments et le nouveau tableau de compartiments existeront en même temps, les paires clé-valeur nouvellement insérées seront placées directement dans le nouveau compartiment et l'accès à l'ancien compartiment déclenchera une opération de migration.

// 进入后是一个简单的判断，之后的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. Mettre à jour le statut interne: Lorsque toutes les paires clé-valeur des oldbuckets sont déplacées, l'état interne de la carte sera mis à jour et les oldbuckets seront supprimés.

4. Scénarios d'utilisation

• 1.recherche rapide: Lorsque vous avez besoin de rechercher rapidement une valeur basée sur une clé, Map offre des performances de recherche avec une complexité temporelle moyenne de O(1).
• 2.Supprimer les doublons: Lorsque des clés uniques doivent être stockées, les clés de carte ne peuvent pas être répétées et la fonction de déduplication peut naturellement être réalisée.
• 3.collection dynamique: Map fournit des opérations flexibles lorsque les paires clé-valeur doivent être ajoutées ou supprimées dynamiquement.
• 4.Données liées: Map est un bon choix lorsque les données existent sous la forme de paires clé-valeur et doivent être mises à jour ou interrogées fréquemment.

5. Suggestions d'utilisation

1. pré-attribué: Essayez d'utiliser la fonction make pour allouer de la capacité à une carte de taille connue.
2. Sélection du type de données : utilisez des types de données plus volumineux, tels queintouint64。
3. Stockage du pointeur: Pour les structures ou les variables contenant de grandes quantités de données, essayez d'utiliser des pointeurs pour transférer et stocker des valeurs.
4. Contrôle de la concurrence: Pour un accès simultané, utilisezsync.MapOu implémentez votre propre carte simultanément sécurisée.

6.Matériaux de référence

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