Maps en Go

Généralement, il existe deux implémentations courantes de la structure de données map : la table de hachage (hash table) et l'arbre de recherche (search tree). La différence est que la première est non ordonnée et la seconde est ordonnée. En Go, l'implémentation de map est basée sur des seaux de hachage (qui sont également une table de hachage), elle est donc non ordonnée. Ce chapitre n'expliquera pas en détail le principe d'implémentation, car cela dépasse le cadre des bases. Une analyse approfondie sera effectuée ultérieurement.

TIP

Pour comprendre le principe de map, vous pouvez consulter Implémentation de map

Initialisation

En Go, le type de clé d'une map doit être comparable. Par exemple, string et int sont comparables, tandis que []int ne l'est pas et ne peut donc pas être utilisé comme clé de map. Il existe deux méthodes pour initialiser une map. La première est le littéral, avec le format suivant :

map[keyType]valueType{}

Quelques exemples :

mp := map[int]string{
   0: "a",
   1: "a",
   2: "a",
   3: "a",
   4: "a",
}

mp := map[string]int{
   "a": 0,
   "b": 22,
   "c": 33,
}

La deuxième méthode utilise la fonction intégrée make. Pour une map, elle accepte deux paramètres : le type et la capacité initiale. Exemple :

mp := make(map[string]int, 8)

mp := make(map[string][]int, 10)

Les maps sont des types de référence. Une map de valeur zéro ou non initialisée peut être accédée, mais ne peut pas contenir d'éléments. Il est donc nécessaire de lui allouer de la mémoire.

func main() {
   var mp map[string]int
   mp["a"] = 1
   fmt.Println(mp)
}

panic: assignment to entry in nil map

TIP

Lors de l'initialisation d'une map, il est recommandé d'allouer une capacité raisonnable pour réduire le nombre de redimensionnements.

Accès

L'accès à une map se fait comme l'accès à un tableau via un index.

func main() {
  mp := map[string]int{
    "a": 0,
    "b": 1,
    "c": 2,
    "d": 3,
  }
  fmt.Println(mp["a"])
  fmt.Println(mp["b"])
  fmt.Println(mp["d"])
  fmt.Println(mp["f"])
}

0
1
3
0

On peut observer à partir du code que même si la map ne contient pas la paire clé-valeur "f", une valeur est toujours retournée. Pour une clé qui n'existe pas dans la map, la valeur retournée est la valeur zéro du type correspondant. De plus, lors de l'accès à une map, il y a en fait deux valeurs de retour : la première est la valeur du type correspondant, et la seconde est une valeur booléenne indiquant si la clé existe. Par exemple :

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   if val, exist := mp["f"]; exist {
      fmt.Println(val)
   } else {
      fmt.Println("la clé n'existe pas")
   }
}

Obtenir la longueur d'une map :

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   fmt.Println(len(mp))
}

Stockage de valeurs

Le stockage de valeurs dans une map est similaire au stockage dans un tableau. Par exemple :

func main() {
   mp := make(map[string]int, 10)
   mp["a"] = 1
   mp["b"] = 2
   fmt.Println(mp)
}

Lors du stockage, l'utilisation d'une clé existante écrasera la valeur d'origine.

func main() {
   mp := make(map[string]int, 10)
   mp["a"] = 1
   mp["b"] = 2
   if _, exist := mp["b"]; exist {
      mp["b"] = 3
   }
   fmt.Println(mp)
}

Cependant, il existe un cas particulier : lorsque la clé est math.NaN().

func main() {
  mp := make(map[float64]string, 10)
  mp[math.NaN()] = "a"
  mp[math.NaN()] = "b"
  mp[math.NaN()] = "c"
  _, exist := mp[math.NaN()]
  fmt.Println(exist)
  fmt.Println(mp)
}

false
map[NaN:c NaN:a NaN:b]

On peut observer à partir du résultat que la même clé n'a pas écrasé les valeurs, et qu'il peut même en exister plusieurs. Il est donc impossible de juger de son existence et de récupérer normalement la valeur. En effet, NaN est défini par la norme IEEE754, et son implémentation est effectuée par l'instruction d'assemblage de bas niveau UCOMISD, qui est une instruction de comparaison non ordonnée de nombres à virgule flottante double précision. Cette instruction prend en compte le cas de NaN, donc le résultat est qu'aucun nombre n'est égal à NaN, et NaN n'est pas égal à lui-même. Cela entraîne que la valeur de hachage est différente à chaque fois. Ce point a fait l'objet de vifs débats au sein de la communauté, mais l'officiel estime qu'il n'est pas nécessaire de le modifier. Il convient donc d'éviter autant que possible d'utiliser NaN comme clé de map.

Suppression

func delete(m map[Type]Type1, key Type)

La suppression d'une paire clé-valeur nécessite la fonction intégrée delete. Par exemple :

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   fmt.Println(mp)
   delete(mp, "a")
   fmt.Println(mp)
}

map[a:0 b:1 c:2 d:3]
map[b:1 c:2 d:3]

Il convient de noter que si la valeur est NaN, il est même impossible de supprimer la paire clé-valeur.

func main() {
   mp := make(map[float64]string, 10)
   mp[math.NaN()] = "a"
   mp[math.NaN()] = "b"
   mp[math.NaN()] = "c"
   fmt.Println(mp)
   delete(mp, math.NaN())
   fmt.Println(mp)
}

map[NaN:c NaN:a NaN:b]
map[NaN:c NaN:a NaN:b]

Parcours

Utilisez for range pour parcourir une map. Par exemple :

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   for key, val := range mp {
      fmt.Println(key, val)
   }
}

c 2
d 3
a 0
b 1

On peut voir que le résultat n'est pas ordonné, ce qui confirme que le stockage dans une map est non ordonné. Il est intéressant de noter que bien que NaN ne puisse pas être accédé normalement, il peut être accédé via un parcours. Par exemple :

func main() {
   mp := make(map[float64]string, 10)
   mp[math.NaN()] = "a"
   mp[math.NaN()] = "b"
   mp[math.NaN()] = "c"
   for key, val := range mp {
      fmt.Println(key, val)
   }
}

NaN a
NaN c
NaN b

Vidage

Avant Go 1.21, pour vider une map, il fallait supprimer chaque clé de la map une par une.

func main() {
  m := map[string]int{
    "a": 1,
    "b": 2,
  }
  for k, _ := range m {
    delete(m, k)
  }
  fmt.Println(m)
}

Mais Go 1.21 a introduit la fonction clear, il n'est donc plus nécessaire d'effectuer les opérations précédentes. Un seul clear suffit pour vider.

func main() {
  m := map[string]int{
    "a": 1,
    "b": 2,
  }
  clear(m)
  fmt.Println(m)
}

Sortie :

map[]

Set

Set est une collection non ordonnée ne contenant pas d'éléments répétés. Go ne fournit pas de structure de données similaire, mais comme les clés d'une map sont non ordonnées et ne peuvent pas être répétées, une map peut être utilisée pour remplacer un set.

func main() {
  set := make(map[int]struct{}, 10)
  for i := 0; i < 10; i++ {
    set[rand.Intn(100)] = struct{}{}
  }
  fmt.Println(set)
}

map[0:{} 18:{} 25:{} 40:{} 47:{} 56:{} 59:{} 81:{} 87:{}]

TIP

Une structure vide n'occupe pas de mémoire.

Attention

Une map n'est pas une structure de données sûre pour la concurrence. L'équipe Go estime que dans la plupart des cas, l'utilisation de maps n'implique pas de scénarios hautement concurrents, et l'introduction de verrous mutuels réduirait considérablement les performances. La map dispose d'un mécanisme de détection de lecture/écriture interne. En cas de conflit, une fatal error sera déclenchée. Par exemple, la situation suivante est très susceptible de déclencher une fatal.

func main() {

   group.Add(10)
   // map
   mp := make(map[string]int, 10)
   for i := 0; i < 10; i++ {
      go func() {
         // opération d'écriture
         for i := 0; i < 100; i++ {
            mp["helloworld"] = 1
         }
         // opération de lecture
         for i := 0; i < 10; i++ {
            fmt.Println(mp["helloworld"])
         }
         group.Done()
      }()
   }
   group.Wait()
}

fatal error: concurrent map writes

Dans ce cas, il est nécessaire d'utiliser sync.Map comme alternative.