Go Maps expliqué : comment les paires clé-valeur sont réellement stockées

Ceci est un extrait du post ; l'article complet est disponible ici : https://victoriametrics.com/blog/go-map/.

Si vous êtes nouveau sur Go, il peut être un peu déroutant de comprendre comment utiliser les cartes dans Go. Et même lorsque vous êtes plus expérimenté, comprendre comment fonctionnent réellement les cartes peut être assez difficile.

Prenons cet exemple : avez-vous déjà défini un « indice » pour une carte et vous êtes-vous demandé pourquoi on l'appelle « indice » et non quelque chose de simple comme la longueur, comme nous le faisons avec les tranches ?

// hint = 10
m := make(map[string]int, 10)

Ou peut-être avez-vous remarqué que lorsque vous utilisez une boucle for-range sur une carte, l'ordre ne correspond pas à l'ordre d'insertion, et il change même si vous parcourez la même carte à des moments différents. Mais bizarrement, si vous faites une boucle dessus exactement au même moment, l'ordre reste généralement le même.

C'est une longue histoire, alors attachez votre ceinture de sécurité et plongez-y.

Avant de continuer, juste un avertissement : les informations ici sont basées sur Go 1.23. Si les choses ont changé et que ce n'est pas à jour, n'hésitez pas à m'envoyer un ping sur X (@func25).

Map in Go : Démarrage rapide

Parlons donc des cartes dans Go, c'est un type intégré qui agit comme un stockage clé-valeur. Contrairement aux tableaux dans lesquels vous êtes coincé avec des clés sous forme d'indices croissants comme 0, 1, 2, etc., avec des cartes, la clé peut être de n'importe quel type comparable.

Cela vous donne beaucoup plus de flexibilité.

m := make(map[string]int)
m["a"] = 1
m["b"] = 2

m // map[a:1 b:2]

Dans cet exemple, nous avons créé une carte vide en utilisant make(), où les clés sont des chaînes et les valeurs sont des entiers.

Maintenant, au lieu d'attribuer manuellement chaque clé, vous pouvez gagner du temps en utilisant une carte littérale. Cela vous permet de configurer vos paires clé-valeur en même temps, dès la création de la carte :

m := map[string]int{
    "a": 1,
    "b": 2,
}

Tout ce que vous faites est de lister les clés et leurs valeurs entre accolades lorsque vous créez la carte pour la première fois, aussi simple que cela.

Et si vous réalisez plus tard que vous n'avez plus besoin d'une certaine paire clé-valeur, Go est là pour vous. Il existe une fonction de suppression pratique qui supprime la clé dont vous ne voulez pas : delete(m, "a").

La valeur zéro d'une carte est nulle, et une carte nulle est un peu comme une carte vide à certains égards. Vous pouvez essayer d'y rechercher des clés, et Go ne paniquera pas et ne fera pas planter votre programme.

Si vous recherchez une clé qui n'est pas là, Go vous donne simplement la "valeur zéro" pour le type de valeur de cette carte :

var m map[string]int

println(m["a"]) // 0
m["a"] = 1      // panic: assignment to entry in nil map

Mais voici le problème : vous ne pouvez pas ajouter de nouvelles paires clé-valeur à une carte nulle.

En fait, Go gère les cartes d'une manière assez similaire à la façon dont il gère les tranches. Les cartes et les tranches commencent par zéro, et Go ne panique pas si vous faites quelque chose d'« inoffensif » avec elles alors qu'elles sont nulles. Par exemple, vous pouvez parcourir une tranche nulle sans aucun « drame ».

Alors, que se passe-t-il si vous essayez de parcourir une carte nulle ?

var m map[string]int

for k, v := range m {
    println(k, v)
} 

Rien ne se passe, aucune erreur, aucune surprise. Cela ne fait rien en silence.

L'approche de Go consiste à traiter la valeur par défaut de tout type comme quelque chose d'utile, et non comme quelque chose qui fait exploser votre programme. Le seul moment où Go fait une crise, c'est lorsque vous faites quelque chose de vraiment illégal, comme essayer d'ajouter une nouvelle paire clé-valeur à une carte nulle ou accéder à un index hors limites dans une tranche.

Il y a quelques autres choses que vous devez savoir sur les cartes dans Go :

• Une boucle for-range sur une carte ne renverra pas les clés dans un ordre spécifique.
• Les cartes ne sont pas thread-safe, le runtime Go provoquera une erreur fatale si vous essayez de lire (ou d'itérer avec une plage for) et d'écrire simultanément sur la même carte.
• Vous pouvez vérifier si une clé est dans une carte en effectuant une simple vérification ok : _, ok := m[key].
• Le type de clé d'une carte doit être comparable.

Plongeons dans ce dernier point concernant les clés de carte. J'ai mentionné plus tôt que "la clé pourrait être de n'importe quel type comparable", mais il y a un peu plus que cela.

"Alors, qu'est-ce qu'un type comparable exactement ? Et qu'est-ce qui ne l'est pas ?"

C'est assez simple : si vous pouvez utiliser == pour comparer deux valeurs du même type, alors ce type est considéré comme comparable.

func main() {
    var s map[int]string

    if s == s {
        println("comparable")
    }
}

// compile error: invalid operation: s == s (map can only be compared to nil)

Mais comme vous pouvez le voir, le code ci-dessus ne se compile même pas. Le compilateur se plaint : "opération invalide : s == s (la carte ne peut être comparée qu'à zéro)."

Cette même règle s'applique à d'autres types non comparables comme les tranches, les fonctions ou les structures qui contiennent des tranches ou des cartes, etc. Ainsi, si vous essayez d'utiliser l'un de ces types comme clés dans une carte, vous êtes pas de chance.

func main() {
  var s map[[]int]string
}

// compile error: invalid map key type []intcompilerIncomparableMapKey

Mais voici un petit secret, les interfaces peuvent être à la fois comparables et non comparables.

Qu'est-ce que ça veut dire ? Vous pouvez absolument définir une carte avec une interface vide comme clé sans aucune erreur de compilation. Mais attention, il y a de fortes chances que vous rencontriez une erreur d'exécution.

func main() {
    m := map[interface{}]int{
        1: 1,
        "a": 2,
    }

    m[[]int{1, 2, 3}] = 3
    m[func() {}] = 4
}

// panic: runtime error: hash of unhashable type []int
// panic: runtime error: hash of unhashable type func()

Everything looks fine until you try to assign an uncomparable type as a map key.

That's when you'll hit a runtime error, which is trickier to deal with than a compile-time error. Because of this, it's usually a good idea to avoid using interface{} as a map key unless you have a solid reason and constraints that prevent misuse.

But that error message: "hash of unhashable type []int" might seem a bit cryptic. What's this about a hash? Well, that's our cue to dig into how Go handles things under the hood.

Map Anatomy

When explaining the internals of something like a map, it's easy to get bogged down in the nitty-gritty details of the Go source code. But we're going to keep it light and simple so even those new to Go can follow along.

What you see as a single map in your Go code is actually an abstraction that hides the complex details of how the data is organized. In reality, a Go map is composed of many smaller units called "buckets."

type hmap struct {
  ...
  buckets unsafe.Pointer
  ...
}

Look at Go source code above, a map contains a pointer that points to the bucket array.

This is why when you assign a map to a variable or pass it to a function, both the variable and the function's argument are sharing the same map pointer.

func changeMap(m2 map[string]int) {
  m2["hello"] = 2
}

func main() {
  m1 := map[string]int{"hello": 1}
  changeMap(m1)
  println(m1["hello"]) // 2
}

But don't get it twisted, maps are pointers to the hmap under the hood, but they aren't reference types, nor are they passed by reference like a ref argument in C#, if you change the whole map m2, it won't reflect on the original map m1 in the caller.

func changeMap(m2 map[string]int) {
  m2 = map[string]int{"hello": 2}
}

func main() {
  m1 := map[string]int{"hello": 1}
  changeMap(m1)
  println(m1["hello"]) // 1
}

In Go, everything is passed by value. What's really happening is a bit different: when you pass the map m1 to the changeMap function, Go makes a copy of the *hmap structure. So, m1 in the main() and m2 in the changeMap() function are technically different pointers point to the same hmap.

For more on this topic, there's a great post by Dave Cheney titled There is no pass-by-reference in Go.

Each of these buckets can only hold up to 8 key-value pairs, as you can see in the image below.

The map above has 2 buckets, and len(map) is 6.

So, when you add a key-value pair to a map, Go doesn't just drop it in there randomly or sequentially. Instead, it places the pair into one of these buckets based on the key's hash value, which is determined by hash(key, seed).

Let's see the simplest assignment scenario in the image below, when we have an empty map, and assign a key-value pair "hello": 1 to it.

It starts by hashing "hello" to a number, then it takes that number and mods it by the number of buckets.

Since we only have one bucket here, any number mod 1 is 0, so it's going straight into bucket 0 and the same process happens when you add another key-value pair. It'll try to place it in bucket 0, and if the first slot's taken or has a different key, it'll move to the next slot in that bucket.

Take a look at the hash(key, seed), when you use a for-range loop over two maps with the same keys, you might notice that the keys come out in a different order:

func main() {
    a := map[string]int{"a": 1, "b": 2, "c": 3, "d": 4, "e": 5, "f": 6}
    b := map[string]int{"a": 1, "b": 2, "c": 3, "d": 4, "e": 5, "f": 6}

    for i := range a {
        print(i, " ")
    }
    println()

    for i := range b {
        print(i, " ")
    }
}

// Output:
// a b c d e f 
// c d e f a b     

How's that possible? Isn't the key "a" in map a and the key "a" in map b hashed the same way?

But here's the deal, while the hash function used for maps in Go is consistent across all maps with the same key type, the seed used by that hash function is different for each map instance. So, when you create a new map, Go generates a random seed just for that map.

In the example above, both a and b use the same hash function because their keys are string types, but each map has its own unique seed.

"Wait, a bucket has only 8 slots? What happens if the bucket gets full? Does it grow like a slice?"

Well, sort of. When the buckets start getting full, or even almost full, depending on the algorithm's definition of "full", the map will trigger a growth, which might double the number of main buckets.

But here's where it gets a bit more interesting.

Quand je dis « seaux principaux », je parle d'un autre concept : « seaux de débordement ». Ceux-ci entrent en jeu lorsque vous vous trouvez dans une situation de collisions élevées. Imaginez que vous ayez 4 compartiments, mais que l'un d'eux est complètement rempli de 8 paires clé-valeur en raison de collisions élevées, tandis que les 3 autres compartiments sont vides.

L'article complet est disponible ici : https://victoriametrics.com/blog/go-map/.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!