Mappe Go

In generale, ci sono solitamente due modi per implementare la struttura dati delle mappe: tabelle hash (hash table) e alberi di ricerca (search tree). La differenza è che le prime sono non ordinate, mentre i secondi sono ordinati. In Go, l'implementazione di map è basata su hash bucket (che è anche un tipo di tabella hash), quindi sono anche non ordinate. Questo articolo non spiegherà troppo i principi di implementazione, che vanno oltre l'ambito delle basi, verrano analizzati in profondità in seguito.

TIP

Per comprendere i principi delle mappe, puoi visitare Implementazione di map

Inizializzazione

In Go, i tipi di chiave di una mappa devono essere confrontabili, ad esempio string e int sono confrontabili, mentre []int non è confrontabile e quindi non può essere utilizzato come chiave di una mappa. Ci sono due modi per inizializzare una mappa. Il primo è il letterale, il formato è il seguente:

map[keyType]valueType{}

Ecco alcuni esempi

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

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

Il secondo metodo utilizza la funzione incorporata make. Per le mappe, accetta due parametri: tipo e capacità iniziale. Ecco un esempio:

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

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

Le mappe sono tipi di riferimento. Le mappe con valore zero o non inizializzate possono essere accessibili, ma non possono memorizzare elementi, quindi è necessario allocare memoria per esse.

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

panic: assignment to entry in nil map

TIP

Quando si inizializza una mappa, si dovrebbe cercare di allocare una capacità ragionevole per ridurre il numero di espansioni.

Accesso

L'accesso a una mappa è simile all'accesso a un array tramite indice.

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

Osservando il codice, si può notare che anche se la mappa non contiene la coppia chiave-valore "f", c'è comunque un valore di ritorno. Per le chiavi non esistenti, la mappa restituisce il valore zero del tipo corrispondente. Inoltre, quando si accede a una mappa, ci sono in realtà due valori di ritorno: il primo è il valore del tipo corrispondente, il secondo è un valore booleano che indica se la chiave esiste. Ad esempio:

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("chiave non esistente")
   }
}

Per ottenere la lunghezza di una mappa

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

Memorizzazione di valori

Il modo per memorizzare valori in una mappa è simile a quello per memorizzare valori in un array. Ad esempio:

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

Quando si memorizza un valore utilizzando una chiave esistente, il valore originale verrà sovrascritto

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)
}

Tuttavia, esiste anche una situazione speciale, ovvero quando la chiave è 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]

Osservando il risultato, si può notare che chiavi identiche non sono state sovrascritte, ma possono esistere più volte e non è possibile giudicare se esistono, quindi non è possibile ottenere normalmente i valori. Poiché NaN è definito dallo standard IEE754, la sua implementazione è completata dall'istruzione assembly di basso livello UCOMISD, che è un'istruzione per confrontare numeri floating-point a doppia precisione in modo non ordinato. Questa istruzione considererà la situazione di NaN, quindi il risultato è che qualsiasi numero non è uguale a NaN, e NaN non è uguale a se stesso, il che fa sì che il valore hash sia diverso ogni volta. Questo punto è stato anche discusso intensamente nella comunità, ma il governo ritiene che non sia necessario modificarlo, quindi si dovrebbe cercare di evitare di utilizzare NaN come chiave di una mappa.

Eliminazione

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

Per eliminare una coppia chiave-valore è necessaria la funzione incorporata delete. Ad esempio

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]

Va notato che se il valore è NaN, non è nemmeno possibile eliminare la coppia chiave-valore.

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]

Iterazione

È possibile iterare su una mappa utilizzando for range. Ad esempio

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

Si può vedere che il risultato non è ordinato, il che conferma anche che le mappe sono memorizzate in modo non ordinato. Vale la pena notare che, sebbene NaN non possa essere ottenuto normalmente, è possibile accedervi tramite iterazione. Ad esempio

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

Svuotamento

Prima di go1.21, per svuotare una mappa, si poteva solo eseguire delete su ogni chiave della mappa

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

Ma go1.21 ha aggiornato la funzione clear, quindi non è più necessario eseguire le operazioni precedenti. È sufficiente un solo clear per svuotare

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

Output

map[]

Set

Set è una collezione non ordinata che non contiene elementi duplicati. Go non fornisce un'implementazione di struttura dati simile, ma le chiavi di una mappa sono non ordinate e non possono essere duplicate, quindi è possibile utilizzare una mappa per sostituire 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

Una struttura vuota non occupa memoria

Attenzione

Le mappe non sono una struttura dati sicura per la concorrenza. Il team di Go ritiene che nella maggior parte dei casi l'uso delle mappe non coinvolga scenari ad alta concorrenza e l'introduzione di lock mutex ridurrebbe notevolmente le prestazioni. All'interno delle mappe c'è un meccanismo di rilevamento di lettura/scrittura. Se c'è un conflitto, verrà attivato un fatal error. Ad esempio, la seguente situazione ha una probabilità molto elevata di attivare fatal.

func main() {

   group.Add(10)
   // map
   mp := make(map[string]int, 10)
   for i := 0; i < 10; i++ {
      go func() {
         // Operazione di scrittura
         for i := 0; i < 100; i++ {
            mp["helloworld"] = 1
         }
         // Operazione di lettura
         for i := 0; i < 10; i++ {
            fmt.Println(mp["helloworld"])
         }
         group.Done()
      }()
   }
   group.Wait()
}

fatal error: concurrent map writes

In questo caso, è necessario utilizzare sync.Map come sostituto.