Almacenar pares clave-valor con mapas hash de Rust

Introducción

Bienvenido a Storing Keys With Associated Values in Hash Maps (Almacenar claves con valores asociados en mapas hash). Este laboratorio es parte del Rust Book. Puedes practicar tus habilidades en Rust en LabEx.

En este laboratorio, exploraremos el concepto de mapas hash y cómo se pueden utilizar para almacenar claves con valores asociados.

Skills Graph

Almacenar claves con valores asociados en mapas hash

La última de nuestras colecciones comunes es el mapa hash. El tipo HashMap<K, V> almacena una asignación de claves de tipo K a valores de tipo V utilizando una función hash, que determina cómo coloca estas claves y valores en la memoria. Muchos lenguajes de programación admiten este tipo de estructura de datos, pero a menudo la llaman de diferentes maneras, como hash, mapa, objeto, tabla hash, diccionario o matriz asociativa, por nombrar solo algunas.

Los mapas hash son útiles cuando quieres buscar datos no mediante un índice, como se puede hacer con los vectores, sino mediante una clave que puede ser de cualquier tipo. Por ejemplo, en un juego, podrías llevar un registro de la puntuación de cada equipo en un mapa hash en el que cada clave es el nombre de un equipo y los valores son las puntuaciones de cada equipo. Dado el nombre de un equipo, puedes recuperar su puntuación.

Repasaremos la API básica de los mapas hash en esta sección, pero muchas más funcionalidades se encuentran en las funciones definidas en HashMap<K, V> por la biblioteca estándar. Como siempre, consulta la documentación de la biblioteca estándar para obtener más información.

Crear un nuevo mapa hash

Una forma de crear un mapa hash vacío es utilizar new y agregar elementos con insert. En la Lista 8-20, estamos llevando un registro de las puntuaciones de dos equipos cuyos nombres son Blue (Azul) y Yellow (Amarillo). El equipo Azul comienza con 10 puntos, y el equipo Amarillo comienza con 50.

use std::collections::HashMap;

let mut scores = HashMap::new();

scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

Lista 8-20: Crear un nuevo mapa hash e insertar algunas claves y valores

Ten en cuenta que primero debemos usar el HashMap de la sección de colecciones de la biblioteca estándar. De nuestras tres colecciones comunes, esta es la menos utilizada, por lo que no se incluye en las características que se traen automáticamente al alcance en el preludio. Los mapas hash también tienen menos soporte de la biblioteca estándar; por ejemplo, no hay una macro incorporada para construirlos.

Al igual que los vectores, los mapas hash almacenan sus datos en el montón (heap). Este HashMap tiene claves de tipo String y valores de tipo i32. Al igual que los vectores, los mapas hash son homogéneos: todas las claves deben tener el mismo tipo, y todos los valores deben tener el mismo tipo.

Accediendo a valores en un mapa hash

Podemos obtener un valor del mapa hash proporcionando su clave al método get, como se muestra en la Lista 8-21.

use std::collections::HashMap;

let mut scores = HashMap::new();

scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

let team_name = String::from("Blue");
let score = scores.get(&team_name).copied().unwrap_or(0);

Lista 8-21: Accediendo a la puntuación del equipo Azul almacenada en el mapa hash

Aquí, score tendrá el valor asociado al equipo Azul, y el resultado será 10. El método get devuelve un Option<&V>; si no hay un valor para esa clave en el mapa hash, get devolverá None. Este programa maneja el Option llamando a copied para obtener un Option<i32> en lugar de un Option<&i32>, luego unwrap_or para establecer score en cero si scores no tiene una entrada para la clave.

Podemos iterar sobre cada par clave-valor en un mapa hash de manera similar a como lo hacemos con los vectores, utilizando un bucle for:

use std::collections::HashMap;

let mut scores = HashMap::new();

scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

for (key, value) in &scores {
    println!("{key}: {value}");
}

Este código imprimirá cada par en un orden arbitrario:

Yellow: 50
Blue: 10

Mapas hash y propiedad (Ownership)

Para tipos que implementan el rasgo (trait) Copy, como i32, los valores se copian en el mapa hash. Para valores con propiedad (owned values) como String, los valores se moverán y el mapa hash será el propietario de esos valores, como se demuestra en la Lista 8-22.

use std::collections::HashMap;

let field_name = String::from("Favorite color");
let field_value = String::from("Blue");

let mut map = HashMap::new();
map.insert(field_name, field_value);
// field_name and field_value are invalid at this point, try
// using them and see what compiler error you get!

Lista 8-22: Mostrando que las claves y valores son propiedad del mapa hash una vez que se insertan

No podemos usar las variables field_name y field_value después de que se hayan movido al mapa hash con la llamada a insert.

Si insertamos referencias a valores en el mapa hash, los valores no se moverán al mapa hash. Los valores a los que apuntan las referencias deben ser válidos al menos durante el tiempo que el mapa hash sea válido. Hablaremos más sobre estos problemas en "Validating References with Lifetimes" (Validando referencias con períodos de vida).

Actualizar un mapa hash

Aunque el número de pares clave-valor es creciente, cada clave única solo puede tener un valor asociado a la vez (pero no al revés: por ejemplo, tanto el equipo Azul como el equipo Amarillo podrían tener el valor 10 almacenado en el mapa hash scores).

Cuando quieres cambiar los datos en un mapa hash, debes decidir cómo manejar el caso en el que una clave ya tiene un valor asignado. Podrías reemplazar el valor antiguo con el nuevo valor, sin tener en cuenta en absoluto el valor antiguo. Podrías mantener el valor antiguo e ignorar el nuevo valor, agregando el nuevo valor solo si la clave no tiene ya un valor. O podrías combinar el valor antiguo y el nuevo valor. ¡Veamos cómo hacer cada una de estas cosas!

Sobrescribir un valor

Si insertamos una clave y un valor en un mapa hash y luego insertamos la misma clave con un valor diferente, el valor asociado a esa clave se reemplazará. Aunque el código de la Lista 8-23 llama a insert dos veces, el mapa hash solo contendrá un par clave-valor porque estamos insertando el valor para la clave del equipo Azul ambas veces.

use std::collections::HashMap;

let mut scores = HashMap::new();

scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Blue"), 25);

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

Lista 8-23: Reemplazando un valor almacenado con una clave en particular

Este código imprimirá {"Blue": 25}. El valor original de 10 ha sido sobrescrito.

Agregar una clave y un valor solo si la clave no está presente

Es común verificar si una clave en particular ya existe en el mapa hash con un valor y luego tomar las siguientes acciones: si la clave ya existe en el mapa hash, el valor existente debe permanecer tal como está; si la clave no existe, insertarla y un valor para ella.

Los mapas hash tienen una API especial para esto llamada entry que toma como parámetro la clave que se desea verificar. El valor de retorno del método entry es un enumerado (enum) llamado Entry que representa un valor que puede o no existir. Digamos que queremos verificar si la clave para el equipo Amarillo tiene un valor asociado. Si no lo tiene, queremos insertar el valor 50, y lo mismo para el equipo Azul. Usando la API entry, el código se ve como en la Lista 8-24.

use std::collections::HashMap;

let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);

scores.entry(String::from("Yellow")).or_insert(50);
scores.entry(String::from("Blue")).or_insert(50);

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

Lista 8-24: Usando el método entry para insertar solo si la clave no tiene ya un valor

El método or_insert en Entry está definido para devolver una referencia mutable al valor de la clave Entry correspondiente si esa clave existe, y si no, inserta el parámetro como el nuevo valor para esta clave y devuelve una referencia mutable al nuevo valor. Esta técnica es mucho más limpia que escribir la lógica nosotros mismos y, además, funciona mejor con el verificador de préstamos (borrow checker).

Ejecutar el código de la Lista 8-24 imprimirá {"Yellow": 50, "Blue": 10}. La primera llamada a entry insertará la clave para el equipo Amarillo con el valor 50 porque el equipo Amarillo no tiene un valor ya. La segunda llamada a entry no cambiará el mapa hash porque el equipo Azul ya tiene el valor 10.

Actualizar un valor basado en el valor antiguo

Otro caso de uso común para los mapas hash es buscar el valor de una clave y luego actualizarlo en función del valor antiguo. Por ejemplo, la Lista 8-25 muestra un código que cuenta cuántas veces aparece cada palabra en un texto. Usamos un mapa hash con las palabras como claves e incrementamos el valor para llevar la cuenta de cuántas veces hemos visto esa palabra. Si es la primera vez que vemos una palabra, primero insertaremos el valor 0.

use std::collections::HashMap;

let text = "hello world wonderful world";

let mut map = HashMap::new();

for word in text.split_whitespace() {
    let count = map.entry(word).or_insert(0);
    *count += 1;
}

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

Lista 8-25: Contando las ocurrencias de palabras usando un mapa hash que almacena palabras y recuentos

Este código imprimirá {"world": 2, "hello": 1, "wonderful": 1}. Puedes ver los mismos pares clave-valor impresos en un orden diferente: recuerda de "Accediendo a valores en un mapa hash" que iterar sobre un mapa hash ocurre en un orden arbitrario.

El método split_whitespace devuelve un iterador sobre subsecciones, separadas por espacios en blanco, del valor en text. El método or_insert devuelve una referencia mutable (&mut V) al valor de la clave especificada. Aquí, almacenamos esa referencia mutable en la variable count, así que para asignar a ese valor, primero debemos desreferenciar count usando el asterisco (*). La referencia mutable sale de alcance al final del bucle for, así que todos estos cambios son seguros y permitidos por las reglas de préstamo (borrowing rules).

Funciones de hash

Por defecto, HashMap utiliza una función de hash llamada SipHash que puede proporcionar resistencia a ataques de denegación de servicio (DoS, del inglés denial-of-service) que involucren tablas hash. Esta no es la función de hash más rápida disponible, pero la compensación de una mejor seguridad que se obtiene con la disminución del rendimiento vale la pena. Si analiza su código y descubre que la función de hash predeterminada es demasiado lenta para sus propósitos, puede cambiar a otra función especificando un hash generador (hasher) diferente. Un hash generador es un tipo que implementa el rasgo (trait) BuildHasher. Hablaremos sobre rasgos y cómo implementarlos en el Capítulo 10. No necesariamente tiene que implementar su propio hash generador desde cero; https://crates.io tiene bibliotecas compartidas por otros usuarios de Rust que proporcionan hash generadores que implementan muchos algoritmos de hash comunes.

Resumen

¡Felicidades! Has completado el laboratorio "Almacenar claves con valores asociados en mapas hash". Puedes practicar más laboratorios en LabEx para mejorar tus habilidades.