Mapa do Go

Geralmente, existem dois tipos de implementação de estrutura de dados de mapa, tabela hash (hash table) e árvore de busca (search tree), a diferença é que a primeira é não ordenada, a segunda é ordenada. Em Go, a implementação de map é baseada em buckets de hash (também é uma tabela hash), por isso também é não ordenada. Esta seção não vai explicar muito sobre os princípios de implementação, isso está além do escopo básico, será analisado em detalhes posteriormente.

TIP

Para entender o princípio do map, pode ir para implementação do map

Inicialização

Em Go, o tipo de chave do mapa deve ser comparável, por exemplo string, int são comparáveis, enquanto []int não é comparável, portanto não pode ser usado como chave do mapa. Existem dois métodos para inicializar um mapa, o primeiro é literal, o formato é o seguinte

map[tipoChave]tipoValor{}

Alguns exemplos

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

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

O segundo método é usar a função incorporada make, para map, recebe dois parâmetros, respectivamente tipo e capacidade inicial, exemplo abaixo

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

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

Mapa é um tipo de referência, mapa com valor zero ou não inicializado pode ser acessado, mas não pode armazenar elementos, então é necessário alocar memória para ele.

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

panic: assignment to entry in nil map

TIP

Ao inicializar um mapa, deve-se tentar alocar uma capacidade razoável para reduzir o número de expansões.

Acesso

A forma de acessar um mapa é como acessar um array através de índice.

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

Através do código pode-se observar que, mesmo que o par chave-valor "f" não exista no mapa, ainda há um valor de retorno. Para chaves que não existem no mapa, o valor de retorno é o valor zero do tipo correspondente, e ao acessar o mapa na verdade há dois valores de retorno, o primeiro é o valor do tipo correspondente, o segundo é um valor booleano, representando se a chave existe, por exemplo

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("chave não existe")
   }
}

Obter o comprimento do mapa

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

Armazenar Valor

A forma de armazenar valor no mapa também é similar ao array, por exemplo

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

Ao armazenar valor usando uma chave existente, vai sobrescrever o valor original

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

Mas existe um caso especial, quando a chave é 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]

Através do resultado pode-se observar que o mesmo valor de chave não sobrescreveu, pelo contrário pode existir múltiplos, também não é possível julgar se existe, portanto não é possível obter valor normalmente. Porque NaN é definido pelo padrão IEE754, sua implementação é feita pela instrução assembly UCOMISD, esta é uma instrução de comparação sem ordem de números de ponto flutuante de dupla precisão, esta instrução considera o caso de NaN, portanto o resultado é que qualquer número não é igual a NaN, NaN também não é igual a si mesmo, isso também faz com que cada valor de hash seja diferente. A comunidade já discutiu intensamente sobre isso, mas o oficial acha que não há necessidade de modificar, então deve-se evitar usar NaN como chave do mapa.

Excluir

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

Para excluir um par chave-valor, precisa-se usar a função incorporada delete, por exemplo

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]

Vale notar que, se o valor for NaN, não é possível nem excluir o par chave-valor.

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]

Percorrer

Através de for range pode-se percorrer o mapa, por exemplo

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

Pode-se ver que o resultado não é ordenado, o que também confirma que o mapa é armazenado de forma não ordenada. Vale mencionar que, embora NaN não possa ser obtido normalmente, pode ser acessado através de iteração, por exemplo

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

Limpar

Antes do go1.21, para limpar o mapa, só era possível fazer delete para cada chave do mapa

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

Mas o go1.21 atualizou a função clear, não precisa mais fazer a operação anterior, só precisa um clear para limpar

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

Saída

map[]

Set

Set é uma coleção não ordenada que não contém elementos repetidos, Go não fornece uma estrutura de dados similar, mas a chave do mapa é justamente não ordenada e não pode ser repetida, então também pode usar mapa para substituir 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

Uma struct vazia não ocupa memória

Atenção

Mapa não é uma estrutura de dados segura para concorrência, a equipe Go acha que na maioria dos casos o uso de mapa não envolve cenários de alta concorrência, introduzir mutex reduziria muito a performance, mapa tem mecanismo de detecção de leitura e escrita interno, se houver conflito vai disparar fatal error. Por exemplo, nas seguintes situações há uma grande possibilidade de disparar fatal.

func main() {

   group.Add(10)
   // map
   mp := make(map[string]int, 10)
   for i := 0; i < 10; i++ {
      go func() {
         // operação de escrita
         for i := 0; i < 100; i++ {
            mp["helloworld"] = 1
         }
         // operação de leitura
         for i := 0; i < 10; i++ {
            fmt.Println(mp["helloworld"])
         }
         group.Done()
      }()
   }
   group.Wait()
}

fatal error: concurrent map writes

Neste caso, precisa-se usar sync.Map para substituir.