HashSet y BTreeMap en Rust

Un HashSet (conjunto hash) es una colección de valores únicos. Si metes el mismo valor dos veces, solo se guarda una. Piensa en la lista de invitados en la puerta de una fiesta: al de seguridad solo le importa si tu nombre está en la lista, no cuántas veces lo escribieron.

Ya conoces Vec y HashMap. En esta página verás las otras colecciones que más vas a usar: HashSet, los ordenados BTreeMap y BTreeSet, y VecDeque para colas. Al final hay una tabla que te ayuda a elegir la adecuada.

Crear un HashSet

HashSet está en std::collections, así que necesitas una línea use. El método insert devuelve un bool: true si el valor era nuevo y false si ya estaba.

use std::collections::HashSet;

fn main() {
    let mut tags = HashSet::new();

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // ya estaba

    println!("{} etiquetas únicas", tags.len());
}

Salida:

true
true
false
2 etiquetas únicas

▶ Pruébalo tú mismo

Ese bool es más útil de lo que parece. Responde a “¿ya había visto esto?” en el mismo paso en que lo añades, así que no necesitas una comprobación aparte.

Comprobar y quitar valores

contains te dice si un valor está en el conjunto. remove lo saca y, igual que insert, devuelve un bool que indica si de verdad se quitó algo.

use std::collections::HashSet;

fn main() {
    let mut online: HashSet<&str> = HashSet::from(["ana", "ben", "chen"]);

    println!("¿ben está conectado? {}", online.contains("ben"));

    println!("ben quitado: {}", online.remove("ben"));
    println!("ben quitado otra vez: {}", online.remove("ben"));

    println!("¿ben está conectado? {}", online.contains("ben"));
    println!("{} personas conectadas", online.len());
}

Salida:

¿ben está conectado? true
ben quitado: true
ben quitado otra vez: false
¿ben está conectado? false
2 personas conectadas

▶ Pruébalo tú mismo

¿Por qué usar un conjunto en lugar de un Vec aquí? Para hacer contains en un Vec, Rust revisa todos los elementos, uno por uno. Un HashSet va directo a la respuesta, sin importar lo grande que sea. Con un millón de usuarios, la diferencia es enorme.

Precaución

Un HashSet no tiene un orden fijo. Si lo imprimes con {:?} o lo recorres con un bucle, el orden puede cambiar de una ejecución a otra. Cuando necesites un orden estable para imprimir, copia los valores a un Vec y ordénalo, o usa un BTreeSet (lo verás más abajo).

Quitar los duplicados de un Vec

Una tarea muy común: tienes una lista con repetidos y quieres cada valor una sola vez. Hay dos buenas formas de hacerlo, según te importe o no el orden original.

use std::collections::HashSet;

fn main() {
    let visits = vec![3, 1, 3, 2, 1, 5, 2];

    // Forma 1: recoger en un conjunto y luego ordenar para tener un orden estable
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("únicos ordenados: {:?}", sorted);

    // Forma 2: quedarse con la primera aparición de cada valor, en el orden original
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("en orden:         {:?}", in_order);
}

Salida:

únicos ordenados: [1, 2, 3, 5]
en orden:         [3, 1, 2, 5]

▶ Pruébalo tú mismo

La forma 2 aprovecha el bool de insert. retain conserva un elemento solo cuando la closure devuelve true, e insert devuelve true solo la primera vez que ve un valor.

Operaciones de conjuntos: unión, intersección, diferencia

Los conjuntos se pueden combinar como los círculos de un diagrama de Venn. Cada método devuelve un iterador, así que recogemos los resultados en un Vec y los ordenamos antes de imprimirlos para obtener siempre la misma salida.

use std::collections::HashSet;

fn main() {
    let alice: HashSet<&str> = HashSet::from(["rust", "python", "go"]);
    let bob: HashSet<&str> = HashSet::from(["go", "java", "rust"]);

    let mut both: Vec<_> = alice.intersection(&bob).collect();
    both.sort();
    println!("los dos saben:   {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("alguno sabe:     {:?}", either);

    let mut only_alice: Vec<_> = alice.difference(&bob).collect();
    only_alice.sort();
    println!("solo alice:      {:?}", only_alice);

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("solo uno sabe:   {:?}", only_one);
}

Salida:

los dos saben:   ["go", "rust"]
alguno sabe:     ["go", "java", "python", "rust"]
solo alice:      ["python"]
solo uno sabe:   ["java", "python"]

▶ Pruébalo tú mismo

difference va en un solo sentido: alice.difference(&bob) es “lo que Alice sabe y Bob no”. Si los intercambias, obtienes la lista de Bob. symmetric_difference mira los dos lados a la vez: todo lo que sabe solo uno de los dos.

BTreeMap y BTreeSet: siempre ordenados

BTreeMap funciona igual que HashMap, y BTreeSet igual que HashSet. La diferencia es que mantienen sus claves ordenadas. Cuando los recorres, obtienes las claves en orden, siempre.

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let text = "el gato vio el pez en el mar";

    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    for (word, count) in &counts {
        println!("{word}: {count}");
    }

    let scores: BTreeSet<u32> = BTreeSet::from([72, 95, 58, 88]);
    println!("más baja: {:?}", scores.first());
    println!("más alta: {:?}", scores.last());
    println!("todas: {:?}", scores);
}

Salida:

el: 3
en: 1
gato: 1
mar: 1
pez: 1
vio: 1
más baja: Some(58)
más alta: Some(95)
todas: {58, 72, 88, 95}

▶ Pruébalo tú mismo

La API de entry es la misma que viste en la página de HashMap. Como el mapa es un BTreeMap, las palabras salen en orden alfabético sin tener que ordenarlas aparte.

Un detalle: el texto del ejemplo no lleva tildes a propósito. BTreeMap ordena las cadenas por sus bytes, no según el alfabeto español, así que una palabra como “árbol” quedaría después de “zorro”.

¿Cuál deberías elegir?

• Usa HashMap / HashSet por defecto. Las búsquedas suelen ser más rápidas.
• Usa BTreeMap / BTreeSet cuando necesites los datos en orden: imprimir un informe ordenado, encontrar la clave más pequeña o más grande, u obtener un rango de claves.

VecDeque: una cola

Un VecDeque (se pronuncia “vec dec”) es una lista en la que puedes añadir y quitar elementos rápidamente por los dos extremos. Eso lo convierte en la opción natural para una cola: el primero que entra es el primero que sale, como la gente haciendo fila.

use std::collections::VecDeque;

fn main() {
    let mut line: VecDeque<&str> = VecDeque::new();
    line.push_back("ana");
    line.push_back("ben");
    line.push_back("chen");

    while let Some(person) = line.pop_front() {
        println!("atendiendo a {person}, {} siguen esperando", line.len());
    }
}

Salida:

atendiendo a ana, 2 siguen esperando
atendiendo a ben, 1 siguen esperando
atendiendo a chen, 0 siguen esperando

▶ Pruébalo tú mismo

Podrías usar Vec::remove(0) para esto, pero eso desplaza todos los demás elementos una posición. pop_front en un VecDeque no lo hace, así que sigue siendo rápido aunque la fila sea larga.

¿Qué colección debo usar?

Colección	Úsala cuando necesites…	Ejemplo
Vec<T>	Una lista ordenada a la que accedes por posición	Las líneas de un archivo, una lista de puntuaciones
HashMap<K, V>	Buscar rápido un valor por su clave	Nombre de usuario → perfil
HashSet<T>	Valores únicos y comprobar rápido “¿está aquí?”	Páginas visitadas, palabras prohibidas
BTreeMap<K, V>	Clave → valor, con las claves siempre ordenadas	Un conteo de palabras impreso en orden alfabético
VecDeque<T>	Añadir y quitar por los dos extremos	Una cola de tareas o de mensajes

Si dudas, empieza con un Vec. Cámbialo cuando notes que lo recorres una y otra vez buscando algo (usa un conjunto o un mapa) o que quitas muchos elementos del principio (usa un VecDeque).

Errores comunes

Meter tu propio struct en un HashSet sin los derives necesarios. Un HashSet necesita calcular el hash de sus valores y compararlos para saber si son iguales. Tu struct no sabe hacer eso automáticamente:

use std::collections::HashSet;

struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
}

error[E0277]: the trait bound `Point: Eq` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Eq` is not implemented for `Point`

error[E0277]: the trait bound `Point: Hash` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Hash` is not implemented for `Point`

El compilador te dice que Point no implementa los traits Eq (comparar si dos valores son iguales) ni Hash (calcular su hash), y un HashSet necesita los dos.

La solución es una sola línea encima del struct: #[derive(PartialEq, Eq, Hash)]. Para un BTreeSet también necesitarías PartialOrd y Ord, para que sepa cómo ordenar. Consulta Traits comunes para ver qué significa cada uno.

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
    visited.insert(Point { x: 1, y: 0 });
    visited.insert(Point { x: 0, y: 0 }); // repetido, se ignora
    println!("{} casillas visitadas", visited.len());
}

Salida:

2 casillas visitadas

▶ Pruébalo tú mismo

Práctica

1. La primera repetida

Dadas las palabras ["rojo", "azul", "verde", "azul", "rojo"], imprime la primera palabra que aparece por segunda vez. Pista: insert devuelve false cuando el valor ya está en el conjunto, y break detiene el bucle.

Ver solución

use std::collections::HashSet;

fn main() {
    let words = ["rojo", "azul", "verde", "azul", "rojo"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("Primera repetida: {word}");
            break;
        }
    }
}

Salida:

Primera repetida: azul

▶ Pruébalo tú mismo

!seen.insert(word) se lee como “no se pudo insertar”, es decir, “esta ya la había visto”. "azul" es la primera palabra que se repite. "rojo" también se repite, pero más tarde.

2. Letras en orden

Cuenta cuántas veces aparece cada letra en "mississippi" e imprime los conteos en orden alfabético. Pista: usa un BTreeMap con el mismo truco de entry(...).or_insert(0) de la sección de BTreeMap, y recorre word.chars().

Ver solución

use std::collections::BTreeMap;

fn main() {
    let word = "mississippi";
    let mut counts = BTreeMap::new();

    for letter in word.chars() {
        *counts.entry(letter).or_insert(0) += 1;
    }

    for (letter, count) in &counts {
        println!("{letter}: {count}");
    }
}

Salida:

i: 4
m: 1
p: 2
s: 4

▶ Pruébalo tú mismo

Con un HashMap, estas cuatro líneas podrían salir en cualquier orden. El BTreeMap mantiene sus claves ordenadas, así que i, m, p, s se imprimen en orden alfabético siempre.

Resumen

• HashSet guarda valores únicos. insert y remove devuelven un bool que te dice si algo cambió.
• contains en un conjunto es rápido, incluso con conjuntos enormes. En un Vec revisa todos los elementos.
• union, intersection, difference y symmetric_difference hacen operaciones de conjuntos. Ordena los resultados antes de imprimirlos.
• BTreeMap y BTreeSet mantienen las claves ordenadas; úsalos cuando el orden importe.
• VecDeque es la cola por excelencia: push_back para entrar en la fila y pop_front para salir.

Comprueba lo que aprendiste

Comprueba lo aprendido

1. ¿Qué devuelve set.insert(x) si x ya está en el conjunto?

true Un error false El valor anterior

2. Quieres imprimir un conteo de palabras en orden alfabético sin ordenarlo tú. ¿Qué mapa encaja mejor?

HashMap BTreeMap Vec VecDeque

3. ¿Por qué imprimir un HashSet con {:?} puede dar una salida distinta en cada ejecución?

Porque un HashSet no tiene un orden fijo Porque {:?} es aleatorio Porque los conjuntos pierden valores con el tiempo Porque solo pasa en modo debug

4. ¿Qué colección es la mejor para una cola en la que el primero que entra es el primero que sale?

HashSet BTreeSet HashMap VecDeque

Puntuación: 0 / 4

Para leer más

• Resumen de std::collections — documentación de la biblioteca estándar (en inglés): una guía más larga para elegir colección, con la velocidad de cada operación.
• HashSet — Rust by Example (en inglés): un ejemplo ejecutable de union, intersection y difference.
• HashSet — documentación de la biblioteca estándar (en inglés): todos los métodos de conjuntos, incluidos is_subset y retain.
• BTreeMap — documentación de la biblioteca estándar (en inglés): mapas ordenados, incluido range para obtener solo una parte de las claves.
• VecDeque — documentación de la biblioteca estándar (en inglés): todos los métodos de cola, como push_front, pop_back y front.