HashMap: la API, el patrón entry y por qué exige Hash y Eq

Cuando necesitas asociar una clave con un valor y recuperarlo rápido, la respuesta es HashMap<K, V>: inserción, búsqueda y borrado en tiempo constante medio, sin importar cuántos millones de entradas guarde. Detrás hay una tabla hash moderna —la SwissTable, sondeo abierto con aceleración SIMD— pero su superficie es sencilla y su idioma central es el patrón entry, que evita el desperdicio de buscar la misma clave dos veces. Y todo descansa sobre un requisito que no es capricho: la clave debe implementar Hash y Eq, porque uno elige dónde mirar y el otro confirma qué encontraste.

La API esencial

Un HashMap se llena con insert, que devuelve el valor anterior si la clave ya existía (envuelto en Option), y se consulta con get, que devuelve Option<&V> porque la clave podría no estar. El resto de la superficie es igual de directo.

use std::collections::HashMap;

fn main() {
    let mut edad: HashMap<String, u32> = HashMap::new();
    edad.insert(String::from("Ada"), 36);
    let previo = edad.insert(String::from("Ada"), 37); // Some(36): sobrescribe
    assert_eq!(previo, Some(36));

    if let Some(a) = edad.get("Ada") {          // get acepta &str, no solo &String
        println!("Ada tiene {a}");
    }
    println!("existe Alan: {}", edad.contains_key("Alan")); // false
    edad.remove("Ada");                          // Option<u32> con el valor quitado

    for (nombre, a) in &edad {                   // orden NO especificado
        println!("{nombre}: {a}");
    }
}

Un detalle fino y muy útil: get no exige &K, sino cualquier tipo que la clave pueda prestar mediante el trait Borrow. Por eso un HashMap<String, V> se consulta con un &str sin construir un String temporal: String se presta como str. La iteración con for recorre pares (&K, &V) en un orden no especificado y deliberadamente aleatorizado entre ejecuciones; si necesitas orden, esa es señal de que quieres un BTreeMap, no un HashMap.

El patrón entry: una sola búsqueda

Considera la tarea canónica de contar frecuencias. La versión ingenua consulta la clave, decide, y vuelve a consultarla para escribir: hashea y sondea la misma clave dos o tres veces.

use std::collections::HashMap;

fn main() {
    let texto = "el gato el perro el gato";
    let mut cuenta: HashMap<&str, u32> = HashMap::new();

    // INGENUO: dos busquedas por palabra
    for palabra in texto.split_whitespace() {
        if !cuenta.contains_key(palabra) {  // busqueda 1: hash + sondeo
            cuenta.insert(palabra, 0);       // busqueda 2: hash + sondeo
        }
        *cuenta.get_mut(palabra).unwrap() += 1; // busqueda 3: otra vez
    }
}

El patrón entry elimina el desperdicio. map.entry(clave) calcula el hash y localiza el bucket una sola vez, y te devuelve un Entry —una vista sobre esa ranura, esté ocupada o vacía— con métodos para resolver el caso sin volver a buscar.

use std::collections::HashMap;

fn main() {
    let texto = "el gato el perro el gato";
    let mut cuenta: HashMap<&str, u32> = HashMap::new();

    for palabra in texto.split_whitespace() {
        *cuenta.entry(palabra).or_insert(0) += 1; // UNA busqueda por palabra
    }
    // {"el": 3, "gato": 2, "perro": 1}

    // and_modify para el caso ocupado, or_insert para el vacio:
    let mut vistos: HashMap<&str, u32> = HashMap::new();
    vistos.entry("clave").and_modify(|n| *n += 1).or_insert(1);
}

or_insert(v) inserta v si la ranura está vacía y, en ambos casos, devuelve &mut V al valor —por eso el += 1 funciona directamente sobre él—. Sus parientes afinan el patrón: or_insert_with(|| caro()) difiere la construcción del valor por defecto para no pagarla si la clave ya existe, or_default() usa el Default del tipo, y and_modify aplica un cambio solo cuando la entrada estaba ocupada. Es el idioma con el que Rust dice inserta-o-actualiza sin recorrer la tabla dos veces.

flowchart TB
e[Llamada a entry de la clave] --> h[Se calcula el hash y se sondea una sola vez]
h --> occ[Variante Occupied si la clave ya existe]
h --> vac[Variante Vacant si la clave no existe]
occ --> mod[and_modify ajusta el valor presente]
vac --> ins[or_insert coloca el valor inicial]
mod --> ret[Referencia mutable al valor]
ins --> ret
style h fill:#fab387,color:#11111b
style occ fill:#a6e3a1,color:#11111b
style vac fill:#89b4fa,color:#11111b
style ret fill:#cba6f7,color:#11111b

Por qué exige Hash y Eq

Aquí está la razón de fondo. Una tabla hash guarda cada par en un bucket elegido a partir de una huella numérica de la clave: eso lo aporta Hash. Pero varias claves distintas pueden caer en el mismo bucket —una colisión—, así que al buscar hace falta comparar la clave candidata con las que hay allí para saber cuál es la tuya: eso lo aporta Eq. Uno dice dónde mirar; el otro dice cuál es. Por eso la cota exigida a toda clave es K: Hash + Eq, y ninguno de los dos sobra.

De ahí nace un contrato inviolable, el mismo del nivel 16: si dos claves son iguales, deben tener la misma huella. Formalmente, a == b obliga a hash(a) == hash(b). Si se rompe, dos claves iguales irían a buckets distintos y buscar una que insertaste devolvería None —el valor está, pero el mapa mira en el sitio equivocado—. Por eso Eq y Hash se derivan siempre juntos.

use std::collections::HashMap;

#[derive(PartialEq, Eq, Hash)]   // los tres, y coherentes por construccion
struct Coord { x: i32, y: i32 }

fn main() {
    let mut m = HashMap::new();
    m.insert(Coord { x: 1, y: 2 }, "A");
    assert_eq!(m.get(&Coord { x: 1, y: 2 }), Some(&"A"));
}

El hasher por defecto y cuándo cambiarlo

El HashMap de std no calcula la huella con cualquier función: usa SipHash 1-3 sembrado con una clave aleatoria por proceso. Esto no es un adorno: sin semilla aleatoria, un atacante que conociera el algoritmo podría fabricar miles de claves que colisionan a propósito, degradando cada bucket a una lista y convirtiendo tus O(1) en O(n) —un ataque de denegación de servicio por colisión, el célebre HashDoS—. La aleatoriedad por proceso lo neutraliza, a cambio de un hash algo más lento y de que el orden de iteración cambie entre ejecuciones.

Cuando no recibes claves de un adversario —índices internos, claves que tú generas, un bucle caliente— puedes cambiar el hasher por uno más veloz sin tocar tus tipos, gracias a la separación Hash / Hasher del nivel 16. Basta construir el mapa con otro BuildHasher:

// Con el crate `rustc-hash`: mismo HashMap, hasher no criptografico y mas rapido.
use rustc_hash::FxHashMap;

fn main() {
    let mut veloz: FxHashMap<u32, &str> = FxHashMap::default();
    veloz.insert(7, "siete");     // misma API, sin resistencia a HashDoS
}

La regla práctica: deja el hasher por defecto siempre que las claves puedan venir de fuera; cámbialo a FxHashMap o ahash solo en rutas internas y calientes donde hayas medido que el hashing domina.