Mapas - Algoritmos y Programación II

Podemos pensar en los mapas como una generalización de los arreglos, donde en lugar de usar solo enteros como índices, podemos usar otros tipos de datos. Por ejemplo, podemos acceder a un elemento de un mapa usando una cadena como índice edades["alice"] en lugar de un entero como edades[0].

Los mapas son una forma de asociar claves a valores, y son útiles para almacenar datos que se pueden identificar mediante una clave. Por ejemplo, en el caso de edades, la clave es el nombre de una persona y el valor es su edad.

En Go, un map es una referencia a una tabla hash^[1], y el tipo de map se escribe como map[K]V, donde K y V son los tipos de sus claves y valores. Todas las claves en un mapa dado son del mismo tipo, y todos los valores son del mismo tipo, pero las claves no necesitan ser del mismo tipo que los valores.

No hay restricciones sobre el tipo de valor V.

Los tipos que se pueden usar como clave son aquellos comparables con ==: booleanos, números, strings, punteros, canales, y tipos compuestos como structs cuyos campos sean todos comparables o arrays con elementos comparables. En cambio, los slices, mapas y funciones no son comparables y no se pueden usar como clave.

1
2
3
4
// Válido
m1 := make(map[string]int)
m2 := make(map[int]string)
m3 := make(map[[3]int]string) // array de 3 ints como clave

1
2
// Inválido: slice como clave (no compila)
// m := make(map[[]string]int)

Los mapas son dinámicos, es decir, que pueden crecer o reducir la cantidad de elementos a medida que se agregan o eliminan.

La función built-in make se puede usar para reservar la memoria que usará un mapa:

1
edades := make(map[string]int)

También podemos crear un mapa literal para crear un nuevo mapa con algunos pares clave/valor iniciales:

1
2
3
4
edades := map[string]int{
    "alice": 31,
    "charlie": 34,
}

Esto es equivalente a

1
2
3
edades := make(map[string]int)
edades["alice"] = 31
edades["charlie"] = 34

Una expresión alternativa para un nuevo mapa vacío es map[string]int{}.

Cuando se conoce la cantidad aproximada de entradas, es más eficiente pre-asignar espacio con un segundo argumento en make:

1
edades := make(map[string]int, 100) // capacidad inicial para ~100 entradas

Esto evita que el mapa tenga que redimensionar su tabla de hash internamente a medida que crece.

Los valores de un mapa también pueden ser otros mapas. Por ejemplo, para asociar nombres de estudiantes con sus notas por materia:

1
2
3
4
5
notas := map[string]map[string]int{
    "alice": {"matematica": 8, "lengua": 9},
}

fmt.Println(notas["alice"]["matematica"]) // 8

Si el mapa interior no está inicializado, asignar un valor produce un error. Por eso es común inicializarlo antes de usarlo:

1
2
3
4
if _, ok := notas["bob"]; !ok {
    notas["bob"] = make(map[string]int)
}
notas["bob"]["matematica"] = 7

Los elementos de un mapa se acceden mediante la notación habitual de subíndice:

1
2
3
edades["alice"] = 32
edad := edades["alice"]
fmt.Println(edad)

y se pueden eliminar con la función built-in delete:

1
delete(edades, "alice")

Todas estas operaciones son seguras incluso si el elemento no está en el mapa; una búsqueda en un mapa utilizando una clave que no está presente devuelve el valor cero para su tipo. Por ejemplo, lo siguiente funciona incluso cuando "bob" aún no es una clave en el mapa porque el valor de edades["bob"] será 0.

1
edades["bob"] = edades["bob"] + 1

Las formas abreviadas de asignación x += y y x++ también funcionan para los elementos de un mapa, por lo que podemos reescribir la declaración anterior como

1
edades["bob"] += 1

o incluso de forma más concisa como

1
edades["bob"]++

Para enumerar todos los pares clave/valor en el mapa, usamos un bucle for basado en range, similar a los que vimos para slices. Las iteraciones sucesivas del bucle hacen que las variables name y age se configuren con el siguiente par clave/valor:

1
2
3
for name, age := range edades {
    fmt.Printf("%s\t%d\n", name, age)
}

charlie  34
bob      3

Los mapas en Go no están ordenados y si mostramos todos los pares clave/valor almacenados es posible que el orden se modifique de una ejecución a la siguiente. Esto es intencional; hacer que la secuencia varíe ayuda a forzar que los programas sean robustos entre implementaciones.

Para enumerar los pares clave/valor en orden, debemos ordenar las claves explícitamente, por ejemplo, usando la función Strings del paquete sort:

1
2
3
4
5
6
7
8
9
10
11
12
13
import "sort"

var names []string

for name := range edades {
    names = append(names, name)
}

sort.Strings(names)

for _, name := range names {
    fmt.Printf("%s\t%d\n", name, edades[name])
}

bob      3
charlie  34

Dado que conocemos el tamaño final de names desde el principio, es más eficiente asignar un array con el tamaño requerido de antemano. La siguiente declaración crea un slice que inicialmente está vacío pero tiene la capacidad suficiente para contener todas las claves del mapa edades:

1
names := make([]string, 0, len(edades))

En el primer bucle range mencionado anteriormente, solo necesitamos las claves del mapa edades, por lo que omitimos la segunda variable del bucle. En el segundo bucle, solo necesitamos los elementos del slice names, por lo que usamos el identificador en blanco _ para ignorar la primera variable, el índice.

El valor cero para un tipo mapa es nil, es decir, nulo. En otras palabras el mapa no tiene memoria asignada y no se puede usar. Un mapa nil es diferente de un mapa vacío, que es un mapa que tiene memoria asignada pero no tiene claves.

1
2
3
var edades map[string]int
fmt.Println(edades == nil)
fmt.Println(len(edades) == 0)

true
true

La mayoría de las operaciones sobre mapas, incluyendo la recuperación, delete, len y los bucles range, son seguras de realizar en un mapa nil, ya que se comporta como un mapa vacío. Sin embargo, almacenar en un mapa nil provoca un error:

1
edades["carol"] = 21

panic: assignment to entry in nil map

Antes de poder almacenar valores, se debe asignar memoria al mapa.

Acceder a un elemento de un mapa mediante subíndices siempre devuelve un valor. Si la clave está presente en el mapa, obtenemos el valor correspondiente; si no, obtenemos el valor cero para el tipo del elemento, como vimos con edades["bob"].

Para muchos propósitos, eso está bien, pero a veces necesitamos saber si el elemento realmente estaba allí o no. Por ejemplo, si el tipo del elemento es numérico, podemos necesitar distinguir entre un elemento inexistente y un elemento que casualmente tiene el valor cero, utilizando una prueba como esta:

1
2
age, ok := edades["bob"]
if !ok { /* "bob" no es una clave en este mapa; age == 0. */ }

Es muy común el siguiente patrón que combina las dos sentencias anteriores dentro de la condición del if, asignación y comparación en una sola línea:

1
if age, ok := edades["bob"]; !ok { /* ... */ }

Utilizar un subíndice en un mapa en este contexto produce dos valores; el segundo es un booleano que indica si el elemento está presente. La variable booleana a menudo se llama ok, especialmente si se usa inmediatamente en una condición if.

Al igual que con los slices, los mapas no se pueden comparar entre sí; la única comparación legal es con nil. Para verificar si dos mapas contienen las mismas claves y los mismos valores asociados, debemos escribir un bucle.

1
2
3
x := map[string]int{"a": 1}
y := map[string]int{"a": 1}
fmt.Println(x == y)

invalid operation: x == y (map can only be compared to nil)

Una aplicación común de los mapas es usarlos como un conjunto (set), es decir, una colección de elementos sin orden ni repetición^[2]. Como Go no tiene un tipo set nativo, podemos simularlo con un mapa cuyas claves son los elementos del conjunto.

La forma más sencilla es usar map[Tipo]bool:

1
2
3
4
5
6
conjunto := make(map[string]bool)
conjunto["manzana"] = true
conjunto["pera"] = true

fmt.Println(conjunto["manzana"]) // true
fmt.Println(conjunto["banana"])  // false (no está presente)

Para verificar si un elemento pertenece al conjunto, usamos la sintaxis de dos valores:

1
2
3
if conjunto["manzana"] {
    fmt.Println("manzana está en el conjunto")
}

Para eliminar se usa delete como con cualquier mapa.

Una variante más eficiente en memoria usa struct{} como tipo de valor, ya que struct{} ocupa 0 bytes (a diferencia de bool que ocupa 1). Esta es la forma preferida en código Go cuando la eficiencia importa:

1
2
3
4
5
6
conjunto := make(map[string]struct{})
conjunto["manzana"] = struct{}{}

if _, ok := conjunto["manzana"]; ok {
    fmt.Println("manzana está en el conjunto")
}

1Ejercicios¶

Los ejercicios de este capítulo están en 06-maps/ejercicios/ del repositorio taller-go. Cada directorio contiene un README.md con el enunciado y los esqueletos para resolverlo.

2Enlaces recomendados¶

Footnotes¶

Durante el curso veremos qué es y cómo funciona una tabla de hash.
↩
Más adelante estudiaremos los conjuntos como estructura de datos. Por ahora nos alcanza con saber que los conjuntos no pueden tener valores repetidos.
↩