Nous discuterons de l'implémentation de la carte dans un langage sans génériques, examinerons ce qu'est une table de hachage, comment elle est organisée dans Go, quels sont les avantages et les inconvénients de cette implémentation, et ce à quoi vous devez faire attention lorsque vous utilisez cette structure.
Détails sous la coupe.
Attention! Si vous connaissez déjà les tables de hachage dans Go, je vous conseille de sauter les bases et d'aller
ici , sinon il y a un risque de se lasser du moment le plus intéressant.
Qu'est-ce qu'une table de hachage
Pour commencer, je vais vous rappeler ce qu'est une table de hachage. Il s'agit d'une structure de données qui vous permet de stocker des paires clé-valeur et, en règle générale, de posséder des fonctions:
- Cartographie:
map(key) → value
- Inserts:
insert(map, key, value)
- Suppressions:
delete(map, key)
- Recherche:
lookup(key) → value
Table de hachage en langue go
Une table de hachage dans la langue go est représentée par le mot-clé map et peut être déclarée de l'une des manières ci-dessous (plus à leur sujet plus tard):
m := make(map[key_type]value_type) m := new(map[key_type]value_type) var m map[key_type]value_type m := map[key_type]value_type{key1: val1, key2: val2}
Les principales opérations sont réalisées comme suit:
- Insérer:
m[key] = value
- Enlèvement:
delete(m, key)
- Recherche:
value = m[key]
ou
value, ok = m[key]
Faire le tour d'une table en aller
Considérez le programme suivant:
package main import "fmt" func main() { m := map[int]bool{} for i := 0; i < 5; i++ { m[i] = ((i % 2) == 0) } for k, v := range m { fmt.Printf("key: %d, value: %t\n", k, v) } }
Lancement 1:
key: 3, value: false key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true
Exécuter 2:
key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true key: 3, value: false
Comme vous pouvez le voir, la sortie varie d'une exécution à l'autre. Et tout cela parce que la carte de Go n'est pas ordonnée, c'est-à-dire qu'elle n'est pas ordonnée. Cela signifie que vous n'avez pas besoin de vous fier à l'ordre lors de vos déplacements. La raison peut être trouvée dans le code source du langage d'exécution:
L'emplacement de recherche est déterminé
au hasard , rappelez-vous ceci! La rumeur veut que les développeurs d'exécution forcent les utilisateurs à ne pas se fier à l'ordre.
Aller à la recherche de table
Regardons à nouveau un morceau de code. Supposons que nous voulons créer des paires "nombre" - "nombre de fois 10":
package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} fmt.Println(m, m[0], m[1], m[2]) }
Nous lançons:
map[0:0 1:10] 0 10 0
Et nous voyons que lorsque nous avons essayé d'obtenir la valeur de deux (que nous avons oublié de mettre), nous avons obtenu 0. Nous trouvons des lignes expliquant ce comportement dans la
documentation : «Une tentative de récupération d'une valeur de carte avec une clé qui n'est pas présente dans la carte retournera la valeur zéro pour le type des entrées dans la carte. ", mais traduit en russe, cela signifie que lorsque nous essayons d'obtenir la valeur de la carte, mais qu'elle n'est pas là, nous obtenons une" valeur de type zéro ", ce qui dans le cas du nombre 0. Que faire, si nous voulons distinguer les cas 0 et l'absence 2? Pour ce faire, nous avons créé une forme spéciale d '"affectation multiple" - une forme où au lieu de la valeur unique habituelle, la carte renvoie une paire: la valeur elle-même et un autre booléen qui répond à la question de savoir si la clé demandée est présente dans la carte ou non "
Correctement, le morceau de code précédent ressemblera à ceci:
package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} m2, ok := m[2] if !ok {
Et au démarrage, nous obtenons:
map[0:0 1:10] 0 10 20
Créez une table dans Go.
Supposons que nous voulons compter le nombre d'occurrences de chaque mot dans une chaîne, lancez un dictionnaire pour cela et parcourez-le.
package main func main() { var m map[string]int for _, word := range []string{"hello", "world", "from", "the", "best", "language", "in", "the", "world"} { m[word]++ } for k, v := range m { println(k, v) } }
Voyez-vous une capture de
gopher ? - Et il l'est!
Lorsque nous essayons de démarrer un tel programme, nous obtenons une panique et le message "affectation à l'entrée dans une carte nulle". Et tout cela parce que mapa est un type de référence et qu'il ne suffit pas de déclarer une variable, vous devez l'initialiser:
m := make(map[string]int)
Un peu plus bas, il sera clair pourquoi cela fonctionne de cette façon. Au début, il y avait déjà présenté 4 façons de créer une carte, nous en avons examiné deux - cette déclaration en tant que variable et la création via make. Vous pouvez également créer en utilisant la conception "
Littéraux composites "
map[key_type]value_type{}
et si vous le souhaitez, même initialiser immédiatement avec des valeurs, cette méthode est également valide. Quant à la création en utilisant new - à mon avis, cela n'a pas de sens, car cette fonction alloue de la mémoire à la variable et lui renvoie un pointeur rempli avec un type de valeur zéro, qui dans le cas de la carte sera nul (nous obtenons le même résultat que en var, plus précisément un pointeur sur celui-ci).
Comment la carte est-elle transmise à une fonction?
Supposons que nous ayons une fonction qui essaie de changer le nombre qui lui a été transmis. Voyons ce qui se passe avant et après l'appel:
package main func foo(n int) { n = 10 } func main() { n := 15 println("n before foo =", n) foo(n) println("n after foo =", n) }
Un exemple, je pense, est assez évident, mais inclut toujours la conclusion:
n before foo = 15 n after foo = 15
Comme vous l'avez probablement deviné, la fonction n est venue par valeur, pas par référence, donc la variable d'origine n'a pas changé.
Faisons un tour de carte similaire:
package main func foo(m map[int]int) { m[10] = 10 } func main() { m := make(map[int]int) m[10] = 15 println("m[10] before foo =", m[10]) foo(m) println("m[10] after foo =", m[10]) }
Et voilà:
m[10] before foo = 15 m[10] after foo = 10
La valeur a changé. "Eh bien, Mapa est adopté par référence?", Demandez-vous.
Non. Il n'y a aucun lien dans Go. Il est impossible de créer 2 variables avec 1 adresse, comme en C ++ par exemple. Mais alors vous pouvez créer 2 variables pointant vers la même adresse (mais ce sont des pointeurs, et ils sont dans Go).
Supposons que nous ayons une fonction fn qui initialise la carte m. Dans la fonction principale, nous déclarons simplement une variable, l'envoyons pour initialiser et regarder ce qui s'est passé ensuite.
package main import "fmt" func fn(m map[int]int) { m = make(map[int]int) fmt.Println("m == nil in fn?:", m == nil) } func main() { var m map[int]int fn(m) fmt.Println("m == nil in main?:", m == nil) }
Conclusion:
m == nil in fn?: false
m == nil in main?: true
Ainsi, la variable m a été passée
par valeur , par conséquent, comme dans le cas du passage d'un entier régulier à la fonction, elle n'a pas changé (la copie locale de la valeur dans fn a changé). Alors pourquoi la valeur située en m change-t-elle? Pour répondre à cette question, considérez le code du langage d'exécution:
Map in Go n'est qu'un pointeur sur la structure hmap. C'est la réponse à la question de savoir pourquoi, malgré le fait que la mappe est passée à la fonction par valeur, les valeurs elles-mêmes changent - tout dépend du pointeur. La structure hmap contient également les éléments suivants: le nombre d'éléments, le nombre de «compartiments» (présentés sous forme de logarithme pour accélérer les calculs), le germe pour la randomisation des hachages (pour le rendre plus difficile à ajouter - essayez de ramasser les clés afin qu'il y ait des collisions continues), toutes sortes de champs de service et surtout, un pointeur vers des compartiments où les valeurs sont stockées. Regardons l'image:
L'image montre une représentation schématique de la structure en mémoire - il y a un en-tête hmap, le pointeur vers lequel est une carte dans Go (il est créé lorsqu'il est déclaré avec var, mais il n'est pas initialisé, ce qui provoque le blocage du programme lors de la tentative d'insertion). Le champ des compartiments est un référentiel de paires clé-valeur, il existe plusieurs de ces compartiments, chacun contient 8 paires. Tout d'abord dans le "bucket" se trouvent des emplacements pour des bits de hachage supplémentaires (e0..e7 est appelé e - car
des bits de hachage
supplémentaires ). Viennent ensuite les clés et les valeurs en tant que liste de toutes les clés, puis une liste de toutes les valeurs.
Selon le hachage de la fonction, il est déterminé dans quel «bucket» nous mettons la valeur, à l'intérieur de chaque «bucket» il peut y avoir jusqu'à 8 collisions, à la fin de chaque «bucket» il y a un pointeur vers un autre, si le précédent déborde.
Comment évolue la carte?
Dans le code source, vous pouvez trouver la ligne:
c'est-à-dire que s'il y a en moyenne plus de 6,5 éléments dans chaque compartiment, une augmentation du tableau de compartiments se produit. Dans le même temps, le tableau est alloué 2 fois plus, et les anciennes données y sont copiées en petites portions à chaque insertion ou suppression, afin de ne pas créer de très gros retards. Par conséquent, toutes les opérations seront légèrement plus lentes dans le processus d'évacuation des données (lors de la recherche, nous devons également rechercher à deux endroits). Après une évacuation réussie, de nouvelles données commencent à être utilisées.
Prendre l'adresse de l'élément de carte.
Un autre point intéressant - au tout début de l'utilisation du langage que je voulais faire comme ceci:
package main import ( "fmt" ) func main() { m := make(map[int]int) m[1] = 10 a := &m[1] fmt.Println(m[1], *a) }
Mais Go dit: "ne peut pas prendre l'adresse de m [1]". L'explication de la raison pour laquelle il est impossible de prendre l'adresse de la valeur réside dans la procédure d'évacuation des données. Imaginez que nous prenions l'adresse de la valeur, puis la mapa a grandi, une nouvelle mémoire a été allouée, les données ont été évacuées, les anciennes ont été supprimées, le pointeur est devenu incorrect, de telles opérations sont donc interdites.
Comment la carte est-elle implémentée sans génériques?
Ni une interface vide, ni la génération de code n'y sont pour rien; le tout est de la remplacer lors de la compilation. Considérez ce que les fonctions familières de Go deviennent:
v := m["k"] → func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer v, ok := m["k"] → func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) m["k"] = 9001 → func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer delete(m, "k") → func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)
Nous voyons qu'il existe des fonctions mapaccess pour les accès, pour l'écriture et la suppression de mapassign et mapdelete, respectivement. Toutes les opérations utilisent unsafe.Pointer, qui ne se soucie pas du type vers lequel il pointe, et les informations sur chaque valeur sont décrites par un
descripteur de type .
type mapType struct { key *_type elem *_type ...} type _type struct { size uintptr alg *typeAlg ...} type typeAlg struct { hash func(unsafe.Pointer, uintptr) uintptr equal func(unsafe.Pointer, unsafe.Pointer) bool...}
MapType stocke les descripteurs (_type) de la clé et de la valeur. Pour un descripteur de type, des opérations (typeAlg) de comparaison, prenant un hachage, une taille, etc. sont définies, donc on sait toujours comment les produire.
Un peu plus sur son fonctionnement. Lorsque nous écrivons v = m [k] (en essayant d'obtenir la valeur de v à partir de la clé k), le compilateur génère quelque chose comme ceci:
kPointer := unsafe.Pointer(&k) vPointer := mapaccess1(typeOf(m), m, kPointer) v = *(*typeOfvalue)vPointer
Autrement dit, nous prenons un pointeur sur une clé, la structure mapType, à partir de laquelle nous découvrons les descripteurs de la clé et de la valeur, le pointeur pour se mapper lui-même (c'est-à-dire, map) et le transmettre à mapaccess1, qui renverra un pointeur sur la valeur. Nous plaçons le pointeur sur le type souhaité, déréférençons et obtenons la valeur.
Examinons maintenant le code de recherche de l'exécution (qui est légèrement adapté à la lecture):
func lookup(t *mapType, m *mapHeader, key unsafe.Pointer) unsafe.Pointer {
La fonction recherche la clé dans la carte et renvoie un pointeur sur la valeur correspondante, les arguments nous sont déjà familiers - c'est mapType, qui stocke les descripteurs des types et valeurs de clé, la carte elle-même (mapHeader) et un pointeur sur la mémoire qui stocke la clé. Nous renvoyons un pointeur vers la mémoire qui stocke la valeur.
if m == nil || m.count == 0 { return zero }
Ensuite, nous vérifions si le pointeur vers l'en-tête de la carte n'est pas nul, s'il y a 0 élément et renvoyons une valeur nulle, si c'est le cas.
hash := t.key.hash(key, m.seed)
Nous calculons le hachage de clé (nous savons calculer pour une clé donnée à partir d'un descripteur de type). Ensuite, nous essayons de comprendre quel «seau» vous devez aller voir (le reste de la division par le nombre de «seaux», les calculs sont légèrement accélérés). Ensuite, nous calculons le hachage supplémentaire (nous prenons les 8 bits les plus significatifs du hachage) et déterminons la position du «bucket» en mémoire (arithmétique d'adresse).
for { for i := 0; i < 8; i++ { if b.extra[i] != extra {
La recherche, si vous regardez, n'est pas si compliquée: nous passons par les chaînes de "seaux", en passant au suivant, si vous ne l'avez pas trouvé. La recherche dans le "bucket" commence par une comparaison rapide du hachage supplémentaire (c'est pourquoi ces e0 ... e7 au début de chacun sont un "mini" hachage de la paire pour une comparaison rapide). Si elle ne correspond pas, allez plus loin, si c'est le cas, alors nous vérifions plus attentivement - nous déterminons où se trouve la clé soupçonnée d'être recherchée, comparons si elle est égale à ce qui a été demandé. S'il est égal, déterminez la position de la valeur en mémoire et retournez. Comme vous pouvez le voir, rien de surnaturel.
Conclusion
Utilisez des cartes, mais sachez et comprenez comment elles fonctionnent! Vous pouvez éviter un rake en comprenant certaines des subtilités - pourquoi il est impossible de prendre l'adresse de la valeur, pourquoi tout tombe pendant la déclaration sans initialisation, pourquoi il est préférable d'allouer de la mémoire à l'avance, si le nombre d'éléments est connu (nous éviterons les évacuations) et bien plus encore.
Références:
"Allez les cartes en action", Andrew Gerrand«Comment le runtime go implémente les cartes efficacement», Dave Cheney"Comprendre le type à emporter", William KennedyImplémentation de la carte intérieure, Keith Randallcode source de la carte, Go Runtimegolang specaller efficacegopher images