16 `HashMap`

Un HashMap<K, V> es una colección que almacena pares formados por una clave y un valor. K representa el tipo de las claves y V el tipo de los valores. A diferencia de un vector, cuyos elementos se identifican por su posición, en un HashMap cada valor se asocia a una clave única, que se utiliza para insertarlo, buscarlo o modificarlo.

Este tipo de colección resulta especialmente adecuado cuando el acceso a los datos se realiza a partir de un identificador en lugar de una posición. Por ejemplo, una agenda telefónica que asocia nombres con números de teléfono, un diccionario que asocia palabras con sus definiciones o una tabla que asocia direcciones MAC con direcciones IP.

HashMap está implementado mediante una estructura de datos denominada tabla hash. Para cada clave se calcula un número entero mediante una función hash, y ese número se utiliza para determinar la posición donde se almacenará el elemento dentro de una tabla.

Gracias a este mecanismo, cuando se desea buscar un elemento no es necesario recorrer toda la colección. Basta con volver a aplicar la función hash a la clave para localizar la posición donde probablemente se encuentra el valor. Decimos probablemente porque dos claves distintas pueden producir el mismo valor hash y, por tanto, corresponder a la misma posición.

Cuando dos claves distintas producen el mismo valor hash se dice que se ha producido una colisión. Las implementaciones modernas de las tablas hash incorporan mecanismos para resolver estas colisiones de forma eficiente. Como consecuencia, las operaciones de inserción, búsqueda y eliminación tienen, en promedio, una complejidad temporal constante, es decir, (O(1)).

Desde el punto de vista del programador, todos estos detalles son completamente transparentes. Basta con proporcionar una clave para insertar, buscar o eliminar un elemento, sin preocuparse por cómo se almacena internamente.

16.1 Uso básico de un `HashMap`

El siguiente ejemplo ilustra las operaciones básicas sobre un HashMap:

use std::collections::HashMap;

fn main() {
    let mut tabla = HashMap::new();

    // Insertamos dos elementos.
    tabla.insert("00:11:22:33:44:55", "192.168.1.10");
    tabla.insert("AA:BB:CC:DD:EE:FF", "192.168.1.20");

    // Mostramos la tabla completa.
    println!("{:?}", tabla);   

    // Mostramos el elemento asociado a una clave
    println!("IP: {}", tabla.get("00:11:22:33:44:55").unwrap());

    // Reemplazamos el valor de un elemento
    tabla.insert("00:11:22:33:44:55", "192.168.1.100");

    // Eliminamos un elemento
    tabla.remove("AA:BB:CC:DD:EE:FF");

    println!("{:?}", tabla);   
}

Ejecutar▶

La sentencia use std::collections::HashMap; importa el tipo HashMap de la biblioteca estándar. A diferencia de tipos como i32, bool, char, String o Vec, es necesario importar HashMap antes de poder utilizarlo.
Crea un HashMap vacío mediante el método asociado HashMap::new(). La variable se declara como mut porque su contenido va a modificarse.
Inserta dos elementos mediante el método insert(). Obsérvese que no es necesario indicar los tipos de las claves ni de los valores, ya que Rust los deduce a partir de los datos insertados.

El método insert() devuelve un Option con el valor anterior asociado a la clave. Si la clave no existía, devuelve None. Pero en muchos casos, como en este ejemplo, el valor devuelto por insert() es ignorado.
Muestra el contenido completo del HashMap utilizando el especificador de formato {:?}. Como ocurre con los vectores, HashMap implementa el trait Debug, lo que permite mostrar su contenido con println!(). El orden en que aparecen los elementos no está definido y puede variar entre ejecuciones.
Recupera el valor asociado a una clave mediante el método get(). Este método devuelve un Option, por lo que en este ejemplo se utiliza unwrap() al saber que la clave existe. Tal y como vimos en la Sección 12.4.3.

El método get() devuelve un Option<&V>, es decir, una referencia al valor almacenado. De este modo, el elemento permanece dentro del HashMap y puede seguir utilizándose posteriormente.
Reemplaza el valor asociado a una clave existente. Para ello basta con volver a llamar a insert() utilizando la misma clave y un nuevo valor. El valor anterior se sustituye automáticamente.
Elimina un elemento mediante el método remove(). Si la clave no existe, el método no produce ningún error y simplemente no modifica el contenido del HashMap.

16.2 Acceso mediante el operador `[]`

Además del método get(), también es posible acceder a un valor mediante el operador [].

println!("{}", tabla["00:11:22:33:44:55"]);

A diferencia de get(), el operador [] devuelve directamente una referencia al valor asociado a la clave. Si la clave no existe, el programa finaliza produciendo un panic. Por este motivo, en la mayoría de las situaciones se prefiere utilizar get(), que devuelve un Option y permite tratar de forma segura el caso en que la clave no exista.

El operador [] solo puede utilizarse para leer un valor. No es posible modificar un elemento mediante una asignación. Para modificar el valor asociado a una clave debe utilizarse el método insert(), que reemplaza el valor anterior si la clave ya existe.

use std::collections::HashMap;

fn main() {
    let mut tabla = HashMap::new();

    tabla.insert("00:11:22:33:44:55", "192.168.1.10");
    tabla.insert("AA:BB:CC:DD:EE:FF", "192.168.1.20");

    // Lectura mediante el operador []
    println!(
        "IP: {}",
        tabla["00:11:22:33:44:55"]
    );

    // El operador [] no puede utilizarse para modificar un elemento.
    tabla["00:11:22:33:44:55"] = "192.168.1.100"; // ¡Error!
}

Ejecutar▶

16.3 La API `entry()`

En ocasiones es necesario realizar una operación distinta según que una clave exista o no en el HashMap. Por ejemplo, puede ser necesario insertar un valor únicamente si la clave no existe, inicializar un contador o modificar el valor asociado a una clave existente.

Una posibilidad sería comprobar primero si la clave existe y, a continuación, actuar en consecuencia. Sin embargo, este enfoque no es el más eficiente, ya que obliga a buscar la misma clave dos veces: una para comprobar si existe y otra para insertar o modificar el valor.

Para resolver este problema, HashMap proporciona la API entry(), que realiza una única búsqueda y permite actuar sobre la entrada correspondiente, tanto si la clave ya existe como si no.

16.3.1 El método `or_insert()`

El método or_insert() se utiliza junto con entry(). Recibe un valor que se insertará únicamente si la clave indicada en entry() no existe previamente en el HashMap.

Si la clave ya existe, no sucede nada y el valor asociado se conserva.
Si la clave no existe, se inserta un nuevo elemento con dicha clave y el valor indicado.

Este comportamiento resulta útil para inicializar valores sin tener que comprobar previamente si la clave existe.

use std::collections::HashMap;

fn main() {
    let mut contador = HashMap::new();

    contador.insert("HTTP", 443);

    contador.entry("HTTP").or_insert(443);
    contador.entry("SSH").or_insert(22);

    println!("{contador:?}");
}

Ejecutar▶

En este ejemplo, la clave "HTTP" ya existe, por lo que conserva el valor 443. En cambio, la clave "SSH" no existía y se inserta con el valor 22.

16.4 Recorrido de un `HashMap`

Los elementos de un HashMap pueden recorrerse mediante un bucle for. Dependiendo de la información que interese obtener, existen tres posibilidades:

iter(), que recorre pares formados por la clave y el valor.
keys(), que recorre únicamente las claves.
values(), que recorre únicamente los valores.

El siguiente ejemplo muestra las tres formas de recorrer un HashMap.

use std::collections::HashMap;

fn main() {
    let mut tabla = HashMap::new();

    tabla.insert("HTTP", 80);
    tabla.insert("HTTPS", 443);
    tabla.insert("SSH", 22);

    // Recorremos claves y valores.
    for (protocolo, puerto) in tabla.iter() {
        println!("{protocolo}: {puerto}");
    }
    println!();

    // Recorremos únicamente las claves.
    for protocolo in tabla.keys() {
        println!("{protocolo}");
    }
    println!();

    // Recorremos únicamente los valores.
    for puerto in tabla.values() {
        println!("{puerto}");
    }
    println!();
}

Ejecutar▶

Al igual que ocurre al mostrar un HashMap mediante println!("{:?}"), el orden en que se recorren los elementos no está definido y puede variar entre ejecuciones.

16.5 Otras operaciones habituales

Además de las operaciones vistas hasta ahora, HashMap proporciona otros métodos de uso frecuente.

use std::collections::HashMap;

fn main() {
    let mut tabla = HashMap::new();

    tabla.insert("HTTP", 80);
    tabla.insert("HTTPS", 443);
    tabla.insert("SSH", 22);

    println!("{:?}", tabla);
    println!("¿La tabla está vacía? {}", tabla.is_empty());
    println!("Número de elementos: {}", tabla.len());
    println!("¿Contiene HTTP? {}", tabla.contains_key("HTTP"));
    println!("¿Contiene FTP? {}", tabla.contains_key("FTP"));

    println!();
    tabla.clear();
    println!("{:?}", tabla);
    println!("¿La tabla está vacía? {}", tabla.is_empty());
}

Ejecutar▶

len() devuelve el número de elementos almacenados en el HashMap.
is_empty() devuelve true si el HashMap no contiene ningún elemento y false en caso contrario.
contains_key() comprueba si una determinada clave existe en el HashMap. Devuelve true si existe y false en caso contrario.
clear() elimina todos los elementos del HashMap, dejándolo vacío.

16.6 Resumen

En este capítulo hemos estudiado HashMap<K, V>, la estructura de datos que permite asociar claves con valores.

Las ideas principales son las siguientes:

Un HashMap almacena pares clave-valor y permite acceder a los valores a partir de su clave.
Las claves deben ser únicas; insertar un valor con una clave ya existente sustituye al valor anterior.
Los elementos pueden insertarse, consultarse, modificarse y eliminarse mediante los métodos proporcionados por la biblioteca estándar.
El método get() devuelve un Option<&V>, por lo que es necesario tratar el caso en que la clave no exista.
La API entry() permite insertar o modificar valores de forma eficiente sin realizar búsquedas repetidas.
Es posible recorrer un HashMap mediante un bucle for, obteniendo referencias a sus claves y valores.

Los mapas hash son una de las colecciones más útiles de Rust cuando se necesita localizar información de forma rápida a partir de una clave. Junto con los vectores y las cadenas, constituyen una parte fundamental de la biblioteca estándar y aparecen con frecuencia en aplicaciones reales.

16.1 Uso básico de un HashMap

16.2 Acceso mediante el operador []

16.3 La API entry()

16.3.1 El método or_insert()

16.4 Recorrido de un HashMap

16.5 Otras operaciones habituales

16.6 Resumen

16.1 Uso básico de un `HashMap`

16.2 Acceso mediante el operador `[]`

16.3 La API `entry()`

16.3.1 El método `or_insert()`

16.4 Recorrido de un `HashMap`